Mean Max

ゲーム概要

CodinGameの10日間コンテスト。水を運ぶTankerをぶっ壊し水をかき集めるゲームです。2人対戦ゲームでそれぞれ3つのユニットを操ります。3つのユニットはそれぞれ役割とスキルが異なっていて↓のような感じです。

ユニット名	役割	スキル
Reaper	水の採集	動きを鈍らすTarを撒く
Destroyer	Tankerを破壊する	相手を吹き飛ばすグレネードを投げる
Doof	スキル使用に必要なrageを走って溜める	水の採集を妨害するOilを撒く

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

世界21位/2512人、国内2位/67人でした。

アルゴリズム概要

1手読み＋匠の評価関数で戦ってました。ビームサーチ系で探索しても2手が限度だろうし、相手が絡むと読んでも意味ないし、2手読みくらいなら評価関数でカバーできるやろの精神でした。

シミュレータ

まず１・２日目に完璧なシミュレータを作りました。シミュレータ部分に関しては公式でjavaのコードが上がっていたので基本そのまま移植した感じです。移植が終わったらArenaを全員自分にして動きを完全に予測できる状態にして、シミュレータの結果と次のターンの入力に差異があったらAssertをかけるって感じで細かいバグを潰していきました。

探索

まず全員WAITにして各ユニットがスキルを何処に打つかだけを探索します。

Reaper：自分自身 + wreckに近づいてる敵reaper
Destroyer：自分自身 + 自Reaper + 敵が近づいてるWreckの周り8箇所(吹き飛ばし目的)
Doof：敵が近づいてるWreckの中心 + 自Repaerと敵Reaperが同居してるWreckには敵にだけoilがかかる位置

上記の位置をそれぞれ探索して一番評価が高くなる位置をスキル発動位置にしました。

その後、各ユニットの「8方向の全速力(reaperは半速も)＋↑で求めた位置にスキル」の組み合わせを全探索しました。つまり(8+8+1) * (8+1) * (8+1)の全探索です。時間はほぼほぼ余裕でしたが、衝突が起きまくるシチュエーションでタイムアウトしてたので45msで雑に打ち切る処理は入れてました。

敵の動き予測も軽く入れてましたが効果があったかは謎です。

評価関数

ベーススコア + reaperのスコア + Destroyerのスコア + Doofのスコア - 敵のスコア

ベーススコア

水とrageの量によって加点。

Reaperのスコア

Reaperが既にWreckに乗っている場合、速度に応じて加点（速度が0に近いほどプラス)。
それぞれのWreckについて「Reaper-Wreck間のスコア」を算出して、一番高いスコアを評価値に加点。
ただし自DestroyerがTankerをすぐに壊せそうなら「Reaper-Tanker間のスコア」も算出して、そっちの方が高いければそっちのスコアを加点。

Reaper-Wreck間のスコア

「水の量/Reaper-Wreck間の距離」をベースにして敵Doofが近くに居たら減点、Wreckに到達できそうにないなら大減点。

※到達できるかの判定方法

この画像のように、reaperから見て一番近い端と左右の端までのレイが全てブロックされてたら到達できないと判定。敵ユニット＋Tankerがブロックの対象です。

Destroyerのスコア

それぞれのTankerについて「Destroyer-Tanker間のスコア」と言うものを出して、一番高いスコアを評価値に加点。
Destroyer-Tanker間のスコアは「水の量/Destroyer-Tanker間の距離」で算出。

Doofのスコア

自Doofの一番近くにいる敵Repaerに近づくと加点
自Doofの一番近くにいる敵Repaerに一番近いWreckに近づくと加点

敵のスコア

水の量＋一番近くにあるWreckの距離に応じて加点

反省点

・今回のゲームを見た瞬間「Coders Striker Back」や「Fantastic Bits」が頭によぎり、それで上位を取った人のアルゴリズムはGAだったので「すわっ！これはGA案件か！？」と思ったんですが、対戦ゲームAIをGAで書くことにまだちょっと懐疑的だったり、50msでは収束しなさそうだし相手の妨害は予測できなさそうだからGA止めたんですがやっぱりやればよかった。（収束早めるには行動数削ればいいし、敵は無視しても良さそうだった）

・匠の評価関数戦術はやっぱ限界がある気がする。