CODE OF KUTULU

CodinGameの10日間コンテスト。迷宮サバイバルゲーム(?)です。

f:id:y_kwn:20180625235257p:plain

リプレイ：https://www.codingame.com/replay/320515989

世界3位/2092人、日本1位/67人でした。

ルール

4人対戦ゲームで最後まで生き残った人が勝利します。

敵と接触するとライフ(Sanity)が20減少します。ただ歩いているだけでも3-6減少していきます。2マス以内に他プレイヤーが居るとライフの減少が1～3に緩和されます。

敵はWandererとSlasherの2種類が存在します。Wandererはただ追跡するだけの敵で、Slasherは直線上のプレイヤーに狙いを定めて一足飛びで切りかかってきます。

プレイヤーは上下左右の移動の他にPlan・Light・Yellという行動が取れます。

ざっくり説明すると、Planはライフの回復・Lightは敵の追跡をかわす・Yellは他プレイヤーの動きを止めるという効果があります。

ゲーム性

他プレイヤーを見殺しにして最後まで自分が生き残れば勝ちですが、自分が生き残るためには他プレイヤーと協力しなければいけないというジレンマがあるゲームです。

基本的な勝ちパターンは、なるべく単独行動を取らず他プレイヤーと一緒に行動し被害を最小限に抑え、要所要所でYell等を使って他プレイヤーのライフを削っていく感じの動きになります。

アルゴリズム概要

chokudaiサーチで6手読みしてました。ただ、ほぼほぼ全パターン読み切れてたのでchokudaiサーチである意味はあんまりなかったと思います。

シミュレータ実装

Refereeは公開されていましたが、そんなに作業量は無いなと思ったので移植という形じゃなくてほぼほぼ自分で再実装しました。

デバッグに関しては、もうこれはシミュレータ実装の常套手段ですが、アリーナを全員自分にしてシミュレーション結果とリアルな結果の差分を見て、差分があったらエラーログを出すって方法でバグを潰していきました。

Slasherのstateの切り替えやtargetの取り方のデバッグで泣きそうになりましたが、1日半（土曜夕方～日曜夜）で完璧クオリティのシミュレータが完成しました。

45msecで大体10000～20000回シミュレーションできました。（ちなみに自分のAIのコメント出力の数字はシミュレーション回数です）

シミュレータ高速化

多分一番効いたのは経路探索の省略です。どう省略したかは単純で、任意の(x1,y1)から(x2,y2)まで何手でたどり着けるかを[w*h*w*h]のテーブルで持っていただけです。

同様に任意の(x1,y1)から(x2,y2)に進む場合、1手目はどの方向に進むかを[w*h*w*h][4]のテーブルで持っていました。

※[4]の意味 ： 探索優先度がターン毎にRDLU→DLUR→LURD→URDL→RDLU→...と切り替わるので4つ持つ必要がある

ただ、LightEffectが存在する場合は大人しくBFSで検索してました。

chokudaiサーチ部

6手読みで、遷移は2手目までは「待機・上下左右・plan・light・yell」の8パターンで、3～6手目は「待機・上下左右」の5パターンでした。

遷移の間、他プレイヤーは待機上下左右の5パターンのうちから簡易評価関数が最も良くなる方向に行動します。

※敵の簡易評価関数 : ダメージ食らう位置だったら-1000 - 1番近くの味方までの距離 * 2.0 + 1番近くの敵までの距離 * 1.0

評価値は「1手目の評価値 * 1.0 + 2手目の評価値 * 0.98 + 3手目の評価値 * 0.96」みたいな感じで、各ターンの評価値を足し合わせた値を使いました。

遠いターンの盤面は他プレイヤーの行動によって予想と全然違う盤面になってるはずなので、6手目の評価値だけをみるのは微妙な気がしたので足し合わせることにしました。

同じような理由で、計算時間的に7手読み以上も余裕でできますが、あんまり遠いターンを読んでもしょうがないないなという理由で6手で打ち切ってます。（実際性能は上がらなかった）

評価関数

自分のSanity * 100
1番近くのWandererまでの距離 * 1.0
Wandererのターゲットが自分だったら-10
Wandererと隣り合っていたら-100
1番近くのSlasherの距離 * 0.5
Slashが直線上にいたら-10
Lightの個数 * 0.05 （ちょっとでも得するなら使うようにした）
Planの数 * (6-_sanity_loss_group)*5*100 (他に1人巻き込んでplanを使うと採算が取れるように調整)
1番近くのシェルターまでの距離 * 0.25

（以下1手目限定）
他プレイヤーのSanity * -20
他プレイヤーに対してYELLを使っていたら-200 （YELLの無駄打ち防止）
1番近くの他プレイヤーまでの距離 * -2.0 (3人以上生き残ってるときのみ有効)

※遠いターンの他プレイヤーの予測位置は当てにならないので、他プレイヤーに関する評価は1手目限定にしてます

反省

  • 終了後のチャット眺めてた感じblasterpoardさん・Agadeさんはminimaxを使っていたっぽいです。minimaxとBFSの組み合わせっぽい？自分もminimaxはありかなと軽くは思っていたんですが、軽く思っていただけでした。ビームサーチ系が当たり方針だという思い込みがあったので(まぁ当たりではあったと思うけど)、真面目に考察するフェーズまで行かなかったのが後悔ポイントです。

  • あと1手あれば1位だったけど、その1手はminimaxだったと思う。

  • パラメータ調整をやりすぎるのは悪手なんですが今回はやらなすぎた感がある。

  • 大局を見た上での調整を全く入れてなかったので、ちょっとは入れても良かったかも。初期位置が相手と離れすぎていたら序盤は合流を最優先にするみたいな。

  • (」・ω・)」うー!(/・ω・)/にゃー!をコメント芸でやればよかった。（今思いついた）