ICFP Programming Contest 2015

今年もICFP Programming Contestに参加していた。今回は「Japanese Curry.」というチームで、メンバーはA氏とJ氏と私の三人だった。

今回の問題はテトリス風のゲームをプレイするAIを作るというもの。以下のような特徴がある。

• ゲーム盤が六角形の敷き詰めで構成されている。
• 盤の大きさや落ちてくるピースの形が一つに決まっておらず、パラメタになっている。これらは問題ごとに指定される。
• 次にどのピースがやってくるかを選ぶ疑似乱数が決まっているので、ゲーム終了まで先読みできる。決められた数のピースを消化するか、死ぬと終了。
• AIからゲームへの入力をコマンド列として与えるのだが、それを文字列として解釈したときに特定の句(phrases of power。コトダマ?)が含まれていると回数に応じて点が得られる。これは主に(全部?)ラヴクラフトの作品からの引用になっているが、問題文中には一つしか明記されておらず、主催者のヒントを頼りに探すことになる。

例年に比べると単純な問題だったのでモチベーションを維持できるか心配だったが、終わってみるといろいろ工夫を要求されて楽しかった。クトゥルフ要素も良いフレーバーになっていた。

やったことは以下。

+0:00 問題文を読む。テトリスだ。

+1:00 入力パーサを書く。といってもJSONなのでaeson一発。ここで既存フォーマットを使うのは核心部分以外に費やされる実装労力を極力削減しようとしているようで、去年までの問題の傾向との違いを感じる。就寝。

+11:00 起きたらA氏がUnicode文字の六角形⬢⬡とANSIカラーシーケンスを組み合わせた美しい盤面表示関数を完成させていた。これは単なる文字列なのでトレース出力などに埋め込むことができ、最後までデバッグに貢献した。続いてA氏は斜交座標を併用するべきだと主張し、J氏とともに実装を開始した(これは終わってみるとまったくその通りで、問題文にある座標系だけを使っていたら手間が爆発してしまう)。あまりやることがないので、提出用コードのコマンドライン解析部分を書き、ひたすらピースを下に落とし続ける馬鹿AIを書いて提出してみる。ゲームが終了するのと同時にコマンド列も終了していなければならないらしく、この方法では1点も取れないことが分かる。

+12:00 このあたりでJ氏が離脱。以降二人チームになる。方針を話し合った結果、各ピースについて置ける場所を全列挙し、置き方についてはヒューリスティクス系の探索で選ぶことになった。まず可能な置き方を列挙する関数を書く。深さ優先探索をするだけだったが、ピボットの座標が負になれるなどややこしい要素が多くて時間がかかる。終了状態から初期値へと逆方向に探索すれば、盤面がほぼ空の状態だと主要部分の計算量をO(width * height)からO(width + height)に落とせそうなことに実装後に気付いたが、これを試す機会はなかった。この間にA氏はゲームルールを実装し、最初の馬鹿AIを改良して0点でない点が取れるAIを書いていた。その後やることがなくなったとのことなのでペアプログラミングに移行。

+13:30 回転を使わない置き方については全列挙ができるようになる。ここでA氏は回転の実装を続け、私はビームサーチの実装に取りかかる。

+15:30 ビームサーチの実装が終わり(ただしバグっていて貪欲法の劣化版になっていた)、解を出力できるようになる。しかし、出力を見ても何をやっているか分からないのでステップ実行のできるシミュレータを書く。

+16:30 ルール部分のバグを潰しつつシミュレータを書き終わる。

+18:00 評価関数として、現在のスコア、「置けるピースをなるべく下に置くことを好む」の二つを実装する。これにより、問題0を死なずに最後まで解けるAIが完成する。しかし非常に遅いので時間を取って最適化することになった。

+19:30 いくつかボトルネックを潰すことに成功する。ビームサーチの実装が壊れていたことに気付いて直す。まだコードが遅いので、高速化の方法を考えた結果、盤面の表現を、疎な永続ビット集合であるIntSetから密なビットマップに変更することに決める。その間、A氏は手当り次第に評価関数用の特徴量を実装することになった。

+23:00 A氏が穴の数を数える特徴量を実装した。私のほうはビットマップの実装でバグを量産して一向に実装が進まないので、あきらめてLightning Division用の解を生成しはじめる。この時点ではじめて問題0以外の解を目視で確認する。AIが遅いので、問題によってはビーム幅を1に絞ったり、穴の数を数える特徴量を外したりした。

+24:00 Lightning Division終了。どうやら「穴の数」に重きをおきすぎていることが判明する。穴がなくても、ブロックの積み方が入り組んだ形になるとどうしようもなくなるケースを確認する。就寝。

