読者です 読者をやめる 読者になる 読者になる

codeVS 2.0

2.0が終わって、やっとまとめる気になったので記事にする。
全く知らない人向けかも。

CodeVSとは

ゲームAIを作るのが目的で
1回目は、タワーディフェンス
2回目は、ぷよぷよみたいな落ち物ゲーム

予選と決勝に分かれていて、学生予選8位以内で決勝に出れる。

決勝に出るには

他のプログラミングコンテストに比べて、かなりプログラミングに関する技術力の敷居が低い。

TopCoderで上位になるような人があまり参加しないことが最大の理由で、今年で2回目だったけど、去年の優勝者であるjelliesさんなどが本気で参加しなかったこともあって、今年もそれほど技術力は要求されなかったように思う。

最低限、プログラミングできる必要はあるけど、シミュレーション系のゲームが好きな人は良い成績を取れるのではと感じる。予選の期間は長いので難しいけど、今年の決勝のように戦略レベルで差がつくような展開になれば、プログラミングが不得意でも十分優勝も有り得る。
戦略>>>>>超えられない壁>>>>>プログラミング能力
なので、その辺を意識すると良いかも。

学生側から見れば、就活にも役立つと思うので、就活に困っている人は参加するといいかも。
就活に困らないレベルで優秀な人も結構いるけど。

CodeVS 1.0

1回目はタワーディフェンスだった。
去年のことなので短るまとめると

予選は入力がほぼ一定だったらしく事前に計算できたため計算しておいて出力するだけと問題のある予選ではあった。
結果的には、スキルが全然ない人はいなくて問題にはならなかった気がする。

決勝はjelliesさんが僅差で優勝して、今年はshoheiさんが会場を沸かせていたけど、個人的にあれはあまり凄くなくて、jelliesさんの決勝は本当に運を持ってた。

アルゴリズムに関しては、迷路をつくることとタワーを強化することが完全に独立してて、タワーを強化する方はほぼ最適解だったので差がつかなくて、迷路を作る方は大したアルゴリズムはでなかったらしい(結局、ソース読んでないなぁ、自分のはかなりひどかった)。
処理時間で資金が減っていくルールだったので、事前に予想していた資金はあるけど死ぬゲームではなく資金がなくて死ぬゲームだったので、これが重要になって結果的には割りと言語を縛る必要があって、それは微妙だったかもしれない。
出場者のほとんどはC++で出ていたはず。

CodeVS 2.0

今年は落ち物ゲームだった。
予選は、連鎖する形が決まっているシステム連鎖と不定形の探索するアルゴリズムに分かれていて、予選のルールではシステム連鎖が優秀だった。かといって不定形のアルゴリズムで決勝に出られた方は何人かいるので、システム連鎖が必須だった訳ではない。

他に、クライアントを多重起動できることに予選終了の3日前に気づいて、自分は有効利用することができなかった。これが意図的なものなのかは分からない。
そもそも予選の1回の実行時間を最大使うと9時間かかって、3つのケースがあったのでプログラムを改善してそれが結果に反映されるのに最大で27時間かかる状態だった。
システム連鎖は時間には余裕があったようだけど、不定形は時間をかけるほど良くなるアルゴリズムなので必然的に時間を最大限つかう方法になったことが大きい。
複数で同時に実行できるので、Amazon EC2とかリソースをちょっとだけ借りるとかいう発想もあったようだけど、まぁやりすぎな感はある。
けど、不定形はスペックにかなり依存するので、自分の環境はそんなに悪くないのだけど、もうちょいスペックあればいけるのにみたいな状態があって、来年に参加するなら最新のCPUを積んだPCで参加したい。

決勝について、1回目のCodeVS 1.0は予選の延長みたいな感じで決勝があったけど、今回は予選とのルールが大きく変わっていた。
プログラミングの能力云々ではなくて第一感が重要で、決勝のルールを見た時に、まず1000ターンを終えるような戦いにはならないから、相手にブロックを降らせて戦う感じになると自分は思ったけど、そう考えなかった人が多かったようで、半分くらいの人は戦略の時点で負けていたので、面白い決勝になった気がする。
予選でシステム連鎖を使っていて、決勝で不定形に切り替えたのはshoheiさんだけだったように思う。予選ではシステム連鎖が優秀だったことも背景にあるのだろうけど、自分が取っていた方法を切り替えるのは難しい。
個人的に決勝前は予選とルールが異なると出場者の負担になるしパフォーマンスは落ちるし微妙じゃないかと思っていたけど、自分みたいなプログラミングが微妙な人間がRedCoderクラスに勝つには戦略の時点で優位に立たないと厳しいから、決勝でルールが大きく変わって良かったのではと考えを改めた。
来年はどうなるか分からないし、今年の失敗があるので、来年の決勝進出者はそのへんもちゃんとやりそうでチャンスない気もする。

