ICFPC 2012
http://icfpcontest2012.wordpress.com/
年に1度のICFP Contestでした。
O(nwn)というチームで参加していました。自分以外のメンバー：@uwitenpen,@kou_miyam,@hasi_t,@nico_shindannin,@WtbH
ICFPC4回目の参加で初めてチームを作ってみた。
1日目
問題読んで、ああー普通のMarathon系かーと思う。仕様変更だるそう…
そのうちuwiさんがシミュレータを実装して、hasiさんがそれをラップしたブラウザで動くGUIを作ってくれたので、サンプルのマップを遊んでみる
→むずい。これ仕様追加が無くてもこれだけで十分72時間のコンテストになりそう
アルゴリズムの案をいくつか考えてみるけどかなり無理ゲーな予感が
詰将棋的に、特定の経路で動いて岩をよけたりしておかないとのちのち死亡確定、みたいなマップが解けるAIを作れる気がしない
寝ようとしたら追加ルールでFloodが来て、うげーこれは完全に殺しに来てる…どうすんだこれ…と絶望感に浸る
とりあえずMarathonMatchで用意されてるみたいなCUIで実行するテスターを作ってこの日は終了
2日目
テストケースになるマップを自分で作らないとなあ、と思うもどのくらいまで想定して良いかがわからないので難しい
とりあえずランダムなマップのジェネレータだけは作った、けど生成されたマップを見ても全然面白くない…
誰かがパズルマップを作っていたのでそれを手で解くのに熱中し始める。このときが一番面白かったかもしれない
診断人さんによってuwiさんのJava製シミュレータをC++に移植されていたので、それをベースにして、ランダムウォークしつつテキトーな評価関数を元によさげな方向を選んで歩き回るのを書いてみる
ひとまずは取れるλからどんどん取っていけばいいんじゃね、ということで、評価関数の要素は取ったλの数と近くにλがあるかどうか（到達可能かどうかも考慮）、くらい
contest1.mapやcontest2.mapくらいはゴールできていた。けど、局所的に目先のλを取りに行くだけのAIなのでちょっとややこしい盤面になるとてんで話にならない
あとはこの日はこれのバグを取りつつ終了。何かトランポリンとか来てたけど無視って寝る
3日目
起きたらbeardが仕様追加で来てた。
草と岩がぶつかったときの仕様がよくわからなくて多少紛糾する→バリデータ様が正義
この辺で、バリデータの動作が最後にAbort付けなくてもAbort扱いになっていることに気づく。Aとはなんだったのか
もう一個仕様追加来る予定なのであまり気は進まなかったが新仕様を黙々と反映させる
実装し終わった頃に最後の仕様追加horockが来た
もっと派手なのが来ると思ってたけど、このくらいの変更では物足りない、と思うようになってしまっていた
これも実装
あとは評価関数に新仕様の要素を反映させたり微妙な高速化をやったり、
探索しきれないようなでかい盤面対策に、ランダムウォークの結果を1ステップずつ進めていたのを複数ステップ一気に進めるようにしたり
4日目
提出に向けて、SIGINTをトラップして終了できるようにしたり、細かいバグを直したりちまちま高速化したり。
来た方向に即戻る移動は意味が無いことが多いので起きづらいようにしたらまあまあスコアが上がった（ゴールできない盤面がゴールできるようになるわけではないけど）
今の評価関数ではgreedyに近いλから取りに行ってしまうのでどうしてもcontest6.mapがクリアできない。
改善できないかと、状態を複数保存するbeam search的な探索も書いてみたけど遅すぎてどうにもならなかった
最後にhasiさんに提出してもらおうとしたら、Linux上でコンパイルしたらちゃんと動かず"A"しか返さないという問題が発生していた
結局解決できず、審判環境では動くことを願ってそのまま提出することになった。各自の手元では動いてるし環境依存するようなコードはたぶん入れてないと思うのに、謎
最終的にはサンプルマップのスコア合計はbestの80%くらいだったかな
AtCoderの非公式ジャッジに（勝手に）提出してみると、京都チームには負けてるっぽい
反省
オンラインでのチーム戦は難しいなー
ICPC的なコンテストだったら各自別々の問題を解く、でよいけど、こういう巨大な一つの問題に取り組む、というときは作業をうまく分割して分担しないといけない
そしてこれは分割が難しめなタイプの問題だった
次回参加するときはチームで現地に集まる、というのをやってみたいですね
最初の方絶望に浸っている時間が長くて、仕様追加が予告されているというのもあって最初の実装ができるまでに時間が掛かってしまった。
とりあえずスコアが取れる実装ができたときにはもうlightning終わっていた
やっぱりスコアが一つも出てない状態というのはモチベーション上がりにくい。1つでもベンチマークになるスコアが出るとそれを超えようという意識が生まれる
マップのupadteは、毎ターンで盤面全コピなとても遅いのしか作れなかった。変化する可能性のある岩やWだけトラッキングする、という方針でやったらどうにかin-placeに高速にできるのかな…
あと探索のヒューリスティクスはもっと入れて良かった。岩の隣を開けるとか
あとから仕様変更が来るのは自分としては結構つらかった。ルールが決まってる問題を集中して考えたいです
