ICFP Programming Contest 2011
日本開催ということで今年は初めて大規模なチームを組んで本気参加
チーム名は"Unagi: The Gathering"で，チームメンバーは
自分，秋葉，いるーん，いもす，hos先生，tos先生
の競技プログラミングに最適化された６人
結果は多分今ひとつな感じぽいけど，問題も自分が過去に参加した中では一番面白かったし，初めてのチーム戦も非常に楽しかった．
一日目
お昼
大学の授業出ながらルールを読む．
どうやらカードゲームのAIを作るらしい．
SKとか出てきてよくわからんのでとりあえず「β 簡約! λカ娘」を読んで勉強することになった．
なんかtwitterで他のチームの人たちが進んでる雰囲気を出していたのでとりあえずブラフでてきとーな発言をしておいた．
夕方
授業後秋葉家へ移動しつつ，妄想上の作戦を色々作った．
このころ作った作戦はあとになってみるとワロス過ぎた．
ゾンビゲーという言葉が聞こえてきたので，とりあえずブラフでputゲーという事にしておいた．
@imos,@ir5と合流して秋葉家へ着いた．
最強の GUI が完成していてテンションが上がる．
関数適用の回数が良く分からないので，decループを作って解析．
decループだと167しか効かないことがわかり，敵を倒すにはhelpループ→attack かーということになった．
とりあえず一体倒さないことにはゾンビゲーもできないので，まずは敵を一体倒すことから始めることになった．
夜
メンバーで唯一関数型が得意な@toslunarが合流．
役割分担を決め，@iwiwiがC++でシミュレータを書いて，他の人は有用そうな関数を作成しておくことになった．
探索とかもしたいので，C++でnewして参照渡しだとメモリリークで死ぬから毎回コピー渡しすることになった．
(f x) (g y) の適用ができないと255番以外への攻撃すらできない…
SKを駆使することで，gがカードの場合はできるようになった．
(f x) (g y) = (S(K(f x))g)y
一般の場合はtos先生とhos先生に考えてもらうことにした．
用意されているインタプリタに打ち込む作業が修行だったのでundo機能とかステップ関数適用とか搭載したGUIでも作るかーと思ってJavaで作りはじめた．
二日目
深夜
パーサ部分は書き終わったので，秋葉さんと一緒にC++とJavaでシミュレータを書いた．
とりあえずブラフでゾンビパウダーが完成したことにした．
いるーんにより相手の255をループdecするだけの最初のサブミットがされた．
シミュレータがゾンビ以外できた気分になったので寝た．
朝
起きたら@hos_lyricが合流していた．
どうやら指数的に大きくなる関数があって，コピーを使っているC++版シミュレータが落ちるらしい．
C++オワコン感が漂ってきてhos先生がD言語でシミュレータの実装を始めた．
C++はコピーやめて参照にし，メモリ管理機能つけて，探索終了時に探索で使ったメモリを解放することにした．
自分はコンボデバッグ用にワンステップずつ関数適用する機能の実装をすることにした．
tos先生によりSK変換器がなぜかHaskellで実装されていて他の人の環境で動かなくて大変だった．
昼
秋葉さんのシミュレータが完成していたので，動作チェックをした．
decループのダメージはltgと一致するのだが，helpループの回復量が一致しない…
C++とJavaでは一致したのでどうやら我々の解釈が間違っているらしい
部分適用もカウントする解釈にしたら一致した．
夕方
昼飯食べに行って，そのままTCOに参加するため一度帰宅．
GUIとかイラネと思って，ltg互換のCUIにして満足した．
コンボ作ろうと思って色々考えたが，getループだと決められた場所からしか発動できないので不動点関数が欲しいなーと思い，SK版の不動点関数をググって調査．
普通の不動点関数だとcall by valueで動かないのでググッて見つけたcall by value用の普通のλ式YコンビネータをSKに変換すれば良いに違いないと思ってλ→SK変換器を実装し始める．
実装班の方はいもすがtos先生のSK変換器をC++に変換して秋葉さんのシミュレータとマージし，まともなAIが書けるようになったらしい．
三日目
深夜
眠さでTCOが壊滅的だったが，とりあえず通過はできたのでよしとしてコンボ考えながら寝ることにした．
が，まともなコンボがいろいろできたのでwikiに書きこんでたら秋葉さんが早く来いというので秋葉家へ出発．
朝
秋葉家へ到着．
helpループ→attackで敵を672ターンくらいで殲滅するAIが秋葉さんといるーんの実装班により作られていた．
相手の0付近を速攻で倒しに行くためのコンボを搭載してもらいつつ，ゾンビ用の関数を作ることにした．
ゾンビ用関数はIを受け取って発動するので，forループさせるためには別の関数をもう一つ送り込む必要があるなぁ…と思ったらcopyを使えば自分の場に用意するだけでよかった．
help i i をループさせれば，限界突破して殺せるので便利．
いつの間にかSK変換器が関数合成とかもできるようになっていたらしいが，すでにSK慣れしすぎて直接SK式書いた方が速かった．
66体を一気に殲滅できるゾンビパウダーが完成した．
昼〜夜
起きてゾンビパウダー実装してもらった．
面倒なので.shに直書きされたｗ
シミュレータは探索とかしなくてもnewしっぱなしだとメモリがヤバいらしく，C++オワコン感が非常に漂っていたが，秋葉さんがガベコレ実装するという激しいことをしていた．
いもすにより内部リーグが構築され，色んなAIを自動対戦させれるようになった．
相手より先に４発打てればほぼ殲滅できるので，hos先生とtos先生と一緒にゾンビパウダーのショートコーディングを開始した．
ゾンビ送り先はこちらから倒しやすい255にした方が便利で，255倒すのも01のHPを大きく犠牲にしてattackのみで倒すことにした．
01のHP減らすと敵のゾンビ対策にもなって一石二鳥．
最終的に123ターンで殲滅できるものが完成した．
hos先生によりincゲーということになったので，putマシンからput-incマシンに進化した．
四日目
深夜〜朝
色々な作戦が開発された．
- 永続dec
- 毎ターンdecを行えるコンボ
- 敵が普通のreviveを必ず行って来る場合，敵の行動を完全に封じつつ，こちらは２ターンに一度自由行動ができるので確実に勝てる
- dec-zombie
- decとzombieを同一ターンで行うことにより敵の関数を消す
- でこぼこ
- help 2i (2i+1) ループによりでこぼこさせて敵のゾンビを防ぐ
- 関数構築が遅すぎてゾンビに間に合わないorz
- 撃墜
- コピー版C++シミュレータが死んだ関数を作ることにより敵のシミュレータを倒す
速攻ゾンビで敵をほぼ殲滅したあと，中盤はダメージ可変の小ゾンビ，永続dec，dec-zombie，普通のdecを適切に行うという戦略に決まり，実装してもらうことにした．
中盤以降の戦略を実装前のはそんなに強くなくて，先の中盤戦略がどれくらい強いかもよく分からないので，強いチームはゾンビゲーだろうと推測し，対ゾンビハメAIも並列で作ってもらってどのくらいハマるは試してもらうことにした．
はめ殺しAI
- 255を速攻で作る
- 相手の0番を倒す
- 相手が0をrevive→永続dec
- 0番を必ずreviveするAIの場合，勝利確定
- 相手がこっちの255を倒しにきた→永続revive
- ゾンビを送るために255を必ずdecしに来るAIの場合，勝利確定
われわれのゾンビAIには余裕勝ちできるが，ゾンビを打たれる前に構築するには0番に永続reviveを設置する必要があり，0番使えないのは痛い，強いチームはハマらないだろうなどの理由により結局普通のゾンビで行くことになった．
中盤以降の戦略を実装したAIが提出されたが，結構負けるため，原因を考えることに．
序盤でのほぼ殲滅には成功し，その後reviveのスピードに追いつけずに，逆転されているという分析になったので，forループdecで敵を殲滅するショットガンを搭載してもらうことにした．
decは敵が死んでいてもエラーにならないのでとても便利．
撃墜は強いチームには効かないだろうということで，結局組み込まれなかったが，ひょっとすると結構効くのかも知れない…
最終的に提出したAI
- まず最初に255を倒し，ダメージ6144の大ゾンビ発射機を設置(6144は255倒すのにも使用して再利用)
- 大ゾンビで倒せる一番小さいインデックスに発射
- 我々のゾンビは相当速そうなので，0付近を倒されてかつゾンビで上書きされない限り，敵をほぼ殲滅できるはず
- 大ゾンビで倒せないなら一番関数の複雑度が高い場所を攻撃
- すでに一度倒してreviveしてきたところの場合，永続decコンボを設置して攻撃
- 重要なスロットが死んだら必ずreviveするというAIの場合，これが決まった瞬間勝利確定
- HPが高い場合はダメージ可変の小ゾンビを飛ばして攻撃
- 低くて十分複雑ならdec-zombieで消す
- 全部のHPが低ければショットガンを設置して撃ち続ける
- すでに一度倒してreviveしてきたところの場合，永続decコンボを設置して攻撃
- 0123のみrevive
- もう少し守るべきだった
終了後
終了直前に，関数構築中にそのスロットが死んでもそのまま構築を続けるというバグが発覚したが時間中に治すことができなかった．
そのまま構築するとターンが無駄になるだけでなく，関数も消えてしまうので痛い．
他にも実はもう二箇所バグっていたらしく，それらを直すと関数消してしまわなくなり，結構強くなったぽい．
