マラソン頑張りました (TopCoder Open 2013 MM R3参加記)

TopCoderにはマラソンマッチという部門があります。
基本的に”最適解”は求まらない問題が与えられて、できるだけ”ベターな解”を求めるプログラムを書いた人が優勝です。
期間が長いのも特徴で、今回は2週間ありました。
今回の問題はこんな感じ。

平面上に円がたくさん置いてあるので、お互いが重ならないように円の位置を修正してください。
ただし、円にはそれぞれ重さがあって、動かすには(重さ×動かした距離)のコストがかかります。このコストの合計が低ければ低いほど良い解とみなされます。

tco13mmr3-1

今回の問題はTopCoder Openという大会の一部で、4位までが秋にワシントンDCで行われる決勝に招待されて、文字通り世界のトップコーダー達とキャッキャウフフできます。

成績

自分の成績ですが、予想外にも14日のうち7日目辺りから1位争いを始め、13日目まで1位と僅差の2位につけてました。まさかの初参加で決勝進出かと夢を見ます。
tco13mm3-2
初参加の日本人が上位にいるぞということで、こちらから一方的に知ってるだけだった人たちに期待してもらって嬉しい思いをしたり。
そして迎えた最終日。最終的な順位はこうなった。

知ってた！
そんな甘いはずないですよね…

解法概要

剛体シミュレーションによって制約(重なってはいけない)を満たし、円の元々の位置への引力と振動を与えることで局所改善を行った。
初期配置は密度の高い円から順に距離0の位置に配置した上で、配置済みの円の合計面積がある程度(0.75-1.15)以上になれば残りは大きく外側に離した位置からスタートする。
初期配置を決めるパラメータはある程度見込みのない値は学習するが基本ランダム。(ソース)

活動記録

思い出としての気持ちの記録と作業記録をごちゃまぜ箇条書きで。

準備フェーズ(1日目)

問題どこで見れるのか分からない。30分右往左往する。
とりあえず1回提出してみよう。適当に円が重ならなくなるまでじわじわ外に動かすプログラム書いてsubmit。ちゃんと点数が付いた。思ったよりとっつきやすい。
プログラムの実行状況を絵的に表示するプログラム(ビジュアライザ)は、自分で作るなり改造するなりした方がいいと聞いてたので、前から気になってたCinderを使って実装した。楽しい。
公式のTesterを介さなくてもテスト走らせられるよう、テストケースを2000件ほど抽出しておく。

考察フェーズ(2日目)

以前wataさんに「マラソンのコツはコードを書かないこと」というアドバイスをもらったのを思い出し、コードから離れて問題の性質について考えてみる。
2つの円が重なってる状況とか、1つの円が3つの円に囲まれた状況とか、小さい局面での最適解を考えたりする。
逆にざっくりした捉え方をするなら、できるだけエネルギーの低い結晶をつくるタスクって感じがする。物理法則が役に立ちそうな気配を感じる。
円それぞれに対して、元あった位置への引力を設定した上で、衝突反発と引力がバランスするまでシミュレーションしてみるって方針を立てる。小さい局面のいくつかでも最適解が出そう。

実装フェーズ(3日目〜5日目)

物理思い出しながらコード書いてみる。カオスな動きで謎にテンション上がる。
だんだんまともに動き始めてきた。スコアは微妙。
重い円は軽い円を弾き飛ばして内側に入ってきて欲しかったんだけど、最初固まりになりすぎてて重い円がうまく引力で内側に落ちてこれてない。
円の初期配置はある程度ばらしたほうが良さそう。ただ適当にばらすんじゃなく、小さくて重いやつを優先的にいい位置に配置したいので、密度(m/r^2)が高い円ほどスタート位置が内側にくるようにする。
このへんで10位以内に。今の方針は悪くなさそうと手応えを得る。

高速化フェーズ(6日目〜7日目)

高速化は終盤にやるのが定跡なんだろうけど、本番サーバの特性知らないのも気がかりなので、早いうちにやっとくことにする。
Example Testのログを使って回ってるループ数測ったり時間かかってる部分の特定をがんばる。
座標などはfloatに丸めてシミュレーションした方が速かったのでそうした。要因未調査。キャッシュヒット率とかかな?(効果: 1.2倍)
基本的なSIMD命令を使用(1.3倍)
ループ内でのメモリアロケーション排除とか、事前計算可能な値は先やっとくとかの基本的な処置(1.2倍)
シミュレーションのアルゴリズム自体の高速化も必要そう。勉強のいい機会なので「ゲーム制作者のための物理シミュレーション剛体編」読んだりBox2Dのソース読んだりする。
一番のネックになってた衝突検出に、本で勉強したSweep and Pruneを2軸で適用する(5倍)
トータルでループ10倍以上回るようになった。
とうとう1位に立つ。うまくいきすぎでは・・・

