あと

方針はよく覚えてないのですが、ライトニングの時点では、

  • ゴールに突っ込む上で障害物となる物体に接するように線をひいてそこを目指す
  • なんか死ぬなーと思ったらフィーリングで何か避ける
  • 無数のアドホックな補正(障害物の真横通った後に再突撃しなおすのを修正するとか、ゴール通り過ぎたらブレーキかけるとかもろもろ)

とかそんな感じ。サンプルはそれなりに解けたと思う程度。「ゴールに突っ込む上で障害物になる物体」が横一直線に並ぶと終わるなど、まぁ色々ダメダメ。

でまぁ、1日目終わったあとに、この具体的にどういう条件で評価されるかの指定の足りないっぷりとかからして、今回のテーマはこう、「ソフトウェアってヘンな条件でもちゃんと動かんといかんぜよ」みたいなのがあるんじゃないか(いやホントこいうの大事だと思うんですよ。仕様を明確に伝えて来なかった客はもちろん悪いんだけど、仕様をきちんと確定させられなかった俺も悪いみたいなそういう、なんか微妙にずれてるですが)とか勝手に妄想して(だからレイテンシが高い状態でのチェックも欲しいかなぁとか思ったわけだけど)、速度とかより、色んなマップで死なずにゴールに行ける確率を増やしたいなぁと思いました。

でそういう方針で色々実装したのですが、最終的には

  • 見つけた静的なオブジェクトは地図に記入していく。地図に記入する時にすごく近いオブジェクトは同一のクラスタに属するとしてグルーピングする。
  • ゴールに向かう上で邪魔な位置にある一つのクラスタに対して、左右どっちから回ると良いか考える:
    • そのクラスタが小さくてかつ遠ければ、左右を選ぶ時間が十分にあるとして、そのクラスタを抜けた次に邪魔になるオブジェクトがゴールに近い方に向かう。 「どっちから抜けてもいいんだからクレーターとか少ない方から抜けてくれよおいおいそんな茨の道を行かんでくれっ」を雑に実装した感じ。これを再帰的にやれば複雑な迷路もラクに解けると思ったけど、実装するのがめどかったので他を優先したのでできなかった。
    • 近いか大きければさっさと回れる方から回るって感じだったかと思う。
    • 片方の端が壁に接触していたら、そっちは選ばない。
    • で、考えたらその先を「目的地」として座標を保持。もちろん何もオブジェクトがなければゴールが目的地になる。
    • こいう目的地ベースで、あまりころころ変えないようにしてやることによって局所最適な感じでうろうろするだけ、っていうのを避けたつもり。
  • 目的地に向かう際、その次の目的地が急カーブを要する場合は減速。
    • この減速量が完全にフィーリングの手調整だったのはまずかったなぁ。ちゃんと計算してやるべきだった。
    • これのせいで単純なマップはライトニングより弱くなった。これは私の妄想した今回の趣旨によると、正しい判断だと思ってるけどはてさて。 id:tanakh さんとか私のよりのろい感じですね。
    • むしろもっと遅くしても良かった気がする。曲がり切れずに死ぬこと多い気がする…
  • 目的地に近づいたら、次の目的地へのカーブを開始するために、今の目的地をやめて次のを見て動くようになります。この時に古い目的地の存在を忘れるため、曲がってる最中に避けたはずのクレーターに落ちたりして大変です。それの補正をアドホックにやります。要は目的地をちょっと動かす。
  • ここまではあまり安全性について考慮されてないのですが、最後に安全弁として、今の状態を1秒続けているとどうなるか…というのをシミュレートしてみて、死ぬなーと思ったら
    • 10ステートに関して同じく1秒死なないかどうかチェックしてみて、死なないのがあれば現在のステートに最も「近い」ステートを選択。1秒間同じステートを取るっていう雑なチェックだけど、これでかなり不穏な死に方が減った。
    • 全部死が預言された場合、一番長く生きられるステートを選択。これは良かったのかわからない…現在の戦略を0.5秒繰り返した後に0.5秒別の行動をすれば生きられる、みたいな感じだったかもしれないのに、局所的に生き長らえられる戦略で緩慢な死を待つ状態になってたこともあった気がする…
    • あと、「本当にそれ何やっても死ぬんか?ブレーキ入れて左入れまくったら生きられるんちゃうんか?」みたいな状況で死んでいく様を何度も見たので、このロジックはバグってたのかもしれない。かなり長時間バグ調べたけどよくわからんかった。角速度の絶対値が大きくなってしまっていると、逆方向に戻すのはそれなりに時間がかかるみたいで、人間が見ると助かりそうに見えちゃうので判断が難しかった…
  • なるべく最初の方に書いたような、「戦局全体を大きく見る」ようなところに気合いを入れるようにしました。でも実際は後半に述べたみたいな、とりあえず今死にそーなのなんとかせんとねみたいなののアドホックな対処に使った時間が多かったし、実際のところもうちょい安全管理はきちんとやった方が良かったなぁ…と id:tanakh さんのボットを見てて思いました。
  • あとパラメータ推定ね。すごいいい加減に加速度推定はやったんだけど、三日目まで角度に関するルールが全く理解できてなくて(そもそも状態遷移が間違ってたとか)、何度も読みなおした結果「よくわからんけど俺は間違っている、それだけはわかる」という結論に至り、それっぽく角加速度推定みたいなのとか実装して、なんかちょっとずれてるけど大部良くなったしいいかーと放置した。
  • 正直なところ、パラメータ推定とかシミュレーション精度とかもうちょい上げて、死なないロジックをもうちょいきちんと組めばかなり良くなっただろうなーと思ったんだけど、あんまりそれって面白くないよね。むしろもっと時間があれば迷路をガツンと解くようなのとかに時間を使ってたんじゃないかと思う。
    • パラメータ推定は今回のコンテストで割といらないと思った部分でした。みんなちゃんとやればそれなりにできるだろうし、みんなそれなりにやる必要はあるだろうし、「宿題」的な感は否めなかったかなぁと。

