Hatena::Grouptopcoder

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

2017-08-07ICFPC2017

ICFPC2017の参加記録です。以下、nodchipの主観で書いているため、事実と異なる点がある可能性があります。

チームメンバー

今年は現在の同僚・前職の同僚・コンピューター将棋関連の知人の計6名で参加しました。

(辞書順・敬称略)

問題概要

periaさんのTweetを引用します。

タイムテーブル

1日目 20:00頃
  • 会場到着。あまりにも豪華な会場だったためメンバー全員ビビる。
1日目 21:00~
  • コンテスト開始。なかなか問題文が公開されない。
  • 問題文公開とともに日本語訳開始。序文を翻訳している間に他のメンバーが問題を読み終える。
  • 翻訳が面倒になったため放置。他のメンバーに問題文を教えてもらう。
  • どうやらグラフ上のエッジを取っていって、ラムダ鉱山からの道を引いていくゲームらしい。
  • 勇み足ぎみにゲームのデータ構造を書き始める。
  • コンピューター将棋い精通したメンバーが多かったため、命名パターンはやねうら王に似せた。

  • 基本データ構造「Position」が完成。Positionを指し手データ構造「Move」に従って更新するPosition::do_move()を実装する。

  • 評価値を計算するEval::evaluate()を実装した。全計算しているので遅い。
  • プレイヤーに取られていないエッジの集合を表すデータ構造を実装。大分前のマラソンマッチで使ったデータ構造の流用。
1日目 00:00~
  • 連結成分をの管理にUnionFindを使った。
  • 指し手を一手戻すPosition::undo_move()を実装するためUnionFindのundoの方法を調べる。
  • 普通に見つかった。縮退をさせず、unionSet()したときに更新された値を全てスタックに保持しておけば良いらしい。
1日目 03:00~
  • 基本ライブラリのパフォーマンスベンチマークを作った。
  • CodeXLを使ってパフォーマンスプロファイルを取ってみた。ベンチマーク自体が一番遅いことが分かった。無かったことにした。
  • メンバーのアドバイスのおかげで、Eval::evaluate()の差分計算の方法を思いついた。
  • 追加するエッジeの両端srcとdstについて、srcを含む連結成分内の全ての頂点とdstを含む連結成分の全ての鉱山の直積集合をとり、それぞれについてスコアを足していけば良い。srcとdstをひっくり返して同様に計算する。
  • 各プレイヤーが取ったエッジからなるグラフを追加で持たせてやれば、時間計算量はならしでdo_move()一回につき鉱山の個数になる(はず)。
  • 就寝…
1日目 08:00~
  • データ構造が色々とバグっているので修正した。
  • undoをしなければならないデータ構造ってバグりやすい気がする…。
  • これっていちおう永続化データ構造と言えるのだろうか…。
  • メンバーがオンラインモードの出力をゲームサーバーとつなげる仕組みを作ってくださったのだがWindowsで動かなかった。
  • 仕方なくC#で再実装した。
1日目 12:00~
1日目 15:00~
1日目 18:00~
2日目 12:00~
2日目 15:00~
3日目 21:00~
  • AI調整
3日目 00:00~
3日目 09:00~
  • 仕様変更…。
  • Moveデータ構造を変更し、splurge・optionに対応できるようにした。

3日目 12:00~
  • Moveデータ変更に伴うビルドエラーの修正をした。
3日目 15:00~

3日目 18:00~
  • ヴィジュアライザで遊ぶ。
  • optionが正しく処理されていないバグを発見…。
  • デバッグ…。
3日目 21:00~

総括

  • 最後に重大なバグが発覚したのが痛かった。次回参加するときはQA体制を充実させたい。
  • 最終的にsubmitしたAIは各頂点のスコアの期待値を計算してGreedyに取るというものらしい。反復深化平均最大化法より強かった。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20170807