ゲームＡＩ連続セミナー
第３回事前資料 I「迷路を解くＡＩを使ってゲームを作る」
企画 ＆ プログラマー向け

三宅 陽一郎y_miyake@fromsoftware.co.jp

2007.5.8

「迷路を解くＡＩを使ってゲームを作る」の主旨（１） 前回のアンケートの感想から、事前資料を独立した資料として製作することにしました。講演資料だと中途のものしか準備できないからです。
（２） 事前に読まれることで、第３回のセミナーの内容をよりよく理解できるように製作しています。
（３） この資料は、 「迷路を解くＡＩ」を作ることを通して第１回から第３回のセミナーの内容を理解します。
（４） Ｑ＆Ａ形式になっているので、考えながら気軽に読んでください。Ｑ１〜１０まであります。巻末には付録としてパス検索アルゴリズムをまとめてあります。

「迷路を解くＡＩを使ってゲームを作る」の主旨（５） この資料を作っている間に、ＩＧＤＡ日本の懇親会行くと「研修のテキストみたいなものを作れないか？」という話題がありました。
そこで、各Ｑ＆Ａごとに「課題」を用意することにしました。
課題は、プログラマー向けと企画向けを用意してあります。
飛ばして読んでも問題ありません。
課題などという大層な名前がついていますが、プログラマーと企画が和気あいあいと「あーしようか、こうしようか、あーでもない、こーでもない」と、話し合いながら、ＡＩを使ったミニゲームを作って行く時間を提供することを目的にしています。

この資料の目標

迷路の中を自分で考え、自由に移動できるＡＩたちを作って、それを使ったゲームを考えよう！

ポイント

以下の解説は「開発者が事前に行動を仕込むのではなく、ゲーム内でＡＩ自身に考えさせる」という点に着目するとわかりやすいです！

作成工程
Ｓｔｅｐ１ ＮＰＣが迷路の中を自由に移動できるようにする。
Ｓｔｅｐ２ ＮＰＣが自分で行動を考えられるようにする。
Ｓｔｅｐ３ ＮＰＣたち互いにが協調できるようにする。
Ｓｔｅｐ４ ＮＰＣたちを使ってゲームを作ってみる。

ステップを踏むごとにＮＰＣは賢くなりますが、それぞれのステップごとにどんなゲームデザインが考えられるか考えてみよう！
設定は説明のため簡単な迷路とゲームルールにしますが、任意に変えて考えてみてくださいＳｔｅｐ１

ＮＰＣが迷路の中を自由に移動できるようにする。
気軽に読もう！

NPCの自由な移動 ①
Ｑ1： 与えられた迷路を抜けることが出来るＡＩを考えてみよう！
どのように実装すればよいか？

NPCの自由な移動 ①

Ａ

Ａ1： 迷路をグラフとて表現する。

①「迷路内の移動＝グラフ上の移動」と問題が簡単になる。
グラフ検索のアルゴリズムでＡＩを動かすことが可能になる。
Ａ

① Ｂ

Ｃ

②

Ｆ

⑦ＧＩ

③⑥④Ｄ

世界表現
Ｅ

最大３分岐の合流しない迷路は２分木(binary tree)と等価である

④
Ｅ

⑤
⑥⑦Ｈ

⑧Ｂ
③Ｃ

Ｄ

⑤②Ｊ

Ｆ⑧ Ｇ
ＩＪ

このように、ゲーム世界をＡＩの制御のために表現したものを世界表現という。

Ｈ

NPCの自由な移動 ①Ａ

動作例①②ＡＣＦ① ＢＤ②⑦⑤④③Ｃ③Ｂ

Ｄ

Ｅ④Ｅ⑤ＧＩ⑧⑥Ｈ⑥⑦Ｊ
Ｆ

工程１：企画が迷路を製作する
Ｉ
工程２：プログラマーが世界表現（ここでは２分木）を実装する。
工程３： グラフ検索アルゴリズムを実装する。
ゲーム中：スタート地点からゴール地点までパス検索を実行し、ＮＰＣにパスにパスをたどらせる。

