ICFPC2019に参加したんだよ - ちゃっくのメモ帳

破滅

追記

チームメンバーは僕の他にすごぷろ(@jke_null)、zakuro(@emotionalcattle)、kuwa(@lrmystp)、葦(@Ashur_titech)でICFPC 2019にチームIQ1として参加した。
一応使用言語は僕がC++、すごぷろさんがPython、zakuroさんがjs、葦くんがC++から途中でPythonに変更した感じ。

金曜日夜
問題を読んで「関数型おじさんの書いたなろう小説かな」って気持ちになった。

土曜日
問題概要を共有した後、僕が入力のパーサーを書き始めてバグらせる。デバッグしてたら後からパーサーの実装を開始したすごぷろさんと同時にパーサーの実装が完了する。
この間にzakuroさんが自動テストツールを作り始める。
IQ1は土曜日から開始したがコンテスト自体は金曜日の夜から始まっており、作業開始時点でteleportとcloneが追加されていた。
個人的には去年のICFPC的にcloneはlightningが終了した後に開始すると思っていたので驚いた。

基本的な方針としてすごぷろさんはとりあえずDFS+最適化でcloneにさっさと手をつけようとしていた感じだった。
僕はビームサーチで探索していこうかなという感じ。
葦くんは盤面をグラフにしてく方針を考えていたっぽい。kuwaさんもこれに賛成してた。

zakuroさんに「コマンドラインから動く自動テストツールが欲しい」って言ったら夕方には完成していた。流石って感じ。

1日目はビームサーチ書ききれずに終了。
すごぷろさんはDFSをするやつを書き終えていて流石に速いなあという気持ちになった。
葦くんも実装が完了していなかった。

日曜日
すごぷろさんがいつcloneを動かしてたかしらないけど日曜日にはdfs+cloneが動くようになっていた。
僕はビームサーチを動かしたら最後の方に盤面が小さい穴だらけになってビームサーチである程度減らした後にBFSで近いところにから埋めていくという方針に変更。

また、日曜日の朝には新しい部門が生えていた。Lambda-coinをマイニングするという部門で土曜の23時から開始していたが、やるなら早い方が良かった。(これは仮想通貨の特性上)。
すごぷろさんは気がついたらマイニング用のパーサーを書いていてくれた。
すごぷろさんとマイニングしたほうが良いか相談したけど他のチーム見る限り2万点くらいは取れそうな雰囲気を感じてやったほうがいいかなぁくらいの感じになったので葦くんに投げた。
このマイニングが思ったより大変で大まかな方針は経っていたが実際にそれでいけるかは問題によるなぁという気持ちは会った。

僕はビームサーチ→BFSという方針を相変わらずやっていたが、Wheelの実装でバグらせていた。Wheelの使用を途中でキャンセルできないのでBFSで1マス移動で探索するとバグることに気がつくのに時間がかかった。
すごぷろさんは多分DFSとCLONEの最適化をしていたんじゃないかなぁ(多分)

月曜日
社会人組は出勤してしまったので僕と葦くんだけでやっていた。
葦くんはマイニングの実装が大変そうだというのと方針が微妙で頭を抱えていた。
15時くらいに「盤面全体を初めからiSeqとoSeqの両方が含まれないように一定サイズで区切って最小全域木を構築したら行ける気がする」とか適当なことを言ったら葦くんは実装をしてくれたけど、これは実際に入力に対してやろうとすると区切ったブロックが小さくなりすぎて制約を満たせなかったらしい。この時点でマイニング終了なので諦めた。

僕はビームサーチ+BFSで1~150のケースで割とすごぷろさんのケースに勝てていたのでビームサーチである程度削った後はBFSで最寄りの空きますに移動したあとにそこからビームサーチをし直すことを繰り返すという方針に拡張していた。
実際にやろうとすると計算コストがおもすぎるが、そこはサーバーで4並列で動かせばまぁなんとかなるやろという雑な方針。
更に、腕の優位性は大きい盤面で効いてきそうというのと大きい盤面のほうがスコアが重要になってくるはずなので開始地点から近い腕は最初に取っておくことにした。
ビームサーチの評価関数は「残り未到達領域+ターン数-腕の数」とした(小さい方が優秀)。
ビーム幅20~30くらいで深さは20~100くらいで探索した。
これをサーバーで150ケース計算したら月曜日が終了してしまった。

反省

ビームサーチを使うと、どうしても1,2マスよりも大量の未到達マスがある方向に行ってしまうので最終的にあちこちに未到達マスが残ってしまい、最後の方で大量の移動をすることになってしまう。
これはビームサーチに探索の深さ制限を設けてるからであるが、この制限は計算時間的に外すことができないのでホントは1,2マス残った部分を評価関数に含めるべき。ただ、これを計算すると評価コストが上がりすぎてビーム幅か探索の深さを諦めることになるので却下。
結果としてはビームサーチを選択したのは余り良い方針ではない。
この問題は明らかにTSPなので焼きなまし+2-optとかが良いらしい。
この辺りの勘が働かなかったのはどうしてもマラソン系を普段やらないからというのと、ちゃんと考察せずに思いつきの方針で突っ切ろうとしたのがダメ。

後は実装力が低すぎた。実装中になって「あー、この方針このあたりでバグるなぁ」をいくつも見つけてしまったのでこういうのをなくすべきなんだろうなぁという気持ちになった。(あとは普通にバグらせる(普通にバグらせるな))