AtCoder Heuristic Contest 012(AHC012) -AtCoder 10th Anniversary- 参加記
問題
結果
99,533,533点で2位。パフォーマンスは3202で赤パフォ。嬉しい！
解法
線の引き方
円や斜めの線を考えるのは難しいので、縦横の線のみを引いて、グリッドで管理する。縦線なら (px, py) = (x, -1e7), (qx, qy) = (x+1, 1e7) のようにすることで、イチゴが直線上にくることがなくなる。
縦と横の線を何本引くかだが、円の内部に人数と同じくらいのピースが出来て欲しいので、縦本数 x 横本数 が 合計人数 * 4 / π に最も近くなるようにする(円の内部にイチゴは沢山あるので、イチゴ0個のピースはあまり出来なさそう)。隣接の線が十分近づけばイチゴ0のピースが増えるので、グリッドが多めに作られるようにした方が良さそう、と途中で思ったがスコアは下がった。
データの持ち方
以下のデータを管理する。
- 各グリッドにイチゴが何個あるか
- 2次元配列num[*][*] で管理すると、線を1本移動させた時に変化があるのは num[i-1][*] (or num[*][i-1]) と num[i][*] (or num[*][i]) になる
- 1〜10個のイチゴを含むピースの個数
- 各x(y)座標に存在するイチゴのy(x)座標を昇順にソートしたもの
焼きなまし
初期解は均等な幅で線を引く。
近傍は線を1本ランダムに選び、-30〜30移動させる。イチゴの個数の変化は、座標管理しているのでしゃくとり法(?)で O(移動量 * 線の数+所属が変わるイチゴの数) で計算できる。
// 縦線を正の方向に移動させる部分のコード for (int i = v[r].qx; i <= v[r].px+m; i++) { // m が変化量。iが所属が変わるx座標 int h_idx = 1; // しゃくとりで管理するインデックス for (const int _y : xp[i+R]) { // x座標がiであるイチゴのy座標 while (h[h_idx].py < _y) h_idx++; // vdは変化量を管理する配列。実際に遷移する時に個数を管理する配列に変化量を足す。 vd[0][h_idx-1]++; // イチゴの個数を増やす vd[1][h_idx-1]--; // イチゴの個数を減らす } }
評価値は ケーキが配られなかった人数 + 1〜10個の余ったピースの数 / 100。低いほど良い。最初の項だけなら素のスコアで、余って無駄なピースも減って欲しいので第2項も加えたがスコアは微増だった。
差分計算はジャッジサーバで16M回くらい。手元だと22M回くらいで、焼きなましの最適な初期値が手元とジャッジサーバで違うようで、提出で調整していた。
差分計算について[追記: 2022/7/5]
- xp[t] = x座標がtであるイチゴのy座標を昇順にソートしたリスト
となるデータを前計算で用意しておく。図において、x=10からx=13に移動させているので、所属が変化するイチゴはxp[11]とxp[12]を見れば全て分かる(簡単のためx=10,13にはイチゴはない)。あとはx座標ごとに、リストの手前からy座標が小さい順に、縦方向にどのグリッドに属するかをしゃくとり法の要領で計算していく。しゃくとりの頭がイチゴのy座標で、おしりがそのy座標を超えない一番上の横線、となる。
これで高速に差分が計算できるが、実装ではさらに個数の変化量を一時配列に入れておきnumの更新は遷移が採択された時に行う。numの更新を直接行ってしまうと、遷移が採択されなかった時に元に戻す作業が発生して無駄が生じる。
時系列
問題読み&考察 (0:00〜0:30)
まあ、線を移動させて焼きなましだろうなと思う。斜め線引いた時個数計算するのは自力では無理。テスターから引っ張ってくれば計算できるだろうけど、それで戦えるはずがないので却下。合計人数が最大1,000人でグリッドが50*50=2,500作れるので縦横で良さそう。初期解や高速化案を考える。
実装(0:30〜2:20)
頑張って実装する。山登りで微妙なスコアが出て、数行変えて焼きなましにするとスコア爆増するの、何回やっても気持ち良い。
初提出(2:22)
99.2M点でぶっちぎり1位でビビる。
提出2(2:43)
評価関数変更して微増。
パラメータ調整(〜4:00)
ひたすらパラメータ調整。焼きなましの初期温度はかなり低めにした方が良かった。
感想
2位で初赤パフォで出来過ぎた。1位の99.78Mはどうやっても勝てなかっただろうから悔いなし！正直なところ橙が限界で赤いくのはもう無理だと思っていたけど、上振れれば到達できることが分かったので頑張りたい。あとパフォ3000オーバーを3回位出せばいけるっぽい。何年かかるんだ…？
AtCoder Heuristic Contest 011(AHC011) -Sliding Tree Puzzle- 参加記
問題
結果
最終2,440,715,276 点で20位。暫定は40.6M点で21位。
解法
完成図の木を作るパートと完成図のパズルを解くパートの2つがある。
完成図の木構築
基本方針はBFSでランダムに枝を伸ばしていく。完成図は木なので、タイルを置いたらそのタイルが伸びる方向には、必ず置いたタイルから枝が伸びる。なので、別のタイルが伸びる方向が重ならないように枝刈りすることができる。例えば、下図において、マスAに左図のようにタイルを置いた場合、マスBにはAから枝が伸びる。なので、右図のようにマスCにマスBに繋がるタイルをおくことができない。
どのマスに何のタイルを置いたかを管理する配列と、伸ばす方向が重ならないように管理する配列を用意することで、木であることを保持しながらあるタイルを置けるかどうかの判定をO(1)で行える。葉のタイルはそれ以外のタイルが置けない場合にのみ置く。
以上の操作で、完成図が作れなかった場合、ランダムに1タイルを選び、そのタイルの伸びる1方向を残してその他の方向の部分木を除去し、もう一度BFSを行う。木のサイズが大きくなったら更新していく。5000イテレーションで完成しなかった場合は局所解にハマっていると判断して、一からやり直す。
パズルを解く
- 完成図と現在の配置から、マンハッタン距離をコストにして最小二部マッチングをハンガリアン法で解いて、どのタイルをどこへ移動させるかを決める。パズルとして不可能な配置の場合には、同種のタイル1ペアの移動先をスワップすることで完成可能にする。(参考:https://manabitimes.jp/math/979)
- 外周の4辺のうち、1タイルあたりのコスト(1.で計算した最小コスト)が最小の辺を次に揃える辺に決める。
- 2.で決めた辺をビームサーチで揃える。評価値は揃える辺のタイルの完成図とのマンハッタン距離。揃える辺のタイル以外は全て同一視して状態を管理する(そうしないと完成しなかった)。
- 1〜3を繰り返し行い、3x3になったらBFSで最短手順を探索する。
アルゴリズム全体
完成図は一定時間内(1,000ms〜1,500ms)でできるだけ沢山見つける(N=6で300個、N=10で10個程度見つかる)。残り時間で、マンハッタン距離のコストが小さい順に、完成図のパズルを解き、一番良い解を出力する。完成図の探索時間、ビーム幅はNごとにパラメータ調整した。
ざっくり時系列
1〜3日目
まずは木を完成させないとなぁと思い、頑張って実装する。最初のプログラムだとN=10で一つ完成図を見つけるのに5秒くらいかかったので、高速化する。
4日目
パズルを解きたいけど、ルールベースで解いても絶対にスコア伸びなさそうだし実装も重そうなので、全部を一気に揃えるビームサーチを書く。N=6は揃うこともあるけど、N=10だと全く揃わない。完成図の空きマスから遠いほどコストを高くすれば外側から上手いこと埋まっていくのでは？と思ったが、コストが低いところをぐるぐるするだけでダメ。
5〜6日目
多分、高コストのタイルを一旦悪い方向に動かす操作が行われないのがいけない。ので、1辺ずつ揃える&揃えるタイル以外は無視、で上手くいった。初提出で12位くらい。
7〜8日目
完成図を複数見つけたり、細かい調整を行う。
9日目
c4.8xlargeを借りて、大量ケースでバグチェック&パラメータ調整を行う。1000ケースに1回ぐらいSegmentation Faultするバグがあった。やっぱりチェックは大事。
その他
距離を最初にマンハッタン距離にして放置して、そこを改良するのを完全に忘れていた…。二乗和にするだけで暫定スコア40.6M→41.3Mになるという…。最終順位で言うとおそらく20位→17位になっていたはず。アホすぎる。。
THIRD プログラミングコンテスト 2021 (AHC007) 参加記
問題
結果
14,165,902,434点で39位。
解法
毎ターン、不確定の辺の長さを[d, 3d]からランダムに決めてクラスカル法でMSTを求めることを複数回行い、半分以上で対象辺が使われていたら採用する。解法としてはこれだけで、ひたすら高速化していた。以下高速化のためにやったこと。
- 前処理として、全部の辺の長さをランダムに決めてMSTを求めるのを150回行い、150回すべてで採用された辺は採用確定、1回も採用されなかった辺は不採用確定とする。
- MSTを複数回求める部分で、はじめの5回全て不採用だったら不採用とする。
- 採用の閾値を超えたら終了。また、残り全て採用でも閾値を超えないなら終了。
- クラスカル法のUnion-Findで、すでに確定した辺をuniteするところは同じ操作となるので、そこまで終了した時点での状態(親の配列とランクの配列)を保存して、毎回それを復元してMSTを求める。
- ソートすべき辺はvectorで管理して、確定した辺は順次削除していく。
以上をやって1ターンに60回程度のMSTを行なった。
反省点・その他
- ある程度MSTの試行回数が増えるとスコアの伸びに限界が見えたので、何か工夫をしないととは思っていたけど、結局いつもの通り何もできずに終わった。どうすればいいですか？
- [d, 3d]ではなく[1.13d, 2.87d]とかにするとスコアが伸びるらしいのでやってみたところ14.2Gを超えた。生成ロジック通りにやるのが最善じゃない場合もあるというのは覚えておく。
- 50位以内入ったし転職できるならしようかな。
HACK TO THE FUTURE 2022 予選 参加記
問題
結果
最終6,155,200点で25位。暫定は20位。
解法
技能レベルの推定
タスクが終了する毎に山登り法で推定した。
- 近傍は一つの技能のレベルを+1 or -1するのと、一つを+1しもう一つを-1する、の2種類
- 評価値は実際にタスクにかかった日数と予測日数との差の2ノルム
タスクの割り振り
割り振るタスクの選択
依存関係のDAGを見たときに、深さが深いものがボトルネックになるので、深い方から100個程度を割り振りを考えるタスクとする。これだけだと序盤にタスクが割り振られない人が出てくるので、完了したタスクが200個未満の時点では、すぐに割り振り可能で深さが浅くないタスクも選択する(これをやるとビジュアライザの見た目は良くなってそうだったが、スコア的にはあまり変わらなかった)。
タスクの割り振りと処理順序
考慮するタスクを選択したら、タスクを誰に割り振るのか、どの順番でタスクを処理するのか、の二つを考える。処理順序については依存関係に矛盾しない範囲で任意性がある。この二つを同時に焼きなます。考慮するタスクを処理する順序に1列に並べて、それぞれ誰に割り振るかが決まれば、各タスクの処理開始日が計算でき、選択した全てのタスク完了までシミュレーションが可能である。
近傍
近傍は以下の二つ。
- 一つのタスクを選択し、別の人に割り振る
- タスクの列において距離が10以下の二つのタスクを選択し、依存関係に反しなければ順序を交換する
評価関数
評価指標は以下の四つ。
- 全てのタスクが完了するまでの日数
- 各人のタスクを処理していない(暇をしている)日数の平均
- 各人のタスクが完了するまでの日数の平均
- 各人のタスクを処理している日数の平均
1がスコアそのものに直結するが、1のみだと探索が上手く進まないので、効率が良いタスク割り当ての指標として2〜4を採用した。
実行時間
終了したタスクがあるターンはこの焼きなましを実行する訳だが、あと何ターンでタスクが全て完了するか不確定なので、使ってもよい時間を推定しなければいけない。今までの1日あたりのタスク処理個数(= 完了タスク数 / 経過日数)と残タスク数から、残りの日数を単純に計算する。序盤ほど予測日数が長くなり、終盤ほど正確になるので、適当に補正値をかけるようにした。
初期解
一番最初の初期解は深さが深い順に並べて、ランダムに人を割り振る。それ以降は、前回の焼きなまし結果を復元し、新しいタスクは後ろに追加する。
その他
RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 参加記
問題
結果
最終5,214,965,972点で14位。暫定は259,015,342点で17位。
解法
収穫機7個以下の時
収穫機が少ない時には、価値の高い野菜に直接移動した方が効率が良い。ポリオミノの置き方を全列挙し、一番資金を稼げる配置を計算する。ポリオミノの最後の1個が、その時点での盤面で価値最大の野菜に置かれるように限定する。
収穫機8個以上の時
連結を保ちながら、次に取る野菜へ移動させていく。次にどの野菜を取るかをビームサーチで探索する(ビーム幅12)。次にどの野菜を取るかを決めたら、そのノードはターゲットの野菜を取るまでターンを進める。考えるべきは、ビームのソート方法・次にどの野菜を取るか・どの収穫機を動かすか・収穫機をどこに動かすか・収穫機の購入をいつ止めるか、の5つ。
1. ビームのソート方法
収穫機が多い順、同じなら資金の多い順にソートする。
2. 次にどの野菜を取るか
基本的に価値の高い野菜を取りたいが、遠すぎると効率が悪くなる。なので、距離d・価値vの野菜の評価値をv*0.8dとして、評価値の高い野菜3つを次に取る候補とする。距離が収穫機の個数より遠い野菜はそもそも候補に入れないようにした。
3. どの収穫機を動かすか
取り除いても連結性が保持されるものが候補となる。候補が複数ある場合は、動かさなかった場合に次に収穫される野菜の価値が最小のものを動かす。次に収穫される野菜は、収穫機の個数ターン先までしか見ない(例えば収穫機が10個だとして、その収穫機が50ターン後には同じ場所にはいなさそう)。
4. 収穫機をどこに動かすか
ターゲットの野菜までの最短のマスに動かす。候補が複数ある場合は、どれを動かすかの時と同様に、そのマスで次に収穫される野菜の価値が最大のマスに動かす。次に収穫される野菜は、収穫機の個数ターン先までしか見ない。
5. 収穫機の購入をいつ止めるか
購入を止めるタイミングを830・840・850ターン目の3パターン試して、もっとも良かったものを採用する。830〜850にしたのはその辺りで止めるのが最適なケースが多かったから。個数ベースではなくターンベースなのは、ビームサーチと相性が良いから(実装が楽だから)。
ざっくり時系列
1日目
問題を読む。当たり方針思いつかないと勝負にならなそうなので、思いつけるように祈りを捧げながら眠る。
2日目
連結を保ちながら動かすのが良さそうと思い実装する。次にどの野菜を取るかは適当に評価値を決めて貪欲に取っていく。226Mで5位くらい。とりあえず良さげな方針を思いつけたので一安心。
3・4日目
評価値を色々いじるけど、最初の適当に決めたのが強すぎて改善できない。
5日目
ビームサーチを実装して247Mで順位表1ページ目に戻る。いつもずっと2ページ目にいるから気分が良い。
6日目
細かいところを改善して253M。土日が残ってるけど、アイデアは尽きて本質的な改善はもう無理そう。
7・8日目
ひたすら1000ケースでのパラメータ調整と、バグ死しないか大量テストケースでチェック。259Mまで上がる。
反省点
やっぱり上位勢と比べると工夫が足りない…。未来を考慮したマスの評価とかもしたけど上手くいかなかった。シンプル解法+パラメータ調整で赤行けるかみたいになってきたな。
ColorShapeLinks AI competition 2021 参加記
参加者10人中、BaseTrackで同率1位、UnknownTrackで2位でした。
ゲームルール
重力付き4目並べ(https://en.wikipedia.org/wiki/Connect_Four)。ただし、通常と異なるのは、コマには色(color)と形(shape)の2要素があり、どちらかの要素で4目連続で並べたら勝ち。
- ボードサイズは6 x 7
- 先手は白い丸いコマを10個と白い四角いコマを11個持っている
- 後手は赤い丸いコマを10個と赤い四角いコマを11個持っている
- 先手は白のコマを4目並べる or 丸いコマを4目並べれば勝ち
- 後手は赤のコマを4目並べる or 四角いコマを4目並べれば勝ち
1盤面で同時に2つの4目並べを行うイメージ。通常のConnect4では自分の手番で相手が勝つことはないが、このルールだと、相手の形を自分が並べてしまうことがある。
(上記パラメータはBaseTrackのものでUnknownTrackではもっと大きいサイズとなる)
戦略
基本的にはMCTS。木の展開はWikipediaそのまま(https://ja.wikipedia.org/wiki/モンテカルロ木探索#UCT_(Upper_Confidence_Tree))。cは0.8に設定。
高速化
盤面をビット表現して高速化した。ビット表現は通常のConnect4を完全解析するコードの解説記事を参考にした(http://blog.gamesolver.org/)。64bit整数5つ*1で盤面表現でき、手番を進める操作・4目並んでいるかの判定がビット演算で高速に行える。すごく賢い。他の落ち物ゲーでも使えそう。
ランダムプレイアウトの改良
プレイアウトは以下のようにした 。
- 勝ち確定の手があればそれを指す(一手読み)
- 次の相手の手番で置かれたら負ける列があるなら、その列に置く(二手読み?)
- 次の相手の番に同じ列に置かれたら負けるなら、その列には置かない(二手読み。相手の形を置く場合は、次の相手の手番で別の列に置かれて負けることもあり得るが、そこまで計算していると遅くなり弱くなったので、同じ列のみ考慮した。)
- 序盤(先手・後手5手ずつ)は自分の形しか使わない
- 上記以外はランダムに選択
序盤定石
序盤(先手・後手5手ずつ)は定石を作成した。自分のAIのリプレイを見ていると、序盤は自分の形しか使わないし、直感的にも序盤に相手の形使ったら弱そうなので、そのように限定する。自分の形しか使わないと通常のConnect4と同じになるので、通常のConnect4の最善手を使えば良いのではと思い、使ってみると後手はめっちゃ強くなった。しかし、面白いことに先手は全く強くならなかった。なので、先手の定石は一手30秒かけてMCTSで作成した。 提出コードサイズの制限は1MBなので、定石は序盤のみしか使用できなかった。
終盤読み切り
終盤(先手12手目以降・後手11手目以降)はαβ法で最後まで読み切って最善手を指すようにした。ただ、終盤までくるとMCTSでも勝ち負けが逆転するような手は指されないっぽいので、あまり意味がなかったかもしれない。
Unknown Track
今までの話は全てBase Trackの戦略。Unknown Trackでは盤面が64bitに収まらないのでBigIntegerを使ったが、使い物にならないくらい遅くなったので、何の工夫もせず完全にランダムプレイアウトでMCTSをした。
その他
- 言語はC#のみだったが、余裕を持って打ち切ったつもりでも、GCのせいでTimeoutするということが頻発した。プレイアウトの回数に上限を設けるのと、制限時間の50ms前に打ち切るようにした。GCの起動が相手のプログラムにも依存しているっぽいのがやばかった。時間ギリギリまで使う相手だったらGCを押し付ける闇のゲームが可能かもしれない。
- Unknown Trackでは複数コア使えるので、来年も参加するなら並列化を試してみたい。
- 頑張れば完全解析できそうな気がする。完全解析されても提出1MB制限があればコンペは成立するか(?)
*1:頑張れば64bit整数3つでいけそうだったけど、プログラムが複雑になる&速くはならなそうなので5つにした
AHCで局所探索の途中経過を可視化する
自分の備忘用。公式のビジュアライザを少しだけ変更してMP4ファイルを作成する。
1). 可視化したい状態をファイル名を連番にして出力する。
. ├── a.out ├── main.cpp ├── out │ ├── out_0000.txt │ ├── out_0001.txt │ ├── out_0002.txt │ └── out_0003.txt └── tools
2). 公式ビジュアライザを変更する。自分の出力ファイルと同じディレクトリに、拡張子だけ変更してsvgファイルが出力されるようにする。変更するのは最後の出力の一行のみ。
fn main() { if std::env::args().len() != 3 { eprintln!("Usage: {} <input> <output>", std::env::args().nth(0).unwrap()); return; } let in_file = std::env::args().nth(1).unwrap(); let out_file = std::env::args().nth(2).unwrap(); let input = std::fs::read_to_string(&in_file).unwrap_or_else(|_| { eprintln!("no such file: {}", in_file); std::process::exit(1) }); let output = std::fs::read_to_string(&out_file).unwrap_or_else(|_| { eprintln!("no such file: {}", out_file); std::process::exit(1) }); let input = parse_input(&input); let output = parse_output(&input, &output); let (score, svg, err) = vis_default(&input, &output); if err.len() > 0 { println!("{}", err); } println!("Score = {}", score); // std::fs::write("out.svg", &svg).unwrap(); std::fs::write(format!("{}.svg", &out_file[..out_file.chars().count()-4]), &svg).unwrap(); }
3). tools/make_movie.shに以下のスクリプトを用意する
#!/bin/sh input_file=$1 dir=$2 num=$3 for ((i = 0; i <= ${num}; i+=1)) do echo ${i} n=$(printf "%04d" $i) cargo run --release --bin vis ${input_file} ${dir}/out_${n}.txt qlmanage -t -s 512 -o ${dir}/ ${dir}/out_${n}.svg mv ${dir}/out_${n}.svg.png ${dir}/out_${n}.png done rm ${dir}/*.svg ffmpeg -i ${dir}/out_%04d.png -pix_fmt yuv420p -f mp4 ${dir}/output.mp4
4). スクリプトを実行する。
$ ./make_movie.sh [インプットファイル] [1).で用意したファイルがあるディレクトリ] [連番の終わりの数]