⑧ ＧＪＨ

NPCの自由な移動 課題 ①
プログラマー

実際に、与えられた迷路に対してニ分岐ツリーを実装し、パス検索によってＮＰＣをスタート地点から出口まで導いてみよう。
全幅検索（ＢＦＳ）、深さ優先検索（ＤＦＳ）など検索アルゴリズムを試してみよう。
迷路を自動生成するプログラムを作ってみよう。
企画

迷路をＡＩの為のデータとして表現し、グラフ検索のプログラムにより、与えられた迷路を最短で抜けるＡＩを実現できる。
これだけの能力から、どんなゲームが設計できるだろうか？
また、迷路を自動生成できるとすれば、どんなゲームデザインが考えられるだろうか？

NPCの自由な移動 ②
Ｑ２：金塊を集めて迷路を脱出するゲームを考えてみよう！
設定： ３つの金塊を集めて迷路を脱出する。

NPCの自由な移動 ②
Ａ２：世界表現の上に情報を埋め込む
ノードに情報を埋め込むことで、条件付きパス検索の問題になる。

Ａ①Ａ

① Ｂ

Ｃ

②Ｆ

⑦②Ｄ
③⑤④

世界表現

Ｂ
③Ｃ
Ｄ

Ｅ

④Ｅ

⑤ＧＩ

⑧⑥Ｈ
Ｊ

⑥⑦Ｆ

⑧ Ｇ
Ｉ

作成した世界表現に情報を埋め込んで行くことで、ＮＰＣにより賢明な能力を付与することが出来る。

ＪＨ

NPCの自由な移動 ②
Ａ

動作例

①Ａ

① ＢＣ

②

Ｆ

⑦⑧②
③⑤ＧＩ

Ｄ

⑥④③ＣＥ

Ｂ

Ｄ

Ｈ

④Ｅ

⑤Ｊ

⑥⑦
Ｆ

⑧ Ｇ
ＩＪＨ

NPCの自由な移動 課題 ②

プログラマー

各ノードに情報を埋め込めるようにデータ表現を設計してみよう。
３つの金塊の情報を、ランダムに末端のノードに配置できるようにしよう。
３つの金塊を取って迷路を脱出する最短経路を導くアルゴリズムを実装しよう。
企画

世界表現に情報を埋め込むことで、例えば、ゲーム起動ごとにランダムに金塊の位置を変えても、最短経路でそれらを集めて迷路を抜けるＮＰＣを実現できる。
このＮＰＣを使って、どんなゲームが考えられるだろうか？
また、金塊以外にもいろいろな設定を加えて、ＮＰＣにさせることの幅を広げてみよう。

NPCの自由な移動 ③
Ｑ３：ＡＩに基本的な情報を与えよう！
設定： スイッチ（Ｓ）を押すと迷路を脱出する扉（Ｄ）が開く。

ＳＤ

NPCの自由な移動 ③
Ａ３：「スイッチを押せばドアが開く」という知識を表現する
ＡＩが使える形で知識を与えることで、ＡＩは知識をベースとした制御が可能になる。
Ａ

① Ｂ

Ｃ

②Ｆ

⑦⑧

知識表現

③⑤

ＧＩ

Ｄ

⑥④

Ｅ

Ｄを「開いている」状態にするにはＳを押せ。

ＨＳif(D is closed) push(S)Ｊ Ｄ

ＡＩが解釈するべき情報はＡＩが利用できる形で与えることで、初めてＡＩに知識に基づいた行動を取らせることが出来る。これを知識表現という。（人工知能の基本）

NPCの自由な移動 ③

Ａ①

動作例
②Ａ

① ＢＣ

②Ｆ

⑦Ｄ

⑤③Ｃ
③④ＢＤ

④Ｅ
Ｅ

⑤ＧＩ

⑧⑥

