2009-06-30

lightning 。とりあえず問題読む。よくわからんが VM 作る必要があることはわかった。こんくらい簡単だと JIT とかしたくなりそうだけどとりあえずインタプリタにしておくかーと適当に実装。うまく動かない。

動かない…動かない…動かない…とやってたらなんか IRC 情報によると state bit の使いかたを逆にしたら動くとか動かないとか。まぁなんか動いてるようには見えるが依然として score が -1 なんだけど…とか思いつつまぁ気にせずどうやって解くか考える。

何をどういう順番でやったか知らないけど、あれこれ考えてるうちに spec が修正されたと思う。その時には 1001 の解答らしきものを生成しそうな Ruby スクリプトができる感じにはなってたと思う。一生懸命物理を思い出してあれこれ考えてたんだけど、 Appendix に簡単に解ける方法が載っててアホか俺はと思った。あとビジュアライザは今回かなり速い段階で作ったと思う。

でまぁ寝たんだと思う。起きてさぁどうしたもんかいなと思いつつ 100x の他のを解いた。まずこのへんで問題だったんだけど、 osf 作ればそれでいいんだと思ってたから、データ調べて適当に解答作ってたのだった。

でまぁそのまま 200x はどうしたもんかなぁと考えたけど、要は軌道は円なんだから、 100x と同じ要領で、自機がいる点と地球に対して反対側の直線を考えて、予定到着時間に目標の物体が通るかどうかを考える感じでやった。まぁたいていちょっとずれてるので適当に手動で調整して、っていうアプローチだった。適当調整の部分は簡単なスクリプトとプログラムを併用した。

次 300x 。対象が楕円だから到着時間を推定できないんだよなぁということで悩む。あれこれ考えたところ、まぁこっちは従来通り Hohmann で行くけど、向こうへの到着予定時間はわからんので、対象の行動予定を全部洗って、その履歴内にあるようならまぁ調べてみるって感じでやった。外しまくるけどまぁ補正すれば色々大丈夫。

とそのあたりで他に12問解いてる子はいなかったので、大差で1位に立った。このへん: http://shinh.skr.jp/m/?date=20090627#p19

でまぁ、手動調整のコツはつかめたので、手動調整に頼りまくって高速に辿りつけるように調整していた。そして lightning 終了3時間前に手動調整は disqualify されると書いてあると気付く。うげーと思って手動調整プログラム/スクリプトを自動化した。自動化したところ点数は落ちたが 100x と 200x はなんとか通るようになった。 200x はたぶん追加される問題は解けない可能性が高いだろうが…で、その自動化した物体は 300x は 3003 が通せなかった。無念。そして lightning 終了。3時間でこの自動化ができたのは助かったと言えば助かったが、その間に何人かに抜かれて、5位くらいだったと思う。ただ翌日考えるに、この自動化もよく考えると最初っから相手の行動予定を知ってることを前提にやっちゃったのでダメか。

反省としてはルールをちゃんと読むことってことと、問題のバグとかの可能性がある点は放置して別のことをやるというような時間配分をすべき、とかか。

寝て…寝れなかったので、とりあえず反省を元に C++ でキチンと書きなおす。まずは VM は速いにこしたことないだろう…と JIT …は面倒だったので、その場で C コードを生成して実行するように。 validation の際は問題のバイナリが変わるだろうから、あらかじめ作っておくってのはイカンわけだね。この VM はほとんどバグも無いし速いしで文句の無い感じだった。5秒以内に 3M step は実行するようだ。

この最中にしんどいと思ったら熱出てることに気付いて悲しかった。加えて1日分の作業の書き直しとか相当ダルいので、めげかけた。しかし頑張った。 400x はとりあえず放置で2日目は全て使う覚悟で。

このへんで寝たか、そして起きた。 100x を解く C++ コードを書く。 Ruby と同じことしてるつもりなんだけど 1004 が通らん。どうしたもんかなぁと思ったけど、後々そのノウハウは必要になるかもしれないし…と適当に到着してから adjust するコードを書いた。そこでわかったのはここでやった種類の補正はうまくいかんし、確実性が低いということだった。最終的には後で捨てた。

