はじめに

筆者はコンシューマゲームもアーケードゲームもソーシャルゲームもガッツリプレイするGameholicな人間なのだが、データサイエンスを仕事にしているにもかかわらずCEDECの講演を聞いたことは一度もなかった。
自分自身の可能性(意味深)を拡げていくという狙いも兼ねて直近開催されたCEDEC 2020の講演を眺めていたところ、強化学習を使った対戦AI構築に関する講演があったため本稿にて紹介+軽く解説をしたい。
※ なお、筆者は強化学習について座学で学んだ程度であり、一部理解・説明が誤っている可能性がある。もし誤りを発見した際はぜひコメント欄で指摘いただきたい。

CEDECとは

"CEDEC（Computer Entertainment Developers Conference）はゲームを中心とするコンピュータエンターテインメントの開発、ビジネス、関連する技術、機器の研究開発などに携わる人々の技術力向上と知識や情報の交流を促進するためのカンファレンスです。" (公式HPより引用)
ゲーム業界で働いている人には馴染み深いであろうカンファレンスだが、少なくとも日本のゲーマーにはあまり注目されていないように感じる。自分自身を省みるに、ゲーマーは基本的に自分のプレイしているゲームの新情報やゲームそのものの配信、大会などに興味があるのであってそのゲームがどのようにして成り立っているか、にはあまり興味を持たないのかもしれない。
ただ、講演を覗いてみるとこれがなかなか面白い。今年はスクエニの社運を賭けた？FF7R発売から半年経っていないこともあり、FF7R関連の講演が目立った。
トレンドとしては開発におけるテスト環境(QAシステム、デバッグシステム)の構築とか、映像におけるキャラクターの表現(レンダリングなど)に関する講演が多かった。背景にはゲームハードウェアの性能の向上とそれに伴う映像の高解像度化、ゲームのボリュームの増加による工程の長大化があるのかなという印象。
機械学習もQAシステムに適用されているケースが多かったが、カードゲームにおける対戦AIの構築に強化学習を用いている事例が講演されており、強化学習に個人的に興味があるのでここで紹介する。

概要

タイトル：自己対戦と強化学習によるNPCの意思決定の研究事例(リンク)
発表者：眞鍋和子さん(株式会社スクウェア・エニックス)
Abstract：2人対戦カードゲームであるドラゴンクエストライバルズにおいて、モンテカルロ木探索とDQNを用いてNPCの意思決定モデルを構築する実験を行った。その他、クラウド学習環境についても紹介し、最後に、課題と今後の展望について述べる。
発表資料：CEDiLのこのリンクよりダウンロード可 ※会員登録が必要

強化学習とは

"強化学習（きょうかがくしゅう、英: reinforcement learning）とは、ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習の一種。エージェントは行動を選択することで環境から報酬を得る。強化学習は一連の行動を通じて報酬が最も多く得られるような方策（policy）を学習する。環境はマルコフ決定過程として定式化される。代表的な手法としてTD学習やQ学習が知られている。" (Wikipediaより)
なんだか難しい事が書かれているが、何らかの報酬があり、状態があり、そして行動が選択できる環境下で、各状態について最大の報酬を得られるような行動を機械学習で探索する手法である。報酬の概念がわかりやすいこともありゲームへの適用例がよく紹介されるが、別にゲームにしか適用できないわけではなく、ロボットの制御や自動運転にも応用できる。

環境

ドラゴンクエストライバルズというオンライン2人対戦のカードゲームが本講演の題材である。カードだけでなくリーダーキャラクター(遊戯王でいうところの遊戯とか城之内)にも固有の能力があるのが面白い。シャドウバースしかり、最近の対戦型カードゲームは大体こうなのかもしれないけど。~~インターフェイスもどことなく…~~

背景・解くべき課題

そもそも対戦用のAIが実装されておらず、練習用に欲しいというユーザの要望があった。よって対戦用のAIを構築しようとなったわけだけれども、そこには「環境が刻一刻と変化していく(カードの追加/廃止など)」というソシャゲならではの課題があった。
また、対戦型カードゲームのデザイン上の課題もあり、それが

不完全情報ゲームである(プレイヤーから見ることができない相手の情報が存在する)
不確定ゲームである(バトル開始時に山札がシャッフルされる、カードの効果にランダム性が含まれるものが存在する)

