【技術本】ゲーム開発者のためのAI入門

https://amzn.to/44yUWu3


【技術本】ゲーム開発者のためのAI入門

へポスト
ゲーム中のコンピュータ制御キャラクター(以下CPU)のAIの実装方法について紹介している。
本著作中で下記のことが学べる。

・LOSアルゴリズムによるプレーヤーに対するCPUの追跡と逃避
・パターンムーブメントによる命令リスト配列で擬似知能
・フロッキングによる群れの動作
・ポテンシャル関数による物理学原理を利用して追跡、逃避、群れの再現
・経路探索の様々な手法と軽量化の方法
・A*アルゴリズムによる経路探索
・AIのスクリプト化(ゲームデザイナの参加も促す)
・有限状態機械によりCPUの状態を複数用意し移行状態を管理
・ファジー理論による曖昧さの定量化による数値化
・ルールベースAIの実装方法
・確率の基礎
・ベイズ法による不確定な状況下で意思決定
・人間の脳神経を模したニューラルネットワークの実装方法で意思決定をする
・遺伝的アルゴリズムで一定環境下で評価された固体同士の能力を掛け合わせて世代を重ねて進化

初めは単純な真偽判定に等しい決定論的AIを使用して、従来のレトロゲームで起こりうるプレーヤーとCPUの攻防の実装方法を紹介している。
その後、曖昧さの定量化のためのファジー理論などを足がかりに、不確定な要素に基づく意思決定ができる非決定論AIへと徐々に紹介は移っていく。最終的にはプレーヤーの状態を検知しそれに合わせて柔軟に対応を変化させ、プレーヤーの行動を学習し、プレーヤーのスキルに合わせてCPUも進化していく実装の入り口まで案内してくれる。
プレーヤーに如何に変化に富んだ新体験を一つのゲーム上で供給し続けることができるかにおいて、AIの存在は欠かせない。プレーヤーを魅了し続け、共に成長し、プレーヤーの予測しにくいものへ進化し続ける事ができるゲームを創れたら、プログラマとして本望ではないだろうか。そんな知的好奇心と技術への足がかりを提供してくれる著作だと感じた。

実際の著書には、理論の紹介に加え、実際のソースコード、及び実行例などが、絵図をふまえて紹介されている。
各章独立している、どこから読み始めても問題ない。
以下、概要を記す。

--------------------------------------
1.GAME AIとは

・決定論的AI
GAME AIの基本。振るまいや性能はあらかじめ規定され予測可能。
あいまいさはない。
実装、テスト、デバッグが容易。ただし全ての振る舞いを明示的に実装する必要あり。
プレーヤーが明示的振る舞いを予測できてしまう＞ゲームの寿命を短くしかねない。

・非決定論的AI
ある程度の不確定要素があり、予測不可能な部分がある。
例：CPU側のキャラクターがプレーヤーの戦法に適応し始めること。
学習機能に、ニュートラルネットワーク、ベイズ法、遺伝的アルゴリズムなどが用いられる。
独自の学習や推論が可能。創発的な振る舞いが可能。
デバッグが難しい。

プレーを続けるほどゲームが進化し、学習し、順応するのがベスト。
ゲームの寿命を伸ばす。

--------------------------------------
2.追跡と逃避

・LOS追跡
敵がプレーヤーに対して、常に直線的に追いかけるアルゴリズム
グリッドマップでの経路をブレゼンハムのアルゴリズムを利用して、経路を探索。

・追撃
LOSアルゴリズムを応用し、プレーヤーのスピードを含めた移動先を予測して移動、追撃する。
プレーヤーが向きを変えると、敵は都度移動先の予想を更新して対応する。

--------------------------------------
3.パターンムーブメント

知的な振る舞いをしているような錯覚を与えるための手法。
実装：命令リストの配列を使って、ゲームループを繰り返すたびにコンピュータ制御のキャラクターの動作を指示する。

--------------------------------------
4.フロッキング

