ICFPC 2017 に参加した

ICFPC 2017 にチーム「ゲームセンターYAGI」として参加しました。メンバーは以下の4人です。

リポジトリhttps://github.com/seikichi/icfpc2017 です。

今年の問題

無向グラフが与えられます。 このグラフの頂点は都市鉱山のいずれかを表していて、辺はを表しています。

このゲームの目的は、川の領有権を主張(claim)して、各鉱山をできるだけ多くの都市と(川によって)繋げることです。

各プレイヤーは自分のターンに以下のいずれかの行動を行います。

  1. 他人によって claim されていない川をひとつ claim する。
  2. パスして「claimする権利」を1貯める。
  3. 溜まっている「claimする権利」を全て消費して、溜まっている権利数+1本の連続する川を claim する。

所定のターン数が経過するとゲームが終了し、各プレイヤーのスコアが以下のルールによって計算されます。スコアが最大であるプレイヤーが勝ちです。

  • 全ての都市 S について、以下を計算して合計する。
    • S からそのプレイヤーが claim した辺によって到達可能な各鉱山 M について、以下を計算して合計する。
      • M から S までの距離 (claim した辺以外も利用できるときの距離) の二乗

これ以外にも細かいルールが存在しますが、詳しくは問題文を参照してください。

タイムライン

1日目

  • 21:00 コンテストスタート。コンテストサーバが落ちる。

  • 21:08 問題文を入手する。

  • 21:40 問題文を大体読み終えたので、実装に入る。

    • 1人がシミュレータを書いて、1人が CI を整備し、残りの2人が AI を書くという分担になった。
  • 23:00 タイムアウト付きの spawn の実装に嵌まる。

    • fread(buffer, 1, sizeof(buffer), file) と書くべきところを fread(buffer, sizeof(buffer), 1, file) と書いていたのが原因。悲しい。
  • 00:04 ようやく spawn のテストが通る。ここからシミュレータの実装に入る。

    • JSON をパースしたりダンプするのが面倒くさい。心を無視にして実装していく。
    • シェルスクリプトで AI を作るとタイムアウトしたときに親プロセスしか殺されず、子プロセスが残る問題を見つける。プロセスグループを使って kill するように spawn を修正する。
  • 03:30 セットアップフェイズまで実装完了。ライブラリの整備も進む。

  • 03:40 寝る。

  • 10:30 起きる。

  • 11:20 シミュレータに GamePlay フェイズを実装。

  • 11:30 昼飯を食べに行く。

  • 15:00 Scoring フェイズを実装。これで一応シミュレータが完成。しかし、シミュレータを作っている間にプロトコルが破壊的に変更されていたので、これに対応しないといけない。

    • 今までは入力を一個入れると出力が一個あるようなインターフェイスだったので、普通の spawn のインターフェイスで何とかなったんだけど、新しいインターフェイスでは、ハンドシェイクを先にやる仕様になったのでこれが使えなくなった。
    • 破壊的に変更を “small change” って表現するのやめてほしい。
  • 17:00 新しいプロトコルに対応するために spawn とシミュレータを書き直した。

  • 20:00 貪欲AI (毎ターン、合法手の中からスコアが最大になるような手を選ぶ) を書いた。

  • 21:00 貪欲AI に枝刈りを追加して高速化。lightning にはこれを提出した。

2日目

  • 21:30 飯を食べに行く。鯖が美味しかった。

  • 01:00 寝た。

  • 11:00 起きた。寝すぎ。

  • 12:00 昼飯を食べに行く。ラーメン。

  • 14:00 鉱山に近づいていくAIを作った。

    • 最も近い鉱山への距離 (他人が claim した辺は通れないとして考える) を最小化する手を選ぶ。
    • 何をやっても鉱山に近づけない場合は貪欲AIにフォールバックする。
  • 16:30 タイムアウトしそうになったら弱いAIにフォールバックする仕組みを作った。

    • しかしこれはちゃんと動かないことが後になって判明する。
  • 18:00 夕食を食べに行った気がする。

3日目

  • 20:00 初手の選び方を改善した。

    • できるだけ強い連結成分を選び、連結成分の中心に近い鉱山を選ぶ、というヒューリスティック
    • 連結成分の強さは、頂点数×鉱山数で表すことにした。
    • 「連結成分の中心への近さ」は「その鉱山から他の都市への距離の和」で測ることにした。この和が小さいほど中心性が高い。
  • 23:30 貪欲に次の手を選ぶ際に、到達したときにスコアが最大となる未達都市への距離を最小にするような手を優先するようにした。

    • 今までは次の1手のスコアしか考慮していなかったので、将来的に遠くまで行けるパスがあっても軽視されることがあった。
  • 仕事のため、自分の ICFPC ここで終了。

所感

今年は仕事のため月曜日は参加できませんでした。1日少ないとかなり短く感じます。 (普通なら有給休暇を取ればいいんだけど、今年は4週間ぐらい入院したので有給休暇をほとんど使い切ってしまっていたので)

1日目の最初の方はずっと spawn に嵌っていて、2日目もタイムアウトの実装で時間を使ってしまったので、ここらへんをライブラリで済ませられればもっと AI の実装に時間を使えた気がします。 シミュレータは別に提出するプログラムじゃないので、もっと手を抜いて実装すべきだったのかも。

AI の出来はいつもどおりっていう感じです。そろそろもっと高度な探索とかをしたいなー。

あと、そろそろ C++ にも飽きてきたら別の言語が使いたい。 来年は Rust で。