ＨＳ
ＪＤ
「ドアが閉まっている」
ことを目撃する

if(D is closed) push(S)

⑥⑦
Ｆ

⑧ Ｇ
Ｉ

Ｈ

Ｓ

Ｊ

Ｄ
スイッチＳを押しに行こう！

知識表現

NPCの自由な移動 課題 ③
プログラマー「スイッチを押せばドアが開く」という知識をＮＰＣが利用できる形で実装してみよう。
実装した情報を適切な場所、タイミングで発動させるように、実装してみよう。
企画

知識表現を用意することによって、ＮＰＣはゲーム内の様々なオブジェクトを適切に使うことが出来るようになる。
この例で、いくつかのギミックを加えることを考えてみよう。

Ｓｔｅｐ２

ＮＰＣが自分で行動を考えられるようにする。
僕が僕の行動を考えるんです！

自分で行動計画を立てるNPC ①
Ｑ４：「金塊を取ってスイッチを押して迷路を抜ける」ようにＮＰＣに計画を立てさせるにはどうすればいいだろうか？
設定： ３つの金塊を集めてから、スイッチ（Ｓ）を押すと迷路を脱出する扉（Ｄ）が開く。

ＳＤ

行動計画を立てるNPC ①③
プランニングを行う
Ａ４：「プランニング」を用いよ「プランニング」とは、ＡＩが未来の行動のプランを自ら作成する能力のことである。詳しくは第２回テキストを見て頂くとして、そのための下準備が必要である。ここでは、連鎖によるプランニングの準備を解説しよう。

前提条件

なし

金塊クリア

ドアが開いている行動

金塊を集める

スイッチを押す

扉を通る

効果

金塊クリア

ドアが開いている

迷路クリア

前提条件 … 行動をするために必要な条件
行動… 実際のアクション効果… 行動による結果
このように、「行動のデータセット」を作っておくと…

プランニング
金塊を集める

連鎖スタートスイッチを押す

金塊を集めて脱出する「効果」から「前提条件」を検索して、行動をつなぐ「連鎖」によって行動プランを自動的にＡＩに立てさせることができる。

なし
金塊を集める

連鎖

扉を通る

金塊をクリア

金塊をクリアスイッチを押す

連鎖

ドアが開いている

連鎖

ドアが開いている

扉を通る

ゴール

迷路クリア

迷路クリア

行動計画を立てるNPC ①

Ａ
①

動作例
②ＡＣ
Ｆ

① Ｂ

Ｄ

②⑦⑤④③Ｃ

③Ｂ

Ｄ

Ｅ

④Ｅ

⑤Ｇ
Ｉ

⑧⑥

ＨＳ
ＪＤ

⑥⑦Ｆ

⑧ Ｇ

Ｈ

ＳＩ

ＪＤ

行動計画を立てるNPC ①
プログラマー「連鎖によるプランニング」についての技術を調査して、実際に実装してみよう。
企画「連鎖によるプランニング」は、行動のセットを増やすと、多彩な行動プランのバリエーションが自動的に形成される。
行動のセットを追加して、より多彩な行動が可能なようにしてみよう。

Ｓｔｅｐ３

ＮＰＣたち互いにが協調できるようにする。
知っていること、これからしようとすることを伝え合う

協調するＡＩを作る ①
Ｑ５：２体のＮＰＣが「金塊を取ってスイッチを押して迷路を抜ける」
ようにチームとして行動させるにはどうすればいいだろうか？
設定： ３つの金塊を集めてから、スイッチ（Ｓ）を押すと迷路を脱出する扉（Ｄ）が開く。

Ｘ

Ｚ

Ｙ

Ｓ
Ｄ

協調するＡＩを作る ①
Ａ５：ＮＰＣを協調させる①領域による分担担当

担当
Ｘ

Ｚ

Ｙ

Ｓ
Ｄ
２者の間であらかじめ領域を決めて実行する

行動計画を立てるNPC ①
動作例

