23:10 15/08/12
ICFP Contest 2015
今年も ICFP Programming Contest に参加していました。
今年はチーム名 "Natsubate!" で @nya3jp, @phoenixstarhiro, @chunjp, @gusmachine, @riesz と私の6人チーム。 チームのレポジトリは https://github.com/nya3jp/icfpc2015。 使用言語は C++ (メインのソルバー) Python (ソルバー群の制御や諸々のスクリプト) JavaScript (可視化や人間用UI)。 公式の スコア表 曰く予選ラウンドの順位は6位とのことです。
今年の問題は、基本的にはテトリスのAIを書けという問題でした。ただし
- １ブロックが正方形ではなく正六角形の六角テトリス。
- ４つ繋がりのミノに留まらず、かなり好き勝手な形の塊が落ちてくる。インベーダー型のとか落ちてきた。
- ユニットを動かしたり回転したりするコマンドの列として特定のパターンを入れるとボーナススコア。 （ユニットの操作中に上上下下左右左右ＢＡって押すと点が入るみたいなイメージ）
- 予選ラウンドの間はどのパターンにボーナスが入るかは明かされない。 公式が漏らすヒントから察したり、 スコアを監視して自分の計算より高かったらボーナス踏んだと判定して察するなどで探す必要あり。
- 本番では全パターンがAIプログラムに入力として渡される。
というもの。六角テトリスというとイメージが湧かないかもしれませんが、要するにこうです。
（画像は Natsubate! チームの、プログラムの動作結果可視化用UI兼、プログラムじゃなくて人間が遊ぶ用UI）
自分としては割と好きなバランスの問題でした。 やらなきゃいけないことがステップバイステップで一列に並んでるんじゃなくて、 列消しゲームとしての側面に注力したい人はそっちができるし、 ボーナスパターン埋め込みゲームとしての側面に注力したい人はそっちを好きなだけやれる。 ボーナスパターンを当ててみろという頓知クイズ要素が楽しみたければそれもできる…けれど、 こういう本質的でない部分は、全部プログラムに与える入力として保証されてるので、 最終決勝ラウンドの勝負には影響しないので無視してもよい。
自分がやったことなど
[1日目21:00～22:00] Googleハングアウトで6人ビデオチャットしながら問題の読み合わせ。 大雑把にタスク決めて役割分担。
[～2日目02:30] とりあえず感じを掴むために人間が遊べるようにするGUI作る係になったので JavaScript で作る。 32bit整数乗算をフルに使う疑似乱数生成器、 数がdoubleしかないJavaScriptで書くのどうやるんだーとチャットに書いたら、 即座にチームメートが16bitに分解して整数でうまく実装してくれる。便利。 六角座標で回転ってどう実装するのが格好いいのだーとチャットに書いたら、 C++で問題シミュレータ書いてた人が既に C++ 版実装できてますよと教えてくれて便利。
[～12:00] 寝たり起きたり @nya3jp 宅に全員集合したり。 チームのスコア状況ダッシュボードを nya さんが作ってくれてたので、 さっきの人力プレイ結果をXHRでsubmitするにはえーとえーとと言いながら Cross-Origin Resource Sharing について付け焼き刃で学んだ。便利。
[～17:00] 昼の会議により、私のゲーム環境と @riesz さん作の問題ビジュアライザを一本化しましょうということになったので、 合流して作業続行。ユニット初期出現位置のバグを直したり、 前いたのと同じ位置に戻ってくる動きはできないというルールを実装したり。
しているうちに、ユニットをボタン押しっぱなしにしてぐるぐる回しているとたまにブロックが欠ける、 というバグが報告されたのでデバッグ。しかしわからない。 完全に同じ引数でも稀に Math.floor の出力が変わるとしか思えない挙動をする…。 仕方ない気にはなるけど今はコンテスト中で時間が惜しいし後で追おう、 と思って Math.floor を使わないで済むようにコードを書き換えて対処。
※ コンテスト終了後に最小再現例を作って調べたら v8のバグを突いていた みたいでした。 浮動小数点数の 0 には±の符号があって、そのマイナスの方のゼロの Math.floor(-0) は扱いがややこしいようで、 大雑把に理解した限りでは、 v8ではJITで型特化などして最適化したコードでも -0 が来たら非最適化版にフォールバックするみたいな処理があって、 そのフォールバックの結果コードを再実行する部分のエスケープ解析にバグがあって、 一部のコードが嘘の最適化でスキップされてしまうっぽい？
[～23:00] テトリス AI を組んでいる人たちを横目に見ながら GUI の微妙な改善などをしていました。 undo は @riesz さんが既に作っていたので redo 機能とか。
[～3日目01:30] この時点ではチームの AI は落としたい所に一直線にユニットを落としに行くだけで、 ボーナスフレーズの埋め込みは全く考えていない状態だったので、 このAIの出力した動かし方は全く変えないで、コマンド文字だけを変えて （※注: 今回のルールでは例えば同じ "左に1マス動かす" コマンドでも6通りの方法が用意されていて、うまく選ばないとボーナス発動できない） 得点を得る用に書き換えるルーチンを実装してみる。 動かし方を変えない範囲だと多分動的計画法で最適解も出せるはずなのだけど、 やってみた限りではほとんど全くボーナスとれなかったので、この方針は根本的にダメだと諦める。
[～12:30] 寝たり起きたり集合したり。
[～16:00] 昼の会議で引き続きパターン埋め込み部門担当係を続けることになったので考える。 落とす場所を決める時に同時に最適にパターンを埋められることを考えつつ解くAI… というのが究極的には最強なのだろうけれど、3日間のコンテストではそこまで行き着ける気がしない。 テトリス部門とパターン埋め部門の分業もしにくい。 落とす場所は完全にテトリス部門の都合の良いように決める、 パターン埋め部門は指定の場所に落とすまでのコマンド列を限界まで書き換えて頑張る、 という分業が妥当であろう。
既存のテトリスAIから、問題指定の出力ではなく「この位置に落とす」という指定の列を受け取る方法も考えられるけど、 徹底して分業するなら、いったん出力されたコマンド列を再ロードして、ここでブロック固定されてるな、 とか判断しながら再構成する方がよい。その辺りを実装。できた。問題はここからどうパターンを埋め込むか。
[～18:00] NP困難な最長経路問題とかを帰着できる気がするので、最適解を求めようとするのはまあ無理だろうな、 と思って適当に実装できそうな方針を考える。
- いまいる位置からパターンを埋め込む動きをしても、その後から頑張れば目的地まで動かせるなら、 貪欲にそのパターンを埋め込んじゃう
- 2通り以上埋め込めるパターンがあるときは、適当なヒューリスティクスでどっちを使うか決める
という貪欲方針。これを実装したコマンド列rewriter AI名付けて「リラックマ」君を実装。 かなり得点稼げていい感じのランクに付けた。
[～24:00] ただし遅い。夕ご飯食べに出かけて帰ってきても最大のマップ(problem 24)の書き換えが終わらないとは…。 @phoenixstarhiro がC++の共通ルーチンのリファクタリング＆高速化するとのことだったので、 ひとまずそれを待つことにして、品質面での改善を色々したりとか、他のAIとの結合してくれる supervisor さんの仕様に合わせるとかをしていました。
[～最終日08:00] 起きた。
[～13:00] 色々高速化したら3秒くらいで24面が終わるようになったので良しとした。 ユニットの始点からの可動範囲と終点への到達可能範囲を計算するBFS二発が実行時間の50%くらいになって、 この部分はあまり改善できる気がしなかったので。
「いまいる位置からパターンを埋め込む動きをしても、その後から頑張れば目的地まで動かせるなら」 の判定を繰り返すので、目的地へのreachabilityを繰り返し繰り返し計算することになるわけですけど、 このgoal-reachabilityはユニットが最上段に出現するたびに一回だけ全体で計算して、 ユニットが後戻りしてはいけないという制約を考えても、 ユニットの現在位置より真に下の位置ではこの reachability は最初の状態から不変ということを利用して計算を端折るのはそれなりに効果があったかも。
[～21:00] 基本方針はあとは変わらずで、 重なりがありうるパターンを重ねるケースを考慮するとか、 複数候補があるときに優先するものの選び方頑張ってみるとか、 どれも候補がないときにどっちに動くか少しは考えてみるとか、 ひどいバグを直すとかでスコアをちょこちょこ改善。終了。
