na_o_ysのブログ

プログラミングなど

ICFPC 2015 参加記

ICFPC2015 にソロで出た。刺激的な三日間でした。

一日目

朝

問題を読む。

ハニカム構造のテトリスの AI を作れば良いらしい。

Ruby でコマンドラインで可視化しながら Qualification Problems の json を読む。

12:00

Problem 1 を単純に左下詰めで提出して、とりあえず正のスコアを取った。

15:00

C++ で AI を書き始める。アルゴリズムの方針は

  • Source から出てきた Unit に対して, Lock 可能位置 (lockable) を全列挙する
  • 評価関数を使って最もスコアの良い lockable を採用する

source の先読みはやらない。 (余裕があれば考える)

17:00

気分転換に外出してゴルフ。

23:00

lockable の列挙ができた。

評価関数 (仮) を作って、それに基いて動く AI ができた。

と思いきや、盤面の実装がハニカムになっていない (矩形になってる) ことに気付いて、ふて寝。

二日目

12:00

ハニカム化ができた。

http://www.redblobgames.com/grids/hexagons/ を参考に、

  • Board は直交座標系で管理
  • Unit の移動と回転の際に, Axial 座標系を介する

14:00

入出力の部分に取り掛かる。

json 入出力は Ruby でやることにした。

Ruby が標準入出力を通して C++ の AI を叩く。

[problem.json] - IO(Ruby) - [answer.json]
                    |
                 AI(C++)

15:00

提出しては 0 点、デバッグ、の繰り返し。

17:00

いくつかのバグを倒す。

半分くらいの問題で正の得点が取れた٩(๑❛ᴗ❛๑)۶

休憩。

21:00

バグが無くならない！

三日目

朝

デバッグ

12:00

デバッグ

15:00

やっと評価関数が作れるぞ。

17:00

でこぼこを少なくするためには、表面積を小さくすれば良い。

各空きマスの周囲の埋マス数に、行番号で傾斜をかけた値を評価値とした。

人並みのスコアになった。

21:00

Qualification 114 位でした。

f:id:na_o_s:20150810223841p:plain

振り返りと気付き

大半の時間がデバッグだったけど、最終的に書いたものが全部動いたので、良かった。

アルゴリズムについて

アルゴリズムに関しては、まだ改善の入り口にも達していない感じがする。

数日かけて実装するコンテストに出たのが初めてで、実装してる間も力不足を感じた。

ビームサーチとか、探索系アルゴリズムを組む練習をしていこう。

デバッグが辛かった

コーディングしてる間は楽しいんだけど、デバッグが何時間も続くと気が狂ってくる。

セブンイレブンで甘い物仕入れて食べてた。糖分を取ると集中力がウソみたいに上がる。

チームで出たい (重要)

チームだったらあれもこれも出来るのになーと思いながら開発していた。

AI に関しては方針の相談とか、デバッグのお手伝いとか。息抜きとか。

あと開発の補助的な部分が多分とても大きくて、

  • AI のバージョン管理、スコア管理ツール
  • ビジュアライザ・シミュレータ

など、あるのと無いのでは効率が全然違うが、ソロだと作ってる暇が無い。

クラウド環境が欲しかった

AI によっては問題を実行する度に 5 分くらい待ち時間が出て、めんどうだった。

AWS でスーパーマシンを用意しておくと捗ると思った。

楽しかった

今年に入ってから、開発合宿に何度か行ったり、数日根詰めて開発する機会が多い。

短期集中で目に見えるものを作ると達成感があるし、なんとなく、集中力の幅が広がる気がする。

長期間で大きなことをするのが苦手な性格っぽいので、こういう機会を大事にしていきましょう。と思った。

お疲れ様でした！