フロッキング（群れ）の動作
.結合：各ユニットを隣接ユニットの平均一に向かって誘導
.整列：各ユニットの向きが隣接ユニットの平均的な向きにあるよう誘導
.分離：各ユニットが隣接ユニットと衝突しないよう誘導
視野の幅をコントロールすることで多彩な群れを演出できる
視野幅狭い：一列の行列
視野幅広い：ランダムな群れ

--------------------------------------
5.ポテンシャル関数に基づくムーブメント

物理学の原理を利用し、あらゆる物理現象を再現できる関数。
分子間の斥力、引力のポテンシャルエネルギーを計算し、
前章で紹介した敵の追跡、逃避、群れのコントール、障害物回避も計算できる。

欠点は、CPUをリソースを大量に消費すること。
最適化：フィールドをグリッドに分割し、グリッド内の事象のみ計算対象にする。
対象から離れすぎていて何の作用ももたらさない物の計算はしないのが鉄則。

--------------------------------------
6.基本的な経路探索とウェイポイント

・基本の経路探索
LOSアルゴリズムと障害物のトレーシングを組み合わせた追跡

・ブレッドクラム経路探索
プレーヤーは見えないパン（ブレッド）を落とし、敵がその後をたどる方式

・ウォールトレーシング
たくさんの小部屋で構成されたマップで有効
敵キャラの向きを軸に、特定の方向を優先して移動するよう実装することで、
複数の小部屋を巡回するような動きを再現できる。

・ウェイトポイントナビゲーション
経路探索は処理負荷がかかるので、あらかじめ計算しておく手法

--------------------------------------
7.A* アルゴリズムによる経路探索

現代のゲーム開発で最も使われている経路探索アルゴリズム。
経路探索の問題に効果的な解決策を提示。
視野を遮る障害物がある場合に威力を発揮。

膨大な移動可能な座標をグリッド範囲で区分けしてタイル状に単純化する。
タイル数が多い場合は、その中でも範囲を限定するなど工夫する。
下記リストを用意する。
・オープンリスト：調査が必要なタイルリスト
・クローズドリスト：調査済みのタイルリスト
各タイルには下記情報を持たす
・1.前のタイルへのリンク（起点はclosedなので、周囲のopenはみな起点を指す）
・2.起点からの移動コスト値
・3.目的地タイルへのコスト値（障害物関係なし）
・2+3の合計スコア
起点から隣接するタイルをオープンリストに加え、
上記タイルごとの情報で評価し、完了したらクローズドリストに追加する。
再び、クローズドリストの隣接をオープンリストに加え評価を繰り返していく。
最もスコアが小さい状態で目的タイルに到着すれば完了。
あとは、前のタイルへのリンクを辿ればよい。

袋小路も検知
目的地に投薬できないまま、新たなオープンリスト候補がなくなれば終了。

地形コストとして応用も可能

・影響マッピング
相手の視野、攻撃レンジなど動的な影響の変化。
敵が倒されたタイルを動的にコストを上げて、コンピュータが回避するよう知的行動をとらすなど。

--------------------------------------
8.AIのスクリプト化とスクリプティングエンジン

ゲーム上の各種設定値をコンパイル等不要な外部ファイルにして、
動的再設定を可能にさせる。
各種ルーチン化できる挙動をグラフィカルなものや単純なスクリプト経由で呼び出し柔軟に設定できるようにすることで、エンドプレーヤやゲームデザイナの参加による微調整も可能にする。

--------------------------------------
9.有限状態機械

規定の何種類かの状態のいずれか一つで存在することができる抽象機械のこと。
状態を変更すべきタイミングを判断する条件セットを定義できる。

単純な例：
[初期状態]->プレーヤー発見->[追跡]
[初期状態]->プレーヤーパワーアップ->[逃避]
[追跡][逃避]->プレーヤーの視野外になる->[初期状態]
など

--------------------------------------
10.ファジー理論