Ａ

① Ｂ

Ｃ

②Ｆ

⑦ＤＸ
③⑤Ｚ

Ｇ
Ｉ

⑧⑥④Ｅ

Ｙ

ＨＳ
ＪＤ

協調するＡＩを作る ①
Ａ５：ＮＰＣを協調させる② チームＡＩ：階層型タスクネットワーク（タスクによる分担）
全体のタスクを分割して、最適なＡＩに割り振る。

チームＡＩ
チームＡＩとは、チーム全体を制御するための思考（見方によっては完全にチート）

迷路をクリアする

金塊を集める

ドアを開ける

金塊Ｘを取る

スイッチＳを押す

金塊Ｙを取る
金塊Ｚを取る協調するＡＩを作る ①
動作例Ａ

① Ｂ

Ｃ

②Ｆ

⑦ＤＸ
③⑤Ｚ

ＧＩ

⑧⑥④Ｅ

Ｙ

ＨＳ
ＪＤ

協調するＡＩを作る ①
A５：ＮＰＣを協調させる③ チームＡＩ：マルチエージェント・プランニング
チーム全体の行動をプランニングする。

チームＡＩ

迷路をクリアする
金塊を集める

ドアを開ける

金塊Ｘを取る
金塊Ｙを取る

スイッチＳを押す

金塊Ｚを取る

チーム全体のプラン
金塊Ｘを取る

スイッチＳを押す
プランの同期。 金塊を取ってからスイッチを押す。
これを行えるためには２体間で「結果の共有」が必要。

金塊Ｙを取る

金塊Ｚを取る協調するＡＩを作る ①
動作例
Ａ

① Ｂ

Ｃ

②Ｆ

⑦ＤＸ
③⑤Ｚ

ＧＩ

⑧⑥④Ｅ

Ｙ

ＨＳ
ＪＤ

協調するＡＩを作る 課題①
プログラマー「階層型タスクネットワーク」（ＨＴＮ）について調査して実装しよう。
「マルチエージェント・プランニング」について調査して実装しよう。

企画「階層型タスクネットワーク」（ＨＴＮ）では、分解されたタスクに適したメンバーを選ぶ必要がある。
例えば、「金塊を集める」「スイッチを押す」二つのタスクに適したＡＩをどちらか選ぶための条件とは何だろうか？

ＮＰＣを協調させることで、チームとしての行動を実現することができる。
ＮＰＣの協調のポイント

情報の共有
結果の共有
これまでの行動の結果を共有する。或いは、得た情報を共有する。
（例）金塊Ａを取った、金塊Ｃを取った…

プランの共有これからの行動のプランを共有する（例）私ＮＰＣ１は金塊Ａを取りに行きます
では、私ＮＰＣ２はスイッチＳを押しに行きます

行動の同期
行動を同期させる（例）金塊を全て取ってからスイッチＳを押す

協調するＡＩを作る ②Ｑ６：２体のＮＰＣが情報を共有するためにはどうすればよいだろうか？
設定： ３つの金塊を集めてから、スイッチ（Ｓ）を押すと迷路を脱出する扉（Ｄ）が開く。

ＸＺＹＳＤ協調するＡＩを作る ②
Ａ６-１：共有メモリ、或いは黒板に認識した結果を書き込む
結果の共有
共有メモリ
金塊Ｘを取る
金塊Ｙを取る
金塊Ｚを取る
スイッチＳを押す

1..取った
0… 取ってない-1… 不明

0 or 1or-1
0 or 1or -1
0 or 1or -1
0 or 1or -1

黒板モデル
全金塊を集める
0 or 1or-1
金塊Ｘを取る
0 or 1or-1
金塊Ｙを取る
0 or 1or-1
金塊Ｚを取る
0 or 1or-1

報告

ドアを開ける

報告

0 or 1or-1
スイッチＳを押す 0 or 1or-1