1004 の補正の最中に書いたコードで有用だったものは、物理系の完全なシミュレータだった。この手のシミュレータは慎重に書かないと結構間違えるんだよなぁ…とビクビクしつつ書いたけど、まぁ割とあっさりうまく動いた。

200x 。スクリプトでやっていたことを移植する。めんどくさい。マジでめげる。そしてよくバグる。数値計算が微妙にずれまくる。シミュレータや問題のバイナリが微妙に仕様と違う計算をしていることを疑ってばかりだったのだけど、たいていのケースでずれる理由は与えてる初期時間がおかしいことだった。まぁ妙なコードを適当に書いたらそれなりに動いたので OK とした。 validation で増えるテストケースをさばける自信が無い感じだった。

300x 。手作業でやっていた微調整を自分でやるのは大変だった。バイナリサーチ書けば良かったんだろうけど、ローカルミニマムとかあるんじゃないかなぁというのと、実装がラクな方が良いということで、もちょいヘチョいのを書いた。最初に 10 値をずつずらして 10 分割した中で一番良いものを選んで、次に 5 ずつずらして…というのを繰り返すヤツ。これは遅かったのが問題だった。最後まで問題だった。よく考えると収束したら終了するくらいのことはしておけば良かった。この作業を 200x に移植して 200x も安定感が増えた。ただ 3003 が微妙にあやしい感じだったので、汎用的にするならもうちょっと良い補正方法を考えないとなぁと思いつつ、そろそろ人生に疲れてきたので 400x へ。

400x 。基本は複数ターゲットがいるだけで 300x と同じでいいだろう。むしろ軌道に 900sec 乗るのが苦手だったので、こっちの方が簡単だ。月には到達できないが、とりあえず近傍のいくつかを回収できるようにしたい。問題は月だなぁと思いつつ、まぁそんなに大きくズレないようなので、補正フェーズで正確なシミュレーションができてりゃいいだろう、と月入りシミュレータを実装。微妙にズレる。色々調べてみると、まずそもそも月の位置の計算がおかしい。これはアホみたいな話だけどテストプログラムで input として自機との相対位置を喰わせていたのであった :)

しかしまだバグっていた。まず自機とその他で誤差の量が違う。その他から直そう。とりあえず VM の吐いた C コードをゴルフしていけばリバースエンジニアリングできるだろう…とガリガリやっていた最中に、ふとこの VM の仕様で月の前回位置ってちゃんと覚えてるのかな? と思った。厳密に計算するなら、月の2回分の位置が重力として必要なのだけど、ナイーブに実装するなら前回の位置を2回使うとか、今回の位置を2回使うとかいうバグがバイナリにあっても不思議はない。適当にやってみたところ、今回の位置を前回の重力計算にも使ってそうなことが判明した。

これで誤差は相当減ったが、自機だけ相変わらずおかしい。これひょっとして自機って月無視してなくね…と思って自機のシミュレーションだけ 300x 以下用のに変えてみたところ、動く。アホかー。そしてそのすぐ後に 400x バイナリのアップデートが行なわれていた。アホかー。

で 300x ベースの 400x のコードを適当に走らせて、4位に復帰。そして寝る。

起きても8位だった。これは結構頑張れるなーと思う。

400x をいじっていく。 300x ベースだったので対象に近付いてから対象の軌道に入るコードだったのだけど、よく考えると自機は円軌道を描いてる前提なので、対象の軌道に近い円に補正する方が賢い。そう変更すると対象が楕円軌道描いてるヤツのスコアがかなり良くなった。 300x の名残りで対象は常に最初に発見した一番近い子、ていう感じだったんだけど、現在一番近いもの、に変えたら楕円の 4002 が良くなった。これで5位に。

