ICFPC2011
"CopyKawaii"で参加してた。どのカードが一番かわいいか議論になって僕はzombieかわいい派だったが、copyかわいい派がいたので腹いせに名前をそれにした。
↓submitしたコード
http://int.main.jp/files/ltg-opt.d.tar.gz
半分くらい使ってないが。(これも反省だなぁ)
色々反省はあるが、一応時系列で書いておくと、
最初どうしたらいいかわからんかった。
で、とりあえず、
- LTGプログラムをもっと簡単に書けるようにする(eval.cppから呼ばれてる関数達)
- その上でアルゴリズム書く(zombie-help.cpp)
という問題かなー、と、思って、
上を僕が、下を @taitai_jp が書いていた。
LTGプログラムは、定数書くのが超めんどくさくて、f (g 10) とかが書けないので、それをコンパイルするコードを書いた。
最初のメモによると、
式をSKに変換
ltg-opt.cpp に書いてある
const char *progs[] = {
"attack (0)(1)(15)"
};
を
expand integer = (((attack zero ) (succ zero ) ) (get (succ <emit_inc 15> ) ) ) <- 整数の展開
expand sk = (((S (K ((S (K (((S (K (attack zero ) ) ) succ ) zero ) ) ) get ) ) ) succ ) <emit_inc 15> ) <- SKの展開
↓実行されるコード
right slot=0 card=zero
left slot=0 card=attack
left slot=0 card=K
left slot=0 card=S
right slot=0 card=succ
right slot=0 card=zero
left slot=0 card=K
left slot=0 card=S
right slot=0 card=get
left slot=0 card=K
left slot=0 card=S
right slot=0 card=succ
right slot=1 card=zero
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
left slot=1 card=succ
right slot=0 card=zero
とかやります
リークしてるけど負けないで!!と書いてある。(メモリは1GB使えるので、メモリリークはOSに任せて問題無いはずだった。が、これが、後に死因はメモリリークじゃね？疑惑の原因となるので、ちゃんと解決すべきだったな…)
最終的には、これに
- スロット参照($)、外で指定した変数の参照(@)、virtual slotの参照(*)
- スロット参照の最適化
- 定数生成の最適化
が入った。virtual slotは、数字じゃなくて名前で参照できるスロットだと思ってもらえれば。
あと、さらに、これを制御するスクリプトも作って、
set e = 0 set m = 2 label a set m0 = $e * 2 + 2 set m1 = $e * 2 + 3 set m = $m + 1 attack ($m0)($e)(8192) attack ($m1)($e)(3072) set e = $e + 1 goto a
みたいなのを書けるようにした。このようにしておけば、ループ不変式を外に出す最適化したりとかできるので、有利だろう、と思って、1.5日目ぐらいを終えた。
次の日、上のスクリプトを色々強化していた。
このへんで、taitai_jpがzombieのhelpが挙動変じゃねとか言って、効果が反転してることにやっと気付いた。いつだっけ…2日目の昼か夕方くらい。それで、attack + zombieの組み合わせで、なんとかするのをサーバにあげておいたら、1500ターンくらいで全滅されられはじめて、我々の限界が14000ターンとかだったので、真面目に考える必要が出てきた、が、コンパイラが改善できるところが沢山あったので、考えるのはtaitai_jpに任せて改善をしていた。結局、この状態は最後まで変わらず、taitai_jpが考えて何か書くと問題が出て、それを僕が修正するというパターンだった。
んで、いざ、何か書こう、と思ったが、制限の多いスクリプトで書くのは予想に反してめんどすぎるので没。複数の式にわたるグローバルな最適化ができなくなるが、まあ、三日でそこまでやる自信は無かったので、
eval_and_run_at("8192", vm, CompileParam(RIGHT, imm_slot, 8, false), ch);
while (1) {
for (int i=0; i<255; i++) {
vm["v"] = i;
vm["o"] = 255-(i/4);
eval_and_run_at("attack ($v)($o)(@8)", vm, CompileParam(RIGHT, imm_slot, 129, false), ch);
}
}みたいな、C++の文字列をコンパイルするところまでにして、それの制御はC++で書こう、という感じにした。これは最後までそうなっている。
シミュレータが不安定だったので半分くらい書き直した。なんか限界で境界条件のチェックを放棄して寝た。ここで、4,5時間寝るつもりが11時間寝ていた。僕は自分では徹夜とかできない人間だと思っていたが、二日目まで意外と大丈夫だったので、「いやー俺って徹夜しても平気な人間なんだよねぇ〜」とか思ってたが、全然そんなことは無かったようだ。
寝ている間に、SKコンビネータのページ(このページのこの三日間の参照数とか知りたいところである)が参照されてて、引数の順番入れ換えれば最内ループでGetする数をかなり減らせるということがわかったらしい。細かいのを考えるのは嫌であまり真面目にカード見てなかった僕は、2晩続けてカード達と睨み合いを続けるtaitai_jpの姿勢を見習わねばならないな、と思った。
なんかそんなこんなで、taitai_jpが数十時間続けて不変式の移動を考え、僕が定数生成の細かい最適化を入れ続けた結果、614ターンで、何もしないスクリプトを撃破するという状態になった。が、この時点で朝の6時か7時くらいで、slot0殺し対策とか入ってなくて、なんか無理っぽい感じになってきた。
あと何かが不安定で、Invalid outputで死ぬことが増えた(原因はあとでわかったことだが、無限ループ時の1000回適用のチェックをしてなかったのでそのへん)
memory exceedsとか出てたので、メモリリーク説を提唱し、メモリリークを消した。メモリリークは30分あれば消せる自信はあった。すなわち、
- exprの部分は、lifetime決まってるからメモリプールで大丈夫
- シミュレータのカードは、traverseが一瞬で書けるからmark & sweepは一瞬で書ける
だった、実際、両方あわせて30分くらいで書いたと思う。mark & sweep は↓こんなん。
static void
mark(Card *c)
{
if (c->mark) {
return;
}
c->mark = true;
if (c->is_number) {
return;
}
for (int i=0; i<c->u.func.cur_num_applied; i++) {
mark(c->u.func.args[i]);
}
}
static Card*
sweep(Card *c, Card *prev)
{
head:
if (c == NULL) {
return prev;
}
if (c->mark) {
c->mark = false;
Card *tmp = c->chain;
c->chain = prev;
prev = c;
c = tmp;
goto head;
} else {
Card *f = c;
c = c->chain;
// delete f;
goto head;
}
}しかし、やっぱり死んでいた。mark&sweepがなんかおかしいのが原因かもしれんかったが、ここらへんで、8:40とかで、memory exceedsで死ぬか、invalid outputで死ぬか、の選択を迫られて、memory exceedsで死ぬほうをとった。なので、最後のdeleteはコメントアウトされている。
個人的には、C/C++のメモリは全く問題ではないと考えていて、
- ライフタイムが静的にわかるならメモリプールでいい。これは解放コスト減らせるのでmalloc/freeより効率がいい。
- トラバースが良く定義できるなら、mark & sweepぐらいすぐ実装できる
- 境界こえるのはvalgrindがあれば検出できる
という感じなのだが、死ぬ原因がデバッガで追えない環境だと、「死因がメモリまわりかも」という不安と戦い続けなければならないというのがあるというのがわかった。今後は気を付けよう。
C++を使った理由は、C++で書くのが一番慣れて早く書けるからで、例えば、Pythonで200行書くのとC++で1000行書くのだったら、C++で書くほうが早いという僕の都合だったが、まあ、なんかGCの付いた言語もC++と同じくらいの早さで書けるようにならんといかんな、と思った。(GoかDあたりにするか)
このへんで終了。
半分くらいコード使ってない。
- 制御スクリプト → まあ、この方向性が無理だと最初に判明したのはよかったかもしれんが。
- slotの状態を見てアロケートするvirtual slot allocator → シミュレータの状態が安定したのが5時間前とかで色々実験する時間が無かった
- スロット死んだときのイベントハンドラ → 同じくシミュレータの状態が安定したのが5時間前とかで色々実験する時間が無かった
- zombie-help.cpp以外の対戦ルーチン
- シミュレータver.1
こういう、書き捨てるプログラムは、良いのか悪いのかいつも悩むよね。僕は、やる気を加速させるのに必要だから良いものだという説を主張したいが。
個人的に反省点としては、ループが書けるというのに気付けなかったところか…
- exampleに書いてある
- チームメンバ僕以外全員知ってた
- 確かに途中で「ループがうまく使えれば〜」みたいな会話があった気がする
と、ヒントがあったにも関わらず、僕は書けないか、もしくは、相当努力しないと書けない、と、思いこんでいた。
ループが書けるのを知ってれば、
- 落ちる原因はそこらへん突いてるだろ
- 関数をカウンタ増やして適用するのはできるはず
とか、気付けたのでまあ、もうちょっとなんとかなったんだろうなぁ、と思う。
あとチームの反省点としては、処理考えるのがtaitai_jpひとりだったのがよくなかったかもしれん。あと僕ひとりにコード書かせたことか。5ターンでinvalidしてるの原因はループ書けるからだ、と、誰か教えてほしかった。
まあ、かなり楽しかった。人生で始めて本気出したんではないかという気がするぐらい密度の高い三日間だった。来年やるならちゃんと説明読もう。あと putだけ全く存在理由がわからんかった。
