ICFP programming contest 2018
無職なこともあり、とても楽しい問題だったこともあり、久々にほぼガチで参加してる会になりました。いや楽しかった。順位表が凍結された段階での最終順位は2位で、1位は絶対に無理、その後にできた変更はしょうもないので、おそらく7位とかそのあたりの、5位強みたいなところに落ちついているのでないかと想像してます。暫定2位といっても特に良いところはなく、得点を決める式のおかげで、大幅なとりこぼしが無いだけで、推定1位のウナギに対して全順序がついて負けてる形のはずで、大変くやしい。が、まあ僕的には頑張ったとは思う。
初動
パーサやシミュレータを実装して、簡単なシングルスレッドAI、下から順に塗っていって、既にあるブロックとつながっていないところに置かざるを得なくなると、 Flip する、というものを Ruby で書く。デフォルトよりは大幅によくなることを確認して、いい問題だなあ……と思いつつ、寝る。
シミュレータについて、 SML 的ななにかからコンパイルされた JS だから、単純な方法でこれ切り出せるでしょ……と思ったけど、それに時間を使う余裕は最後までなかった。それに限らず、時間的余裕は最後までなかった。
起きて、 Flip のコストがとてもでかいこと、並列化が大変嬉しいこと、を再確認して、スケジューリングは賢くなくて良い(つまり無駄な動きをしても良い)から、 Flip はできればしない、かつスケールし、できればヘッドのMoveとFillの比が良い方針を考える。
思いついたのは、やはり下からスケジュールして行くのだけど、自分の左右と真下を塗る、という方針。Move:Fill比が最大1:3で、なんとなく良さそうに思ってた。
# B がボット、 O が担当する Fill する範囲 # 右方向が Z 軸、上方向が Y 軸、奥が X 軸で進行方向 OBO _O_
でも実装してみると最初の戦車ぽい形のやつすらダメで、理由は説明しずらいけどとにかくこの方針で Flip 無しはできないのでした。もう少しちゃんと考えてから始めるべきだった。
エレベータ
次に考えたのは、上方向から見た X-Z の平面を 3x3 の区間に分割して、並列に動くボットは、その空間の中で一回以上塗ることが可能などこかにアサインされる。イメージとしてはエレベータなのだけど、その 3x3 の中心を下って上がって、途中で塗って返ってくる。 3x3 の中央は、ロボットが作業用なので、まだ塗っていない領域が下の方にある場合は底の蓋をしてしまわない。
この方針でたいていの問題が Flip 無しで塗れる感じになり、 3x3 のグリッドの作りかた9種類をそれぞれ試すと、どれかは Full Division の問題を解けるようになりました。
最初に間違った方針で時間を浪費してしまったこともあり、 Lightning Division 中には全部の問題にたいしてまともな点数の結果を返すことができませんでした。見積りをあやまったな、と。
Lightning Division が終わった後も、このコードはバグバグだったので、それを修正しまくって、一通りバグが取れて、一通り FA の問題に適用し終えて提出すると、 FA に対しては全て1位が取れている感じになっていました。潜伏していた人もいたかもですが、これが Lightning Division に提出できていればなあ……と残念。
さてこのエレベータの方針は、
という2点の TODO がありました。 Full Division のルールを検討するまでは、これは結構面白い課題だと思ってたので、是非やりたいなーとか思っていました。ですが、構築はそれなりにうまくいっているので、まだ実装してない解体を優先しました。最終的にもこれらの TODO は手つかずのままだった。
役割が無くなったボットは、とりあえず天井まで移動して、それから次に行きたい場所をアサインする、という流れだった。そういう感じでやると、当たり前だけど x=1 z=1 にいるやつは x=5 z=1 に移動しようとして、 x=5 z=1 にいる子が x=1 z=1 に移動しようとする、いわゆるデッドロックが頻繁に起きていた。これはまあ、定期的に全員が Wait を発行している場合、ランダムなタスクの担当者を入れ替える、という雑な方法で解決した。まあこの問題は頻繁に起きることではあるけど、しかしスコアに大幅な影響を与えるほどの問題ではないであろうとそのままにした。
解体して良いかという判断
解体は、構築と違って、この座標のブロックを消して大丈夫か…という判定が自明じゃないので、そこをまずあれこれと考えました。最終的に、近似的な方針でやることにした
- 最初に地面から幅優先探索する
- とあるブロック X に幅優先で辿りついた時、 X に同時に辿りついた元のブロック群が、ブロック X を支えている、と仮定する
- ブロック Y を消して良いかを考える時、 Y が支えている全てのブロックをチェックし、そのいずれかが Y によってのみ支えられている時、そのブロックは消してはいけない
例えば
ＡＢＣ Ｄ Ｅ
だと、依存関係は
Ａ→Ｂ→Ｃ ↑ Ｄ ↑ Ｅ
となるので、Ｃしか破壊できないと正しく判定される。
ＡＢＣ ＤＥ Ｆ
だと
Ａ→Ｂ→Ｃ ↑ ↑ Ｄ→Ｅ ↑ Ｆ
なので、Ｃに加えて、ＡとＥも、どちらかなら破壊して良い。何故ならＢはその両者から支えられているから。
保守的になりすぎて消せるブロックを消せないと判定するケースがあって、
ＡＢＣＤＥ Ｆ＿＿＿Ｇ Ｈ＿＿＿Ｉ
だと、どれを消しても大丈夫なはずだけど、Ｃしか消せないと判定されてしまう。
Void による解体
解体可能判定が上記で決まった後も、特に良いアイデアが無かった。よって、よく覚えてないけど、おおむね構築時の 3x3 に分配するアルゴリズムを使いまわす感じの、しょうもない実装で実現した。
解体時は構築時と違って、 Void によって移動範囲が減ることは無いため、あまり大変なバグは起きることはなくて、まあほどほどのタイミングでこれは完成した。ただ 3x3 に切っていくという方針はそもそも解体にとって良い方法ではないため(特に上述の解体可能判定が正しくないため)、かなり遅いものになってしまったという感じ。
感想戦で twitter で見た方法として、解体は構築の逆再生をすれば良いというのを見て、なるほどこれをやっていれば解体について使った時間の多くの人的時間を節約できたなあ……と思った。
平面 GVoid による解体
明らかに構築に比べて解体で得ている得点がイマイチだったので、解体をもう少し考えることにした。
結果、解体は GVoid でまとめてやるのがやりやすく、依存解析をすっとばせる部分がたくさんあるのもあって、むっちゃいいじゃん、となった。とはいえ、 3次元 GVoid はこの段階では「管理大変そうだなあ…」という感覚があり、2次元 GVoid で上から順に切りとっていくソルバを作った。
これはコード量はおおくはないし、このソルバ自体は前述のソルバと違って全ての問題を解く汎用性はないけど、多くの問題に関しては前述のソルバを凌駕するものとなった。こういう、問題によって違うソルバが有効になる問題は一人チームだとキツいんじゃよーと思いつつ、だがうまくいったのでよしよしと思いつつ次へ。
最高記録管理、あるいはインフラ
今回一人チームきっっつい、と思った部分はいくつもあったのですが、一番きつかった部分でした。今回の問題の場合、単一のプログラムがベストの解を出す必要はなく、複数の似たようなプログラムがそれぞれ出した解の最高の物を提出すれば良い形式で、かつ、その最高の解が必ずしも最終バージョンのプログラムによって生成されている必要はない、という形式でした。
そのため、提出できる解のうち最高のものを管理し、かつその最高のものを越えた解があればそれでアップデートする必要がありました。これは2種類のめんどくさいタスクを追加しました
- 開発中のシミュレータはおそらく正しくないため、現段階でのシミュレータで実行してみて、たしかに一番良い結果が更新された、と判断すれば最高記録として記録する仕組みを作りました。0点を取ると死ぬ今回のルールでは、これは安全で良いアプローチだと思うのですが、問題はシミュレーション自体が大変遅いものであったということでした。おかげで、常に「なんだかもう覚えてないけど、なんかの計算結果を(おそらくムダに)検証している、という状態になりました。
- 3D モデル X を別のモデル Y に変換する、というタスク(FR)は時間が足りなかったこともあり、単純にそれが一番効率だと考えられたこともあり、 X を完全に解体してから Y を完全に構築する、という方針で解きました(たぶん他のチームもそうやっているかと思います)。これは X を解体する最高記録を残しつつ、 Y を構築する最高記録も残して、んでその二つの最高記録をマージしなきゃだということになります。めんどくさい
- 当時の段階では、 FR なモデル(つまり解体&構築なやつ)は、ものによってはひょっとすれば解体+構築より効率的な実装ができるかもなあ……と思っていたので、解体+構築を同時にやるようなアルゴリズムが後でできるかも、という仮定の元、2日目寝る段階では、 FR は単に FA+FD をまとめてやる物を計算して寝たのでした。よって FR 解から FA 解と FD 解を切り出してきて、一番良い FA & FD を切り出す、というような余計なタスクが発生しました
などなどやってるうちに、結構な時間が溶けました。結果として、 FA+FD よりも FR を効率的に解く方法を考えられる問題はぱっと見見つからず、 FA+FD を効率的に解けることを期待したインフラも完全に無駄になりました。
今にして思えば、アルゴリズムで作った手順が、シミュレータで間違ってることは基本的に無いため、再確認は特にせず最高記録を更新する手順にすれば良かったなあ……と思う。
まとめて 3D GVoid
この段階でもう一度リーダーボードを眺めて、構築も解体もほどほどに良い解は提出できている(Flipも無いし並列化もされている)ので、特に「こういうタイプの問題で弱い」みたいなのは無く、単に全て弱いことがわかっていました。そこで、複雑な問題は再計算する時間が無いため、単純な問題に対して単純でかつ有効な解は無いか……ということを考えました。
すると、単純な問題での解体がイマイチな点数であることに気付いたので、あれこれ考えました。あれこれ考えた結果、単純な問題は問題全体を GVoid で消してしまえるのでは……と気付きました。
で、最初に8体に分裂して、全体を消して、終了、みたいなやつを作りました。あたりまえでしたが簡単な問題については劇的な効果がありました。今にして思えばこのロジックをさらに良くして、一回で消し切れない問題に対しても 3D GVoid を使う解を生成する価値があったと思っています。
たしかこれをやってるあたりでリーダーボードが凍結されました。
GFill を使ってみたい
このあたりで、「やりたいことは無数にあるけど、期間内で実際にやれて、かつスコア的に劇的に有効な手が思い当たらんなあ…」と思ってました。その結果、 GFill 使ってないのはムダすぎるよね、と思いました。
で……ごくシンプルな 1D GFill と Fill で解ける問題だけを解くソルバを作りました。序盤の方の問題はこれで全部解けるだろ……という気分で作ったのですが、実際見てみると壊滅的で、 FA 3問くらいの最高記録を更新できただけで終わりました……
まとめ
すごく楽しかった。まじですごかった(低語彙力)。問題をぱっと見た時に、「なるほどこれ俺もできそうだ」と思うにも関わらず、いざやってみるとすごく簡単なことですらクッソ大変、というのがすごく良かった。大変明確に動くヴィジュアライザなども用意されていた。
例年と比べてもノンゼロの点数が少なかったらしい。敷居が高かったのでは、という観測もあるみたい。ごくごく個人的な感覚では、今回の問題の敷居は高くなかったと思う。常に Flip on の状態で動く解が主催から与えられているので、その中にある移動命令いくつかをつなげるだけでノンゼロの点数は簡単に得られる。単に、今までノンゼロを得ていたチームの中でほとんど実質参加してなかった層が、自明なノンゼロ解を発見できなかった、もしくは ICFPC 自体の参加者が減っている、そのあたりが理由じゃないかなあ……と思う程度には、今回の問題は弱いチームに配慮されている問題だったのではないかと思う。
個人的には、 Full Division で追加されたルールは全て必要なかった。今思えば、全ての追加ルールが、単純にゲームをシンプルにする方向に変わった気がする。当初の問題で、勝てたかっていうと今よりもっとひどい負け方をしていると予想されるのだけど、ただどっちが楽しめたかっていうと、 GVoid/GFill の無いルールだったんじゃないかな。というか、最初に考えたエレベータ方針をもっときっちり詰めたかったな。
いやでもまじで当たり回だったとおもってますマジで