黒板モデルは「共有メモリ＋知識源」からなり、知識源は、書き込まれた情報から２次、３次…情報を抽出する。
共有メモリに自動的な情報処理機能をつけた発展版と思ってください。

知識源による情報の抽出
知識源による情報の抽出

協調するＡＩを作る ②
Ａ６-１： （発展）黒板に記憶と行動プランを書き込む
1..取った
0… 取ってない-1… 不明

金塊を集める

黒板モデル

0

金塊Ｘを取る

01-1金塊Ｙを取る
金塊Ｚを取る
ドアを開ける知識源
による情報の抽出

0.. NPC_Aが行くと宣言
1… NPC_Bが行くと宣言-1… 不明-2 … 既に取ってあるので行かなくよい。

金塊Ｘを取りに行く

金塊Ｚを取りに行く

1-2
0

Ｓを押しに行く1

金塊Ｙを取りに行く

0スイッチＳを押す

結果の共有

宣言

報告

0プランの共有動作例
Ａ① Ｂ ＸＤ

Ｃ

②Ｚ Ｆ

⑦⑤Ｇ

Ｉ ⑧③⑥④ ＥＹ
ＨＪ

この時点で、NPC_Aが金塊Ｘを取った。
NPC_Bは金塊Ｙを取ろうとしている。
従ってＡは、ＹはＢに任せて「次は金塊Ｚを取りに行く」と考える。

黒板モデル
金塊を集める
0
金塊Ｘを取る
1 金塊Ｘを取りに行く
金塊Ｙを取る-1 金塊Ｙを取りに行く
金塊Ｚを取る
0 金塊Ｚを取りに行く
ドアを開ける
0
スイッチＳを押す
Ｓを押しに行く010-1-1

協調するＡＩを作る ②
Ａ６-２：情報を交換する
ＮＰＣ-Ａの記憶
金塊Ｘを取る
金塊Ｙを取る
金塊Ｚを取る
スイッチＳを押す

0
1
-1
0

0

ＮＰＣ-Ｂの記憶
金塊Ｘを取る
1
金塊Ｙを取る-1
金塊Ｚを取る
0
スイッチＳを押す
0

1

知識交換(Knowledge exchange)モデルは、お互いのエージェントが決められた形式を持っていることを前提とする（同じ構造でなくてもよい）。

協調するＡＩを作る ②
Ａ６-２：情報を交換する
ＮＰＣ-Ａの黒板
金塊Ｘを取る
0
金塊Ｙを取る
1
金塊Ｚを取る-1
スイッチＳを押す
00

ＮＰＣ-Ｂの黒板
金塊Ｘを取る
1
金塊Ｙを取る-1
金塊Ｚを取る
0
スイッチＳを押す
0
金塊Ｘを取りに行く

金塊Ｚを取りに行く

1
0
0

金塊Ｚを取りに行く0
1
0

Ｓを押しに行く1

Ｓを押しに行く

1

金塊Ｘを取りに行く金塊Ｙを取りに行く

金塊Ｙを取りに行く

知識交換と行動の計画の調整

10協調するＡＩを作る ②
動作例
Ａ

① Ｂ

Ｃ

②Ｆ

⑦Ｚ

⑧

この時点で、NPC_Aが金塊Ｘを取っており、NPC_Bは金塊Ｙを取っている。

③⑤

ＧＩ

Ｄ

⑥④

Ｅ

ＮＰＣ_Ａ，Ｂは互いに情報を交換しあい、金塊Ｘ，Ｙを獲得したことを知る。

ＨＳ

ＮＰＣ_A は、自分がスイッチＳを押しに行くことを宣言し、その宣言を受けて、
ＮＰＣ_Ｂは、金塊Ｚを取りに行く。

ＪＤ

協調するＡＩを作る 課題②
プログラマー「黒板モデル」（Blackboard architecture）を実装して、協調動作を実現しよう。
また、知識交換モデルを実装して、企画と相談して交換のタイミングを決め、協調動作を実現しよう。情報の交換のキャッチボールをし続けないように、交換のタイミングとトリガーを工夫しよう。
企画