あとね、とても重要なことなんですが、今回はビジュアライザを1日目終わって、障害物のクラスタ化を作った後すぐに作りました。

http://shinh.skr.jp/dat_dir/icfp08.png

え今回ビジュアライザ配布されてたじゃんと思う人もいるかもですが、これはすごい重要だったと思います。自分でビジュアライザ作らないと、自分のボットが今何をしようとしてるのか、っていうのをテキストのログと、与えられた絵だけから判断しなければならなくて、イマイチわからんのですよね。

いや自分の書いたプログラムくらいだいたいわかるさという人もいるかと思うんですけど、私の場合は私がどれだけ信用できないか、いわんや酔い潰れた俺をや、ということはよく存じあげてますのでそんなこんな。その点自分で作れば、上の絵だと今どこが「目的地」なのかとかが一目瞭然で、とんでもないところを目的地にするバグとかがあっという間に潰せました。あと危機的状態になると自機が黄色とか赤く光るとか、ブレーキかけると自機がマゼンタ色になるとか。どうでもいいけど赤とマゼンタは似すぎてて、今回最大の失敗はブレーキがマゼンタだったことかも知れない。でも赤い物体が急に青くなるとかは恐いよね。

まぁとにかくこいうのを30分もあれば書けるのだけは web 系時代で私に残された最後の強みみたいなそんなこんなかもしれませんね。例年思うことに、遠まわりに見えてももっと速く SDL 使って可視化しておくべきだった…というのがあるのですが、今回も初日にやっても良かったかもしれない。あと今回思ったのはログをもうちょいキチンとしたフォーマットで残しておいて、可視化つきでリプレイできるようにしておくべきだったなーというような。機会があったらそいうのも試してみよう。

あとは… google-gflags 使ってました。これ私はすごく好きなライブラリなんですけど、正直一番の効果は共同開発者に 1.定数を可変にすることを強要する 2.その定数にドキュメントを書くことを強要する、あたりな気もするので、そいう意味でコンパイルが割とさっくり終わる今回くらいの規模だとどうでもいいかもと思いました。でもパラメータの微調整とかを、スクリプトとか書けばコンパイルしなおすことなく書けるからいいかなぁとは思いました。むしろ TopCoder のマラソンマッチとかで使ってこうかなと。

今回やりたいと思ったけどできなかったこととしては…

  • ちゃんと迷路解ける程度の経路探索。現状では四方囲まれると混乱しはじめる、かな?
  • もっと安全に。正確なパラメータ推定未来予想、安全装置。正直あまり面白そうでない。
  • もちょい賢いビジュアライザ。
  • 自動パラメータ推定。こいうフレームワークみたいなのは作っとくとマラソンでも使えていいかも。
  • たくさんテストケースとしてのマップを作る。あるいはランダムジェネレータなど。

とかがあったかと思います。もっとあったかも。まぁいずれ

あああと議会制弾幕回避機関ね、あれがうまくいかないのはよーく存じ上げてたので、正直なところ、今回考えることもしなかったです。 kinaba さんと niha さんに言及されててびびる。万が一私のせいでミスリードしたならごめんなさい。

あとなんか、 いわさきさんとこ のがすごいよくできてそうだなーと思いました。

全ての定理

そいやこんな話を会社でしました。

なんか true == false を証明したら全ての定理を証明できると聞きましたが、困ったことに私はそれを証明できたみたいです! 以下に Perl による証明を書きます!

> perl -le 'print 0==1'
> perl -le 'print 0==0'
1

つまり Perl は真は 1 として表示されるみたいです。

> perl -le 'print true==false'
1

つまり真! true == false が証明されました!

PHP によっても証明できます。

> php5 -r 'print false=="false";'  (1)
> php5 -r 'print false==0;'  (2)
1
> php5 -r 'print 0=="false";'  (3)
1
> php5 -r 'print true=="false";'  (4)
1

いやあ冷静に見るとなんか推移律とか壊れてますね! 最後の3つを使うと、

上から2つ目(2)を使うと、

false == 0

次に上から3つ目(3)を使うと、

0 == "false"

つまり

false == "false"

いやここまでは当然ですね…そこで最後の(4)を使うと、

true == "false" == false

と true == false が証明されました。たぶんこれで P==NP とか解けてるので1おくえんくらいください。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h