【CEDEC2020】『ドラゴンクエストライバルズ』のゲーム状態と行動を反映した対戦AI構築の試み

2020年9月3日、CEDEC2020において「自己対戦と強化学習によるNPCの意思決定の研究事例」と題されたセッションが行われました。スクウェア・エニックスの眞鍋和子氏によるこのセッションでは、スマホカードゲーム『ドラゴンクエストライバルズ』の対戦AIをモンテカルロ木探索とDQNで構築する方法が発表されました。この記事では、対戦AIの構築方法を図解したうえで、ゲーム対戦以外に応用した事例も紹介します。

DQRの概要と対戦AIニーズの高まり

『ドラゴンクエストライバルズ』（以下、DQRと略記）とは、ターン性を採用したカードバトルゲームです。ゲームタイトルに「ドラゴンクエスト」とあることからわかるように、このゲームで使われるカードのキャラクターはドラゴンクエストに登場するものです。プレイ時には、まずリーダーとなるキャラクターとモンスターから構成されるデッキを構築します。そして、カードをゲームフィールドにおいて攻防を繰り返して、対戦者のリーダーのHPをゼロにすれば勝利します。

モンスターにはそれぞれ固有の特技があり、プレイヤーが使えるカードパックは数か月ごとに追加されます。またデッキの組み方によって、リーダーへのシナジーが発動します。こうしたゲームシステムにより、DQRで勝利するにはデッキを組む際の戦略性と対戦者のアクションを推測することが求められます。

DQRの基本プレイは人間プレイヤー同士の対戦ですが、色々なデッキを試したい、人間相手だと緊張するといったさまざまな理由から対戦AIとプレイしたいというニーズが高まっています。

以下ではDQRの対戦AIの構築方法を解説しますが、この対戦AIは2020年8月に導入されたソロモードで採用されているオートプレイとは異なるものです。また、DQRの対戦プレイはデッキ構築と対戦という2つのフェーズから構成されていますが、解説する対戦AIは対戦のみに対応したものとなります。

DQRの特徴と採用する手法

対戦AI構築に際して適切な手法を選択するためには、ゲームの特徴を理解しなければなりません。DQRの特徴は以下の2点に集約できます。

まず、不完全情報ゲームであるということです。不完全情報ゲームとは、プレイヤーにゲームの状態を知るためのすべての情報が与えられないことを意味します。DQRではデッキからカードを引くことによって使えるカードが決まりますが、どんなカードを引くかは事前には分かりません。

もうひとつの特徴は、不確定ゲームであることです。前述したようにデッキからカードを引く際に生じる偶然性に加えて、DQRではランダムな効果を持つカードもあります。こうした偶然性がゲームに組み込まれていることにより、同じゲーム状態に対して同じ行動を選択しても、生じる結果が異なってきます。

以上のふたつの特徴をもつDQRの対戦AIを構築するためには、膨大なゲーム状態と偶然性が処理できる手法が求められます。そうした手法として有効なのが、ゲームを進めながらリアルタイムで戦略を探索する「モンテカルロ木探索」と、プレイ前に学習して評価器を作成する「DQN」です。

ゲームの状態と行動を網羅的に表現する「木探索」

モンテカルロ木探索とは、木探索とモンテカルロ法を組み合わせた手法です。このうち木探索とは、ゲームの状態を「ノード」、ゲームに対する行動を「エッジ」として表現して、ゲームの進展を網羅的に記述した上で最適な行動を選択する手法です。

木探索を分かりやすく解説するために、〇×ゲームを例にしてみましょう。ある局面における〇のプレイヤーのターンは、現在の〇と×の位置がノード、考えられる〇の置く場所がエッジとして表現できます。〇のプレイヤーが行動すると今度は×のプレイヤーのターンとなり、×のプレイヤーに関してノードとエッジが表現できます。この手順を繰り返すと、ゲームの勝敗が決まるまで枝分かれ状に広がるノードとエッジが記述できます（下の画像参照）。このノードとエッジの集まりは「ゲーム木」と呼ばれます。

木探索を使って対戦AIを構築する場合、AIはノードとエッジを網羅的に記述した上で、AIの勝利につながる行動を選択すればよいということになります。

状態を確率的に絞り込むモンテカルロ法

木探索はゲームの進展を直観的に理解できる上に網羅的に表現できるので、対戦AI構築の手法として優れています。しかし、ルールが複雑なゲームに木探索を応用するとゲーム木が大きくなりすぎて、現実的な演算能力を使って動作させるのが困難になるという欠点があります。こうした木探索の欠点を補完するのが、モンテカルロ法です。

モンテカルロ法ではゲームにおける行動をランダムに選択するようにした上で、一定回数（例えば100回）ゲームの勝敗が決するまでプレイします。こうしたランダムプレイに際しては、勝利した場合や引き分けた場合の評価値を設定しておいて、ランダムプレイ終了時に得られた評価値を集計するようにします。対戦AIは集計された評価値を比較して、もっとも高い評価値が付与された行動を勝利につながる最適な行動として選択します。

