BOTTERS OF THE GALAXY 参加記 - ヴァルの開発記

ゲーム概要

CodingameのBotters Of The Galaxyというコンテストに参加しました。

www.codingame.com

５種類のヒーローキャラクターの中から２人を選んで戦います。

勝利条件は以下のいずれかです。

・敵タワーの破壊

・敵ヒーロー全員の殲滅

・500ターン経過時点でのkill+denyが多い

kill+denyとは、レーンユニット（敵タワーに向かっていく小さいやつ）を倒した数と、倒される前にチームキルで阻止した数の合計です。

チャットではLOLに似てると言われてたようです（私はLOL未プレイなのでその辺はよく分かりませんでした）

最終提出プログラムの内容

最終順位：２位（日本１位）

１．戦略

敵ヒーローの殲滅のみを目標とし、敵タワーの破壊やkill+denyは完全に無視しました。理由は、まずタワーは攻撃力・攻撃範囲・体力が全て高く強力なうえに敵ユニットの湧き位置にもなっているため破壊は困難と判断したのと、kill+denyに関してはヒーロー殲滅戦略だと500ターン経過する前に決着が着くことが多かったので必要なさそうと判断したためです。あとヒーロー同士の激しいぶつかり合いが見たかったというのもあります。

２．戦術

HulkとDr.Strangeを選択し、Dr.StrangeのPullで敵ヒーローを引き寄せ、HulkのBashでスタンさせてひたすら殴るというのが主な戦術です。

ヒーローの立ち位置は、味方レーンユニットの重心を計算し、Hulkはそこより少し敵陣側に、Dr.Strangeは少し自陣側に位置するようにしました。さらに、敵がMelee系ヒーローを使っている場合は少し自陣寄りに、Ranged系を使っている場合は少し敵陣寄りに位置するよう調整しました。

また、Groot(中立ユニット、Creatureとも呼ばれる)には攻撃を仕掛けないようにしました。お金よりヒーローのHPのほうが重要なのと、Grootの相手をしている間に味方のレーンユニットがやられてしまうのは不利になると考えたためです。ただし、敵が起動したGrootが襲いかかってきたときは反撃あるいは回避するようにしました。

３．アルゴリズム

αβ法で１手先読みをしました。ただし、味方ヒーロー２人の行動の組み合わせを全て試すと計算時間が足りなかったので、２人それぞれ個別に探索するようにしました。具体的には

１．Hulkの行動をWAITに固定した状態でαβ探索をしてDr.Strangeの行動を決定

２．Dr.Strangeの行動を１で決定した行動に固定してHulkの行動をαβ探索で決定

という流れです。つまり、探索を２回やる感じです。

また、今回のような同時着手ゲームでのαβ探索の方法は以下の論文を参考にしました。

[同時着手ゲームにおけるAlpha-Beta探索]

https://www.researchgate.net/publication/311951892_tongshizheshougemuniokeruAlpha-Betatansuo

内容はとてもシンプルで、

擬似的に自分が先手で対戦相手が後手と仮定することによってαβ探索を行った．

後手の着手を考えるときは，先手が着手した後の局面ではなく，その前の局面において考えるようにしなければならない．

ということが書いてあります。

４．探索空間の制限

自ヒーローがとれる行動を全て試そうとするとキリがないので、以下の行動のみに制限して探索しました。

自ヒーローの行動

自ヒーロー１人につき以下の行動を探索します。

ATTACK 敵ヒーロー１
ATTACK 敵ヒーロー２
ATTACK_NEAREST HERO
ATTACK_NEAREST LANE_UNIT
ATTACK 行動中の近くのGroot
上下左右斜め８方向についてMOVE_ATTACK 近くの敵ヒーロー
上下左右斜め８方向についてMOVE_ATTACK 近くの敵レーンユニット
アイテムの購入・売却
敵が全員Bushに隠れて３ターン出てこなかった場合、敵が最後に隠れたBushへ向かう

Hulkの場合

CHARGEの有効range内にいる敵ヒーローそれぞれにCHARGE
BASHの有効range内にいる敵ヒーローそれぞれにBASH
自分が敵ヒーローの攻撃レンジ内に入っている場合EXPLOSIVE_SHIELD

Dr.Strangeの場合

敵ヒーローの周辺より自分の周辺に味方レーンユニットが多い場合 PULL
SHIELDの有効range内の味方(自分自身含む)で、かつ敵の攻撃範囲に入っている場合 SHIELD
マナに余裕があるときかHPが少ないときだけ AOEHEAL

ヒーロー１人あたり最大で30通りぐらいです。

移動する場合は移動後に攻撃できるようにMeleeなら0.9, Rangedなら0.8だけ移動するようにしています。スキルの使用はあまり制限せずとりあえず出せるなら出すって感じで、有効かどうかの判断は評価関数に任せています。（ただし、AOEHEALは弱いのであまり使わないように制限しました。）