黒板モデルでは、ＮＰＣ同士の位置に関係なく、情報が共有されてしまう。プレイヤーから見た場合、完全にチートとなる。チートは、プレイヤーを興ざめさせてしまう恐れがあるが、逆に、チートしないことにこだわっても、ＮＰＣの動きを鈍くしてしまう。
また、知識交換モデルでは、ＮＰＣ同士にいつ交換を可能にするべきかを設定する必要がある。この例で、そのタイミングを考えよう。

Ｓｔｅｐ４

このＮＰＣたちを作ってゲームを作ってみるゲームの話をしよう！

ゲームを作る①
Ｑ７：プレイヤーを加えて、知性を持ったＮＰＣを仲間として動かすには？
設定： ３つの金塊を集めてから、スイッチ（Ｓ）を押すと迷路を脱出する扉（Ｄ）が開く。

仲間
player
指示

aiai2

ＳＤ

ゲームを作る①
Ａ７：インターフェースを作ってＡＩに指示が出せるようにする
例えば、「金塊Ｘを取れ」という命令を出すと、ＮＰＣに、何処からでもパス検索をして金塊を取りに行かせることが出来る。
つまり、チームＡＩの部分を、プレイヤーが果たす。
命令を受けたＡＩは、自分でパスを検索して命令を実行する。
仲間
Ｘ

player
指示aiai2

ＺＹ

ＳＤ

ゲームを作る①
動作例
aiＸ

ai2
金塊Ｘを取れ金塊Ｙを取れＹＺ

Ｚ

金塊Ｚを取れＳ

スイッチＳを押せＤ

キャンセル
プレイヤーは抽象的な命令を出すだけで、命令を実行するための細かいプランは、ＮＰＣ自身が考える。

ゲームを作る 課題①
プログラマー

インターフェースを実装して、プレイヤーからＮＰＣに指示が出せるようにしよう。

企画

インターフェースのデザインとパッドのコマンド入力に仕方を考えよう。
どうすれば、プレイヤーがストレスなくＡＩに指示を出せるだろうか？

ゲームを作る②
Ｑ８：プレイヤーを加えて、知性を持ったＡＩを仲間のチームとして動かすには？
設定： ３つの金塊を集めてから、スイッチ（Ｓ）を押すと迷路を脱出する扉（Ｄ）が開く。

仲間
player
指示

ai

ai2

ＳＤ

ゲームを作る②
Ａ８：インターフェースを作ってグループに指示が出せるようにする
例えば、「金塊を取れ」という命令を出すと、ＡＩたちは、自分たちで協調して金塊を取る。
仲間
Ｘ

player
指示
Ｚ
aiＹ

ai2

ＳＤ

ゲームを作る②金塊を揃えるために協力して行動

動作例
Ｘ

金塊を取れ
スイッチＳを押せ
キャンセル

Ｙ

Ｚ

Ｚ

Ｓ
Ｄ
プレイヤーはチームに抽象的な命令を下すだけで、チーム内のプランはＡＩが自ら考えて実行する。

ゲームを作る 課題②
プログラマー

ＮＰＣチームに命令を指定することができるようにし、ＮＰＣチームは受けた命令をチーム内で協調して行動できるように実装しよう。
企画

ＮＰＣチームに渡す命令は、どのようなものが考えられるだろうか？

ゲームを作る③
Ｑ９：プレイヤーをＮＰＣと戦わせるには？
設定： ３つの金塊を集めてから、スイッチ（Ｓ）を押すと迷路を脱出する扉（Ｄ）が開く。

仲間
player
指示

ai

ai2

Ｓ
Ｄ

ゲームを作る③
Ａ９：ＡＩチームを作って同じ条件で対戦させる
全てのメンバーが先に迷路から出れば勝利
プレイヤーチーム
player
Ｘ

指示

aiai2

Ｚ

Ｙ

