Lambda: the Gathering をやった
今年もICFP Programming Contestに参加していた。今回は職場のチームで出てみた。といっても開催日時が悪かったせいでたった二人のチームになってしまったが。相棒のpacakはHaskellerで、本業はISPの経営者らしい。開始前、サーバが欲しいなあと呟いたら、メモリ32Gバイト搭載のマシンをあっさり用意してくれた。結局Gitサーバにしか使わなかったが。チーム名は乱数でyazDual5osになった。
今年の問題はあるカードゲーム*1をプレイするプログラムの作成。面白そうなゲームなのでテンションが上がる。開始+1:00で入出力ライブラリが完成。まともなプレーヤは内部でシミュレーションをするのが必須*2だということが分かったので、シミュレータライブラリを書く。+7:00で一応の完成。+8:00に最初のプレーヤ"nop"(シミュレーションだけして何もしない)を練習サーバに登録。
シミュレータを書いているうちにゲームの仕組みがなんとなく見えてくる。勝利のためには敵のスロットを殺すことが必要で、それにはダメージを与えないといけない。ダメージソースになり得るのは「dec」「attack」「zombie」。手始めに最も扱いが簡単なdecを使ってみることにした。decの与えるダメージは1で、2ターンに一回撃ったとしてもスロット一個(体力1万)を殺すのに2万ターンが必要。ゲームが10万ターンで終了することを考えると遅すぎると思ったので、無限ループを作ることにした。素材はwebで見つけた"S I I (S I I)"。問題文に無限ループのサンプルがあることには気づいていなかった。
任意の関数適用「a b」を作る直接の方法がないことに気づいて絶望しかけるが、すぐに「a (x y)」(ただしxとyはカード)を「S (K a) x y」で表現できることに気づいた。任意の「a b」は、bをスロット0に入れた上で「S (K a) get zero」と書ける。これを自動化して、木構造を入力すると命令列を出力する関数を書く。+12:00あたりでプレーヤ"fill"を提出。無限ループを利用して敵のスロット#255にdecを連発し、このスロットを殺したら次は#254、という単純な動作の上、効率が非常に悪く、8ターンあたり83ダメージしか与えられなかった。さらに練習サーバ上では頻繁にinvalid outputで負けていた。+12:00。
この時点で、スロット#0の重要性を認識する。それどころか過大評価していて、#0が使えないと上述の関数適用ができないと思い込んでいた。(実際には多少のオーバーヘッドを我慢すれば可能)。さらに整数255を作るのに大変なターン数(128を用意してから127回succ)が掛かると誤解していて、最速で敵#0を殺すのはzombie戦術だと考えた。ここで寝る。
"zombie"を提出。基本は"fill"と同じで、#255を殺してから#254に移る前に#255にzombieを仕掛けてhelp 0 0 8192を撃つだけ。やはりinvalid outputでの負けが多い。+22:00ごろ。
zombie戦術の実装中にシミュレータのバグを複数見つけたので、テストすることに。ランダムな式を構築するプレーヤ同士を、公式シミュレータと自作シミュレータでそれぞれ対戦させてゲーム内容をdiffで比較。似たようなことはマーガレットのシミュレータを書いたときにもやったのであっさりできた。見つけたバグを取る。+23:00。
環境を知るために"scout"を提出。普段は何もせず、自分の#0が殺された瞬間にinvalid outputで自殺するだけのプログラム。これがチーム「Wile E.」に45ターンで殺されて衝撃を受ける。やはりdecでは遅すぎでattackを使うべきだということを学ぶ。+24:00。
pacakにinvalid outputについて相談したところ、バッファリングではないかと言われる。標準入出力をNoBufferingにした修正"zombie"は初めての「ちゃんと戦えるプレーヤ」になった。成績は17勝9敗。+26:00。
ここまでのプレーヤは全て、事前に計算された手の列を機械的になぞるだけだったが、reviveを入れるにはメインロジックを一旦中断→revive→復帰、のような動作が必要だった。心機一転して新しいフレームワークを書くことにする。各戦術はMakefileのように依存関係を持ち、準備が整っていれば実行、そうでなければ準備をしなければならない。依存関係を毎ターン再計算することで、理論的には、敵の攻撃でスロット内容が破壊されても復帰できることになる。これをStateモナドをベースにしたTaskモナドとして実装した。しかしTaskモナド上で任意の関数式を効率良く用意するロジック(prepare関数と呼んだ)を書くのには相当苦労して、+32:00で"zombie"をTaskモナドに移植した"zombie1"を提出。
reviveより効率の悪い攻めは撃つだけ不利なので、なるべく高速な攻撃を探したところ、k回help→一回attackを対象をずらしながらループするのを思い付いた。1ターンに30スロットを殺せ、再充填16ターンと試算した。これは当時の水準からすると圧倒的な火力であった。しかしこれには引数を持つ再帰関数の実装が必要。値呼びで使えるSKI上の不動点演算子をひたすらググったりしたが、LtGで実装するにはどれもあまりに複雑だった。途方に暮れていた時、昔見たUnlambdaの公式サイトにループの作り方が載っていたのを突然思い出したので参照してみると、不動点演算子を使わずにself引数を明示的に与えるような実装が紹介してあった*3。これでattack戦術が現実味を帯びてきた。なお、getを使って再帰関数を効率的に表現できることが問題文に書いてあったことに気付いたのはコンテスト終了後。
実装の手が重くなってきたので戦略について夢想する。効率の悪い攻めはreviveされて終わりだが、逆に相手が効率の悪い攻めをしてきたらreviveをしないといけない。他にも自己複製するゾンビを使って毎ターン広範囲reviveやら、指数関数的な大きさの式を構築して敵をメモリ不足orタイムアウトさせる戦術を考えた。就寝。
+48:00ごろ、プレーヤ"attack"のメインロジックが完成した。n=32768のhelpを6回行った後にn=16834のattackで攻撃する。これを反復することで1ターンに最大16スロットを殺せる。詠唱時間は約230ターン。"nop"と対戦すれば600ターンほどで勝利できるはずだった。
しかし、Taskモナド上の未来予測では正しく動作しているものの、実戦のように毎回再計算をさせると無限ループに入って異常動作することが分かる。ここから一日がデバッグに費やされた。prepareのバグを修正し、それによって見つけたバグを修正し、たくさんのアドホックな変更のせいでメンテ不能になったprepareを捨てて「高速堅牢」を目指すqprepareを実装した。qprepareも当然のようにバグっていて、もっと悪いことに小さな設計ミスと大きな設計ミスが一つずつあった。相当やる気を失ったが頑張ってさらにアドホックな回避策(Taskモナドの意味をねじまげる)を実装し、+61:00でついに"attack"を提出。
revive未実装にしては"attack"はそこそこ強かった(9勝3敗)が、対戦結果を見ると単純に速度の差で圧倒されているケースが多いように思った。なんとか詠唱時間を短縮できないか考えたところ、任意の二分木はpushとapplyの列で表現できることに思い当たり、スタックを内臓するオートマトンを作ろうと思い立つ。Haskell風に書くと以下のような感じで、任意のapplyを2ターンで実行できるのが売り。
data Command = Push | Apply type Machine = Command -> Machine machine :: [Tree] -> Machine machine stack Push = machine (get 0 : stack) machine (x:y:stack) Apply = machine (apply x y : stack)
この定義は大きすぎて、これ自体の詠唱に時間が掛かりすぎることがすぐに分かった。しかし魔法のオートマトンを自作するという発想がとても気に入ったので、これの簡略版を実装したが、結局ほとんど圧縮効果がなく、使いものにはならなかった。
時間切れが迫っていたので、確実に効果があると思われるreviveの実装に取りかかる。深夜3時ごろの回らない頭でゴミ捨て場のようなコードを書いた。なんとか間に合ったので、最終プレーヤ"attack.revive.opt"を公式に提出した。最終的に、"nop"に対して最初のスロットを殺すのに191ターン、勝利に541ターンを要した。おそらく上位30チームでは"nop"を200〜300ターンで殺せるプレーヤが主流なので、"attack.revive.opt"は全く歯が立っていないと思われる。
反省点はたくさんあるが、重大なのは、
- デバッグに時間を取られすぎ。しかしどうしたら改善できるか良く分からん。
- 問題文付属のサンプルをちゃんと理解すべきだった。特にgetを介した再帰を思い付かなかったのは痛い。
- チームワークの欠如。当初は、「最悪、互いに独立にプレーヤを実装して、勝った方を提出すれば良い」と考えていたが、その域にすら達しなかった。提出したコードは100%私が書いたもの。
今年の問題はすごく良かったと思う。実際、参加中は異様に楽しかった(カフェイン摂取の影響かもしれないが)。個人的な好みにも合致していた。それだけに優勝争いにすら加われなかったのは残念。