の2つである。前者についてはわからない情報がある以上適切な行動を絞り込むのが極めて難しく、行動の結果たる次の状態としても非常に多くの可能性が残ることになり、(そこに真正面からアプローチすると)計算量が発散することになる。
後者に関しても同様で、ランダム性があるということは取りうる状態数が増えるということになる。これも最適な行動を求める(学習を収束させる)にあたって課題となる。

アプローチ・実験条件

筆者は上記の環境・課題に対し、モンテカルロ木探索、DQNの2つの手法を適用し、所要のパラメータ下でどの程度の強さの対戦AIを構築できるか実験した。
なお、細かい条件は下記である。

リーダーキャラクターはテリー、トルネコの2人
デッキ内容は固定。カード種類はテリーは16種、トルネコは19種(下画像)、枚数は共に30枚。1種類のカードの上限枚数は2枚。
(資料内p13参照)

※ 本講演は写真可・SNS掲載可であり、また資料も公開されていることから上記のように資料内の画像を一部切り抜いて掲載していますが、作者、関係者の方からご指摘があった場合すぐに削除させていただきます。

手法①：モンテカルロ木探索

「モンテカルロ」という名前のごとく、多数試行を繰り返し、その結果から状態・行動ごとの評価値を推定することで最適な行動を決めていく方法。
例えば○×ゲームにモンテカルロ木探索を適用するとこんな感じになる。
(資料p20)

モンテカルロ木探索が強いのは、全ての状態をノードで表現しきれないような環境(ゲーム)。言い換えれば行動による分岐が(網羅できないぐらい)多すぎる、行動の結果の状態変化にランダム性があるなどの特徴をもった環境。
あと、記事では言及されていないけど状態空間が離散でないとうまく働かない。モンテカルロ木探索はランダムに行動を選択するシミュレーションを通して評価値を推定するため、そもそも行動の選択肢が無限にあった場合最適な行動がうまく選択できないからである。
○×ゲームやカードゲームのように取りうる選択肢が(多いけれども)有限なら対応できるが、機械制御のような取りうる入力が無数にある問題には向いていないということになる。

さて、ドラゴンクエストライバルズ(以下DQR)には不完全情報ゲームである、不確定ゲームであるという2つの問題があると述べたが、著者らはモンテカルロ木探索を適用するにあたってこれらの問題に下記のように対応している。

不確定要素への対応
ステート(状態)ノードの間にアクション(行動)ノードを挟み、アクションノードから複数のステートが分岐するように表現したことで対応した。
(資料p24)
不完全要素への対応
まず、状態の同一性の定義を明確にする。どういうことかというと、AIから見える情報が同じであれば同一状態として扱うということ。下記に例を載せる。(資料p28)

その上で、非公開情報が非公開情報として保たれるように、相手の手札を山札を含めてシャッフルした上でシミュレートするようにした。スタート時の相手の手札セットが毎回同じだと、シミュレーションを繰り返しているうちに相手の手札構成をAIが間接的に知ってしまうため。(leakみたいなものかな)

上記の工夫のもと、行動あたりのシミュレーション(モンテカルロ探索)回数を25回にして実験を行った結果、完全にランダムに行動を選択するプレイヤー(CPU)に対して91.3%の勝率を記録した。ただ、これは相手が弱いこともあり、人間から見ると「トッププレイヤーには及ばない」レベルの強さらしい。行動あたりのシミュレーション回数を10000回程度まで増やせばそのレベルまで達するかもしれないといったことも述べられている。
課題は実行時間。標準的な開発マシンで 269ms/行動かかるとのこと。1アクション1秒未満の思考時間なら殆ど気にならないように思うが、やりこんでいるプレイヤーとしては確かに待たされる感覚になるのかも。

手法②：DQN

北九州市のドンキの駐車場で車内から睡蓮花を爆音で流している人達のことではない。(断っておくと、自分は北九州市出身である)
Deep Q-Networkの略で、ニューラルネットワークによって行動価値関数Q(s,a)の値の近似を行う手法である。これだけだと知らない人は何もわからないと思うので、著者の図を使って説明する。
まずQ値を概念的に説明すると、ある状態である行動を取った時に手に入れられる報酬の期待値になる。したがって下のように、とりうる状態×とりうる行動の表(Qテーブル)で表現することができる。

