ICFPC2012参加記
チームW88FでICFPC2012に参加しました． チーム名は東工大の西8号館8階に集まってやってたから．
メンバーは自分と@Mi_Sawa，@tokoharu_sakura，@wand125，@eagletmt，@draftcode，@choro3，ymzk． 当初はwand家でやる予定だったけど，ゼミ室が使えることになったのと人数が多いのとで学内開催になりました．
以下，だいたい時系列の記録． 自分以外の人が何やってたかあまりちゃんと分かってないので，自分のやったことが中心です．
記録以外の感想は 日記へ ．
初日
20時くらいからgithubにリポジトリ用意したりして待機． 21時になって問題を読む． 今年の問題はLambda Lifterという名前で，自分は聞いたことなかったけどその道では有名な概念らしい． 下向きに重力のかかっているフィールドを歩き回ってλを回収する． 地面を掘ってると岩が落ちてくることがあって，これに当たると死亡．
最初は死亡判定が鬼門だった． 自分の上のマスに岩が出現するような状態だと死，ということをWeb Validatorにいろいろ入力食わせたり仕様書を読み返したりして納得する作業をした．
で，1時間以上かけて仕様を把握． よく見るとマップの大きさは最大で1000×1000とか書いてあってやばい感じが漂っている． まあ最初から最大ケースを考えてても仕方がなく，この時点でできるのはAI考えるかシミュレータ書くか手作業で問題解くかなので，自分はRubyでシミュレータを書くことにした． 適当にガシガシ書いてそれっぽいものが完成． その間に@eagletmtが反復深化でAIを作っていたようなので，じゃあこっちも書いてみようと思ってRubyで適当に実装． 一応書き上げたけどこれ以上の発展が思いつかないので方針を変えてA*っぽいものを実装したり，謎のヒューリスティック関数を作ったりしてた．
そんなことをやりつつWeb Validatorをリロードしてみたらテストケースが突然増えててびびる． なんか水位の概念ができて溺死するようになるらしい． 水中でHPが減るタイミングと死亡判定のタイミングが仕様書からはよく分からないので，実行委員の悪口を言いながらWeb Validatorにいろいろ入力を投げて境界条件を洗い出し，@eagletmt，@draftcode，@Mi_Sawaと議論して処理フローを推測した． 条件さえ分かってしまえば実装は楽なのでさくっと実装． このへんで力尽きて SamurAI Codingのルール 読んだり適当な探索アイデアを口走ったりしながら寝る(この時点で7時くらい)．
2日目
10時に起きて，A*のヒューリスティック考えながらシミュレータいじる．
この日は #w8hack
がゼミ室で開催されてたので流れで参加した(と言ってもICFPCやってるだけ)．
ヒューリスティック関数はパラメータいろいろいじっても一定以上良くならず，Beam
Searchにして状態数を減らしてもあまり改善しないのでシミュレータいじるほうが楽しくなってくる．
どうにかしてnethackみたいにコンソール上で打鍵に即座に反応して操作できるようにしたいなー，でもcurses使うとWindowsで動かないしなーと思って調べてたら，Rubyでも
require 'io/console' とするとWindowsの getch()
みたいなことができるようになるらしい．
これを使って手動でさくさく解くためのゲームモードを実装．
夕方ごろにICFPCのMLが一気に届いて，その中にパズルっぽい自作問題へのリンクがあったので遊んでみたり，@wand125の生成した迷路面をAIに食わせてBFS弱いなーという確認をしたりしていた．
その後は#w8hackの打ち上げでピザ食べて，自分は特に進展なく1日が終わる． この時点で@eagletmtの探索が結構良い感じだったので，今後はこのAIを改良すれば良いんじゃないかという感じになってくる． あとλを塊でクラスタリングして巡るようにするといいんじゃないか，とかフィールドの更新は直前に変化したとこの8近傍だけ見れば十分だから高速化できるんじゃないか，とかそれHaskellだと遅延評価で高効率にできるよ！みたいな話をしていた． Lightning Roundは@eagletmtの反復深化探索を投げた．
3日目
朝起きたらTrampolineとBeard and Razorなるものが追加されてた． Trampolineはワープゾーン，BeardとRazorは増える壁とこの壁を消すアイテム． どうもNested Functionの実装にTrampoline使ってたり，関数型言語の偉い人がヒゲの人だったりするらしい． ギャグなんだろうけど元ネタがわからないのでアレ． 仕様書からリンクの張ってある トランポリン動画 が大変シュールだった．
不確定要素が一気に増えたことで単なる探索ゲーの様相を呈してきて，クラスタリングとはなんだったのか……という感じになってめげそうになりつつ大学に向かう電車の中でTrampolineを実装． 大学に着いてからBeardとRazorの実装を開始するも，Beardが伸びる場所に岩が落ちてくるとどうなるのかという問題が……． 仕方ないのでまたWeb Validatorにいろいろ食わせて仕様を解析する．
このへんで@wand125が自動生成した迷路面やnethackみたいなダンジョン面をコミットしたり，@draftcodeがタイムアウトを計りながらAIを動かす評価用スクリプトを作ったりした． CoffeeScriptで生成された面をPythonがC++に食わせて出力をRubyが検証，採点というよく分からない環境が出来上がる．
BeardとRazorの実装が終わったところで集中力が切れたので晩飯食べて，広いマップ用に幅優先探索で直近のλを取りに行くコードを書く． とりあえず岩の近傍のうち下方3マスに入らなければ死ぬ可能性は低いだろう，と見てそこを避けるような経路でλが取れるなら取りに行くようにしたら案外うまく行った．
この実装が終わってしばらくして，新しい仕様追加のメールが来た． Higher Order Rockなる，落とすとλになる岩が見つかったらしい．なんだそれ． 落とすとλになるくせにロボットに当たると死ぬとか微妙に面倒くさい仕様で，エンバグしながらシミュレータを書く．
その後はやることが尽きたので，@draftcode，@eagletmt，@choro3，@Mi_Sawa，ymzkらが探索方法の議論してるのを見ながらシミュレーションの高速化を図っていた． 前日に話してた通り，マップの中で変化が起きるのは直前に変化したマスの8近傍だけなので，更新はマップ全体をなめなくても一部だけ見れば良い． ただ，実装したらどうも元より遅くなっている． 眠かったし諦めて帰宅．
4日目
9時に起きるつもりが気付いたら10時半だった．
海の日も東工大は授業があるらしく，ゼミ室が使えないという話だったのでwand家でコード書く． 8近傍更新のコードをよく見たらバグっていたので，直したらかなり速くなった．
夕方になって，実はゼミがなくゼミ室が空いてるという話を聞いたので大学へ． サンプルを入れてテストしていたらC++コードもRubyコードもシミュレータが怪しげな挙動をしていたので，いくつかのバグを直す． そんなことしていたら21時が近くなったのでtgzに固めて提出． とりあえずREADMEにアルゴリズムの説明でも書くか，となったところで前日に書いた幅優先探索を入れてないことに気づく(元はRubyで書いてたのを提出用のC++コードに移植し忘れてた)．
お疲れ様でした．