このへんで 4004 は月以外パーフェクト、 4002 もかなり良くて、 4001 と 4003 がイマイチな感じだった。 4001 とかをビジュアライザで眺めていると、最初の方は調子が良いのだけど、後の方になると対象との周期差が少なくて、いいタイミングを待ってる間にタイムオーバーになってしまうとわかった。だから対象が反対方向に動いてる 4004 や、楕円を描いてる 4002 は成績が良い。

どうしたもんかなぁと思ったけど、とりあえず 100x のコードを持ってきて、対象が近い時は一旦対象から離れるようなコードを書いてみた。全然ダメ。時間の無駄だった。このへんでどうしたもんかちょっと思いつかなくなる。

そこで、後顧の憂いがあるのがうざいので、不安定そうな 300x を見直そうと思った。 400x の経験を生かしてみたりしてから、やっぱ 900sec ちゃんとついていくかどうか simulation してから挙動を決定すべきだよなぁと思って、確実に 900sec ついていけると判断した時だけ飛ぶようにした。まぁ当たり前なんだけどね。後 900sec ついていけるように、近傍についてから 900sec の間 adjust するコードを入れた。終わってから気付いたのだけど、燃料使ってる間は 900sec にカウントされないらしいので、このコード微妙に失敗するのに飛んじゃう可能性があるなぁ…ああバッファ考えて 1500sec 大丈夫だったら大丈夫、ってことにしてたんだけど、これが 1800 なら良かったのに…ギギギ。逆にうまくいく自信がある時は無駄に時間と燃料を浪費してるしな…

200x も同じロジックでいこうと思った。 200x のコードに同じ変更を backport するのめんどいなぁ…と思ったのだけど、 300x のコードそのまんまでいけるんじゃね? と思ってやってみた。うまくいった。まぁ対象が円であることを仮定する必要が無いわけだね。

400x に戻る。もうやれることは限られてるが 4001 と 4003 をなんとかしたい。色々考えた結果、常に一番近いのを常に対象としてるのが良くないだろうから、そこを直すのが最も効果的なんじゃないかと推測した。簡単なはずの変更なんだけど、完全にコードが対象1体を前提にしてたので、結構大変だった。最初はこの変更は全然うまくいかなくてがっかりしたけど、 magic number を色々調整したらかなり良くなった。これが良くなってる感触を得たのだけど、なにぶんアドホックな遅い作業を対象の数だけ回してるので、遅くなった。最悪10分、速いやつでも3分程度かかってしまう。

これを生成してる間に leaderboard が閉じられつつあるという情報を irori さんからゲット。それなら世界7位より6位の方が良いだろう、と計算が終わった 4001 をサブミット。よし6位だ。きねん写真をとってちょっとすると leaderboard 消えたという話。消えるんなら急ぐ必要なかったなーと思いつつ、他のヤツも submit …したたタイミングでスクリーンショットとりやがりましたよヤツラ! 騙し討ちです。ゆるせません。私が最後に見たのはこんなものでした。

Position  	 Score  	 Team  	 Problems Solved
1 	5171.5322 	pepsiso 	16
2 	5025.1531 	THIRTEEN 	16
3 	4685.6003 	wiiphonies 	16
4 	4406.2437 	Side Effects May Include... 	16
5 	4246.8523 	Intercaml 	16
6 	3948.0274 	shinh 	16
7 	3861.0396 	jabber.ru 	15
8 	3718.6164 	7-15 	16
9 	3618.2471 	Purely Functional Infrastructure 	16
10 	3532.0610 	irori 	16
11 	3531.0112 	Pluk 	15
12 	3431.6513 	cashto 	16
13 	3341.2227 	BSM 	16
14 	3170.9021 	Krakow Dragons 	16
15 	3111.3151 	OneDayPastDue 	14
16 	3102.3321 	Pokryshkin 	16
17 	3075.7607 	NCSU ARC Alums 	16
18 	3066.0340 	Cult of the Bound Variable 	13
19 	3033.8702 	The Blind Hen 	14
20 	3026.4666 	The Usual Suspects 	16

