ゲームAIコンテスト「CodinGame Fall Challenge 2020」に参加して、Legendリーグ63位でした！

f:id:betrue12:20201123205107p:plain

f:id:betrue12:20201123205022p:plain

どんなゲーム？

f:id:betrue12:20201121205452p:plain

素材からポーションを作ってお金を稼ぐゲームです。各プレイヤーはターンごとに「注文リスト内のポーションを調合して報酬を得る」「呪文を使って素材を獲得したり変化させる」「新しい呪文を覚える」「休憩して既に使った呪文を回復させる」のいずれかの行動を取ることができます。最後に稼いだお金が多いほうが勝ちです。

効率よく呪文を使って、短いターンで報酬の多いポーションを作れる手順を組み立てることが何よりも重要です。一方で、覚えられる呪文とポーションの注文は2人のプレイヤーに共通で、どちらかが先に取るとなくなってしまいます。相手が持っている素材と呪文のリストも見えるので、相手の行動を予測したり、相手が欲しそうなものを先回りして取ることで妨害したりする戦術も可能です。

以降の戦略説明ではルール内の言葉が多く登場しますので、ツカモさんのルール和訳も合わせてご覧ください。

codingame:Fall Challenge 2020 ルール要約&内部パターン紹介 - tsukammoの収穫記

戦略

大まかな行動方針は以下の通りです。

最初の6ターン：必ず呪文を習得する
それ以降：ビームサーチを用いて行動を決定する

ビームサーチでも呪文習得は行動の選択肢として考慮するので、全部ビームサーチで行動決定するという案もありました。しかし序盤は相手も呪文を多く取ってくるので、未来のターンで取れる呪文に不確実性が高いと考え、先を読まずターンごとに判断する方法にしました。

序盤の呪文習得

このゲームでは、repeatableな呪文を用いて大量の素材を一気にグレードアップさせていくことが非常に重要です。そのためrepeat回数を考慮した呪文の価値付けをしました。習得可能な呪文を以下のように価値付けして、最も価値が大きいものを習得しました。

呪文1回分の価値 $v$ ：素材の価値を順に $1.25, 2.25, 3.25, 4.25$ としたときの、呪文前後での価値合計の増分
repeatableな呪文の最大回数 $m$ ：1回で消費する素材個数 $x$ 、獲得する素材個数 $y$ とすると、 $m=\lfloor\frac{10}{\max(x, y)}\rfloor$
呪文の価値： $0.75v\frac{1+m}{2} - (消費する先読み税) + (得られる先読み税) + (補正値)$

ポーションの報酬額は素材の価値を $1, 2, 3, 4$ として設定されているため、私も長くこの値を使ってきましたが、差し引きで素材個数が増える呪文を優遇するためにLegend昇格直前で $1.25, 2.25, 3.25, 4.25$ に変更しました。これは呪文がキレイに回るパターンである

個数が増える呪文で個数を増やす→tierを上げる呪文で全体のtierを上げる→ポーションを作って個数が減る→個数が増える呪文で個数を増やす→…

という流れができやすいようにしたいという意図です。

係数 $0.75$ は、呪文の効果と先読み税の得失のうちどちらを重視するかを決めるものです。当初この係数は $2$ でしたが、先読み税が高い呪文を取りすぎて序盤の所持素材に差が付き、そのまま追いつけない試合が多くありました。そのため何度か調整して結果的に $0.75$ に落ち着きました。

補正値では「tier-0の素材を消費する呪文（まだ持っていない場合）」と「消費無しで3個以上の素材が貰える呪文」の価値を $+2$ しています。逆に「既に持っているrepeatableな呪文と消費色・獲得色が全く同じ呪文」は機能が被ってしまうので、価値を $-2$ しています。

ビームサーチ

行動と状態管理

ビームサーチで考慮する行動の候補は以下の通りです。

現時点で見えているポーションの作成
現時点で見えている呪文の習得
呪文の使用（repeatableの場合、可能な全回数を試す）
休息

ポーションの緊急ボーナスや呪文習得の先読み税などは未来のターンでは変動する可能性がありますが、現時点で見えている情報のままとして扱います。また、現時点で出現していない習得呪文やポーションは考慮しません。

状態を表す構造体は以下の情報を管理しています。

