ICFPC2011 参加記録

ICFPコンテスト2011に参加してきました。

近年は予定がかぶったりでまともに参加できていませんでしたが、今回は久々にちゃんと参加できました。実は遠隔でなく泊まり込みで参加するのは初めての体験です。

ひとまず実装や作戦の詳細に関してはチームのページ https://github.com/tanakh/ICFP2011 も参照していただくことにして、コンテスト終了後に使い方を覚えたgit logから私の時系列を思い出せる限り復元してみます。

  • -3 days 計算機パワーが必要な問題を想定し、haskellの並列・分散計算の勉強を始める
    • parは過去の遺物であると聞いて衝撃
    • forkIOでグリーンスレッドを立てまくるだけでマルチコアプログラムが書ける衝撃
    • msgpack-rpcを使って型つきrpcプロトコルがいとも簡単に書ける衝撃
    • STMはメモリと言うからIntくらいしか突っ込めないのかと思い込んでいたが文字通り任意の型が突っ込める衝撃
    • だもんでとにかくSTMを使えば使い回しとか共有とか並列プログラムが思い通りに書けちゃう衝撃
  • -40:00 自前で可視化が必要な問題を想定し、openframeworksというのでビジュアライザを準備し始める
  • 00:00 コンテスト開始
  • 02:18 IOモナドベースのAI開発用DSLを作る
  • 02:52 とりあえず何もしないAIを記述

昼飯時で最初の作戦会議、僕と田中さんがシミュレータ、桜庭さんと林崎さんがAI作りで分業しようということに

  • 05:28 田中さんのシミュレータを検証すべくランダムに手を打つAIを記述
  • 05:41 ２つのシミュレータを比較するプログラムを書く

この頃の主な仕事はジャッジと田中さんのシミュレータを比較して不一致報告

  • 08:40 AI開発班によりゾンビの使い方が解明されはじめる。ゾンビなのでSayakaと命名。
  • 09:30 おかげでシミュレータのゾンビ周りの不一致が見え始める
  • 10:00 ゾンビを起動させる部分は面倒くさいから丸ごと未実装だと言うので無いと困るといったらそんなの10分で書けると豪語するからストップウォッチのスイッチを入れる
  • 10:10 本当に10分55秒で実装される衝撃

それからもしばらくシミュレーターの不一致を洗い出す仕事が続く

  • 15:00 検証用に、一定確率でランダムな挙動をするターンが挟まるSayakaのバリアントを追加
  • 17:10 桜庭さんも、攻撃対象や使用するレジスタなどをランダムに変えるバリアントを作ってくれる

しばらくシミュレーター比較器を改善したり比較したりする作業が続く。
シミュレータのバグとシミュレータ比較器のバグを分離するのがどうしても難しいので、シミュレータを信じて、AIライブラリのモナド化を並行してやってもらうことに

  • 26:00 比較器に「１戦目の棋譜を記録し」「２戦目ではそれを再現するダミーAIを使う」機能が搭載。乱数を使うAIでも、seedを保存したりすることなく比較作業に使えるように
  • 27:00 田中さんによるLTGモナドが完成
  • 27:40 さっそくSitting DuckやRandomなどシンプルなAIをLTGモナド化
  • 28:00 SayakaのLTGモナドへの移植を開始。と思ったらなんとIOをLTGに置換しただけで何事もなく動く衝撃。

思えば最初にIOベースのライブラリを作っておいて本当によかった

  • 29:00 LTGモナドで書かれた戦略を集めたライブラリを作り始める。名前はSoulGems
  • 31:00 チーム内リーグ戦システムを作り始める
  • 34:00 日台同時放送開始
  • 36:00 AI開発班により、ゾンビの中でhelp i i爆撃を行うという最後まで主力となるAIが投稿される。林崎さんによりKyoukoと命名。
  • 37:00 本格的に並列コンテストを開催しはじめる
  • 37:20 林崎さんがKyoukoの最適化に着手