値に対して、真偽のほかにグレーゾーンを定義する。
例：1(真)と、0(偽)の高さの段差を結ぶ斜めの直線を用意する。
そこの傾斜の座標が、どれだけ真偽どちらかに近いかの曖昧な数値となる。
真と偽の位置が逆のものや、傾斜のみで構成される定義もある。
これら定義した条件を掛け合わせて曖昧な条件を定量化する。

やせている1 -> 標準0
標準0 -> 太っている
標準0-1(傾斜)理想体型1-0(傾斜)標準

--------------------------------------
11.ルールベースのAI

推測したり、アクションを決定するための一連のif-then形式のルールで構成されている。
・ワーキングメモリ
既成事実とツールから得られたアサーションを格納
例：コンピュータが相手陣地を偵察し「寺院」「兵舎」「木こり」「槍兵」が存在するという事実を取得

・ルールメモリ
ワーキングメモリに格納された事実を処理するif-then形式のルールを保持
例：上記例で取得した事実に対する論理積(if-thenルール)に一致すると、その事実に対応する実装が記述されている。

・前向き推論
ワーキングメモリに保持されている事実とルールを照合と、ルールの実行を繰り返し、呼出せるルールがなくなるまで繰り返す。

・後ろ向き推論
前向き理論と逆の実装。
事実がなぜ成されたかを探っていく。
例：プレーヤーが奇兵隊をもっていたら、蹄鉄鋼を所有しているはず、さらには兵舎を所有しているはず、と再帰的にさかのぼる。

--------------------------------------
12.確率の基礎

・従来の確率の利用
各キャラクターの振る舞いを達成できる確率。
プレーヤーの行動を統計的に分析し、特定の敵を倒せる確率をもとに、敵の行動に変化を与える。

・確率の頻度の解釈
N回中にある事象がn回発生する確率。

・確率の主観的な解釈
個人の知識、経験、または判断に基づいて特定の事象が起きると考えられる。
度合いを0〜1の尺度で示すもの。

--------------------------------------
13.不確定な状況下で意思決定-ベイズ法

ベイズ法により、ゲーム領域が不確定な状況下にあるとき、この技術を使ってプレーヤー以外のキャラクターに決断を下せるようにする。

・ベイズネットワーク
特定の問題とランダム変数との関係を簡潔に表す図。
ランダム変数を表すノードと、変数間の偶発的な関係を表す円弧またはリンクで構成される。
これらは、因果連鎖、共通利害網、共通効果網などの構造から成る。
これらの構造から、診断推論、予測推論、釈明などの基本的な推論方法で、NPCに判断を決定させることができる。

--------------------------------------
14.ニューラルネットワーク

ゲームで利用されるのは十数個分の単純なネットワーク。
しかし、従来の方法では簡単に解決できないような、非線形的な問題の対処に威力を発揮する。

形状として、複数の入力項目があり、それらを処理判定し、複数の出力を持つもの。
入力にはバイアス値も含み、それぞれ重みが定義づけられており、出力を生成する判定処理は活性化関数と名付けられ、活性関数内の非線形データに基づいて加工される。（例外的に線形的データもある）

--------------------------------------
15.遺伝的アルゴリズム

コンピューターが操作するキャラクターが、プレーヤーの動作、スキルに応じて進化するAIモデルの作成。

・1.第一世代
敵キャラクターの挙動、性格などの要素を染色体に見立て、パラメータとして持たす。
同一キャラクターでも多様性をもたせて量産する。

・2.適正評価
第一世代で量産した各敵キャラクターを評価する。
最もプレーヤーを苦しませた挙動のできた個体を評価。
数値、順位などで定量化。

・3.選択
次の世代のための組み合わせを任意で決める。
1位と2位。1位〜5位など。現実の自然界と異なり、任意数の掛け合わせもOK。

・4.進化
新しく配置する個体を生成する。個体群でもっとも適応力のあるメンバーの染色体を組み合わせる。
突然変異の要素も発生させることが重要。
進化が完了したら、2.適正評価へ戻って、以下繰り返す。

--------------------------------------
付録.ベクトル演算

以上。

へポスト