ICFPC2012に参加しました

去年に引き続きLennMars他二名で参加しました。チーム名は地下ということでスニーカー文庫刊のあるライトノベルから頂戴してTeamKunikidaです。以下ソース。

https://bitbucket.org/LennMars/icfpc2012/src

メンバーが自分以外にOCamlが書けるわけではない情報系1人とプログラマですらない人1人という面子だったので設計には悩みました。結局メインをOCamlで書き、情報系の彼がコード書きに参加できるようOCamlからC++を呼べるようにしておくというのが事前に決めた方針でした。しかし彼は結局ほとんど参加できなかったのでFFI周辺の面倒な作業に時間を取られただけだった感はあります。
結果的にどういう設計になったかというと、C++側では目的地へのルートを計算するためのdijkstra法などを、OCaml側では目的地決めやら評価関数やらの細かい部品と型を整備してノンプログラマでも見様見真似でAIを設計出来るように、という分担をしました。例えばこんな型が定義されています。stateは盤面状態の型。

(*  plan__util.ml *)
type loc = int * int
type plan = state -> command list
type cond = state -> bool
type eval = state -> int
type direct = state -> loc option (* define where to go *)
type move = int * int -> plan (* define how to go. [] is unreacheable *)
type search = (plan * cond) array -> eval -> plan (* select preferable plan. Plans may be synthesized within a search *)
type transmute = state -> state

最終的にメインループに渡されるのは現在の状態から適当な長さのコマンド列を返すplan型の値であり、AIの設計者は盤面の評価関数の型evalの値や複数のplanからA*で探索を行って合成したplanを返す関数の型searchの値などを組み合わせることで新しいplanを書きます。
これらの型の値はhttps://bitbucket.org/LennMars/icfpc2012/src/98929be6c8ef/src/main/plans.mlにまとめてあり、これを見て同じ型同士の値を適当に入れ替えるなどしてOCamlをよく知らない人でもplanが書けるようになったらいいなあ、と思いながら設計しました。実際、https://bitbucket.org/LennMars/icfpc2012/src/98929be6c8ef/src/main/plan_coarse_safety2.mlなどは非プログラマの人が書いたものです。

というようなことがやりたかった訳ですが、仕様変更に追いつくのが大変で主要な道具であるdijkstra法やA*の完成度が低く、また今年も本当に面白いところに辿り着くまでに終わってしまったなあという悔いがあります。来年までに手を二倍速くするかOCamlが書ける一緒にやってくれる人を見つけたいですね……。

(8/28追記)
最終結果はRound1を86位で通過、Round2を89位で敗退でした。たまにセグフォで落ちるようなプログラムの割に案外いい成績でびっくりしてます。なおこのセグフォの原因は未だによく分かってません、先日参加したOCaml Crashで詰められればよかったのだけど時間足らず。