「戦略ゲームAI解体新書」読書会ログ 4 章 後半

読書会

今週も読書会ログ。4章は後半。

4.5 コンストラクション

ここからの題材になる「クラフトシリーズ」の紹介が主でした。

コンストラクションとは

  • 周りから資源を集めて、お城や基地を建設し、その中でさらに兵士や宇宙船を生産するシステム
  • コンストラクションと戦闘を掛け合わせたゲームの場合、交互にかつ効率的にそれらを行う必要がある
  • コンストラクションばかりでは的に破壊され、攻撃ばかりでは物量で敗北する

クラフトシリーズの AI

  • 偵察や戦闘を司るナビゲーションAI
  • 「ウェーブ」という概念を前提に、ウェーブをどのようにプレイヤーの集団にぶつけるかを決定する上位AI （メタAI）

4.6 スカウティング

まず用語。スカウターといえばサイヤ人がつけてるイメージしかなかった。。

スカウティングの難しさ

  • 敵と全く遭遇しないことらしい
  • 人工知能側の斥候が何も情報を持ち帰らないということは、プレイヤー側も敵と接触していないということ。戦わない時間が過ぎてしまう

スカウティングの難しさへの対応

1. スタークラフト, ウォークラフトIII

  • 人工知能側はすでにプレイヤーがどこにいるかを知っており、あたかもスカウトしているように見せる
  • ゲームが冗長にならないようにする工夫として、このチートはよく使われる

2. スタークラフト2

  • 正当にスカウティングを行う
  • スカウティングで、それぞれの座標における敵の種類、観測時刻。
  • 各領域（最初に探索する or メインの通り道 or 偶然探索される) の特性も情報として持ち帰る
  • ハードウェアスペックの向上でスカウターにリソースを割けるように

+α

4.7 パス検索、群制御、ステアリング

パス検索の歴史

しかし、ナビゲーション・メッシュ上のA*アルゴリズムでは解けない移動の問題もあるらしい。
また、ストラテジーゲームでは「集団の移動」という特有の要件もついている。

4.7.1 タイルベースのパス検索

  • 狭い領域
  • キャラクター同士がひしめき合う場面
  • パス検索により移動するキャラクター同士で起こる衝突の問題を回避する

タイルベースのパス検索 (Tile-based pathfinding)

  • キャラクターが占有するタイルをマーキング（占有度マップ）
  • 占有しているスペース以外でA*パス検索する
  • A*パス検索前に単に直進できる場合は検索せず直進する

図がわかりやすい。

包囲攻撃

  • 1体の敵を多数の味方で包囲する方法
  • 敵キャラクターの周囲で空いているスペースを探索する場合にもタイルベースでスペースを検出し、キャラクターを加えることができる

4.7.2 固定パス

  • 開発者がウェイポイントを１つ１つ置いていた時代
    • 90年代では最もよく使われていた
    • 毎回同じパスを通るため、敵のプレイヤーから読まれやすい
    • 経路を変えるためには、毎回ウェイポイントデータを変更する必要
    • 2004 年でも主流は固定パスらしい（著者の現場では）
  • パス検索にすると、完全なデバッグができなくなる
    • ゲーム内で生成されるパスであるため
    • パス検索を導入する際は、主要経路だけ確認する、時間内に辿り着かなければ再検索 or ワープなど、セーフティネットが必要だった

4.7.3 ゾーンによるグループの移動

ユニットによる移動

  • ストラテジーゲームではユニットに対して移動を命じる
  • 2 パターンある
    1. それぞれのキャラクターが目的地までパス移動する場合
    2. リーダーをフォローする場合

それぞれのキャラクターが移動する場合の課題

  • 同じ場所から出発すると縦に並んでしまう
  • 敵からは順序撃破の対象になってしまう

ゾーンベースのパス検索

  • 上記の問題の解消のために導入
  • マップを大きく分割したゾーンを導入し、そこでは自由に動き回れる
  • 移動の際は戦列を横にも展開できるため各個撃破されにくい

ゾーンに関しては書籍の図を参照した方がわかりやすい。

4.7.4 四分木によるパス検索

マップの４等分をスケールごとに変えて繰り返して検索していく方法。
書籍の図の実際のパス検索の様子がわかりやすい。