Q値の定義は様々だが、一つは下記のような式で表される。即時報酬と将来の期待される報酬から構成されていて、将来分は(貰えるのが確定していないので)割り引かれているという点がポイント。

で、DQNはこの関数をニューラルネットワークによって推定する手法。入力が状態で、出力が「各行動ごとのQ値」になる。

先ほどのQテーブルでイメージしてもらうとわかりやすいが、状態と行動のパターンが多い(状態空間と行動空間が大きい)とテーブルを全て埋めるのにありとあらゆるパターンを試さなければならず、膨大な時間がかかるようになってくる。そこで一部の埋まった結果からQ関数を推定する(これが最終的にはQテーブル全体の値を推定することになる)わけである。

さて、DQNのDQRへの適用(著者も書いていたが、実に紛らわしい表記である)だが、ここでもモンテカルロ木探索の時と同様にDQRならではの課題に対処している。

行動空間が階層的で複雑であることへの対応
本ゲームでは複数あるアクションがそれぞれ様々なパラメータを持つため、単純に上のような構成のDQNを使うとゲームの挙動を表現しきれない。従って著者らは、DQNを拡張しより長期的な報酬に重みを置いたDQN(λ)を提案した。具体的には2手、3手先のQ値も考慮に入れている(≒直後のQ値に重みづけして加えている？)とのこと。
不完全要素への対応
ここは資料を読む限りではあまりピンと来なかったが、LSTM(時系列の依存関係をモデリングできるニューラルネットワークの一つ)を組み込み、直前の自身の行動を入力に追加することで対応したとのこと。

最終的なネットワーク構成は下記のようになった。V(s)が報酬関数、A(s,a)が行動関数なのは類推できるが、どう学習するのか(逆伝搬するのか)等は素人なのでよくわからなかった。。ご了承いただきたい。(資料p40)

上図にもあるが、入力となるカードID/ヒーローID/行動はカテゴリ入力で、それらを単純に数値で置換して入力するとネットワークが誤解する(数値の大小に意味があると思ってしまう)のでここではembeddingという手法で変換して入力している。one-hot(カードIDがAなら1、Aでないなら0、のようなエンコーディング)よりもカテゴリの意味の関係を捉えた変換ができると言われている。

上記の工夫のもと、シミュレータで生成した50万ログを入力として学習を行った結果、行動あたりのシミュレーション回数が25回のモンテカルロ木探索を行うプレイヤーに対して67.6%の勝率を記録した。モンテカルロ木探索よりも強くなっているのに加え、行動時間は30ms/行動とモンテカルロ木探索の10分の1程度まで減少した。

所感とか疑問とか

モンテカルロ木探索を適用する際にアクションノードを設けていたが、ランダム性によって複数生じるパターンも含めて直接ステートノード→ステートノードとしてはいけない理由があるのだろうか？そうするとゲーム木上は状態と行動から次の状態が一意に決まらないように見えるからダメなのかな。
両手法の実行時間に関しては、(ローカルで処理しているのなら)実際の端末内で処理させた場合の時間も知りたかった。多分開発マシンよりは長くなると思う。
ニューラルネットワークの線形性を考えるに、あまりに非線形なQ関数はDQNでうまく学習(模擬)できないように思うがどうなのだろう。
DQN(λ)を提案したということは、このゲームの行動には直後ではなく1ターン先、あるいは2ターン先に効力を発揮するとか、3ターン続けて効力を発揮するようなものがあるということだろうか。単に複数のアクションがそれぞれパラメータを持つだけなら、それらを全て別のアクションとして表現すればいいように思うので。遅延して発動するカードとか「このカードが場にある限りうんぬん」みたいな効果のカードとかあるよね、多分。LSTMを組み込んでいる理由もそういうところにありそう。
LSTMに直前の相手の行動も含めたらより強くなるのではなかろうか。相手の状態(手札)は観測できないけど相手の行動は観測できるので。
p45にフィルタリングとあるけど、これはdropoutのようなことをしているのだろうか？何となく過学習を防ごうとしている意図を感じた。
DQNの行動時間30ms/行動というのは推論でありネットワークの学習時間は含まれていないと思うので、その点も知りたかった。頻繁に環境が変わる以上定期的にネットワークを学習し直す必要があり、その意味で学習時間もケアしないといけないと思われるので。