+31:00 gitのコミットログによると、このころA氏が「表面積」「空きマスの上にあるブロックの数」「上端から始めて、下降と左右移動だけで到達できるマスの数」の三つの特徴量を実装したらしい。

+33:00 引き続き苦しみながらビットマップを実装する。盤面を偶数段と奇数段に分割したあと、それぞれを8x8の小ブロックに分割し、各ブロックを一個の64ビット整数で表現するという方針だったが、実装がひたすら苦しかった。1次元の可変長ビットベクトルを介して実装する方が良かったのだろうか。

+40:00 ついにビットマップの実装が終わり、表面積をビット演算で計算できるようになるが、高速化は2倍にも満たなかった。A氏はビームサーチを見限って新しい探索技法を完成させ、「遺伝的探索」と名付けていた。ビームサーチが単一の評価関数を使うのに対し、「遺伝的探索」は特徴量に対して数十個の異なる重み付けを持ち、それぞれの重みに従って複数の最良候補を選ぶことで解の多様性を確保するというアイディアらしい。探索終了後には遺伝的アルゴリズムに基いて新しい重み付けの集合が提案される。説明を聞いても半信半疑だったが、ビームサーチよりも結果が良いようなので以降これを使うことにする。

+42:30 ピースの置き方を一部重複して生成していた問題を修正したところ、AIが2倍早くなる。

+44:00 表面積の計算がまだ重いので、盤面更新にあわせて差分を計算できるようにする。

+46:00 AIの動きを見ると、必要もないのに穴を塞ぐケースが多いようだった。穴の数を数える特徴量があれば防げそうだが、計算があまりに重いので無効になっていた。何か方法はないか首をひねっていると、A氏が突然、オイラー標数を使えないかと言いだす。聞いてみると、

• 連結な平面グラフのオイラー標数(頂点数-辺数+面数)は2である
• なので、盤面のうち空白の頂点と、それらの隣接関係からなるグラフのオイラー標数を数えれば連結成分の数が分かる
• 頂点数と辺数はビット演算で数えられる(差分計算もできる)。面数のうち単位三角形の数はやはりビット演算や差分計算で数えられる。単位三角形でないものの数は、孤立したブロックの集合(島と呼ぶ)の数に等しい
• 島は永続Union-findで管理すれば差分計算で数が求まる！

というアイディアだった。発想に驚嘆しつつ早速実装にとりかかる

+49:00 ひととおり実装したもののUnion-findのバグがとれない。A氏は遺伝的アルゴリズムを自動化しつつ重み行列の更新を続けており、得点がかなり向上していた。明示的に教えていないにもかかわらずAIが複数行の同時消しを行なえるようになったのに驚く。就寝。

+57:00 ついにオイラー標数を使った穴の数の計算が動いたので、満を持してphrases of powerを埋め込むコードを書き始める。方針としては、遺伝的探索で発見したピースの置き場所は変えないことにし、各ピースを置く手順を最適化することにする。各段で右か左の多くとも一方にしか動かない、という制約を入れると、phrases of powerを(場合によっては複数並列で)認識して得点を出力する有限状態機械を考えることで、動的計画法によって最適手順が計算できるので、これを実装することにした。この方法だとphrase of powerを一種類使うたびにもらえる追加点を最適化できないが、これをうまく扱うのは後まわしにすることにした。これは結局最後まで実装することはなかった。

+69:00 ほとんど丸一日をかけた動的計画法の実装が終わる。例によって遅いコードで、"ei!"という三文字のphrase of powerだけを認識する状態でも問題0に対して数秒必要だった。高速化を試みたが、大したことはできなかった。

+70:00 時間管理を実装する。AIのパラメタ1から始めて倍々にし、時間が切れた時点で最善のものを出力する方法を実装した。具体的には、遺伝的探索で使う重み付けの数と、動的計画法で考慮するphrases of powerの長さの合計をパラメタで制御できるようにした。この間A氏はphrases of powerを探していたが、予選問題のマップに埋め込まれていた三つと、長大すぎて計算コストの重い51文字のもの以外は発見できずにいた。

+71:00 A氏が提出用の解を生成している間、phrases of powerを求めてラヴクラフトの引用集、Wikipediaのクトゥルフ関係のページやThe H.P. Lovecraft Wikiをさまよった。結局発見できたphraseは一個だけだった。

+72:00 終了。提出が間に合わなかった問題がいくつかあり、予選順位は66位だった。問題17と問題19では一位だったが、これについては特別な何かを実装したわけではないので、運が良かっただけなのではないかと思う。

感想

速いコードをバグらせずに書けるようになるべきだと思った。