この晩から、林崎さんが訳がわからない勢いでKyoukoを最適化していくのを見て桜庭さんがポカーンとしながらも解説してくれるその説明も付いていけない理解できないのでポカーンとしながらも仲間の健闘を祈る作業が始まる。主な仕事は次々に出てくるモデルの強さとバグをリーグ戦で検証すること

  • 39:00 それでもKyoukoの読める部分を変えてみたバリアントをいろいろ作る。あんまり強くない・・・
  • 40:00 日台同時放送終了
  • 45:00 攻撃を受けて復帰モードに入った際、全スロットをreviveしようとしていたのを、重要なスロットのみreviveする変更を提案。首の皮が繋がればいいということでMamisanと命名。しかしリーグ戦の結果は「試合が終了しない」という謎のもの。

実はこのころのAIには実はまだ無限ループに陥るパスが残っていたので、リーグサーバが悪いのかAIが悪いのかAIに施した改良が悪いのかはっきりせず辛かった。

  • 47:00 19日の朝、みんなが寝ているうちに目がさめたので、LTGモナドに敵味方の過去の行動の統計を収集しAIに提供する機能をつける

まあ、試合中にこれを有効利用するまでには至りませんでしたが

  • 51:00 この日もKyoukoはどんどん速くなる
  • 53:30 ゾンビを埋め込むためにAttackを撃つための犠牲を先頭2スロットではなく少し隙間をあけた２スロットにしておく修正を提案。Help Bombへの耐性が上がることを発見。

２つのふくらみがないことにより鉄壁を誇ることからHomuと命名

  • 56:06 Kyoukoに潜んでいたバグがついに取れる
  • 58:00 終盤戦、バイタルが1〜2のスロットがほとんどになるので、単にループでdecを撃つルーチンを桜庭さんに作ってもらう。MadanNoButouと命名。しかし強くならなかったので棄却。

コンテスト後、僕が組み込む時に「ループを構築する」ルーチンを忘れて「準備されているはずのループを撃つ」ルーチンだけ組み込んでいたことが原因と判明。痛恨のミス。

  • 59:00 偶数番スロットをひたすらreviveするだけのAIを作成。helpゾンビでは焼き切れない。代わりはいくらでもあることからKyubeyと命名。
  • 62:30 Kyoukoのバグが取れた版にMamisanを再び組み込む。守る範囲を変えたバリアントを多数作ってリーグ戦により強さを比較。QB-(n)による蠱毒。「生存スロットが歯抜けになる順にrevive(Kyubey式)」「10スロット(最低限)だけ守る」が最善ということに。
  • 63:30 目覚ましい成長を遂げたKyoukoに、終盤のヨセ、改良されたゾンビ切り口作成ルーチン、QB-10を組み込んだY2CAtkQbを出荷。事実上の最終版となる。

10時間あまり時間を残して余裕の雰囲気、あるいはこれ以上改善手の見つからない手詰まり感が漂う。

  • 63:00 AI開発班、仮想敵を求めてAttackを連打するAIを作り始める。Yumaと命名。

残念ながらバグが取りきれず、コンテスト中の実戦投入には至りませんでした。

  • 仮眠
  • 68:00 READMEを書く
  • 仮眠
  • 72:00 拍手に目覚めるとコンテストは終わっていた。

命令列の最適化なら任せろとばかりAIを際限なく速くしていく林崎さん、使いやすくまた信頼に足るDSLライブラリを短時間で作り出す田中さん、困難なバグ取りや実装でも合理的に必要となれば根気よく作っていく桜庭さんの姿に感銘を受けました。僕としては一人ではICFPCに三日でコードを投げることすら覚束ないような実力ですがこのようなチームに招いてもらって光栄です。４人目として入ることで１人増えた以上の効果をもたらす、ような動きができていたとしたら、それはとっても嬉しいな、と思います。

何と言うか趣味の一致したチームだったのと、Haskellを垂直軸として水平分業できたのが幸いし、充実した７２時間となりました。あと僕の知っている限りでは今年の問題はICFPC史上最高の傑作です。チームの皆様、参加者の皆様、ジャッジの皆様、本当にありがとうございました。