ICFPC 2011
問題は例年通り面白い…とかいう次元じゃなくて無茶苦茶よくできてるなーと思った。感動的に。
L:tG とかいう対戦型カードゲームの AI を書く。 M:tG に名前似てるけど、デッキとか作る感じではなくて、15枚のカードをいつでも使える感じ。カードは256個のスロットに置いていって使う。256個のスロットはそれぞれ HP を持っていて、 HP がゼロになると死ぬ。相手のスロットを全部壊せば勝ち。15枚のカードはそれぞれすごい細かい機能しか持ってない…っていうか関数型ミニ言語のオペレーション一個分しかないので、かなりの枚数を組み合わせて強い効果のある魔法を作っていく感じ。
このへんのバランスが絶妙で、相手を全滅させるような強力な魔法を作ろうとすると、それを作ってる間に殺されたり邪魔されたりするかもだし、かと言ってメラを連打してても相手は死なない…みたいな。主催の人々はかなり色々なルールをテストプレイして強すぎる戦術が無いように調整したらしい。
あと、関数の形をがんばってシンプルにするとデカい魔法を作る時間も結構減らせるのも面白いなーと思った。こう、熟練した魔法使いはデカい魔法をすぐに撃てるのだよ…みたいな。
そのへんがあまりにうまくいってるので、3日間、ゲームを理解すればするほどこのゲームの神バランスはすげーなーと感動しまくりだった。私はプログラム対戦ゲーをしょっちゅう妄想してる感じで、すぐにバランス崩壊しちゃうのはなんとなく想像できてたんで、特に感動できたように思う。
カードのセットを見ると S とか K とか I とか、関数型言語の素養が必要な雰囲気が出まくってて敷居が高そうに見えるけど、例えば再帰を止めなくていい(関数適用が1000回越えると勝手に止まるので終了条件書かなくていい)とか、変数があるから Y コンビネータとか無しで再帰が簡単に書けるとか、問題文の example でそのへんのヒントがきちんと与えられてるとか、実際のところの敷居はかなり低く頑張ってくれてる感じだった。 unlambda の知識とか、ラムダ式からSKIへの変換とかの知識は、むしろ知らない方が有利なんじゃないかくらいの勢いだった気がする。
素晴らしい問題を作ってくださった人々(今回は日本の人が問題を作った)に感謝。
で、私の提出物。
http://shinh.skr.jp/dat_dir/icfp11.tgz
しかし、なんというか個人的には反省の多かった感じだった。たぶん5位程度とかだろうから何言ってんだって感じではあるけど、あきらかにバグが残りまくりだったし、思いついていた戦術で実装できてないものは多いし、正直何やってんだって感じだった。まあ問題がかなり得意分野 (ミニ言語で巨大なコード書き続ける体力とかには自信がある…) だったと認識してるんで、自分に対して不自然に高望みしてる面もあると思う。
主な反省点は時間と戦術のコントロールが全然できてなかったことがあると思う。初日の3時間寝坊からして色々アレだった。シミュレータがやらなくていい速度的な工夫とかやってたりするのもろくでもない感じ。あとそもそも二日目とか GSL (SC2の大会) 決勝見たり他の人のプレイ見たりとか SC2 の他の大会見たりとか、論外的な面が…
戦術の方は、まあ一人でやってるからしょうがない部分もあったと思う。仮想的が全くいないので、相手の戦術が完全に読み切れなくて、思いついた作戦のどれが優先度高いのかとか判断しにくかった。まぁ今回は unofficial duel server を主催の方で用意してくれていて、終了時のターン数とかからかなり相手の戦略を想像できたので、そういう点では良かった。
さて、今回重要だったんじゃないかと思うのは…
- ちゃんと動くシミュレータ(私のは最後までちゃんと動いてなかったみたいだし、構文木を deep copy しまくるので相手が意図的に再帰的に構文木をデカくしてくるとメモリ使い果たす…)
- S とか K とかをラクに書く工夫。これは気合いで全部手書きする根性があればやらなくてもいいし、3日間で書ける程度の最適化ではまず間違いなく全手書きのコードよりデカくなってしまうとは思うので、私はほとんどやらなかった
- ゴルフ。前述の通りオペレーション列を短くできれば速く強い魔法を撃てるので良い。しかしまぁ戦略的なことの方がはるかに重要なので、ここに時間を使い過ぎるのは得策ではなかったと思う
- 臨機応変な戦略の切り替え。例えば自分が使おうとしているスロットが死んだらすぐ生き返す、とかはどう考えても必要だし、相手がしつこく同じスロットを殺してきたりするようなら、それを検知して生き返すと同時に HP 回復もやるような魔法作る、とかした方がいいように思う。たぶん3日では誰もできないだろうと思ってたけど、相手の行動から相手の意図を探索して…とかできれば強いしかっこいい…
- 戦略。まぁ結局これが一番大事
戦略として強そうかなーと思ったのとしては
- 重要なスロットの防衛をキチンとやる
- 速攻で大量虐殺を行なう
- もっと速攻で相手の重要な魔法の妨害を行なう
- 重要なスロットへの攻撃を連続的に行なうことでロックする
- 便利な魔法を使い捨てにせずに再利用できる魔法を準備する
あたりがあった。実際はこの5つの組み合わせになるんじゃないかなーと思う。個人的には引数に与えたスロットを瞬殺しつつゾンビ化させる(ことによって相手の構成をキャンセルさせる)ロックが強いんじゃないかなーとは思ってたけど、そこまでちゃんと実装できなかった。
そのへんを試す時間がなかったのは、比較的簡単にできる速攻虐殺を早めに実装したんで、それをベースに色々足していった上に、 S とか K とか書きやすいフレームワークがロクになかったので、大幅な方針転換がすごくやりにくかったというのがあると思う。
で、現実的に私の AI がやることは…
- いきなりスロット0,1のライフを使って、相手のスロット 255 を殺す。これに2つ意味があって
- 今後相手スロット255はゾンビとして活用させてもらう
- 自分のスロット0,1あたりのHPちょっと減らしとくと相手が 8192 の大量虐殺を固定で最初に撃つ構成になってる場合(この戦術を取る AI はかなり多いと予想された)、かなり有利
- 相手の大量虐殺が先頭から固定の場合は完全に無効化できる
- 相手の大量虐殺が殺せるやつを優先する場合は、重要なスロットである 0,1 を延命できる
- 相手の大量虐殺がダメージ量を適切に調整する場合でも、 0,1 だけしか死なない
- その相手 255 にゾンビを使って相手にとって重要そうなスロットを殺す、で、即座にそのスロットにゾンビを撃って相手に魔法を忘れてもらう
- ここまでが92ターン弱でできるので、相手の大量虐殺は間に合わない、はず
- で、おもむろに大量虐殺を撃ちはじめる
- ただこの実装がいい加減でダメージが 8192 固定で相手の重要スロットを殺せないのだった…
- 大量虐殺が効かなくなったらスロット0を回復させて一匹ずつ殺していくモードに
- これもひどい話で防御重視な相手は全くトドメ刺せないのであった…
- 重要なスロットが死んだら、今の計画を中断して生き返らせる
- dec 連打によるロックは検知しているので、何回か dec で死んだら S(revive)(inc) みたいなのを再帰的にかけることによって急に回復させる
- ちなみに回復ロジックは任意のスロットを使って撃つことができる
- なかなか決着つかないようだったら、おもむろに大量虐殺をあまり狙われなさそうなスロットを使って撃つ
- 最後の4000ターンは死んだスロットを生き返らせるのに専念
- 私の AI はトドメが苦手だったのでこんなしょうもないものでだいぶ強くなった…
今にして思うとまずやるべきだったのは大量虐殺のダメージ量調整ですね…なんでこれやってないんだろう。これやるだけで結構強くなるんじゃないか…? (追記: ホラえらい強くなったよ… http://www.paraiso-lang.org/Walpurgisnacht/store/scoreboard.html )
あとそういえば、今回の ICFPC のサイトには "WHAT'S IN AN IMAGE?" とかいうメッセージとともに画像が置いてあって、これはなんか隠してあるのかなーという雰囲気になってました。これは実は png+jar になってて、実行するとヒント画像が出てくるようになってて、それで Lambda: the Gathering という名前はわかって、アリ対戦の時の ICFPC を主催した人と同じ人であることも考えると、まず間違いなく対戦ものだろうなーということは予想できる感じになってました。他にも情報隠れてるんじゃ…とか思って png と jar 以外のデータ入ってないか…とか探したけど無駄だったのは悲しかった。
あと、この jar は二度実行すると戻るようになっていて、挙動は Quine ぽいんですがファイルを読んでいて、それなのに Q.class とかいう名前がついていてこんなものでは Quine ではないと思ったのですが、後で聞くとこれを Quine と呼んではいけないという議論はあったけど Q.class って名前は残ってしまったとかなんとか。
私は勝手に深読みしてこれはむしろ Y コンビネータ無くても再帰できますよ、ってヒントなんじゃないかとかも思ったりもしました。まあ普通にそんな意図はなかったみたいですが。というのは正しい Quine とファイル読む「Quine」の関係って、 Y コンビネータで再帰するのと、名前つけて再帰するのの関係に似てるんですよね。
