「戦略ゲームAI解体新書」読書会ログ 5 章
- 「戦略ゲームAI解体新書」読書会ログ 1, 2 章 - You are done!
- 「戦略ゲームAI解体新書」読書会ログ 3 章 - You are done!
- 「戦略ゲームAI解体新書」読書会ログ 4 章 前半 - You are done!
- 「戦略ゲームAI解体新書」読書会ログ 4 章 後半 - You are done!
今週も読書会ログ。今回は 5 章。
第５章 プレイヤーと競争する人工知能
プレイヤーが世界をシミュレーションして進めていくストラテジーゲームについて
- 世界：ゲーム内に構築された１つの有機的な世界（庭、島、文明 etc)
- ユーザー：マスターとなって世界を発展させていく役割（村長、国家元首 etc)
- AI：世界そのものが自律発展する人工知能
- 発展する街、成長する文明、進化する生態系、変化する惑星 etc
5.1 マップの下の多層構造
「自己発展する世界を、見えない層を積み重ねることで実現する手法」のことだそうです。
グリッドマップ
- セル（四角形の単位）で縦横に分割されたマップ
- 各セルを単位として、ユーザー側からは思考しやすく、開発側からは管理しやすいという利点
- 多層構造を用いる
- 人工知能がグリッドの状態を知るため
- グリッド上でアクションを行ったり、思考したりするため
シムシティの例
- 4層構造のグリッドマップ (書籍の図がわかりやすい)
- 影響度伝播
- 街が発展する仕掛けは 2, 3, 4 層
- ユーザーのアクションの影響が上層から深層に計算され、逆に最深層からは上層へ向かって、セルに関わるパラメータが計算される
空間的スケール
- 深層に行くに従い、2x2, 4x4, 8x8 と1層目の 1 セルのより大きくしている
- 影響度を考えるときに、それぞれの層で計算する密度や素早さが異なる
- 細かな粒度で素早く影響（人口密度、交通渋滞 etc）
- 大きな粒度で一定の時間幅で影響 （警察や治安の影響力 etc)
- 深層に行くほど、時間のズレを入れてゆっくりゲームを影響を返す
- 空間と時間の階層構造
- ４章 チーム・時間・空間の階層化でも階層について触れられている
書籍では以降で影響度の計算についての説明があるが、とても面白い。シムシティならではあるけど、こういう設計ができるといいなぁと思う。
5.2 エージェント・シミュレーション
実際に街であるのなら、街を動かす人や車といったキャラクターをシミュレーションすればいいと考えるが、80年代ではそのシミュレーション能力はなかった。
これらエージェント・ベースやエージェント指向は90年代に発展したらしい。
GlassBox (シムシティ4）
リソース・ユニット・マップ・グローバルという階層構造
- リソース: 自然資源、社会的資源 (お金、電気、労働、人工 etc）
- ユニット: リソースを保持する。（家、店、工場、人の集団 etc）
- マップ上にユーザーが置く建築物など
- 人単体や車両単体は後述のエージェント
- マップ: 一定の領域。それぞれのセルにリソースを持つ。
- グローバル: リソースの全量
- ユニットは、in/out ベースのルールがスクリプティングされている
- 店に人が一人入ったら(in)一人出ていく(out)
- 店にお金が 10 入ったら(in)、木材が 2 出ていく(out)
パス・ゾーン・エージェントの階層構造
- リソース・ユニット・マップ・グローバルとは異なるレイヤーの階層構造
- パス: 道路、電気・水の輸送経路
- ゾーン: 工場地帯、住宅地帯
- エージェント: 通行人、車両 (約 10000体）
- ゾーン・エージェントは、ルールがスクリプティングされる
- ゾーンに家を建てるなど
- エージェントはユニットで生成され管理される
- 工場ユニットからは、作業員や運搬車両が生成される
- マンションでは住人が生成される
- 家ユニットの「仕事に行く」ルールであれば、家からエージェンを out させる、マップに in させる
- 工場で材料が入ったら(in)、製品が出ていく(out)、公害が出ていく(out)
シムシティ4の社会の仕組み
- 単位はユニット
- ユニットがエージェントを管理し、人と資源の社会シミュレーションを実施する
- ユーザーはユニットを建てることで社会に影響を与える
- 影響は全てルールの連携によって実現される
5.3 スクリプティング
5.2 で出てきたスクリプティングについて
AI Script
- エイジオブエンパイアⅡにおいて、ユーザーがAIを作れるモードで使うスクリプトシステム
- ゲームそのものの成り立ちや仕様が表現されていて、それを読み込むことでそのゲームの全体像を内側から掴むのに役立つ
5.4 地形解析
地形生成と地形解析
- 表裏の関係
- 地形解析 -> 人工知能が空間を利用したプレイをするのを助ける
- 地形生成 -> 地形に沿った決まりきった戦略をとることを阻止し、ゲームに多様性をもたらす
地形解析のための情報
- キャラクターやアイテムごとの必要な地形情報を常に保持させるのは困難
- 汎用的な情報の形式の整備が必要だった
ストラテジーゲームの地形解析でよく用いられる情報
- 地形のコネクティビティ: ２つの地点が移動可能なように地続きであるか？
- 対象の影響範囲: ある対象が空間に及ぼす範囲
- 階層的な地形表現: 対局から局所まで階層的に表現された階層型地形データ
これらは、人工知能が持つ知識の形式（知識表現: Knowledge Representation) の中でも、地形に関する知識表現である世界表現 (World Representation, WR) または、位置依存表現 (location-based information) とも呼ばれる
5.4.1 地形のコネクティビティ
- ある地点とある地点が繋がっているか？
- キャラクターがその場所にたどり着けるか、自動生成した地形が両陣営が繋がっているか？
- コネクティビティ・チェック / パス・チェック
- コネクティビティを計算によってテストすること
- 「パス検索」が役立つ
RPGツクール2003 のダンジョン生成機能でスタートとゴールがつながらないものがあったなあと話題に上がった。
5.4.2 対象の影響範囲
- 攻撃範囲や移動範囲を知りたい
- 平坦であれば簡単だが、起伏のある3次元地形の場合には問題になる。
- それらが離散的に可視化されることで、プレイヤーも人工知能も意思決定ができる
書籍の図を見ないと言葉では分かりにくい。
5.4.3 階層的な地形表現
- ゲーム状態を的確に捉える方法。4.3節の空間の階層化 (ウェイポイント・ゾーンや占有度マップ）のより具体的なもの。
- 人間であればアバウトで良いが、人工知能に命令を解釈させるには、正確な情報、具体的には階層的な地形情報が必要
分割については書籍の図と説明が詳細に書かれていて分かりやすいので省略。
参考文献が CEDEC の資料で見れないものだったので、似た感じのものを探して見てみた。
- 【GDM37】ゲームAIにおける意思決定と地形表現～『LEFT ALIVE』を事例に紹介～ | PPT
- ［CEDEC 2011］AIに命を。「ぽかぽかアイルー村」のアフォーダンス指向によるAI事例と「ARMORED CORE V」の三次元的な移動経路検索
5.5 地形解析の実例
エイジオブエンパイアシリーズを例に解説されている。
5.5.1 タイルベースとエリア作成
- パス検索はタイルベース (Tile-based pathfinding)
- 三角形で敷き詰めたマップ上でのパス検索
- タイルの一定集合をエリア
- エリアはタイルのシードから「スタックベースト・フラッドフィルアルゴリズム (stack-based flood-fill algorithm)」によって高速に形成される
- シード（ペイントツールなら色と考えて）でエリアを認識していく
5.5.2 ゾーン分割
- パス・チェックを行う際に崖のようなマップの断絶がある場合
- マップをゾーンで分割していたとしても、崖でパス・チェックが失敗する or パス・チェックが成功するが実際には崖で移動できない、という事態になる
- そのために崖を考慮したゾーンに分割するとデータサイズが膨らむ
- よって、人工知能側の仕様を考慮したゾーン分割や、崖等のパスに影響するオブジェクトのサイズ設定をする必要がある
5.5.3 影響マップの応用
- 場所を発見するために影響マップを使う手法
- 惹きつける場所 (Attractor) 、避ける場所 (Detractor) という二つの概念を使い、それぞれ、+1, -1 の影響マップを作る
- 味方が hot、敵が cold と同じような考え方
- それを重ねた時に 0 になる場所が最適な場所として発見される
- 味方/ 敵であれば、フロントラインである
- 例としては、金鉱の貯蔵穴、兵士の駐屯地が上がっている
- また、ルート検索にも同様にこの考え方でコストのバイアスをかけることもある
- 一度通った場所は避けるために、Detractor として扱うなど
5.5.4 ミップマップ、ポリゴン、タイルベースの階層型パス検索
エイジオブエンパイアⅡの地形解析について、3つのパス検索しすてむを階層的に使い分けている。
- ミップマップ - パス検索：マップ全体をミップマップかしたデータ上でパス検索を行う
- ポリゴン的パス検索：その場で凸多角形を生成してパス検索を行う
- タイルベースパス検索：タイル上のパス検索を行う
ミップマップ
- マップの全体図を小さなセルの集合に変換する
- エイジオブエンパイアⅡでは、グローバルなパス検索と canPathcheck で利用される
CG をしてると、ミップマップは LOD みたいな感じで捉えていたが、一緒に読書会をしている人はこの本のようにセルに変換する方がイメージ通りと言っていた。
ポリゴン的パス検索
- マップ内で動的に凸多角形を複数生成する
- スタックベースド・フラッドフィルアルゴリズムとほぼ同じ方法で計算できる
- 地形情報が同じ領域を形成し、それを凸多角形に分解する（山間、沿岸、森林 etc)
使いわけ
- グローバル戦略：ミップマップ
- 相手との衝突：ポリゴン的パス検索
- より小さなスケール：タイルベース
5.6 地形生成
5.6.1 グリッド上の自動生成
- マップをグラフィックモデル（描画モデル）から生成するケースは少ない
- その前身となる補助データ上で生成する場合が多い
- グリッドマップのセル上でマップを自動生成し、生成後にその情報を元にグラフィクスを乗せる
- 地形生成とグラフィック生成の工程を分離できる
Empire Earth の例
- 「プレイヤー数」「チーム数」「マップサイズ」「天候」「マップタイプ」「乱数シード」の入力に応じてマップが自動生成される
- マス目で仕切られたマップ
- 開始タイルから始めて、自身に接するタイルの中からランダムにタイルを選んで成長させていく
- 最終的に指定されたタイル数に到達した時点でそれに接するタイルを始点として次の領域の生成をする
- 連続タイルは陸地、それ以外は海になる
- 開始タイルはプレイヤーのそれぞれの始点となり、その周囲は建築用にフラットになる
- 生成された地形を地形解析し、配置物が自動配置される
- 生成された地形タイルの上に、地形モデルデータを被せ、見た目を作っていく
- おそらくここで、山は地形が盛り上がり、フラットな地形は平坦なままとする
5.6.2 ハイトマップによる自動生成
- ハイトマップ（高低マップ）による地形生成
- n各ポイントの地形の高さのみを保持したマップのこと
- 上空から見たハイトマップを模様とみなす方法が多い
- 各ピクセルの値が地形の高さに対応する
- よって、モノクロの画像で対応できる（高い場所はより白く、低い場所はより黒い）
- グリッドマップではなく、普通にテクスチャと同じ解像度で作ることが多い
Horizon Zero Dawn での応用例
- 地形情報だけでなく、植物の種類や、道路に応じたテクスチャマップを用意
- ゲーム内ではこのマップを使ってステージを構築する
- （このゲームは地形自動生成ではない）
Voxel Plugin で遊んでいると、地形の生成や foliage の配置をテクスチャマップを使ってやることがあるので、こういうところで使われているのかぁと参考になった。
5.6.3 ベクターフィールドによる地形生成
- ハイトマップを使ったディスプレイスメント・マッピング (displacement mapping) からベクターフィールドを使ったものへの移行 (vector field displacement)
- ベクターフィールドにすることで、単なる高低から、方向を持った地形生成が可能になった
- 生成の後に侵食 (Erosion, エロージョン）を行うことで自然な地形に見せることができる
5.6.4 多層グリッドによる地形生成
地形を多層的に生成していく手法として、Dwarf Fortress の事例。
最初読んでいると、事例から「多層グリッド」という手法があまり見えてこなくて、どういうことなのかと混乱した。
これまでの事例がタイルベースの生成やハイトマップを使ったものだったので、段階的に作成するということで「多層」としているのだろうか。
ステップについては書籍の図と説明が詳しいので省略。
5.6.5 城壁構築
- 城壁を構築する際に利用するアルゴリズム
- 最終的には凸角形で街を閉包する城壁を作ることが目的
城壁を作るアルゴリズムとグラハム・スキャンの例はとても面白い。こういうの使えるとかっこいいなぁ。
5.7 テクノロジーツリー
テクノロジーツリー (テックツリー / tech tree)
人工知能の場合
- テックツリーが人間プレイヤーが技術を開発していくツリー
- 人工知能のプレイヤーが技術を開発するツリーも同様
- 人工知能の言葉では「依存グラフ (Dependency Graph)」
- あるノードを実現するためには、その前のノードを実現しておく必要がある
- 依存関係を遡ることで、人工知能のプレイヤーは目的とする技術を順番に積み上げていく
マインクラフトの例
- マインクラフトは素材を集めて、その組み合わせで作れる物が増えていく
- テックツリーを構築すれば、作成が簡単。しかし、何がどの素材から作られるかは明示されない
- ツリーはいきなり作れない
- よって、テックツリーを自ら学ぶ必要がある
- これを人工知能にさせるチャレンジがある
5 章終わり。次は６章。