やまぁそれはいいです。対象を増やす変更は、楕円を描いてる 4002 をかなり悪くしていた。調べてみると、燃料使いすぎということだった。 4002 とか全員近付いてくるから全員が対象になっちゃって、さらにそれらが離れてくもんだから、やばいんだよねーと思って、まぁ普通に燃料制限を適当にかけてみた。これはうまくいった。予定よりうまくいって、 4002 も全部回収できるように。ただ必ず燃料3500以上必要なシーンで飛び立てなくなってしまった。これは地球にムチャクチャ近いところからスタートとかさせられるとヤバいけど、大丈夫なのかなぁ。あんまり時間も無いわけだし、今回も前回同様、テストケースはそこまで難しくないと推測してるんだけどな。値のスケールを変えることに本質的な意味はないしね。

なんかもう思いつかなくなったし、そもそもテストが遅すぎてつらい。残りの時間はパラメータ調整だけやりつつ他の部分見直そうと思う。

まぁすぐに思いつくのは 100x の燃料使えば使う程点数が増えるというルール。やれば100点以上増えるしね。ただ validation でコケないように気をつけてコーディングしないといけない。まぁ色々注意しつつ 100x の安定度も上げた。この際 100x のアドホックな修正コードは捨てた。

4001 8体、 4002 9体、 4003 9体 (あれ YouTube に上げたバージョンは月以外全部落としてるね…でも点数落ちた記憶はないので、燃料なり時間なりの理由で点数増えたのかなぁ)、 4004 は割と余裕で10体、という感じだった。 4004 は時間も燃料もかなりあまってたので、 kinaba さんとこの後で見るに月行くのってスイングバイとかせんでもあまり燃料いらないので、案外頑張れば行けたんじゃないかなぁとか思って少し残念だった。

2日目以降は、 Top10 に入る前提で、 validation に耐えることを主眼に置いてアドホックな修正はなるべくしないようにしていたので、 Top10 に入れてるといいなぁ…手動入ってる人が上位に多いと割と上にいけるかもだし。

そういや終わった後にちょっと思ったんだけど、 4001, 4003 に対して、回りのヤツ落としたら一旦地球からかなり離れてしまって、速度が減ったところで逆進して、残りのヤツを狩るとかすれば面白かったんじゃないかなぁとか思った。スコアのルール的に燃料減らしちゃうのはマズいですかね。

反省としては、ビジュアライザもっとよくしておくべきだったなぁと。少なくとも燃料やスコアを表示をしておくべきだった。後アルゴリズムが現在考えてることの表示と。それにビジュアライザ遅かったんだよな。 VM もビジュアライザもそれ自体は良かったんだけど、たぶん通信のために printf と scanf してるのが遅い。ちゃんと本体に組み込むのをやるべきだったかな。ただ 1,2&3,4 それぞれにビジュアライザ組み込むのがめんどかったんだよな。 4 だけでもやればよかった。

後シミュレータが完全になってからは、実際に VM 走らせずに最初から最後までのプランを計算してやる方が良かったと思う。その方が速いし。ビジュアライズもシミュレータだけでできるはずだしな。それをやらなかったのは途中までシミュレータが色々バグってて信用できなかったからだったのだけど。

そういう意味で、一般的に、信用のおけるパーツを一つずつきちんと組んでくのは大事だなぁと思った。あまり中途半端な段階で飽きて次に進むのはあまり良くない。ただまぁ 300x 中途半端で 400x やって、その成果を 300x にかえすとかもできるし、今回は問題のバグもあって完璧なものを作ることができなかったあたり微妙な感じではあったけど。

逆に今回は VM ちゃんと作ったのは良かった。速いしバグが無いと信用できる部品があるのは良いことだった。

兼雑記

ICFPC 2009

なにしたか、と、その反省 - lightning

なにをしたか、とその反省 - 本戦