Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2012-07-16

ICFP Programming Contest 2012 02:00 ICFP Programming Contest 2012 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - ICFP Programming Contest 2012 - nodchipのTopCoder日記 ICFP Programming Contest 2012 - nodchipのTopCoder日記 のブックマークコメント

ICFP Programming Contest 2012 (http://icfpcontest2012.wordpress.com/)に参加しました。

チームメンバーは@peria @henshiru @tzik_tackの4名で、チーム名は「oyososan」です。チーム名の由来はもちろん(?)円周率です。

自分視点で書いているためメンバーの活躍の描写が疎かになってしまっていますが、ご了承ください。

作業1日目 21:00

@nodchip・@periaさん・@henshiruさんの三人で会社の休憩室を選挙してコンテスト開始。

レポジトリにgitを使用することを決める。

問題の内容はとても簡潔で理解しやすいもの。

ロードランナーとかミスタードリラー的な何かを感じる。

作業1日目 23:00

とりあえずシミュレーターがないことには始まらないので@nodchipが書き始める。

ここらへんで@tzik_tackさんが合流。

作業1日目 24:00

後のことを考えて@periaさんがリファクタリングを開始。

UbuntuMacWindowsのいずれでもビルドできるようgypを導入。

@nodchipはWindows + Visual Studio使いなので肩身が狭い。

Windowsからgypを叩くとVisualStudioのソリューションファイルを生成してくれるのだが、

デフォルトがDebugビルドとなっており使いにくいので放置。

@periaさんは遊びやすいようにHTML+jsでシミュレーターを実装した。

作業2日目 12:00

恒例の仕様追加。

@henshiruさんがfloodの追加実装を始める。

@nodchipは2セル間の経路を求める必要が出てくると考え、

幅優先探索による経路探索ライブラリを書き始める。

この時は後にこのライブラリが魔改造されていくとは夢にも思わなかった。

作業2日目 15:00

@henshiruさんがシミュレーターの単体テストを追加。

これが後々大きく影響してくる。

@nodchipは幅優先探索ライブラリを書き上げ、

ラムダをランダムに取得する適当AIと組み合わせて簡単な盤面を解くことに成功。

@nodchip大はしゃぎ。

@tzik_tackさんとAIで遊び始め、どうしても解けない盤面を探し始める。

解けない盤面については経路探索ライブラリに

盤面の局所パターンマッチングによる禁止処理(ハック)を加えることで

解けるようにして行った。

その他、@tzik_tackさんは手動プレイ用のインターフェースの整備。

@henshiruさんは単体テストを拡充しつつWaterの実装。

作業2日目 18:00

@nodchipが取得するラムダの順序を焼きなまし法で調整するライブラリを書き始める。

ここで、焼きなまし法で取得するラムダの順序を決め、

ラムダ同士を幅優先探索で最短経路でつなぐという基本戦略ができた。

@tzik_tackさんにより単体テストの他に品質テストが追加される。

品質テストは、解けて欲しい局所盤面のテスト郡。

@nodchipが経路探索ライブラリに一定の確率で岩の中を突き進む(!)というハックを導入。

この時点では経路探索ライブラリは計算量を下げるために岩を壁として扱っていたため、

岩を押して経路を作るといったことが出来なかった。

ここで向こう側が空白となっている岩を一定確率で透き通るというハックを入れることにより、

その後の精密シミュレーションで正しく岩が押せているという条件付きで、

岩を押す経路を通ることができるようになった。

これにより一部のマップで得点が上がった。

この後も一定確率でほげほげするというハックで得点を上げていくことになる。

@henshiruさんがlightning round用のパッケージを作成、提出した。

夕食へ・・・。

作業2日目 21:00

@periaさんがリファクタリングを続行。

@nodchipが書き散らしたゴミコードを片っ端から整形していく。

感謝に耐えない。

@periaさんが速度向上のための、プロファイラーを準備し、

シミュレーターの高速化に着手。

この日はこれにて終了。

作業3日目 12:00

恒例の仕様追加。trampoline、beard、razorが追加される。

天気がどうのこうの言っていたのは何だったのだろうか?

シミュレーターに@henshiruさんがbeard&razor、

@periaさんがtrampolineを実装。

@tzik_tackさんが部分updateによる高速化を実現。

@periaさんがリファクタリングを続行。

作業3日目 15:00

@henshiruさんが品質評価用スクリプト、

@tzik_tackさんがweb上のvalidatorとの動作一致確認補助スクリプトを導入。

インフラ面が改良される。

@nodchipが岩に埋まって終了する場面に対するハックを入れて得点を改善。

@periaさんがリファクタリングを続行。

作業3日目 18:00

@nodchipがtrampolineの経路を経路探索ライブラリに実装。

恒例の仕様追加。岩の中からラムダが生まれてくるらしい。

@henshiruさんがシミュレーターに実装を始める。

一旦夕食へ。

精密シミュレーションの高速化と

チェックポイントの導入について話し合う。

チェックポイントとはラムダ以外で必ず通らせるセルのこと。

特定の位置にチェックポイントを入れることで、

今までのルーチンで通ることのできなかった箇所を無理やり通れるようにすることを狙う。

@periaさんがリファクタリングを続行。

作業3日目 21:00

@nodchipが経路探索ライブラリの岩の中を突き進むハックを改良し、

岩の中を突き進んだら一定確率で、その先の探索済みフラグを立てるというハックを導入。

こうすることで岩を押したあと、その岩を回避して進むという行動をエミュレーションできるようになる。

このハックは確率的に正しい動きをする。

誤った動きをした場合は、後の段の精密シミュレーションで弾かるので無問題。

@nodchipがチェックポイントの実装を終える。

局所パターンマッチングでチェックポイントをしかけるようにし、

contest9の岩を落とさなければ通れない部分などが無理やり通れるようになった。

@periaさんがリファクタリングを続行。

@nodchipの経路探索+trampolineルーチンに範囲外アクセスバグがあることが判明。

とりあえずの回避ハックを入れてお茶を濁す。

作業3日目 24:00

@nodchipがliftを上から塞ぎそうな岩の近くにチェックポイントを設置するハックを導入。

いくつかのステージでスコアが上がるが、

肝心のtrampoline1は経路探索ライブラリがバグっているのでスコア不明。

@periaさんがリファクタリングを続行。

@nodchipが横方向に通せんぼをしている岩の左右にチェックポイントを設置するハックを導入。

trampoline2がクリアできるようになる。

@henshiruさんが継続的ビルドインフラ及び、

各マップの成績をGoogleスプレッドシートに定期的にアップロードするQAインフラを整える。

これが終盤まで活躍する。

本日はお開き

作業4日目 12:00

@nodchipが経路探索のtrampolineの無限ループバグを修正。

原因は行き先が2以上のトランポリンが1つのターゲットを指している場合に、

のトラックバック経路が合流してしまっていたこと。

探索済みフラグの処理を修正して対処。

@periaさんが精密シミュレーションにrazorの処理を追加。

ひげがそれるようになる。

作業4日目 15:00

@nodchipがhorockの周囲にチェックポイントを仕掛けて無理やり落とすことを画策。

そこそこうまく行く。

@nodchipが岩に埋もれて動けなくなる盤面で、

予め掘っておけば履い出せるようになるような土をチェックポイントに入れるハックを実装。

contest2とflood2がクリアできるようになる。

機械が盤面の学習をするようになった記念すべき瞬間。

@periaさんがリファクタリングを続行。

@henshiruさんがプログラム起動フラグを実装。

どうして今まで誰も実装しなかったのか・・・。

@tzik_tackさんがSIGINTをハンドルするコードを追加。

@henshiruさんが適当にチェックポイントをばらまくコードを追加。

contest9がクリアできるようになる。

作業4日目 18:00

@nodchipがlift付近にチェックポイントを追加。

flood4の成績が微妙に上がる。

@periaさんがリファクタリングを続行。

@henshiruさんが大きいマップで行動を制限するコードを追加。

大きいマップでTLEやMLEしにくくしたが、

成績はそれほど良くないと思われる。

これは仕方ない。

@nodchipが横にあるラムダをとりあえず取りに行くハックを追加。

horock2の成績が僅かに上る。

@nodchipが@periaさんのchangeをrevertしてしまう痛恨のミス。

ただただ平謝り。ごめんなさいm(_ _)m

@periaさんが過去ログから手動パッチして修復。

@henshiruさんが最終版をパッケージングして提出。

これにて終了。

結果

手元での実行結果は、得点の総和/validatorのハイスコアの総和=87%くらい。

この問題でこれだけ取れていれば、自分的にはかなり満足です。

自分の書き散らしたコードをリファクタリングし続けて下さった@periaさん、

シミュレーターから開発インフラまで幅広く担当して下さった@henshiruさん、

重要な局面で様々なアイデアを下さった@tzik_tackさんには頭が上がりません。

本当にありがとうございました。

付録・ICFPC2012語録

  • @henshiru 「kill nodchip」
    • 何故かバイナリ名がnodchipであり、SIGINTトラップのためにCtrl+Cが使用不可能になっていたため"kill nodchip"してくださいということになった。ひどい。
    • これを聞くと https://twitter.com/kinaba/statuses/16758328558 を思い出す。
  • @henshiru 「あと5時間保てばいい」
    • ソースコードが汚すぎてこれ以上保守が難しくなった時に@henshiruさんが放った一言。コードを汚した主な原因は自分です。すいません。
  • @tzik_tack 「Split out brain from nodchip」
    • リファクタリングでプログラムのエントリポイントからAI部分を別ファイルに移動させた際のgitログ
  • @peria 「コーディング規約なんてない」
    • 全員が思い思いにコードを書き進めた結果、コーディング規約なにそれおいしいの的な状態になった時の@periaさんの一言。3日間、よくコードが崩壊しなかったものだと思う。
  • 「ポンポンペイン」
    • 誰が言ったのか覚えていないのですが、印象深い一言でした。
  • @tzik_tack 「頭痛が痛い」 @nodchip「どっちがですか」 @tzik_tack「両方です」
    • 作業3日目の夜の一コマ。実装で頭を抱えつつ、リアルに頭痛がしてくる様子。
  • @henshiru 「@nodchipさんが野生の勘でハックを入れまくった」「論理的に証明できませんよね?」「でも点数が上がってるんですよ」「感動した」
    • 今回自分が入れたハックは殆ど勘で入れたものです。generalな解法じゃないのでかなり心配です。
  • @peria 「なんでこれで解けるのか分からない」
    • 自分が入れたハックに対する一言。内容を説明したところ納得してくださいました。
  • @nodchip 「ゲームパッドありますか?」
    • キーボードでの試遊に疲れて放った一言。JoyToKeyと組み合わせてゲームパッドで遊べるようにしてみました。
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20120716
 |