ICFPC2011参加記録

例年のごとく一人で参加。

時刻は全てUTCで

17日

  • 00:00 問題が公開されたので読む。予想通り殴り合いゲーだ。
  • 01:00 大体問題を理解したので、インタープリタを書き始めてみる。言語はOCamlを選択。というかこれ以外に選択肢がない
  • 03:00 電車で会社に移動しながら戦略を考える。最大のダメージを与えられるのはゾンビなのが分かる
  • 04:00 インタープリタの続きを実装
  • 10:00 このころにはインタープリタはできてたはず。SKIの使い方を考え始める
  • 11:00 無限ループを参考に、S(get)(SK(dec))0が無限dec 0であることに気づくが実装できない。
  • 12:00 S(Kx)yz = x(yz)に気づく。無限dec 0の動作を確認する。
  • 13:00 lazyを発見する。これにより動的にgetできるようになる。
  • 14:00 電車で帰宅。作戦を考える。
  • 15:00 ほぼ部品は整ったので、最初のAIの作成にとりかかる。作戦はすぐに決まる。
  • 21:00 最初のAIが完成する。送信。風呂って寝る。

18日

  • 09:00 活動開始。今のリスト再生AIを拡張するのは無理なので、書きやすい記法を考えようとする。
  • 10:00 モナドが最適なことが分かる。OCamlで書こうとするがいまいちしっくりこない。
  • 11:00 OCamlの型システムと演算子定義がクソだからいけない。そういえばYnotのモナドはかっこよかった。Coqで書いてOCamlに抽出すればいいんじゃね？
  • 12:00 Coqでコード書くのたのしいお

19日

  • 12:00 いつのまにか一日たってた。眠くてしかたがない仮眠してAI書こう。
  • 15:00 AIを書こう。
  • 23:30 結局AIを書き終えられなかった。しかたないので急いで提出

詳細

https://github.com/kik/ICFPC2011

インタープリタ

ゲーム中に存在する全ての値を

type value =
  | ValNum of int
  | ValI
  | ValSucc
  | ValDbl
  | ValGet
  | ValPut
  | ValS
  | ValSf of value
  | ValSfg of value * value
  | ValK
  | ValKx of value
  | ValInc
  | ValDec
  | ValAttack
  | ValAttacki of value
  | ValAttackij of value * value
  | ValHelp
  | ValHelpi of value
  | ValHelpij of value * value
  | ValCopy
  | ValRevive
  | ValZombie
  | ValZombiei of value

といった感じで、完全に記述できる型を用意するのが常識だと思っていたんだけど、まわりのコード眺めてるとそうなってなくてびっくりした。

最初のAI

https://github.com/kik/ICFPC2011/blob/d67edcf101921b1fe72f449799b479cc9c6d8a1a/src/kamaboko.ml

まず、全力で5000と10000を作る。5000で三回攻撃して255を倒す。

次に、255をゾンビ化して0を速攻で倒す。
ゾンビ化のコードを引数つき永続化版にする。
succ zombieを繰り返す

何もしないAIは650ターンで死ぬ。動くこと優先で書いたのだが、この時点ではかなり速かったらしい。
helpで倒すようにすれば256ターン減らせるので、すでに最速の2倍ちょいくらいにはなっていたらしい。