なんか、みんな潜伏しながら読み合いを楽しんでるのに、僕だけ空気読めてないんでは。とか、麻雀で鳴きまくって怒られた人としては不安になってる。

— フキーニョ (@fuqinho) June 11, 2013

機能追加フェーズ(8日目)

一晩動かした結果のベストな配置を横に表示しながらシミュレーション眺めたりして、より短時間でそこへ到達できるヒューリスティックとか無いか考えたりする。あんま思いつかない。
微妙に効率悪い位置に落ち着いてしまう円があったので、全体を揺らす操作でスコア改善
何度も連続で揺らせばスコア改善が続く場合があったので、過去のベストに近いスコアのときはしつこく揺らすようにしてスコア改善
ベストスコアを更新した時の状態を記憶しておいて、直後悪化した場合に一定回数はUndoして別の操作を試みるようにしてスコア改善
引き続き1位。

チューニングフェーズ(9日目〜10日目)

プログラム中で使っている定数を調整したいけど、テストケースごとの得手不得手考えるとそれぞれの定数値の評価は300ケースぐらいで判断したい。
調整したい定数の種類×定数値の候補数×300ケースの実行は手動ではやってらんない
プログラム起動時に定数値を指定できるように修正して、スクリプト回す。PCがフォーッてなる。EC2借りよう…
借りたのはハイCPUエクストララージインスタンス。大人買い気分。シングルスレッドは手元のノートの方が速かったけど、6並列で頑張ってもらう。GNU Parallel便利だな。
意外にも今まで適当に決めてた値が最善だったって場合がほとんどだった。
2位にはつけてるんだけど、見込んでた伸び代が無いと分かって1位のeldidouさんに勝てる気がしなくなってくる。

悪あがきフェーズ(11日目〜13日目)

今の解は、局所改善に物理シミュを使った多スタート局所探索に分類されるのかな。スタート地点の選び方もっと賢くできないだろうか。
円の初期配置を決めるパラメータについて、ランダムじゃなく焼きなましや遺伝的アルゴリズムを試すも、わずかな効果。シミュ中のrandomnessで凸性が乱されてる感じ?そもそも各種探索手法に慣れてなくて勘所が分からない。
円の初期配置について密度以外の新たな基準試す(初期状態で重なりが少ない円は優先度上げる/これまでの最善配置と重なりが少ない円は優先度上げる等) -> 改善/悪化トータルで誤差程度の影響
円への操作について震わせる以外の新しい操作試す(捻る、広げる、力の大きさを入力に応じて変える等) -> 悪化または有意差なし
今まで調整の対象にしてなかった定数を変えてみる -> 悪化または有意差なし
2位を維持するものの、何やっても無駄な気がする状態に陥る。前半戦で感じてた楽しさを感じられなくなって反省会モードになる。

落胆フェーズ(最終日)

案の定潜伏勢や追い込み勢に抜かれていくのを呆然と眺める。抜き返す気力は悪あがきフェーズで尽きてた。
終了10分前の時点で5位。決勝には一歩届かない。未評価の変更をイチかバチかで入れる。スコアが落ちたのを確認して落ち込みながら終了。
終了後にTL上で行われた感想戦は楽しかった。(参加してない時もそれを見るのは好きだった)

感想

今回成績良かったのは、単純に時間を多く割けたこととか、問題と相性が良かったこととか、colunさんの記事等で事前にある程度心構えができてたことが大きかったと思います。方針もちょっとまぐれ当たりっぽかったかな。
一方、反省点としては終了直後に感じたこのへんがメインかなと。

反省点１：eldidouさんと競ってた時期に、目先の得点が欲しくてパラメータチューニングに走ってしまった。他の実装時間を削った上に、少しコードいじればスコアが落ちる状態になって身動きとりずらくなった。

— フキーニョ (@fuqinho) June 19, 2013

反省点２：自分の方針について何がうまくいってて何がうまくいってないのか、理論付けを怠った＆諦めてた。後半場当たり的な思いつきに頼るしかなくなって、それらはうまく行かない上に得られる知見も少なかった。

— フキーニョ (@fuqinho) June 19, 2013

１は単純に時間の使い方間違い。仕事できない人っぽくてやばい。
２は重い感じがしました。ちゃんと理屈付けながら進めるための基礎力が不足している感は否めないんだけど、今の姿勢でやっててもその基礎力が着くことは無さそうなので次参加する時は強く意識しときたいです。

マラソンマッチについては、期間中使える道具はなんだって使える分新しい道具や技術に触れるきっかけになりそうなのと、解が正解/不正解じゃなくどの程度優れているかで評価されるので競争相手がより強く意識されて、短時間コンテストとはまた違った魅力を感じました。次回の具体的な目標も定まったので、また時間作って参加したいなと思います。