ＡＩチーム

Ｓ
player
指示

aiai2

Ｄ

ゲームを作る 課題③
プログラマー

ＮＰＣチームとプレイヤーチームが対戦できるようにする。

企画

このゲームはこのままで面白いだろうか？

ゲームを作る④

Ｑ１０：Ｑ１~９で作ったゲームはまだ全然面白くない。
自分のアイデアや設定を変えて、ＡＩの技術を使った面白いゲームを作ろう！

ゲームを作る④Ａ１０（例）（１） ゲーム設定を変える。
（２） 迷路を広くする。
（３） ３Ｄにする。
（４） …
Ｓ

Ｄ

企画とプログラマーで自由にＡＩを使ったミニゲームを考えて作ってみよう！

（応用例） クロムハウンズ
オフライン コマンダーミッション「オンラインにおいて人間のチームメンバーに指示を出してチームを連携させる」練習として、オフラインのストーリーモードにおいては、フィールドの情報をアンテナで収集しながら、数対のＮＰＣに命令を出してミッションをクリアするステージが用意されている。

プレイヤー
命令

ＡＩチーム

ＮＰＣの処置としては、「命令」を「ゴール」として扱い、与えらたゴールを遂行するためにプランニングを行って実行する。
（注）ただしミッションの都合上、ＡＩの自律的能力はかなり抑えてある。

インターフェース

十字キーで、コマンドを形成して行く。見えているのは、コマンダー自機の背中それぞれの段階で、様々な指令や対象が用意されている。

プレイヤーは命令を出した後は、自分も移動しながら戦局を判断し、新しい命令を出すことでＡＩチームを協調させながら、戦局をコントロールする。
ＡＩは「何をするべきか？」というゴールを人間から与えられるが、「如何にするべきか？」はプランニングによって自分で考える点が新しい点である。

お疲れさまでした。
（１）迷路というゲーム世界に限定して、第１回から第３回の内容を解説しました。
（２）特に迷路の設定が本質ではないので、一般にゲーム全般についてＡＩを使ったアイデアを考えてみてください。
（３）ここで説明した技術の Killzone, Halo2, F.E.A.R,
Chrome Hounds における応用は、第１，２回テキスト、第３回の参考資料をご覧ください。
[参考文献] 第１、２回講演資料と第３回参考資料（第３回申し込みページよりリンク）

http://www.igda.jp/modules/eguide/event.php?eid=41

付録１：技術的発展
Ｑ .Ｅ１ 一般の迷路を扱えるようにする。
Ｑ .Ｅ２ 上記の例では、あらかじめ迷路の全体像が与えられていたが、動的にＡＩが認識した部分だけ迷路の構造が明らかになるようにする。
Ｑ .Ｅ３ ３体以上のＡＩについて協調させる。

Ａ.Ｅ１ 一般の迷路はネットワークグラフになり、パス検索のアルゴリズムは、ダイクストラのアルゴリズムかＡ＊アルゴリズムを用いることができる
Ｄ⑥⑥③⑤④⑦Ａ ①③⑦⑤ＣＣＡ②④⑧Ｂ⑧①②

世界表現

ＢＤ

Ａ.Ｅ２ チートをしないためには、認識した領域だけ使うようにする。
また、ＡＩが未知の洞窟を調査する様子は、プレイヤーから見ても、リアリティーのあるＡＩとなる。動的にグラフ構造を発展させる方法
あらかじめマスクしたグラフ領域のマスクを解除して行く方法、を取ることが出来る。
自分の行かない方角にNPCを派遣して情報を持って来させて、自分の情報と会わせてダンジョンの全体像を知っていくゲームは面白いと思う。
⑥④⑦⑤⑦ＤＡ⑧①②

ＣＢ⑧player

知識交換

NPC

Ａ.Ｅ３
相互作用モデル（多数のＡＩがそれぞれ相互作用をするシステム）は頻繁にコミュニケーションする場合は調整がしずらくなる。そういった場合は、階層構造を導入すると制御がしやすくなる（集中管理型）。