以上のモンテカルロ法と木探索を組み合わせると、状態数が多いゲームであっても、最適な行動を算出することができるのです。

DQRをモンテカルロ木探索で表現する

DQRの対戦AIをモンテカルロ木探索を使って構築する場合、同ゲームの特徴である不完全情報性と不確定性を適切にゲーム木に表現しなければなりません。

DQRでは、対戦者がゲームフィールドに出していないカードを知ることができません。こうした不完全情報性は、ゲームフィールドに出されているカードが同じであれば、ゲームフィールドに出ていないカードが何であろうと同じゲーム状態と定義することによって処理できるようにしました。

また、ランダムな効果を持つカードを使用した場合に生じる不確実性を表現する方法として、「アクションノード」を導入しました。このノードは、確率的に発生する行動を分岐するエッジで表現するものです。例えば50%の確率で効果が発揮されるカードは、ふたつに枝分かれするエッジがついたノードとして表現されます（下の画像参照）。

なお、アクションノードの評価値は、枝分かれした複数の子ノードから期待値を算出するようにしました。

対戦結果と課題

以上のようにしてモンテカルロ木探索を用いてDQRの対戦AI（MCTSプレイヤー）を構築して、ランダムに行動を選択するように構築したランダムプレイヤーと対戦させた結果、MCTSプレイヤーの勝率が91.3%となりました。しかしながら、平均的な人間プレイヤーと対戦してもらって感想を求めたところ、人間のトッププレイヤーには遠く及ばないと返答されました。

MCTSプレイヤーをさらに強くするために必要なのは、シミュレーション数の増加です。モンテカルロ木探索では一定回数ゲームをランダムにプレイした上で評価値を算出するため、シミュレーションの回数が多いほど正確な評価値が得られます。しかし、シミュレーションの回数が増えると、次第に現実的な演算時間で評価値が算出できなくなります。こうした課題に対しては、計算リソースを減らす努力が有効です。

モンテカルロ木探索では多数のシミュレーションが不可欠となるものも、開発後にはあまり調整が必要ないというメリットがあります。さらには、総じて開発コストが安いのも魅力です。こうしたメリットは、次に解説するDQNを使った対戦AIと性能比較する上で重要となります。

最適な行動を学習するDQN

モンテカルロ木探索の他に試みられた手法が、DQN（Deep Q-Network）です。この手法は、ゲームプレイAIの開発で使われる強化学習の一種です。手法の名称にある「Q」とは、「Q-Learning（Q値の学習）」を意味しています。DQNとは、Q-Learningとディープラーニングを組み合わせた手法なのです。

Q-Learningとは、ゲームにおける状態と行動から算出されるQ値にもとづいて最適な行動を導出する手法です。この手法におけるQ値とは、ある状態に対する何らかの行動がゲームの目標達成に寄与する度合いを表したものです。Q値の定義により、AIはこの値がもっとも高くなる行動を選択すればよいことになります。

Q値は、初期値として任意の値が各行動に付与されます。AIはランダムに行動を選択することから学習を開始し、ゲームの目標を達成するまで選択を繰り返します。AIの行動選択時にはQ値が更新されます。この更新に使われる計算式には過去の行動に関するQ値もふくまれているため、ゲームの目標達成に寄与する行動を選ぶとQ値が高い値に更新されます。こうしてAIが行動選択に繰り返すことによって、Q値が最高となる最適な行動を特定することができます。

DQNとは、Q値の更新処理にディープラーニングを用いる手法です。具体的には、ゲームの状態を入力層、選択する行動を出力層としたディープラーニング・ネットワークを構築して、ネットワークにおける重みを更新することを通してQ値を算出します。

DQNを使った時の学習構造

DQR対戦AIの構築にDQNを用いる場合、DQRの複雑なゲーム状態を表現できる学習構造を構築する必要があります。そうした学習構造は、以下の画像のように図示できます。

学習構造において注目すべきは、LSTM（Long Short-Term Memory）です。LSTMとは、時系列データを処理するのに使われるニューラルネットワークです。このネットワークが使われるのは、直前（つまり時系列的に直近）の行動を入力値に反映されるためです。

もうひとつ注目すべきは、カードIDとヒーローIDに関するEmbeddingです。Embeddingとは、カードの特徴のような数値情報として与えられていないものをベクトルとして表現する手法を指します。非数値情報のベクトル化は、ベクトル化したい情報を座標空間にプロットすることによって実行できます。Embeddingは、文字列を処理対象とする自然言語処理にも使われています。

行動空間の表現

以上のような学習構造は、対戦AIが選択可能な行動のQ値を算出するために組まれたものです。各行動のQ値を算出するためには、モンテカルロ木探索におけるゲーム木のように、行動を構造的に整理する必要があります。DQNを使った対戦AIの行動を整理したものが、以下の図に示された行動空間です。

