ICFPC2019 振り返り
ICFPC 2019 にチーム「花脊山の家」として参加しました。メンバーは以下の4人です。(nojima君はあまり参加できなかったけど)
- cos
- nojima
- qwerty
- seikichi
リポジトリは https://github.com/seikichi/icfpc2019 です。去年と同じくRust使用。
問題
最大400x400程度のグリッド状のマップが与えられるので、ロボットを操作して全ての移動可能なマスを塗りつぶせ。マップにはブースター(アイテム)が置いてあり、それを取得して使うと塗れる面積が増えたり、2倍速で移動できるようになったりする。 300問程度のマップは全て公開されてあり、オンラインで解く必要はない。
また、ライトニング終了後の追加仕様で本編とは別にマイニングが可能で、指定された制約を満たすマップを15分に1回作成・解くと、本編でブースターが購入可能になるラムダコインが手に入る。 こちらはオンラインで解かないといけない。
1日目
仕事が終わってから集合場所のホテルに向かう。
19時過ぎ(ICFPC開始が19時)に、ホテルに着いたら問題を読んだり公式のビジュアライザをさわった所、仕様追加でどうせテレポートが出るでしょとか水没するんでしょとか言いつつ、なんか去年の問題の2D版だなあという感じがした。その後、飯を食べてタスクを洗い出してから実装を開始。
まずは入出力・AIの型を適当に決めて分担作業をできるようにしたら、入力パースと最も単純なAI(塗られてない箇所をとにかく塗るAI)をseikichi君とqwertyさん・出力と座標などのライブラリ作成をcos・チーム名決めとチーム登録と問題のビジュアライザ作成をnojima君が担当。
25時くらいにexample01で正の点数を取れるようになったので、問題が更新されるまで寝ることに。
2日目(ライトニング提出まで)
朝起きたらとりあえず問題を読んで、新仕様の入出力対応をcos、1日目のAIのバグ修正を引き続きseikichi君・qwertyさんでやる。バグが取れたら答えの管理をS3を利用するようにしつつ、マニュピュレータを使うようにして13時くらいに初submit。
次にタスクを整理しなおして、速攻でCloneを取りに行って分裂するAIをcos、解答管理・サブミット管理のスクリプトをseikichi君、初期AIのヒューリスティックの調整(回転とかxyの優先度の変更とか)をqwertyさんが担当して実装する事に。
ライトニングまでにCloningを使ったAIもできたので、(Cloneがない場合は同じ挙動するはずなのに点数が違うのはおかしいなあと思いつつ)Cloneが出るまでは初期AI・それ以降はCloneを使ったAIを使うことにしてライトニングは終了。
2日目(真ライトニングラウンド)
ライトニング終わって疲れたので、問題見るのは後回しにしてとりあえずご飯を食べる。帰ってきてから問題を見ると、ライトニング終了から4時間後にマイニングなるものが始まるとおかしい事が書かれてあった。
この、マイニングで利益を得ると圧倒的に本編で有利になる(Cloneが無いマップでCloneが使えるようになるので上位に入るためには必須)し、可能な限り早い段階からやっておかないといけないし、今までのソルバーとは関係ないし、これをライトニング終了直後の4時間で実装しろというのがひどい。
マイニングの自動化周りはseikichi君にまかせて、マップ生成を実装する事に。
マップの内外の制約が一番厳しく、頂点数、面積上限下限(面積の上限は読み間違え)もちゃんとやらないと引っかかるので結構難しい。とりあえずマップの内の制約を満たすようにbfsで頂点をつなげたが、外側にいないといけない頂点を囲ってしまったので、障害物を置くことにして、面積は適当に増やして、頂点数はマップの端を右手法でたどっていく最中に適当に穴を掘って対応した。
グリッドから出力形式への変換がめんどくさいとか斜めの自己交差がめんどくさいとか言いつつ2時半くらいに実装ができてチェッカーで試した所、障害物は置けないことが判明して実装やり直しに…。
今度は、ダイクストラ法で内側の面積を最小にして外側の頂点を囲わないようにしつつ、マップの内の制約を満たしたら内側のエリアからてきとうに長さrの正方形を内側にして太らせて内外・面積下限の制約を満たすまでランダムでマップを生成することにした。
最終的には4時過に実装完了してチェッカーが通った。眠かったし、ランダムでてきとうに実装したのに割とちゃんと動いた。疲れたので寝た。
3日目
CloneのAIのバグ取ったり、各ブースターを取って使うようにしたりした。2倍速とドリルの組み合わせで、掘った穴にぶつかって位置調整するとかでひたすらバグるのがつらかった。発生確率が低かったので、最終的にはあきらめて行動中に不可能な行動を取ろうとすると、キャンセルして行動を決めなおすようにした。
他の人は解答管理スクリプト周りやマップをk分割して順番に塗っていくAIを作っていた。
あと、ランダムのシードが変わると得点が良くなることが結構あったので、良い乱数を引くまでEC2上でガチャを回すようになった。
4日目
ビームサーチっぽいのを雑に実装した。スコアの計算を今から実装するのが難しいので、乱択要素を外してそのまま動かしたときのステップ数をスコアにしておいた。 後はマップをk分割する方がバグっていたのでヘルプに行ったりした。
ちなみにアイテム購入は前半の問題から1個ずつCloneを購入で220面くらいまで買えた。
感想
文句
- ライトニング終了直後にライトイニング始まるのはさすがにきつい
- 実際間に合ったチームが少なすぎて延期になった
- しかも、解くのが難しい割に1回作って後は放置で良い…
- あと、日本はまだましだけど時差によっては悲惨になりそう
- せめて、最初から仕様を公開しておくべきだと思う
- チームとしては延期後の初回には間に合ったのでまあ良し
面白かった所
- パズルソルバーがちゃんと動いてて感動した
- なんか眠い中てきとうに作った割には3,4問程度しか落としてなくてすごかった
- AIを強化するたびに点数が上がっていくのが楽しかった
- 使うブースターの種類を1種類増やすたびに5%くらいは改善していった
- ガチャしたり、ビームサーチでも上がった
- やっぱRustは良い
バグ周り
- ライトニング前のCloneを使うAIがバグってた
- これはバグを直す時間がなかったのでしょうがない
- ビームサーチがバグってて直すのが遅れてガチャが十分回せなかった
- 書いた行数が少なかったので人に任せたが、さっさと直してから他のことに手を付けた方が良かった
- thread_rngのせいでバグったときに再現性がなかった
- small_rngに変えてバグが出るまで実行したりでめんどかった
- ガチャするときに同じseedを使わないようにしておけばsmall_rngでも十分足りる
- グリッド分割のAIが間に合わなかった
- 自分が書いたAIに、他の人がさらに大きい機能を追加しようとして時間がかかった(ブースターを使わないと話にならないので使いまわすのは必須)
- 特に4日目にバグ取るのに手間取った
- 関数の責務が明示的になるように分割したり、出力のバリデーション強化くらいはしておいた方が良かった
その他
- 実質3人だとこれ以上複雑なことやるのは厳しい
- 例えば、マニュピュレータは真横以外につけるとか、ダッシュボードの作成とか、アイテム購入の最適化とかはしてない
- まあ15位以内に入ってるっぽいので十分検討はしてる
- たまに一人チームもいるけど…
- リモートの人に仕事を振るのが厳しい
- discordとか用意した方が良い?
- リモートが厳しいというよりかは参加時間が短いと厳しいのかも
結果
8位だったようです。去年よりも良い結果だったので嬉しい。