2009-07-20 [長年日記]
>> [ぷよらせ] ぷよるアルゴリズムを考えてる 
あいかわらず熱いぷよm@sシリーズや、TASさん（左手）vs.TASさん（右手） などのぷよぷよ動画に影響されて、ぷよるアルゴリズムを作りたくなった。
最終目標は、ぷよ通ルールで相手フィールドも把握する（小連鎖に対応もするし、相手にスキがあればこちらからも仕掛ける）ようなヤツを作ることだけれど、その道のりは長い長い。
つーことで現在できているのは、ぷよ１ルール*1で、致死連鎖*2を目指す、というもの。
100回チャレンジさせたところ、
手数 回 11 1 12 12 13 7 14 17 15 13 16 9 17 13 18 11 19 9 20 1 21 4 22 2 23 1
という結果になった。
15手以内に発火できたのが48回と、ほぼ半数を占める。
ぷよm@s*3で言えば亜美・真美と勝負になるくらいの実力かなあ。千早には届かないだろう。
ちなみにオレ自身は、100回やって15手以内に致死連鎖発火できたのは23回だった。余裕で負けますね！＞＜
作り上げる前に飽きてソース紛失するのが毎度のパターンなので、現時点でのソースをうｐしておく。ソースの読みやすさ？知らないよ、そんなの。
ruby 5ren.rb
で動かす。"\e[1;31m"とかで色づけしてるので、そういう端末でどうぞ。
2009-06-30 [長年日記]
>> ICFP 2009 Programming Contest メモ
期間終了した。参加したみなさま、お疲れ様でした。
今年は衛星を操作する問題だった。課題が 4 種類で、それぞれの課題でパラメータ違いの 4 問があって計 16 問。
- 100x: 円軌道で動いてる自機を、目標の円軌道上に移動させる。
- 200x: 円軌道で動いてる自機を、目標の衛星（別の円軌道を描いてる）に寄り添わせる。
- 300x: 楕円軌道で動いてる自機を、目標の衛星（別の楕円軌道を描いてる）に寄り添わせる。
- 400x: たくさんある衛星に、タッチして回る。給油所があったり、月の重力も気にしたりしなきゃいけなくて、込み入ってる。
問題文PDFの最初に VM の仕様が書かれていて、「なるほどこの VM 上で動くプログラムを書くのか」と思ったら、そうではなかった。各課題ごとにVM 上で動くプログラム（= 自機の動きとか、目標の動きとか、スコアリングとかをシミュレートしてくれる）が与えられてて、オレがやるべきことはそのプログラムに対する入力（具体的には、各時刻での自機の推進力（��Vx,��Vy）をどうするか）を決めること、だった。
去年は「Linux 上で動くシミュレータを配布」という形だったが、環境の整わず参加できない人が多かったようなので、今年は「VM と、それ上で動くシミュレータのコードを配布するから、自前で VM を実装してね」という形になったのだろう。
VM 実装が本題ではないので、VM の仕様はとてもシンプルだった。……のだが。バイナリフォーマットは命令と即値データのペアがズラリと並んでいる形なんだけど、「奇数番地は命令が先、偶数番目はデータが先」という並びになっていた。なぜこんなブービートラップ仕掛けたし。
雑多な感想。
- 最初に "Hohmann problem" でぐぐって何もひっかからなかったので、Hohmann とかはてっきり雰囲気を出すために用意された（中二的）造語か何かだと思ってた。
- 万有引力とかは「りろんは知ってる」状態なので、てきとーに動かしてみるしかやり方が分かんなかった。
- それでも開始 24 時間以内に 1問目が解けたので、たいへんうれしかった。
- "Hohmann transfer orbit" が存在する用語だと気づいたのは、期間の半分が過ぎるころ。そこから 100x, 200x が続々と解けた。もっと早く気づいておけば……。
- VM のコードを毎ステップ解釈してた。何と言う無駄。
- Rubyのコード文字列から Proc を生成するのってどうやるんだっけ？ 分かんないから eval("lambda{#{code}}") しといた。
- 「VMの仕様がシンプルだから比較的ラクに C のコードに落とせたのでは」と、期間後に思った。
- 「他の人が 2 日間しか時間を使えないところを、オレはニートパワーで 3 日フルに使い倒すぜ！」とか思ってた。
- そしたら、3 日目の朝に親父の車が CRASH したので、衛星を CRASH させて遊んでる場合ではなくなった（心理的に）。
追記
ご心配かけてしまいしたが、親父の CRASH は関係者全員無事でした。
正確には親父の懐具合が無事じゃなくなるような気もするが、深くは気にしないぜ！ まさに外道（と書いてニートと読む）！
>> リアルタイムのメモ
- [27日 03:08]
ICFPC のサイトにつながらない。カウントダウンページを開いてた意味が無い。
- [27日 03:30]
つながった。登録したところ、Team ID が #293 だった。この時間でもう293人も登録してるのかー。
- [27日 03:45]
PDF 読む。なんかデブリ回収みたいなことをするマシン操作らしい。去年のと似てるのかな？
VM の仕様を読む。i番目のinstruction の結果は メモリのi番目に入るっぽい？
- [27日 04:15]
(2.4 Orbit Executable Format)奇数番地と偶数番地で、[命令,データ]の順序が違うとか誰得。
- 偶数: [データ(8Byte)][命令(4Byte)]
- 奇数: [命令(4Byte)][データ(8Byte)]
- [27日 04:27]
まだ課題がわかってない。ダウソしたバイナリは何なんだ。
- [27日 05:45]
やっとわかった気がする。
- ダウソしたバイナリがコードで、
- アクチュエータへの入力をオレが決めて、
- その入力を使ってバイナリを実行した結果(trace)をうｐするんだって。
- [27日 05:53]
ねる。
- [27日 11:14]
おきったー。
- [27日 12:04]
VMはcode生成していろいろ最適化、とかやりかけてたけど、そういう小手先のことをやるのをやめおく。まずはベタに動かして通ってからにしようぜ。
- [27日 16:00]
とりあえず動かしながら考えよう。早すぎる最適化は諸悪の根源。
- [27日 17:30]
atan2() って y が先だった！！
- [27日 21:58]
1001 から解ける気がしない。900 step でたどり着けないんすけどー。
- [27日 22:02] (6.1)
To successfully complete this task, the satellite must remain in within 1km of the target orbit radius for 900 seconds.
これってもしかして、目標とする軌道（の1km以内）に900秒間留まれって言ってるの？ 900秒以内にたどり着け、じゃなくて？
- [28日 00:51]
1001 で初めてプラスのスコアをげっと！！！ さて、traceをどういうフォーマットで書き出せばいいのか、説明を読むか。
- [28日 01:04]
osfファイル（trace）を出力するやつができた、ので、1001 の結果をうぷったー。「Successfully uploaded trace solution for scenario # 1001!」結果はいつ分かるの？
- [28日 01:27]
「CRASHED!」って出てた。出力フォーマットを間違ってたようだ。
- 省略したら前ステップと同じ入力を与えたとみなす。
- 最終フレームはスコアが出たステップ。
- 最終フレームのport mappingは空にする。
ということらしい。修正。
- [28日 01:37]
再提出も、はいはい「CRASHED!」。自分で出力した osfを読んで、自前のVMで走らせてみよう。
- [28日 02:43]
通った！！0x2(��Vx)と0x3(��Vy)だけ入力して、0x3e80 にシナリオIDを入れてなかったお(^ω^;;
- [28日 04:07]
PDF に書いてある得点式と、VM が出す得点が全然合わない。faq を見てみたところ、100x には燃料使うほど得点が高いというバグ（？ faqでは仕様だと言ってるが）があるそうな。
つーことで、わざと燃料使いきれば高得点。姑息。
- [28日 06:40]
寝れないので起きる。VMを速くすべき？
- [28日 14:03]
id:ku-ma-me さん(*1)経由で Hohmann 用の式(*2)を知る。（手動）二分探索とかしてたのがアホみたいだ。
- (*1) http://d.hatena.ne.jp/ku-ma-me/20090628/p1
- (*2) http://en.wikipedia.org/wiki/Hohmann_transfer_orbit
- [28日 15:10]
残った燃料を使い切るようにして、とりあえず 100x は終了。全員のスコアボード(*1)とか最初からあったっけ？
100x の 4問を解いて、Score 382。4問しか解けてないグループでは 2位タイっぽい。
(*1) http://icfpcontest.org/scoreboard.php
- [28日 15:27]
VMいじりをためそう。
- [28日 16:13]
毎ステップ、バイナリをデコードしてたのを、・あらかじめcode生成して・eval("lambda{#{code}}")しといて ・それを評価するようにするだけで7倍速とか半端ねぇ。さっさとやっとくべきだった。
- [28日 16:42]
今になって sx, sy が「地球からの距離」じゃなくて「地球への距離」なことに気づいた。つまり符号が逆。どおりでいろんな場所で謎のマイナスをつけないとキチンと動かなかったわけだ。わはは。
- [28日 17:43]
200x は別軌道上の別衛星の1km以内に留まる問題。100x は軌道半径だけ合わせればよかったけど、今度は偏角も合わせる必要がある。
書いたコードの概略。基本動作は2パス。
- test_run
- 開始時点の（自機とtargetの）角度差を th0 とする
- 100xの要領で軌道を変更する。
- 変更後の角度差 th1 を求める。
- real_run
- 偏角差が th1-th0 になるまで、何もしない。
- 自機とtargetは軌道半径が違うから、角速度が違う。よって何もせずとも偏角差がそのうち th1-th0 になる。
- あとは test_run と同じ要領。
100x よりシビアなので、到着後の微調整が必要だなあ。
- target との位置差の分、速度を上げる。
- 1step後、上げた分を戻す。（これで位置が前回のtargetとほぼ一致してるはず）
- target との速度差の分、速度を上げる。（これでほぼ同じ運動をするはず）
- [28日 17:52]
2001, 2003, 2004 は通った。（異様に点が高い気が？？）
2002 は CRASH といわれてビビったが、よく見たらローカルでも -1.0 点だったのである意味安心。
単にステップ数が足りてなかったみたいだ。軌道を合わせるのに38000ステップくらいかかるのに、20000ステップで打ち切ってた。
- [28日 18:04]
2002 も通った。
43rd score:1092.1160 ID:yowa solved:8
- [28日 18:05]
300x を読む。200xと似た問題だけど、自分もtargetも任意の楕円軌道だそうだ。
思いついたのは、
- まず target の時刻→位置を記録しとく。
- 自分を強制的に円軌道にして（径の長さから速度を求める）、
- 半径差と掛かる時間がうまく合うやつを探索する（軌道合わせにかかる時間は公式があった気が）。
- あとは 200x の要領。
とゆー方法だけど、強制的に円軌道にする fuel は足りるんだっけ……？
- [28日 19:50]
3001-3004は、ぱっと見、自分は最初から（ほぼ）円軌道のような気がする。
- [29日 02:35]
300x は自分が円軌道であることを前提にした。
200xと似たやり方だけど、楕円軌道だと半径と角速度が一定ではないからめんどい？
- てきとーな時点 t1 で合流すると決め打って、そのときの target の径を r1 とする。
- (test_run:1) ちょい待った後、自機を半径 r1 の円軌道に飛ばす（200x のやり方）。
- その後、時刻 t1 での角度差をメモる。
- (test_run:2) 待つ時間をちょい変えて、test_run:1と同じことをやる。
- メモってた待つ時間と角度差から、ほどよい待つ時間を計算。
- それを元に本番。
みたいなやり方で、3001,3002,3004 はクリア。
3003 は target がチョー長い楕円軌道で、軌道を一周するのに 160万ステップくらいかかるっぽい。
オレの VM だと 160万ステップに4分くらいかかるので何度もトライするのがめんどいな。
- [29日 8:00]
オレ的に期間終了。
- [30日 3:00]
期間終了。
>> 参加者ブログなどを見て回り
気づいたところで。
参加してそうな人はわかっても、チーム名がわかんないんだ！
期間中に、はてブのタグ「ICFPC2009」を見てれば、他の人が収集してた情報を横から掠め取ることができてたのか！！！
ルールの悲劇。回答は自動生成しなきゃいけない（手でイジるのはダメ）なのは気づいてたけど、VMを複数回走らせるようなマネもダメだってことはよくわかってなかった。
「試行錯誤していいのかなあ？」と思って FAQ を読んでみたけど、
- Q: Is it possible/legal to clone the VM?
- Q: Will it be possible for our solution to read the input binary multiple times? If possible, it would allow us to run the scenario multiple times within a single run of our solution.
- A: As long as there is a primary VM, cloning it should be fine. Does the solution run only taking into account the output of the primary VM? Running a secondary one to try things out as part of the response to the output is fine (just computation, not cheating or looking inside the primary VM).
とゆーとこにその答えが書いてありそうだったけど英語が読めなかったし、そもそも上位入賞するわけないから気にしないでいた。なので、ソースも送ってない。わはは。
