The Eleventh ICFP Programming Contest - 純粋関数型雑記帳

http://www.icfpcontest.org/

疲れた…。
今年はまあ何というか、孤独との戦いであった。
来年はちゃんと休みをもらって、ちゃんとチームを作って出たいと思った。

初日はkzk氏、hillbig氏とともになんかやってました。
今年は問題がシンプルだなと思った。
時間制限3時間とかのICPCのJava Challengeとかよりもはるかにシンプルなのですけど。
そして、問題の制約が恐ろしく緩い。
どこまで想定すればいいのでか。
そして、Windows版が用意されないシミュレータ。

アメリカ語を2時間ぐらい掛けて頑張って読んで、
適当にプロトコルかいたりしてたら、
開始4時間後ぐらいには愚直ダッシュコントローラができてたような気がする。
しばらくしてナイーブな敵と穴避けアルゴリズムが完成して、
すでに与えられたマップが終わってしまった。

しばらくしてMLにスコア自慢が現れて、
自慢げに自分のスコアを張っていっているのだけど、
自分のスコアよりも全体的に2秒程良い。
どうやら最初に方向を合わせる前に加速を開始するとそのぐらい速くなるようだった。
でまあ、最初のマップに対してはやることがなくなってしまった。

ランダムマップジェネレータができてきたので、
それでいろいろやってみると、まったくもって全然ダメだった。
とくに、穴が重なってたり、穴の後ろに穴があったりすると良く無かった。
穴をマージすればそれだけで結構良くなるんでないか？
と思ったので実装したらものすごく良くなってビックリした。
軽い迷路ですら解いてしまう。
でも、デバッグは大変だった。

プログラムはもちろんHaskellで書いてて、
最初TCP通信はNetworkモジュールのconnectToを使ってたのだけど、
Nagleアルゴリズムが無効になってるのかどうか分からなかったので、
結局Network.Socketを使って書き直した。
しかしこれがなんというか腐ってて、
これのSockAddrに入れるPortNumberがネットワークバイトオーダでないといけない。
なので手動でスワップしてやらないといけない。
作った人は何を考えてるんだろうか。

そんなこんなで時間を無駄にしながら、
うおお、一日目にしては結構できたんじゃないのか？
とか思いながらLightning Divisionを提出。
あとまだ倍もあるのか、と思ったりしたけど、
こういうのは後半はあっという間に終わるものであるし、
今回も実際に後半の時間の流れは吃驚するほど速かった。

とりあえずLightning出して、10時間ぐらい寝て、
日曜の夕方頃に起きて、改善を開始した。
不可解な動きをしているところを追跡していったら、
なんと、円をグルーピングするアルゴリズムにバグがあった。
自分の莫迦さ加減に腹が立ってくる。
ほんでから、いくつか動作がおかしな所があったのでそれも修正した。
それから、初日からずっとやろうと思っていた、
隠しパラメータ推定を実装した。
アクセル率とブレーキ率と摩擦係数と角加速度がそれなのだが、
なんとかそれを求めるのを実装して、
自機の動きを改善した。
これにより、目の前にあたりそうなものがあったら確実に当たる前に止まるというのと、
目的角度までピタリと動かすということが可能になった。
まあ実際にはそれ以外の要因で良く穴に落ちるのだが、
それでも、自機が首ふりをしなくなったり穴の前で止まったりしたのはちょっと感動した。

それからは、穴回避のアドホックなコードを追加しまくったのだけど、
なんだか追加すれば追加するほどスコアが悪くなる疑惑で、
結局のところそれらは破棄して、
変更を一つずつ吟味して、本当に効果のあるものだけ採用した。
なんというか、やってた人なら分かってもらえますかね。
なんで、近傍の障害物探知とかやらない方がスコアがいいのかとか。
結局素直に進んだ方がランダムなテストケースに関しては良いことが
多いのかもしれないということですよ。

残り12時間ぐらいになってきた頃からだんだん飽和してきて、
もうこれ以上はこの拡張では無理っぽいとなって、
今までで一番良さそうな構成を作ることにした。
根本的に改善するには、二次元平面上の最短経路探索を実装すべきだったのだろうなあ。
2日目時点でそれを始めていればあるいは…。

というわけで、結局Lightning＋デバッグ＋統計情報利用して自機操作ぐらいしかできなかった。
というかもう、二日目以降一人で、とてもじゃないが勝てる気がしませんよ。
Score SharingとかMLに流れてるスコアにも勝てませんよ。
最初のマップはいろいろ手を加えるほどに自機が慎重な動きをするようになって、
だんだんスコアが下がってくるのですよ。
もうどうすりゃいいのかと。
というわけで今年はLightning狙いですかねえ。

時間も終わったようなので、提出物と絵をいくつか張っておこうと思います。

http://fxp.infoseek.ne.jp/tmp/icfp08.tgz

ソースはめちゃくちゃ汚いです。