4分木の利点

  • 高速かつシンプル、特別な調整も必要ない
  • ３次元に拡張した８分木もある
  • ただし、8分木はスペースの多い平原や宇宙空間では良いが、曲がりくねったダンジョンだと効率的ではなく、用途は限定される
  • 3D ゲーム初期には、BSP (Binary Space Partition) の2分木空間検索も使われていた

4.7.5 地形から距離を取ることによるグループの移動

ここも書籍の図を見る方がわかりやすい。

  • ゾーン分割でフォーメーションを維持しつつ移動する場合に、障害物を回避する
  • ユニット移動を円領域として捉え、パス検索時に、円の半径分だけ障害物からずらして検索する

フォーメーションの追随ルール

三角形のフォーメーションを組む場合に、リーダーをフォローするのではなく、他のキャラクターを追随するルールを決めて移動させることが紹介されている。

4.7.6 群制御

6 つの基本アルゴリズム (モード) からなるとなっている。

  1. フォローイング (following) 特定のキャラクターや仮想的なリーダーに追従
  2. フロッキング (flocking) 一団となって目的に向かう
  3. グルーピング (grouping) 一点に集まる
  4. セパレーション (separation) お互いの間隔を開ける
  5. アボイダンス (avoidance) 障害物を割ける
  6. アライバル (arraival) 特定のポイントに到着する

flock という動詞は初めてみた。

ステアリング

  • 加速度や速度によるキャラクターの移動制御
  • 上記のアルゴリズムもすべてステアリングの一種（でいいのかな？）

アルゴリズムについて

  • 通常のフロッキングに加えて「(6) アライバル」が重視されているのは、ストラテジーゲームの操作ではマウス・ポインティングによるグループ移動の指示が基本のため
  • グループ移動時は、フォローイングだけでなく、狭い場所ではグルーピングで集まり、広い場所ではセパレーションで距離を取り、途中の障害物にはアボイダンスで避けていき、指定座標にアライバルする必要がある。
  • アライバルは、到着地点における各メンバーの立ち位置も決める。リーダーとメンバーの相対座標が定義される。

4.7.7 ファンネル・アルゴリズム

  • A*アルゴリズムなどでパス検索したのち、それを最適化（スムーズ化）するためのアルゴリズム。スムージングとも呼ぶ。
  • パス検索は入力が始点と終点で、出力が始点から終点へのメッシュやポイントの列であるため、粒度に応じてジグザグになりがちなため必要になる

アルゴリズムについて

  • ナビメッシュ上のA*アルゴリズムは、「どの三角形を辿れば最短のパスになるか」を示しているだけ
  • 通常は辺の中点を通るが、特定の頂点に近い側を辿れば、より近いパスがわかるはず
  • スタート地点から隣の２つの頂点をとり、以降は２つの頂点を交互に次の頂点へと移していく
  • スタート地点と、この動かしていく２点での三角形がパス領域の場合はそのまま進めるが、パス領域からはみ出した場合はスタート地点を、その三角形（スタート地点と２点）がパス領域に入るようにスタート地点を動かしていく。

ここも書籍の図を見た方が理解が早いと思う。

4.7.8 ウェーブ

  • ストラテジーゲームや長期的な戦闘のあるゲームに欠かせない概念。
  • ストラテジーゲームでは、移動し戦闘するキャラクター集団のこと。
  • 第一波、第二波、第三波とタイミングを開けて敵ウェーブが攻める。

ソシャゲをしていると、1, 2, 3 回戦みたいな感じで戦闘があることをウェーブと呼んでいると思うが、ストラテジーゲームではだいぶ印象が違うなと感じた。

基本的なウェーブ

  • ヒートマップ（影響マップ）を用いて「ホットポイント」（敵の最も支配的な領域に対してウェーブを発生させる
  • ホットな領域を冷ますようにウェーブを放つ
  • ウェーブが放たれた後は追加の制御はなく、長い経路や戦闘の中で広がり、弱体化していく

制御をかけたウェーブ

  • (a) Attack 攻撃状態
  • (b) Defend 防御状態
  • (c) Regroup 分散してしまった状態に集合をかける（撤退に近い)
  • (d) Retreat 撤退
  • (e) Harass 敵への基地攻撃でターゲットの弱点をついて、即逃げ帰る
    • 生産施設や戦闘能力の無い箇所に現れたりするらしい

上記の制御でウェーブに動的な変化を起こすことを可能にする。
(e) は後述のトークンの制限が撤廃されたときに導入されたらしい。