ここから先は蛇足

アルゴリズム

自分は非システム連鎖だったのだけど、主な評価方法は
・各列に1~S-1のブロックを落として、どれくらい連鎖するか調べる
だけだった。
smallに関しては本当にこれだけで、middleやlargeは連鎖を遅らせるためにブロック数が少ないと評価値を上げるとか多少の工夫があった。
smallの記録は連鎖数35だったけど、平均連鎖数は25くらいで、30を超えることは10%もなかった。

深さ優先探索で、smallは3、middleとlargeは2の深さまで行なっていた。
それぞれの処理時間について、smallは1時間くらい、middleは10分くらい、largeは1時間ちょっとくらい、で行ってた。
smallでしか調べてないけど、深さ2と3で、1つ深さが増えると平均連鎖数が2~3くらいのびた。
1つ深さを増やすと処理時間は、W倍くらいになるので、middleは深さ3にするとギリギリ3時間超えるくらいで、そこはもう少しPCのスペックがあると良いなと思った部分だった。
枝狩りができるともっと深くまで探索することができるのだけど、評価値が単調増加するなら良かったけど、かなり評価値が上下するので、現在のノード以下の評価値で枝刈りするとかはあまり有効じゃなかった。逆に単調増加するような設計にできたら、枝狩りできて良かったのだろうけど。評価値の上から順に10個くらいとか方法がなかった訳ではないかも。

連鎖をするタイミングについては、連鎖数を増やす探索を最後までやりつつ、同時に各パックでの最大得点を記録しておいて、最後まで探索した後に最大得点のパックまでもどれば良いだけ。
最初は、ある程度ブロックがうまってきたら連鎖させるとかアホなことしていたけど、上記したのに気づいてsmallで5連鎖くらいはのびた。

決勝までもう少し精度が上がれば行けるか、ってところだったけど難しかった。
kusanoさんによると、平らになるように連鎖を組むとのびるらしく(発火点が下の方にならないように?)、なるほどなーと思った。

シミュレーションに関しては、連鎖が起こる可能性のあるブロックは、今落としたパックと前の連鎖で消えたブロックより上のブロックに限定されるので、それが最低限の高速化だった。
他には1次元配列にすると良いとか書いてあった。

並列処理について、それぞれのスレッドで1から計算して最も良いパターンを取る方法だから、スレッド数が増えると単純に試行回数が増えて成績が良くなる。別のスレッドと同じ結果にならないようにランダムな部分をもたせる必要があって、上記した潜在連鎖数だけだと結構同じ評価値になるから、最大の評価値から適当に選んで、評価値をもう少し複雑にする場合は

if(最大評価値*95<現在評価値*100)

とかすれば、最大評価値の95%より高い値で考慮するとかできる。
core i7をつかっていて、クアッドコアの8スレッドなんだけど、ハイパースレッディングだから実質4つしかコアが無いわけで、スレッド数を8にした方が良いのか、4つにした方が良いのか謎だった。
windowsとubuntuのタスクマネージャとか見てると差があって、windowsはわりとCPU占有率が100%にならないで、走らしているスレッド数以上のスレッドの占有率が60~70になっている感じで、ubuntuはちゃんと走らしたスレッド数だけ占有率が100%になっていた。性能比較したわけじゃないので、どっちが良いとか分からないけど、ubuntuの方が分かりやすくて良い感じ。
あと、クライアントの多重起動について、気づく前は、並列でやって、気づいた後は単一スレッドに戻して複数クライアントで並列して実行していたのだけど、うまくいかなかった。理由として、2日くらいしかなかったのと、バグを仕込んだりして無駄になった時間があったのが大きいけど、リソースを1つに集中させるのに比べて、リソースを割って数撃てば当たる的な考えの方が有効かどうかは疑問だった。

システム連鎖について、smallに関しては最初からブロックまで指定して連鎖を組んでいくことができるみたいで、それが予想外だった。無理そうだな、と思って試さなかったのが問題。
smallについて、40連鎖を安定して組むなら連鎖する形を決めておかないと無理だな、とは感じていたので推察はついていたのだけど、うまい実装が思いつかなくて、できなかった感じ。
逆にその程度の技術力しかない。