ICFP Programming Contest 2011

去年に続いて今年ものとがわさんパンピーやった…

問題はここ.Lambda: The Gathering というまったくあたらしいオリジナルカードゲームの強いデュエリストを作るというもの.Magic: the Gathering と名前が似てるのは気のせいだ.カードは丁寧にも挿絵付きというプログラム同士ではなく人間同士の対戦まで意識した豪華仕様.Magic: the Gathering とカードデザインが似てるのは気のせいだ.テスト用の対戦サーバまで用意されて他チームとの対戦もできるしコンテスト中にランキングも作られた.Magic: the Gathering とログインページの背景が似てるのは気のせいだ.

要約するとSKIのコンビネータと,zero,succ,dblの自然数演算,inc,dec,attack,helpの攻撃・回復演算,put,get,copyの補助演算,revive,zombieの蘇生演算で相手のスロットを先に絶滅させるターン制ゲーム.本当によくできてるいいゲームだ.まるでGrassでプログラミングしているかのようなプレイ感のカードゲームとでも言ったら伝わるだろうか?

最初,うわーこれ戦略考えつかないわーとか思って,シミュレータ書かずに敵の動作一切見ず可能な限り速攻で焼く盲目バーンAIを組もうと方針を決める.ひとりチームだしシミュレータ書くのめんどうだったしね.ま,どうせ自分の残念なコーディングスピードだと残念なことにもなりそうだったから割り切りで.そういえばラムダ式をSKIに変換する作業なんて久々でなつかしかった.

基本戦略としては,Iを食わせた時に評価されてIに戻る演算をたくさん合成しておき,1ターンに発生させる副作用(攻撃・回復・蘇生など)の量を増やしておくことで,準備完了後絨毯爆撃というカンジ.
最終的には,

  1. スーサイドバーン系AIに速攻焼かれないように若い番号のコマだけ後ろのほうのコマから少しhelp
  2. 複製演算として λ f x. f (f x) を作っておく
  3. 回復演算に (\i -> help 0 0 (K 3072 i)) を作っておく
  4. 回復演算を複製で2倍ずついっぱい増やして合成
  5. 攻撃演算に (\i -> attack 0 ("この演算を評価したときの対象指定スロット") (K 12288 i)) を作っておく
  6. 回復演算と攻撃演算を関数合成 (攻撃 . 回復)
  7. 複製でさらに倍 (攻撃 . 回復) . (攻撃 . 回復)
  8. 蘇生演算で (\i -> revive (K "この演算を評価したときの対象指定スロット" i)) を作っておく
  9. fを合成する (攻撃 . 回復) . (攻撃 . 回復) . (蘇生)
  10. 0番スロットに"2 0 I"を食わせた後f I=>Iを実行してスロットを元に戻す演算 S f (S (K get) (K 0))を作る.
  11. 対象指定スロットを0初期化
  12. 対象指定スロットをインクリメントしながら0番スロットを"2 0 I"で評価 * 256回

とまあ,頭悪いカンジで木偶AI相手に900ターン前後で全滅させる程度にしかならなかった.回復量を低めにとってるのは,もし初期化中に0番がそこそこ削られてしまうと自己再生働かないかなーと思ったからで,その分ブースト回数を重ねてカバー.

しっかし上位陣さらに速くてこちらの演算構成中に全滅させられてしまったり300ターン以内とか意味わかんない.zombieの使い方は結局よくわからなかった.copyによる対象指定との組み合わせでhelpでも送り込んでるのかしら?それならひとつ殺してzombie送って自分のターンでは対象指定をインクリメントするだけでzombieがバイオハザードしてくれるし.たぶんこういうのをシミュレータ付きAIにて戦死者の状況確認しながら加速度的にzombie増やすとああいう速度になる…んだろうか.

流石に色々なアイデアとか戦略出したりそれらを実装したりする必要が高く,デュエルのチーム内ランニングマシンとか物理的リソースも考えると,ICFPCソロプレイは正直キッツイものがあるね.