自分のインベントリにある素材の個数
自分の累積ポーション作成個数
使用可能な呪文のID配列
使用済みの（休息で回復する）呪文のID配列
習得可能な呪文のID配列
作成可能なポーションのID配列
最初の行動
評価値

IDから各アクションの中身を取り出すための配列を別途作っておくことで、状態が持つべき情報をIDだけにしています。ビームサーチでは状態をコピーすることが多いのでなるべくスリムにしました。

ビーム幅は色々試した結果60になりました。時間で探索を切っているので見ているターン数は決まっていませんが、実測では10ターンくらい先まで見ていました。

状態の評価値の計算

状態の評価値の計算に用いるのは、それまでの行動で作成したポーションの価格と作成したターン、そしてインベントリの素材です。

ポーションは相手に取られる可能性があり、なるべく早く取ったほうが有利です。そのためポーションの報酬は、現時点からポーション作成までの経過ターン数に応じた減衰率を掛けて評価値に加算していきます。具体的にはターン数を $t$ として $0.9^{t}$ を掛けています。

さらに「現時点で相手が作成可能なポーション」である場合、次のターン以降には無くなっている可能性が高いので、次ターン以降に作る場合はさらに $0.8$ の減衰率を掛けています。

インベントリの素材の価値はそれぞれ $1, 2, 3, 4$ として計算して合計し、こちらにも $0.9^{t}$ を掛けています。インベントリの素材は「将来的にポーションの報酬に変わる可能性があるもの」なので、本来はポーションの報酬の係数 $0.9^{t}$ よりも低い割合にするのが自然だと思いますが、低くするとポーションを作った直後にインベントリが空になって次の動きが悪くなることが多かったので高めに評価しています。

ただし高いtierの素材がインベントリを圧迫して消費できない状態になってしまうと詰むので、tier-2とtier-3の素材はそれぞれ5個分までしか評価値に算入しません。

例外として、累積6個のポーションを作った状態は特別に扱います。自分が6個のポーションを作った状態でゲームを終わらせるのは有利なので、経過ターン数が少ないほど大きくなるボーナス値を足しました。またインベントリの価値は計算せずに、最終得点計算の基準（つまりtier-1以上の素材1個につき1点）で6個目のポーションの報酬と同じように加算しています。

ゲーム終了条件の考慮

現ターンでゲームが終わる可能性がある状況では、ビームサーチを行わずに行動を判断することがあります。

もし自分の累積作成ポーションが5個で、ポーションを作成することで勝利が確定する場合、ビームサーチを行わずにポーションを作成して終了します。「勝利が確定する」かどうかの判定では、相手がポーションを作るだけでなく呪文で素材ボーナスを目一杯伸ばすことも考慮しています。Gold上位だと、勝ちを読んだと思ったら素材ボーナスを伸ばされて負けることが意外とありました。

また逆に相手の累積作成ポーションが5個で、相手がポーションを作成することで自分が負ける場合、自分はポーション作成または呪文によって可能な限り最終スコアを高めます。これで勝てている試合も意外とありました。

やっていないこと

以下の2つは検討しましたが、効果が期待できるほどしっかり実装に組み込める気がしなかったので見送りました。

まだ見えていない呪文やポーションの注文を予測して未来の行動を評価すること。
相手の未来の行動を予測すること。

何となく良さそうだなと思っていた戦略は、「ある1手目の行動について、相手の行動に応じて分岐するいくつかの展開を考えて、それらの展開の評価値の重み付き平均をその1手目の行動とする」という考え方です。例えば狙っていたポーションが先に取られて非常に苦しい局面になることがあったので、取られた場合の展開も考慮しながら行動を評価すると良さそうだと考えました。

考え方としてはモンテカルロ木探索に近いのかな。ただ実装経験がなく、ビームサーチからの移行も難しそうだったので採用しませんでした。

その他、雑多な感想

前回のパックマンがとても面白かったので、半年間密かに楽しみにしていました。今回もLegendリーグに行けて良かったです。

駆け引きや読み合いも重要かもしれませんが、まずシンプルに効率を上げないと太刀打ちできません。Silverリーグにいた頃、上位勢が自分の想像をはるかに超える速度で呪文を回しているのを見て衝撃を受けました。こんなの無理だろと思っていましたが、ビームサーチをしっかり組んで自分のプログラムが同じような動きをしてくれた時は嬉しかったです。その時のツイート↓