22:15 11/06/27
ICFPC 2011
ここ 8 年くらいほぼ毎年参加していた ICFP Programming Contest ですが、今年は出題者側に回ってみました。 問題の原型決定の議論、画像に変なネタを仕込む、Windows版バイナリのビルドをする、対戦サーバの中身を突貫でどうにかする、 などなどをしていました。 ゲームのバランス調整が非常によくできていたとの評価を頂いているのですが、 肝心のその辺りは、出題チーム内の熟練者達の高度な議論に既についていけなくなっており、 私は全然貢献できていないという…。
詳しいことは 9 月の ICFP で発表があると思いますので、ここでは今年のテーマの紹介だけ。 公式の問題文はこちら です。
一言でいうと、関数を呪文に変えて撃ち合う、プログラミング魔法バトル。
Lambda: the Gathering
L:tG という２人対戦ゲームの AI を作れ、というのが課題です。
カードゲームということになっていますが、カード何回使ってもなくなりませんし、
デッキ選択などもなく常に全種類使えますし、あんまりカードっぽくないかもしれません。
カードには関数が書いてあります。
プレイヤーは、毎ターン交互に、以下のどちらかをします。
- 「自分の場札に手札を適用する」：例えば場に
[3]がある時、 手札[dbl(x)=x*2]を使うと場を[6]に変えられます - 「自分の場札を手札に適用する」：場に
[succ(x)=x+1]が置いてあったら、 手札[0]で、場が[1]に変わります
先手も後手も 0 番から 255 番までの 256 個の場を持っていて、
最初は、
何もしないで引数を返すだけの関数 [I(x)=x] が置いてあります。
場にはそれぞれヒットポイントがあって、初期値10000、最大値65535。
相手のHPを全部ゼロにしたら勝ちです。双方10万ターンプレイして決着が付かなかったら、
生き残ってる場が多い方が勝ち。
inc & dec
攻撃や防御には、HPを変える副作用のあるカードを使います。
[dec(x) = 相手の(255-x)番目の場のHPを1減らして、I を返す][inc(x) = 自分のx番目の場のHPを1増やして、I を返す]
例えば、１ターン目に場の [I] を [0] に適用、
２ターン目に場の [0] に手持ちの [dec] を適用、
とすると、敵の255番目の場に1ダメージ当てられます。これを20000ターン続ければ、
なんと場を一つ撃破！
同じようにして、[succ] を混ぜると、254番目は+30000ターンで、253番は+40000ターンで倒せます。
時間切れの10万ターンまでに、3つも倒せました！あと253個！
programming!
これではラチがあきません。
[0] と [dec] を何回も繰り返す、なんていうループ処理は、
プレイヤーが手で繰り返すのではなく、プログラムにやらせましょう。場に複合的な処理をする関数を作って、
あとで一気に発動！とすると、効果抜群です。関数を組み合わせるためのカードが２種類、用意されています。
[K]function K(x) { return function(y){return x} }[S]function S(x) { return function(y){return function(z){return x(z)(y(z))}} }
関数を返す関数、いわゆる「高階関数」が出てきて怖ろしげですが、大したことはありません。
S は、大雑把にいうと、二つの関数を適当に繋ぐ処理になっているので、たとえば
S(dec)(dec) は、相手の(255-n)番目の場のHPを2減らす関数です。
S(S(dec)(dec))(dec) はHPを3減らす関数、
S(S(S(dec)(dec))(dec))(dec) はHPを4減らす関数…
というわけで、199 ターンかけて dec と S を交互に唱える呪文
S(S(S(S....S(dec)(dec)....)))(dec)
を詠唱すると、1ターン100ダメージの攻撃魔法が完成。メラからメラミを錬成。
この魔法を１番の場に覚えさせておいて、秘技『コードの再利用』
[get(n) = 自分のn番目の場にある関数をコピー]
0番の場で [0][succ][get][0] を連打！4ターン毎に100ダメージの強力なアタックです。
呪文詠唱の200ターンを合わせても、わずか600ターンで敵の255番を沈められます。
公式の問題文の Example にもありますが、無限ループすら簡単に作ることができて、
S(get)(S(dec)(I)) を0番の場に作って [0] を渡すと、
無限に相手の255番に1ダメージを与え続けます。ずっと俺のターン！
…とはいかず、1ターンにつき関数適用は1000回までと制限されています。
この無限ループだと167ダメージ辺りで打ち止めかな。
実は S(get)(S(dec)(I)) を組み上げるのはそこまで簡単ではないのですが、
それにしてもループ無しで S と dec だけで組み上げる100ダメージ呪文よりは速いので、
より高速なアタッカーになるはず。
advanced cards
カードは全15種類あって、活用するのが難しいけれど、使いこなせば強力なカードが幾つも用意されています。 使い道は、あなた次第…。
まとめ
とにかく強力な魔法（関数）を作り上げて、 いかに高速に（少ない枚数のカードで）詠唱するか、 が重要なポイントの一つです。 が、一方で、HPゼロの関数は生き返すまでは使えないため、 広範囲に1万ダメージを与える超強力魔法…などはどうしても時間がかかり、 唱えている間に相手の単体魔法特攻部隊に殺されてしまって使えなくなっちゃったりも。 防御用攻撃用の複数の魔法（関数）を細かく用意しながら、相手の出方次第で臨機応変に、 少しでも隙が見えたら一気に最強魔法を連発！ などなど、色々とやることがあります。
非公式対戦サーバ が立ち上がっていて、 コンテスト終了後も改良されたルーチン達が戦っているようです。 興味を持った方は是非是非参戦してみてください。 ソースコードを見るとザラキを唱えてる人がいたり、"Tiro Finale!" を撃ってる人がいたり、色々賑やかです。
