【GDC2021】深層強化学習はNPCをナビゲーションメッシュという束縛から解放できるか

2021.9.15ゲーム

ゲーム内で人間プレイヤーのように振る舞えるエージェントの開発は、ユーザーにとってのゲーム体験の向上はもちろん、ゲーム開発者にとってもテストプレイやバランス調整の負担を減らすために必要不可欠だと考えられています。その実現に立ちはだかるもっとも大きな壁は、プレイヤーとエージェントを隔てるナビゲーションに対するアプローチの相違です。その溝はゲーム構造が複雑になるほど増大していきます。

7月19日から7月24日までオンラインで開催された「Game Developers Conference」（GDC 2021）にて、Ubisoft La ForgeのR&DプログラマーMaxim Peter氏とR&DサイエンティストJoshua Romoff氏による「Deep Reinforcement Learning For Navigation（深層強化学習を使ったナビゲーションへのアプローチ）」というセッションを取材しました。

このセッションでは、Ubisoftのファーストパーソン・シューティングゲーム『ハイパースケープ』（2020年、ユービーアイソフト）の中で、深層強化学習を使ってエージェントにナビゲーションをゼロから学習させる新たなアプローチを技術検証しています。

人間とAIを根本的に隔てるナビゲーションの相違

ゲーム開発におけるナビゲーションとは、エージェントが目標地点まで移動するための最短ルートをリアルタイムで探索する仕組みを指します。人間のプレイヤーは、ゲーム画面に表示される視覚情報によって移動経路を決定し、入力デバイスによってキャラクターを操作します。一方、エージェントはナビゲーションメッシュ（Navmesh）というデータ構造と、ダイクストラ法やA*探索アルゴリズムを使ったパス検索でNPCを動かします。

『ハイパースケープ』におけるキャラクターの移動手段は、前進と後退、左右への平行移動、旋回、ジャンプ、ダブルジャンプ、ジャンプパッドの6種類です。前進後退と平行移動、旋回はナビゲーションメッシュだけで解決できますが、高低差を越えるジャンプ移動を実装するためには、離れたナビゲーションメッシュ同士を接続するためのジャンプリンクを設置しなければいけません。ジャンプリンクの設置数は、移動手段による到達距離が伸びるほど増えていきます。

たとえば、ジャンプよりダブルジャンプ、ダブルジャンプよりジャンプパッドの方が遠くへ飛べるので、必然的に移動先となるジャンプリンクの候補も増えるというわけです。ここにジェットパックやテレポートという長距離の移動手段が加われば、リンクの数は指数関数的に増えることになります。つまり、キャラクターの移動手段が増えるほど、ナビゲーションメッシュの生成コストとジャンプリンクのストレージコストは増大していきます。

また、人間のプレイヤーは複数の移動手段を直感的に使いこなしてマップを縦横無尽に動き回れますが、エージェントに同じことをさせるためには非常に複雑なアルゴリズムが必要です。当然、パス検索における計算コストも膨れ上がります。現実的なリソースの範疇で商品化できるゲームを開発するには、どうしてもNPCの移動手段やマップ構造の複雑さを制限しなければいけません。

こうした課題の根底にあるのは、プレイヤーとエージェントを大きく隔てるナビゲーションに対するアプローチの相違です。本当の意味で人間らしく振る舞うNPCを実現するためには、エージェントをナビゲーションメッシュという束縛から解き放ち、プレイヤーを模倣した直感的な意思決定ができる仕組みを作る必要があります。

深層強化学習でAIに世界の歩き方を学習させる

人間のプレイヤーはキャラクターを操作してゴールを目指す際に、それぞれの移動手段をどうやって使うかをわざわざ考えたりしません。どの場面でどの移動手段を使えば最短でゴールを目指せるかだけ考えます。それこそが深層強化学習における学習プロセスそのものです。深層強化学習は、完全にランダムな行動を繰り返すエージェントが、成功体験を積み重ねることで徐々に最適解へと自らたどり着く機械学習モデルです。ゲーム情報と各行動の報酬さえ決めれば、エージェントは報酬を最大化する行動を取れるように学習していきます。

今回の技術検証でエージェントに与えられるゲーム情報は、前述した6種類の移動手段に加えて、目的地を示す位置座標、現在のスピードと加速度、レイキャスト（光線の反射からオブジェクト情報を取得する判定手段）によって生成されるDepth Map（深度マップ）です。Depth Mapとは、視点から対象までの距離をマッピングした画像データを指します。

深層強化学習で用いられるニューラルネットワークでは、このDepth Mapが2D Convolutions（2次元畳み込み）でベクトルへと変換されます。これらの情報がLSTM（Long Short-Term Memory、長・短期記憶）というアーキテクチャへ送られることで、エージェントは自身が歩んだ軌跡を記憶できるというわけです。このLSTMの出力がポリシーネットワークへ入力され、エージェントの次の行動を決定します。ポリシーネットワークとは、エージェントが持つすべての選択肢から最善の手を吟味するための仕組みです。

このニューラルネットワークをゲームエンジンに組み込み、5台のマシンを使って225体のエージェントに12時間から15時間学習させたということです。その結果、ナビゲーションメッシュに頼ることなくダブルジャンプやジャンプパッドを器用に使いこなしながら、広大なゲーム空間を動き回るNPCを見事に実現しています。ちなみにエージェントが小刻みに跳ぶ、いわゆるバニーホップを繰り返しながら移動してしまうのは、通常の移動よりもスピードが出てしまうゲームエンジンの仕様をエージェントが学習した結果だということです。

複数のマップでエージェントの学習成果をテストした結果、200m×200m×90mサイズのマップにおける成功率は95％、400m×400m×90mで90％、1000m×1000m×90mで74％でした。ゴールまでの距離が伸びると成功率が極端に低下するのは、レイキャストで得られる周囲の情報のみに依存しているエージェントには、遠くを見渡すような能力がないからだと考えられます。つまり、マップ内の地形によっては、エージェントが一度進入したら二度と抜け出せなくなるような事態も起こり得ることを意味します。

くわえて、計算コストでも課題が残ります。今回の深層強化学習を使ったナビゲーションの計算コストは、キャラクター1体につき毎フレーム（60分の1秒）0.3から1.0ミリ秒を要したとのこと。これに対して、ナビゲーションメッシュを使った従来のナビゲーションにおけるパス検索の時間は、およそ0.3ミリ秒だと報告されています。数体のNPCを同時に動かす程度なら問題ありませんが、100体近いNPCを想定した場合には実用化にはほど遠いパフォーマンスです。