ウェーブ・オブジェクト

  • ウェーブを発生させるためのトークン(許可証)
  • 前のウェーブが敵を殲滅する、撤退・消滅するなどしてトークンを次のウェーブに渡さないと次のウェーブが発生させられない
  • ゲームによっては、制限を取払い無限個のウェーブを発生可能に
  • ただし、通常はゲームの必要数に収められる

キャンペーンモード

  • オフラインでストーリーを進めるゲームモード
  • ウェーブはストーリーの演出上のもの
  • よって、スクリプト言語やエディターによる行動指定で準備される
  • AI というよりは、デザイナーがウェーブ発動のトリガを設定する

意思決定について

うまく理解できていない気がするが、読書会の中で以下のようなことを指しているのではとなった。

  • 生産した後にそこで自動で何かをやってくれるとか
  • 戦術（攻撃・防御モード）によって判定するルーチンが変わるなど

4.7.9 基地構築のための地形解析

コンストラクション（構築）を含むゲームで必要になる。
空き地を確認し、建築物を建てるため人工知能も建築場所を見つける。

  • 最初からある建築物・採掘物の領域は塞がない
  • マップの端の領域は移動のために確保
  • 建築物の行き来がしやすいように通路を通す

など、探索するルーチンがある。

一方でこのルーチンは重くなりがちなので、タイムスライス（フレームを跨いで少しずつ処理）していき、処理が計算待ちでフレームで固まらないようにする。

4.7.10 タイムスライシング処理

処理負荷の高いルーチンでかつ、１フレームで終わらせる必要のない処理に関しては、複数のフレームにわたって分散して処理する。

ウォークラフトⅢ、スタークラフトⅡの例が載っている。
並列性・同時実効性を増すためとあるが、実装が大変になりそうだなぁという印象。

4.7.11 輸送問題

  • あらかじめ決められた場所での直進の輸送は、ユニットの輸送中に敵味方で経路が交差する場合
  • スタート地点と終点をパスチェックすることで経路を計算して、ピックアップからドロップオフまでを動的な状況の変化に応じて対応できる。
  • 輸送の集団に仮想的なリーダーを同時に輸送し、ドロップオフ後のキャラクターたちも、その仮想リーダーのもとでフォーメーションできる

4.7.12 まとめ

  • パス検索は「ナビゲーションデータ上のA*による最小コスト検索」だけでなく、多様な空間を活用する手法の集合でもある
  • これは「スパーシャルAI」そのもの

4.8 時間あたりのコマンド数

APM (Action Per Minutes)

  • 一定時間あたりにアクションを指定する数
  • 人間のプレイヤーは身体的に限度がある
  • 人工知能は APM をかなり上げることができるが、人間が太刀打ちできなくなってしまう
  • 人工知能に制限をつける場合は、多数のキャラクターのアクションを効率的に行う必要が出てくる

ターゲティングの問題

  • 複数の的に直面した時にどの敵を攻撃するか
  • アクションが無駄にならないように、適切に戦力を分散する必要がある
  • APM の限界が来る前に、優先度の高い敵キャラクターに対して、優先度の高いアクションから実行する必要がある

4.9 グループマネジメント

まずはトータルウォーシリーズの人工知能技術について触れて、本筋に入っていっている。

4.9.1 複数の舞台を使い分ける

「トータルウォー：ショーグン２」の意思決定システムの組み合わせの基盤となる４つのモジュール

  • グランド・タクティカル・アナライザー (Grand Tactical Analyzer, GTA)
    • 戦局全体の情報を収集し、認識し、目的を定める。
    • 全体を司る人工知能
    • 敵部隊の指揮官の人工知能そのもの。他の３つを使う中枢でもある。
  • ハイレベル・プランナー
    • グランド・タクティカル・アナライザーの決めた目的を階層的に実際のタスクに分解していく
    • 実際のユニットが実行できるタスクに分解する
  • デタッチメントシステム
    • 決められたタスクを、どのユニットに実行させるかを割り当てる役割
    • ユニット = 複数のキャラクターからなる部隊
    • 割り当てる機能ではあるが、戦術を各ユニットに特性を考慮して分離していくという意味でのデタッチメントだと思う
  • コンフリクト・マネージャー
    • 実際に敵と競り合う時に、どのような戦術を具体的に取るかを決定する
    • 複数の戦術アナライザーを持つ
      • 進軍、ミサイル、捕獲、遠隔攻撃、撤退、など