チームＡＩ
グループ管理ＡＩ

グループ管理ＡＩ

ご感想や質問があれば、メイルかセミナーでお伝えください。

y_miyake@fromsoftware.co.jp(IGDA Japan登録アドレス yoichi-m@pk9.so-net.ne.jp )ＷＥＢ上の意見交換にはＩＧＤＡ Japanのサイトをご利用ください

http://www.igda.jp

付録２:パス検索法 解説
DFS, BFS, Dijkstra, A*

グラフ検索アルゴリズム
パス検索はデータ構造が出来れば、グラフ検索の問題である

主な検索アルゴリズム
DFS

Depth Fir st Sear ch

深さ優先検索BFS

Br eadth Fir st Sear ch

幅優先検索

Dijkstr a Dijkstr a’s algor ithmダイクストラ

A*A* algor ithm

エースター

Depth First Search

DFS

深さ優先検索
深いノードを優先して検索して行く
1.
2.
3.
4.

左優先として、ノードの終点の深さまで行くまだ行っていない子ノードがあるノードまで戻る。
ノードを終点の深さまで行く
目的のノードへたどり着くまでくり返す

１264

352

深さ7

Breadth First Search

BFS

幅優先検索
浅いノードから同じ深さのノードを優先して検索して行く
1.
2.
3.
4.

左優先として、ノードの終点の深さまで行く
まだ行っていない子ノードがあるノードまで戻る。
ノードを終点の深さまで行く
目的のノードへたどり着くまでくり返す

１43

2

567

深さ8

Dijkstr a Dijkstra’s Algorithm
ネットワークの中で最短のパスを探す[前提] ノード間に距離があり、あるノードからあるノードまでコストが定義される（コスト＝２点間の距離）
開始ノードにつながれているノードたちへのコストをチェックする
チェックしたリストの中から最も小さな値のノードの先につながれているノードへのコストを計算し、リストに加える（２）へ戻り、くり返し、目的のノードへのパスを見つける
それがリストの中で最小の値なら終了。そうでなければ （２） へ

(1)
(2)
(3)
(4)

AからＦへの最短経路を求めよ
B 23

B 23

B-E 53

Dが最も小さいC 34

C 34

AＣより
B-E 53
BがABCが小さい
最も小さいB-C 33

D-G 35D 15

C 34

B-E 53D-GがB-CがB-C-E 41最も小さい
最も小さいB-C 33

B-C-F 42

D-G 35B-C-G 42 B-C-EがB-EよりD-G 35 小さいD-G 35

B
Ａ23

E30
10 C

83349F

9520

A-D-G-F 40
最短経路

15D

B-C-E 41G

B-C-G 42
D-G-Fがリストの中で最小

D-G -C 44
D-G-F 40

B-C-E 41
B-C-F 42
B-C-G 42
D-G -C 44
D-G-F 40

B-C-FよりD-G-Fが小さい

A* AlgorithmA*

２点間に複雑に絡まったパスがあり、最短のパスを探す[前提]ノード間に距離があり、あるノードからあるノードまでコストが定義される
Dijkstr a Algor ithm のコストを見積もりコストに変更したもの。そして、目的地へのパスが一つ見つかれば終了（コスト＝２点間の距離＋ゴールまでの見積もりコスト）
見積もりコストは、実際の経路の値より小さい値でなければならない。
（普通はユークリッド距離。以下では説明のため、適当に見積もりコストをつけています）

AからＦへの最短経路を求めよB 23+29
C 34+8

B 23+29

B 23+29

34+8

DGが最も小さい C 34+8

Dが最も小さいCD-G 35+3

D 15+23

D-G-F 40

A-D-G-F 40
最短経路

D-G-C 44+6

B23E

30
10 C

8334

Ａ9F

9155

D20G

このように発見的にパスを検索する方法を、
Heuristic なパス検索という