アイテムの性能は(ステータス/コスト)の大小で判断し、これが高いアイテムを優先的に買います。ステータスは重要な順にManaRegeneration > MaxMana > MaxHealth > Damage > MoveSpeedとしました。例えば、ヒーローのManaRegenが低い場合は(ManaRegen/Cost)が良いアイテムを購入し、ManaRegenが充分高い場合は(MaxMana/Cost)が良いアイテムを購入し、...という感じです。また、敵がHulk＆Melee系ヒーローの場合はゲーム開始直後のみDr.StrangeがMaxHealthを優先してアイテムを買うようにしました。そうしないとDr.Strangeが一人狙いされて瞬殺されることが多かったです（これをしてもわりと瞬殺されていましたが、、、多少はマシになっていたと思います）

敵ヒーローの行動

敵ヒーロー１人につき以下の行動を探索します。

ATTACK_NEAREST HERO
ATTACK 最も近い敵（タワー除く）

敵ヒーローはこの２種類だけです。

計算時間の関係で敵ヒーローの行動はかなり絞り込む必要がありました。そこで、"自分がされて一番嫌な行動は何か"と考えたら、やっぱりヒーローが攻撃されることが一番嫌だなぁ、と思ったのでATTACK_NEAREST HEROにしました。ただ、レーンユニットを攻撃することも当然あると思うので、とりあえず"ATTACK 最も近い敵"を入れておきました。

５．評価関数

以下の５つの評価値を計算します。

勝利・敗北
ヒーローの生存数
次のターン敵に攻撃されたら死亡する（＝詰んでる）ヒーローの数
周囲に敵がいない場合、アイテムを購入できるなら購入したほうが良い
すごい評価値X（後述）

評価値同士を比べるとき、上の１～５を順番に比較します。具体的には、１が異なるなら１が良い状態のほうが良い、１が同じなら２が良いほうが良い、１と２が同じなら…と続きます。

すごい評価値Xは以下の計算で導き出されます。

X = (自ヒーローのHP合計 - 敵ヒーローのHP合計 - 敵レーンユニットのHP合計 / 2 - 自ヒーロー付近のGrootのHP合計)

+ (敵ユニットの死亡数 + 自ヒーロー付近のGrootの死亡数)

+ 次のターン攻撃されたときに回避できないダメージの合計

- 自レーンユニットの重心に近い良さそうな場所へのユークリッド距離 / 2

+ (マナ残量 - マナ最大値) / マナ回復速度

+ ヒーロー２人のうちHPが低いほうのHP

まず１行目ですが、レーンユニットのHPに1/2が掛かっているので、自ヒーローは敵レーンユニットより敵ヒーローやGrootを優先的に攻撃します。

次に２行目、ユニットの死亡数はせいぜい0~3ぐらいなので他の評価値が全て同じ時のタイブレークの働きをします。

３行目の次ターンの読みはけっこう大事です。なぜなら、このターンにさほどダメージを受けなくても、立ち位置が悪いと次のターンに集中砲火を受けるということがこのゲームではけっこうあるからです。

４行目は有利な場所に居続けるための評価です。自レーンユニットに近い位置にいるほうが良いとしています。また、敵ヒーローが全員Bushに隠れている場合はこれをBushの位置へ差し替え、そこへ向かうようにします。

５行目はスキル連発を防ぐために入れたマナ残量の評価です。マナ残量が多いほど良いです。ただ評価対象がマナだけだと最大マナアップアイテムを大量購入するという事案が起こったので、最大マナを引いています。また、マナ回復速度が高いときはスキル連発しても大丈夫なので（むしろ連発してほしいので）、評価値全体に対するマナの重要度を下げるためにマナ回復速度で割っています。

６行目はHPが低いほうの敵ヒーローを優先的に狙うようにするため、またHPが低い自ヒーローが狙われるのを避けるために入れています。

これでだいたい思った通りに、いや思った以上に上手に戦ってくれるBotが完成しました。

やったね！

時間切れで試せなかったこと

Dr.Strangeがお荷物になる試合が多かったのでValkyrieに変える
敵がスキルを使用することを考慮する
敵がMelee２体で来た時は自タワー付近で戦う
アイテム売ってもっと良いのを買う（やろうとしたけどうまく実装できなかった）
評価関数のパラメータが雑すぎなのでちゃんと調整する
ヒーローの数が減ると探索時間が余るので探索空間を広げる

感想

かなり良ゲーだと感じました。Javaのシミュレータをc++に移植するのは大変でしたが、ある程度土台を実装した後は戦略を考えるのが楽しかったです。まだまだ試せていない戦略もたくさんあるので、MultiPlayerで解放されたらまたいろいろ試してみたいと思います。ゲームバランスが良く、上位陣の戦略が様々で一辺倒になっていなかったのも良かったと思います。運営に感謝。