行動空間は3層構造になっています。最上位層には、ゲームフィールドに置かれたカード、プレイヤーが手札として持っているカード、そしてターン終了といった選択可能な行動がオブジェクト単位で整理されています。最上位層の下にある中間層には、各オブジェクトがもつパラメータの種類が整理されています。何らかの効果を発揮する手札であれば、手札を置く位置と効果を発揮する対象というパラメータがあります。ターン終了のようなオブジェクトに関しては、パラメータが設定されていません。最下層には、パラメータの具体的な情報が整理されています。何らかの効果を発揮する手札に関して、その効果を発揮できる対戦者のユニット、さらには手札を置くことができる位置などがまとめされています。

Q値は、以上に示した行動空間の最下層に付与されます。この付与されたQ値にもとづいて、行動空間のなかからQ値が最大となるような行動を絞り込みます。この絞り込みにおいては、以下のような処理が実行されます。

1. 第1ステップ：行動空間のなかにはゲームルールに則していない選択不可なものもあるので、そうした選択不可なパラメータを絞り込み対象から除外するフィルタリングを実行する
2. 第2ステップ：最下層のパラメータからQ値が最大のものを選択して、その値を中間層のパラメータのQ値として渡す
3. 第3ステップ：中間層に渡されたQ値の平均値を計算して、その算出結果を最上位層に渡す。最大値ではなく平均値を渡すのは、「手札の効果は強力だが、置ける位置はあまり良くない」というような総合的な評価をQ値に反映させるため
4. 第4ステップ：最上位層のオブジェクトがもつQ値を比較して、最大となるものを最適な行動として決定する

DQNを使ったDQR対戦AIは、以上のようなQ値にもとづいた最適行動の決定を繰り返すことによって、より最適な行動を選択できるようになります。今回構築した対戦AIには、学習データとしてシミュレーターで生成した50万のログファイルが使われました。

対戦結果と課題

以上のようにして構築したDQN対戦AI（DQNプレイヤー）と前述したモンテカルロ木探索で構築したMCTSプレイヤーを対戦させたところ、DQNプレイヤーの勝率が67.6%となりました。

DQNプレイヤーのMCTSプレイヤーに対する優位は、勝率だけではありません。MCTSプレイヤーは、そのアルゴリズムの性質上、プレイ中のシミュレーション数を増やせばより良い行動を選択できますが、選択するまでの処理時間も増えてしまいます。対して、DQNプレイヤーは高負荷な処理である学習がプレイ前に完了しているので、ランタイムリソースをあまり消費しないのです。

DQNプレイヤーはMCTSプレイヤーより優れているように見えますが、欠点もあります。DQNプレイヤーは、カードパックの更新のようなゲーム設定が大きく変化する度に再学習が必要になります。

これまで解説したふたつの対戦AIの特徴をまとめると、以下のようになります。

MCTSプレイヤー：

1. アルゴリズムを直観的に理解できる
2. 開発後の調整が少なくて済む
3. 開発コストが安い

DQNプレイヤー：

1. MCTSプレイヤーより強い
2. ゲーム設定が大きく変わると、再学習が必要
3. 開発できる人材の確保が困難

以上のように特徴をまとめると、MCTSとDQNにはそれぞれ一長一短があることが分かります。

対戦AIのさらなる応用

人間プレイヤーとの対戦を目的として開発された対戦AIをゲームの対戦以外に応用すると、新たな知見が得られます。

MCTSの性能を評価するために用意したランダムに行動を選択するランダムプレイヤー同士を対戦させたところ、リーダーキャラクターにトルネコを選択した場合に高い勝率となりました。対して、ランダムプレイヤーより強いMCTSプレイヤーどうしを対戦させたところ、テリーがリーダーキャラクターの時に高い勝率となりました。

以上の結果は、ゲームバランスがプレイヤーのゲームに対する習熟度によって変化することを示唆しています。こうした変化は、対戦AIを使うことによってまったく同じ強さのプレイヤーどうしの対戦を実行したことによって、はじめて発見できるものと言えます。

また、強い対戦AIを作り続けることによって、ゲームバランスを崩壊させてしまうようなバランスブレイカーに相当する戦術を発見することが可能となります。バランスブレイカーとなる戦術を発見した場合、そうした戦術がゲームデザイナーの意図に沿うものかどうかを検討することが必要となるでしょう。

バランスブレイカーを検出する対戦AI開発の試みに関しては、昨年開催されたGDCにおいて発表を行いました（以下の発表資料を参照）。

参考資料：Balancing Nightmares: an AI Approach to Balance Games with Overwhelming Amounts of Data

関連記事：【GDC 2019】ソーシャルゲームのバランス調整に遺伝的アルゴリズムを応用する

以上にまとめたDQRの対戦AI構築において注目すべきなのは、ゲームの状態と行動を採用した手法で処理できるように数値化するプロセスではないでしょうか。こうしたプロセスは、DQR以外のターン性カードバトルの対戦AIを構築する際に大いに参考になることでしょう。

Writer：吉本幸記