トータルウォー：ショーグン２でのサンプル

以下、テキストで書いているが、書籍の図を見る方がわかりやすい。

  • サンプルでは、GTA が立てた２つの目的に対して、アクティブになった戦術に対してデタッチメント・システムが、ユニットを割り当てている (特性を配慮し、戦術に対して部隊を割り当てる）
  • 次に、具体的なタスクを与えるために、ハイレベル・プランナーが登場する。
    • ハイレベルプランナーは、GTA から利用され戦術 (例えば側面攻撃)に具体的なタスク(例えば、どの場所で、いつ戦闘を開始するか)を与えていく
    • 書籍では、ハイレベルプランナーの説明がデタッチメントシステムの後になっているが、ここは並行に行われているのかもしれない
  • 続いて、敵に遭遇した場合の戦術を決めるために、コンフリクト・マネージャーが登場する。
  • コンフリクト・マネージャーは複数の戦術アナライザーをもち、敵ユニットに対してどのような戦闘方法（ジョブ）で仕掛けるかを決定する。
  • 攻撃対象のターゲットとそのジョブ（戦闘方法）を指定し「ターゲット/ジョブ」の組み合わせの情報をコンフリクト・マネージャーのメモリープールに保存する
  • そのメモリープールに保存されたジョブを優先度をつけて、各ユニットに割り当てる
  • 各ユニットはこれらのジョブを優先度の順番に実行する

最初読んだ時は、ハイレベルプランナーの役割が最初の説明と違う気がしたが、図を見ると、「GTA -> ハイレベルプランナー -> デタッチメントシステム」という順番ではなく、GTA から両方に線が延びているので、GTA が出す目的 (戦術) に対して、タスク分解と、割り当ての異なる役割をするのがこいつらだとわかった気がした。

4.9.2 城包囲戦のグループ・マネージメント

  • 「予約戦術」という概念が出てくる。待機のために使うようだ。
  • 戦術は「有限状態マシン (Finite State Machine, FSM)」で記述されるらしい
    • 状態遷移図を想像しておけばいいか

4.10 ポートフォリオ

問題を分割した時の、問題領域ごとに取れる戦術の一群をいうらしい

  • それぞれのメンバー（上図の場合は４キャラ）が取りうる戦術を列挙した全体のことをポートフォリオという
  • 全体としては、それぞれの敵が選択する戦術の組み合わせ分だけチームとしての行動パターンがある

行動を決める関数

  • 行動パターンが多すぎる場合は、ゲーム状態ごとにそれぞれの敵が取れる行動を決める関数を用意する
  • これを、選択関数、または局所プレイヤー関数 (pp, partial player function) と呼ぶ
    • ex) キャラクターA は体力が半分以下なら「逃げ去る」だけ
    • ex) キャラクターB は体力が 1/3 を切ると「仲間と合流」 or 「逃げ去る」しか選ばない
  • これらを適用すると、状態によってパターンを限定できる

ゲームツリー

  • １つのゲーム状態を一つのノードとして、すべてのゲーム状態を上から下へツリー構造で記述したもの
  • ここまでで言えば、選択関数を適用済みのポートフォリオが一つのノードになる
    • ゲーム状態が決まれば、選択関数が適用できてポートフォリオが限定されたものになる

ターン制の場合

  • 敵味方が交互に行動するようなケース
  • ゲーム状態はその都度変わっていくので、交互にそれぞれのツリーも延びていく（変わっていく）ことになる

階層型ポートフォリオ探索

  • 上記のゲームツリーの手法の実装の一つ（Hierarchical Portfolio Search, HPS)
  • 特性として、ゲームツリー上での探索方法はどんなアルゴリズムでも採用可能

確かに、ツリーを作った上で、最終的にどの選択肢を選ぶかは探索問題になるのかぁという感想。

4.11 ニューラルネットワークによる学習

背景

  • ストラテジーゲームにおけるユニットは常に多数の敵・オブジェクト、複雑な地形にさらされる
  • プレイヤーの指示から自動的に賢明な行動をとることが難しくなってきている
  • ニューラルネットワークの学習が導入されつつある

誤差逆伝播法のことなど触れられている。
パッとは理解できなかったが、またディープラーニングの書籍と突き合わせて対応させてみたいと思う。

4 章終わり。次は 5 章。面白かったーーーーー！