ICFP Programming Contest 2011

http://www.icfpcontest.org/

今年は会社の同僚と6人で、チーム名 widecat で参加しました。

成績は…よくわかりません。けっこう相性で勝敗が決まるので。とりあえず上位30チームの決勝には残れてるんじゃないかと思います。

AIの戦略

開始直後はまず、復活用の魔法を準備します。

  • 1 ターンで発動し、スロット 0〜82 を revive、さらに inc する
  • 1 ターンで発動し、スロット 192〜255 を revive、さらに inc する

この2種類を用意し、さらにそれぞれのコピーを作っておきます。使うときはコピーの方を使い、オリジナルから複製し直すことで作り直しの手間を少なくしています。

inc で体力を 2 まで回復させているのは、生き返らせたあとに dec ですぐまた殺されるのを防ぐためです。まあ 2 回 dec されるとアウトなんですが。

これを作り終わるまで 75 ターン。その頃には 255 が殺されていることも多いですが、敵のゾンビの初撃には十分間に合います。

次に attack 0 0 8192, attack 1 0 8192 で相手の 255 を殺します。もちろんゾンビを送り込むためです。

その後ゾンビを作ります。こんなコード。

f = '(\i. help i i 8192)'                # f i = help i i 8192
g = '(S %s succ)' % f                    # g n = f n; return n+1
twice = '(S (S (K S) K) I)'              # twice f x = f (f x)
x256 = '(S (S I I) (S I I) %s)' % twice  # x256 f x = f^256 x
gx256 = '(%s %s)' % (x256, g)            # gx256 x = g^256 x
make_zombie = "\start. zombie 0 (S (K %s) (K start))" % gx256

これで make_zombie に数値を適用すると、その番号のスロットから順番に help で殺していく (1 回に 82 体ほど殺せる) ゾンビを敵の 255 番スロットに送り込みます。

このゾンビコードの構築には 110 ターンほどかかります。ちょっと遅いですね。
ゾンビの挙動は自分のスロットに入れておいて、copy で持ってくるというのが定石だったみたいですが、うちのチームは最後まで気づきませんでした。

何もしない敵を倒すには結局 292 ターンほどかかっていました。

やったこと

主に式からコマンド列へのコンパイラを書いてました。
あとチーム内で SKI 経験者(って何だ)は自分だけだったので、S (K f) (K x) で遅延できるよーとかイディオム的なのを紹介したり。
他には AI の回復系の処理を作ったり、他のメンバーが書いた式を軽くゴルフして縮めたりしてました。

感想

チーム参加ってどんな感じだろうと思って初チーム参加だったわけですが、良い点も悪い点も色々見えて興味深かったです。

まず戦略考えるのは複数人のほうが絶対いいですね。自分じゃ思いつかないようなアイデアもいくつかありました。

それと、下回りを作ってくれる人がいると楽だなーと思いました。今回はシミュレーターとか各種ツールをかなりしっかりと作ってくれていて、快適に作業できました。

逆に個人参加のほうが良かった点は、当たり前ですが一人当たりのパフォーマンスは個人参加のときのほうが高かったなあと。昼も夜もなく、コーディングしては寝て、目が覚めたらまたコーディング…という濃密な 72 時間が ICFPC の醍醐味だと思うのですが、今回は昼間はチームで集まって作業、夜は自宅で寝るというスタイルだったのでそんな感じではなかったです。合宿形式だったらまた違ったかもしれませんが。

あとチームで分業するにはあらかじめタスクを分割しておかないといけないので「作りながら考える」方式が使いにくいなあと思いました。一人のほうが早く作り始められるので、実は lightning division は一人でも勝ち目があるのかも。

あとこれは今回の反省点ですが、ICFPC 初参加のメンバーが何人かいたんですが、その人達が面白さを感じられるようもっと配慮してあげられたら良かったなと。

ともあれ、今回の問題は最高に良く出来てて楽しかったです。ジャッジの皆さん、参加者の皆さんお疲れさまでした。また来年お会いしましょう!