ICFPC 2014
総じておだやかに楽しかった。
https://github.com/shinh/icfpc2014
1日目
初日、21時から問題を読む。んー普通だなーと思いつつとりあえず寝る。
起きて Lambda-man の AI を書きはじめる。普通だと思ったけど、 Lisp マシンってこういうふうな感じなんだなぁ、と、知らなかったので普通に勉強になった。とりあえず思った通りに動くものを作ろうということで、アセンブラを Ruby 上の DSL として書く。オペランドの数と型のチェックと、ラベルの解決をするくらいのやつ。
なんとなく何ができるかわかったところで、これはアセンブラ直書きは大変だし変更に弱い…ってことで、そのアセンブラの上に高級言語を作る必要を感じる。素直に Lisp でもいいけど、あまり Lisp 書き慣れてないので、 Ruby 上の DSL をもう1レイヤ重ねることにした。あとは beflisp の知見を生かして、 LLVM bitcode からの変換ってのも考えたんだけど、そういうのがしたければ複数人がいないとな、て感じ。
きちんと理解する時間がもったいなかったので、 Lisp マシンぽいところなのか、難しそうな命令は無視して、 store 命令を使いまくって、普通にローカル変数をいじりまくるような作りにした。こういうのは書き慣れてるので、割とするっと書ける。引数用に用意された frame だけではローカル変数を置けないなーと思ったので、全ての関数は引数と local 変数を置けるもっと広い frame を作ってから、実際の実装に関数 call する、ってことにした。関数呼び出しのオーバーヘッドが大きくなるけど、関数をあまり呼ばない作りにすれば問題ない。コードサイズの制限はゆるいし、命令キャッシュとか無いわけで、 Ruby のレイヤで関数作ってやれば、 template みたいな感じでコードサイズが大きくなる方向でコードの再利用はできるし。
で、できた DSL で、とりあえず時間とともに移動方向を順番に変えるような AI を作ってみた。これは書きにくいなーということで、 AI を書きながら、色々書きやすくしたりした。まぁそれほど良いものでは無いけど、これで最終日まで戦えるかな、って程度にはなった。
各地点への最短距離を調べるコードを DSL 上で書く。配布されてた3つのマップはクリアできるようになった。よく死ぬのが微妙なんで、敵をある程度避けるようにした。直線上で向きあう動きと、2マスだったかそのくらい接近するのを避けるようにする。
最短距離を調べるコードは getXY とか setXY 的な処理をしまくっていたので、デカいマップで不安だった。これは無理かなぁと思いつつデカいマップで試してみると、当然ダメ。
しょうがないので、最短距離調べるアプローチより弱くなるだろうな…と思いつつ、スコア源に引かれる重力モデルを実装してみる。これでもデカいマップはきつかったけど、速度的にはかなり良くなってたので、見る範囲をしぼったりして対処。しかしやはり弱くなる。
ていうかヘンなところにひっかかったりする。なるべく1ターン前のところに戻るのはイヤがるようにしたりすると、まぁまぁ動くようになる。しかしやはり弱くなったように感じる。
あと1時間くらいでライトニング終わるなーというところで、あ、自分からの近距離だけの map に対してだけ最短距離調べるようにして、それとのハイブリッドにしたらいいんじゃね、と気付いて実装したらかなり良くなった。ただこの時のコードには、左端と上端にいる時に動作が不審になるバグがあったと最終日に気付いた。
この Lambda-man の DSL は Ruby のコードと DSL ぽい部分が混じりまくって (Ruby のループの中で DSL の whileP とかいうループが回ったりしている) 見た目がすごいことになってるのだけど、割と私一人が書くぶんには大丈夫程度のものが、割とスルっと書けたので満足することにした。
うーん ghost の AI も書くのかーとなるとシミュレータも書かないとだなー盛り沢山だなぁ、シミュレータの言語は何にしようかなぁ、と寝る。
2日目
2日目にシミュレータを書く、ってのは割と恒例ではある。言語は GC が欲しいな、ってことで Go にした。 D 言語と悩んだけど、既に入ってた Go に軍配が上がった。 Go はまぁちょくちょく触れるけど、書きやすいよね。 Google 社員的にはノリにすごい慣れてるんだよな。 C++ でもこんな感じのコード書いてるよなあ、っていう。あ、 Chrome とかはだいぶ違うけど。
で、 ghost や lambda-man の処理系は、拍子抜けするくらい簡単に作れたのだけど、そこからがこれも恒例の、ゲームロジックの挙動が微妙に違う祭り。ひとつひとつ仕様の読解/理解ミスを正していく。これはいつも以上にドキュメントが量も多くて細かいところに不明なところが多くて大変だった。途中である程度あってりゃいい気もしてやめようかと思ったけど、まぁ信用できない部品を放置するのは ICFPC ではやばい、っていう経験則からがんばった。
最後はリファレンスインプリのバグまで再現して、あとまあ同時にイベントが起きた時のコーナーケースにミスはあるだろうけど、ってあたりまでやって、終了。しかし、途中で、リファレンスインプリのバグはご丁寧に修正されてしまったので、リファレンスインプリと不整合な結果を返すのは我慢して戦うことになってしまった…
次は ghost を書いてみる。今度は Lambda-man 用のアセンブラをちょっといじって ghost アセンブラを Ruby 上に作る。んーなんか 256 instruction くらいならこれでいいんじゃね、ってことで、それで良いことに。
どういうのがいいのかなぁと考える。素直に襲いかかるやつと、一箇所をひたすら防衛するやつ、とかを考えた。後者はいかにも弱そうなので、襲いかかるやつを作ってみた。適当に作ると、これが結構強い。 Lambda-man が虐殺されている様を見るに、あーこれは効率良く pill を集めるとかよりは、避けゲーかなーと思う。
ただ、適当に作った素直に襲いかかるやつは、最初のサンプルマップの初期位置にひっかかる。あたりまえである。というわけでランダム要素とかをちょっと入れてみる。だいぶ良くなるが、まだみんな同じ行動しがちで意味がない。他の AI の案が思いつかなかったので、もうちょっと散らすことにした。具体的には本家パックマンを参考に Lambda-man が向かってる先を目指す、っていうヒネりが無いやつ。
このへんで、はて一通り提出できる体裁はととのったが、はてどこに力を入れるべきか…と考えつつ寝る。
3日目
なにすっぺかなーと考えつつ、細かいバグとかをなおす。感覚としては、 Lambda-man にもっと高度なプログラム的に賢いことをさせるべきだ、ってのがあった。例えば ghost をシミュレーションして短期間の未来予測をするとか、グラフ構造を作って危険な道とか安全な道とか考えて動かすとか、そういうの。
ただこれは与えられてる clock cycle であるとか、自分のアルゴリズム知識的なことと、あとそもそも ghost は適当に襲いかかるだけでも Lambda-man には結構脅威、ってことから、なんかやってみるかなー別にいいか…ってのを繰り返してるうちに終了した。まぁやんなくて良かったんじゃないかなーと思ってるが、謎。
というわけで、なんか割と作りたい雰囲気のものができてしまっているので、細かい完成度上げに使った地味な一日になった。あと途中で昼寝した。 ICPFC 中に5回寝たのはたぶん新記録。
地味なんだけど、結構 AI の細かい作りこみみたいなの、わりと好きなようで、1日だけだと結構たのしい。
まず、 ghost 強すぎ…ってことで Lambda-man の回避装置をちょっとマシにしてみる。いまいち。ていうか Lambda-man 死ぬ時はだいたい挟まれてるのよね。未来予測とかグラフ作りをそれなりにやらないと、たぶん不幸な未来を避けるのは難しい。ていうかこれ普通に考えると運ゲーにならねー、でも賢い人はこの状況で Lambda-man 生かせるのかな…とか思う。
さて死ぬのは諦めた。しかし怯えてる ghost は得点が高いし、 fruit も得点が高いので、こいつらを優先的に喰うことにしよう、てなことをやる。このへんから一人イタチごっこがはじまる。
あ、私の ghost 、 Lambda-man に襲いかかりすぎるあまり、殺すのはいいんだけど得点渡しすぎてる…と思ったので、怯えモードの時は行くところの優先順位を逆転させてやる。逃げ AI 。
うーん ghost 食いにくくなったのかな、と power pill の隣に待機して、 ghost が近寄ってきたら power pill を食って ghost を食べる、ってのを実装する。いくらなんでも無限に待つとザコ AI 相手に power pill の隣でウロウロしてるだけで終わってしまうので、timeout なんかを実装してやりつつ。
あ、私の ghost 、待ちラムダーマンにやられて、標準 AI より得点渡してる…と気付いたので、 Lambda-man が power pill に近い時には怯えモードにしてやる。逃げる逃げる。
なんとなく Lambda-man の生存率が高くなってる。あたりまえだが怯えモードの時に画面の端までいってしまうので、 Lambda-man の power pill 隣待機作戦は、 ghost 喰うのには成功しないものの、その後しばらく安全に移動できるようになっちゃってるぽい。なるほどということで Lambda-man から遠い時は襲いかかるモードにする。
こういう感じの細かい調整をまぁいろいろ。 Lambda-man が一手で ghost を食える時は喰うとか、なるべくがんばって fruit は喰うであるとか、 ghost も最初の頃に入れたランダムな挙動が Lambda-man に近付いてる時とか逃げてる時に出す必要は無いなーとやめてみたりとか、そういうの。
感想
面白かった、と思う。評判があまり芳しくないぽいのはまぁわかる。問題に面白みは足りないと思う。まぁ L:tG とかと比べるのは酷。ただ、分量は多いので、こういうのは一人でやってると無理ゲー感はあるものの、楽しい。 ICFPC って、結構終わってから、誰かと組みたかったな…と思う年はあるのだけど、今回はそうではなかった。ま、そんなに成績は良くないだろうけど、あーなんか色々やったなー的な充実感があった。
あと今回結構、色んなところで(私が一人でやるという前提に立てば)正しい選択を結構できたのではないかな…という感はある。まぁ、このへんは毎年、あーがんばったなーと思いつつ、他の人の思いもよらない作戦に、あーこのくらいは思いつけるべきだった…って思ってるんだけど。まぁ、今回はそういう裏技が思いつきにくい、割と素直な問題だったと思うんだけど…
