「ゲームが進化させる人工知能」
知能感受性についての試論 ～知能が知能を感じること～

三宅 陽一郎2011.11.6 (金) @幾徳祭
y.m.4160@gmail.com
twitter: @miyayou
http://www.facebook.com/youichiro.miyake

Contact Information
Youichiro Miyake• Mail： y.m.4160@gmail.com• Twitter: @miyayou• Blog： http://blogai.igda.jp• LinkedIn: http://www.linkedin.com/in/miyayou• Facebook：http://www.facebook.com/youichiro.miyake

三宅陽一郎 講演資料・論文集
2006-2011年3月までの講演・論文資料を全公開
2006-2010 ゲームAI連続セミナー全７回の講演資料を含む

y_miyake のゲームAI千夜一夜「三宅陽一郎 講演資料・論文集」
http://blogai.igda.jp/article/46500782.html

著作第２２章 プロシージャル技術 （三宅）第２３章 デジタルゲームAI （三宅）ゲームAIについてのロングインタビュー（三宅）コンテンツ第一部
エンターテインメントの人工知能の理論的枠組み
第二部
デジタルゲームAI実例
第三部
世界のゲームAI系国際会議の最近の状況

第１部

エンターテインメントの人工知能の理論的枠組み世の中にはどんな知性があるだろう？

http://www.123rf.com/photo_8100542_underwater-photo-of-a-hard-coral-reef.html© 2011 SQUARE ENIX CO., LTD. All rights
http://www.gatag.net/04/12/2010/190000.html
Oct.8,
2011
http://www.123rf.com/photo_10039937_foggy-forest-at-the-morning-at-autumn.html
reserved
http://www.flickr.com/photos/rotrauds-kleine-welt/346698184/8高度な知性は状況から自由か？

http://pkoko.sakura.ne.jp/html/hatyuurui/tokage/nihonyamari/nihonyamori02.html
http://pkoko.sakura.ne.jp/html/tori/kawau/kawau01.html
http://pkoko.sakura.ne.jp/html/musi/kamikirimusi/serigurobenikamikiri01.html
http://pkoko.sakura.ne.jp/html/ryouseirui/kaeru02.html

思考実験：
人とバッタがデジタルゲーム上でゲームをする
バッタ（リアル）

センサー

人

インター
フェース

ゲーム
フィード
バック

バッタの動きをカメラセンサーでトレースしてデジタルゲームに反映する

思考実験：
人とバッタがデジタルゲーム上でゲームをする
バッタ（リアル）

センサー

人

インター
フェース

ゲーム
フィード
バック

思考実験：
人とバッタがデジタルゲーム上でゲームをする
バッタ（リアル）

センサー

人

インター
フェース

ゲーム
フィード
バック

思考実験：
人とバッタがデジタルゲーム上でゲームをする
バッタ（リアル）

センサー

人

インター
フェース

フィード
バック

思考実験：
人とバッタがデジタルゲーム上でゲームをする• 普段、人間の知性とバッタの知性が出会う状
況は決められている。
• それはかなり一方的な状況が多い。
• しかし、デジタル技術を使えば人間の知性とバッタの知性が出会うその状況、その空間、その方法を変えることが出来る。

人と人の関係性とは何か？

人

現実空間

人

人と人の関係性とは何か？

人

現実空間

人

ルールがある。
ルールを規定しているのは基本的には自然法則。
物理法則→化学法則→巨視的な法則→社会的秩序→地域のルール

人と人の関係性とは何か？

人

仮想空間

ルールを設定する。

人

ゲームという場で知能と人工知能が出会うってどういうことだろう？
場とルールを共有する

インタラクションが規定されるゲーム＝「新しいインタラクションを生成する」- インタラクションの新しい形を提供する- 本来インタラクションできなかった者同士にインタラクションを提供する

- インタラクションの新しい形を提供する- 本来インタラクションできなかった者同士にインタラクションを提供する

知性同士のインタラクション

ゲームとは知性同士の関係性の新しい可能性

人と人の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

人

人
仮想空間

＝
ルールを設定する。

人と人の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

人

人
仮想空間

＝
ルールを設定する。

人と人の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

人 ゲームとは知性同士の関係性を拡張するもの 人
仮想空間＝
ルールを設定する。

人と人の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

人ゲームを通してはじめてわかり合えることがある。
人
仮想空間

＝
ルールを設定する。

人

人

人

http://multiplayerblog.mtv.com/2008/09/18/how-disney-chose-pure/
http://www.4gamer.net/games/079/G007967/20091204007/人

人

http://multiplayerblog.mtv.com/2008/09/18/how-disney-chose-pure/
http://www.4gamer.net/games/079/G007967/20091204007/

人

より正確な図
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

人

インター
フェース

仮想空間

インター
フェース

＝
ルールを設定する。

人

より正確な図
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

人

インター
インター
仮想空間
ゲーム＝人と人の関係性のデザイン
フェース
フェース

＝
ルールを設定する。

人

人

人

より正確な図
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

ゲーム＝人と人の関係性のデザイン
人

インター
フェース

仮想空間

インター
フェース

- 既存の関係性の抽出- 全く新しい関係性の提案＝
ルールを設定する。

人

より正確な図
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

対称ゲーム
＝人と人の関係性のデザイン
人

インター
フェース

仮想空間

インター
フェース

- 既存の関係性の抽出- 全く新しい関係性の提案＝
ルールを設定する。

人

ボードゲーム（≒対称ゲーム）人人ボードゲーム（≒対称ゲーム）

ボードゲーム（≒対称ゲーム）＝人と人の関係性のデザイン
人- 既存の関係性の抽出- 全く新しい関係性の提案

人

人と人の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝

人

つまり人は
現実空間
多くのゲームによって人と人との間にある多様な関係性の可能性の空間を仮想空間
探求して来た＝ルールを設定する。

人

人と人の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝

人

つまり人は
現実空間
多くのゲームによって人と人との間にある
優れたゲームは新しい関係性、新しいインタラクションを提供して来た
多様な関係性の人
可能性の空間を仮想空間
探求して来た＝ルールを設定する。

人と人の関係性とは何か？

人

人

例えばオセロが提供する盤上人と人との関係性とは何でしょう？

人と人の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝

人

つまり人は
現実空間
多くのゲームによって人と人との間にある多様な関係性の可能性の空間を仮想空間
探求して来た＝ルールを設定する。

人

人と人工知能の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝
現実空間

人

?
仮想空間

＝
ルールを設定する。

人工
知能

人と人工知能の関係性とは何か？
宇宙、社会、時代によってルールが設定されている。

＝

人

現実空間
これまでに蓄積されて来たゲームによる
知能と知能との関係性＋
人と人工知能の間だけ仮想空間にある新しい関係性＝
ルールを設定する。

人工
知能

人と人工知能の関係性の二つの方向
宇宙、社会、時代によってルールが設定されている。

＝

人

これまでに蓄積されて来たゲームによる
現実空間
知能と知能とのインタラクションの再現＋
人と人工知能の仮想空間間だけにある
新しいインタラクション＝
ルールを設定する。

人工
知能

人と人工知能の関係性の二つの方向
宇宙、社会、時代によってルールが設定されている。

＝

人

これまでに蓄積されて来たゲームによる
現実空間
知能と知能とのインタラクションの再現
数多の新しいゲーム ＋
人と人工知能の仮想空間間だけにある
新しいインタラクション＝
ルールを設定する。

人工
知能

人と人工知能の関係性の二つの方向
宇宙、社会、時代によってルールが設定されている。

＝

人

これまでに蓄積されて来たゲームによる
現実空間
知能と知能とのインタラクションの再現
数多の新しいゲーム ＋
人工知能
人と人工知能のデジタルゲームが探求して来た領域
仮想空間
間だけにある＝今、様々なデジタル・インタラクティブが新しいインタラクション
ゲームのノウハウに着目する理由＝そこに人工知能は大きな存在感を＝持っている ルールを設定する。

人は人工知能と何処で出会うか？

人

人工
知能

人は人工知能と何処で出会うか？

仮想空間

人

人工
知能

現実空間

現実空間？ 仮想空間（デジタル空間）？

人は人工知能と「何処で」出会うか？
Where

仮想空間

人

人工
知能

現実空間

現実空間？ 仮想空間（デジタル空間）？

人は人工知能と「どのように」出会うか？
Situation

ゲームで

洞窟で
人

街で

戦場で

人工
知能

人は人工知能と「どうやって」出会うか？
How

喋る（言語）
見るだけ
人

聞くだけ

触るだけ

人工
知能

人の認識の上に人工知能をどう表れるか？
How it looks ?

人

人工
知能

人間は人工知能をどう捉えるか？

人の認識の上に人工知能をどう表れるか？
How it looks ?

人

知能

人の認識空間人間は人工知能をどう捉えるか？

人工知能

人の認識の上に人工知能をどう表れるか？
How it looks ?

人

知能

人工
知能

人の認識空間人は生存競争の必要上、自分以外の知性を「いち早く」「どのような能力か」「何を意図しているか？」を感じ取る能力を持つ。

人の認識の上に人工知能をどう表れるか？
How it looks ?

人

知能

人工
知能

人の認識空間人は生存競争の必要上、自分以外の知性を「いち早く」「どのような能力か」「何を意図しているか？」を感じ取る能力を持つ。 ＝知能感受性

知能感受性
人が自分以外の知性を感受する感性
適切な専門後が設定されていないが、デジタルゲームAIでは極めて重要な概念① 知能感受性は自分自身以上の知性を感じ取ることはできない。
② 知能感受性は状況によってその感受能力が、他の感受性以上に変動しやすい。
③ 知能感受性は、対象とする知性の「存在」「特性（能力）」「現在の意図」などを感受する。

知能感受性
知能感受性は状況により高まったり低かったりする。
自分の意図の強さ
知能感受性の
３つのメインファクター①自分の意図の強さ②自分の生存の危険度③人間との類似性

相手の人間との類似度

自分の生存の危険度

知能感受性
知能感受性は状況により高まったり低かったりする。
知能感受性の
自分の意図の強さ
３つのメインファクター①自分の意図の強さ= 自分が何かを強くしようとすればするほど、それを阻害するものに知能を感じる。
②自分の生存の危険度= 生存の危険度が増すとそれを脅かす者へ敏感になる。
③人間との類似性
相手の人間との類似度= 人は自分と似ている（外面、内面）者に
自分と同じレベルの知能を想定する癖がある。
（擬人化が有効な理由）
自分の生存の危険度（相手が最初からAIだとわかっていると知性を感じないリ理由）キャラクターAIの戦略 ①x②① 高度な知能を作る。
② プレイヤーの知能感受性を高める。

知能方程式（プレイヤーが相手に感じる知能）＝ （相手の知能） × （知能感受性）（例） FPS、アクションゲーム :プレイヤーを窮地に追い込んでAIに攻撃させる。
感受性が高い状態 x シンプルなAI
戦略ゲーム、ボードゲーム:
ゲーム上プレイヤーに強い意図を持たせて（領地を増やしたい、あのカードが欲しい） x 高度な思考AI

知能方程式① 高度な知能を作る。
② プレイヤーの知能感受性を高める。

知能方程式（プレイヤーが相手に感じる知能）＝ （相手の知能） × （知能感受性）
つまり、デジタルゲームのAIを作ろうとする時には、
この二つの掛け算を常に考えていなければならない。

知能方程式（デジタルゲームAI版）（プレイヤーが相手に感じる知能）＝ （AIの知能） × （プレイヤーの知能感受性）

プレイヤーの知能感受性を高める
プレイヤーの知能感受性を操作する①プレイヤーの意図の強さ= プレイヤーに勝ちたいと思わせるプレイヤーにこの手を打ちたい
こういうアクションをしたいと思わせる②プレイヤーの生存の危険度= 追い込む③人間との類似性= 人間と似た手を打つ、人間と似たアクションを行う、人間と似たアニメーションをする。

オセロの知能方程式
知能方程式（デジタルゲームAI版）（プレイヤーが相手に感じる知能）＝ （AIの知能） × （プレイヤーの知能感受性）

高度なアルゴリズム

演出、ゲーム設定、プレイヤーの誘導

これまでたくさんの研究

ほとんど研究がない

学術

エンターテインメント

プレイヤーの知能感受性を高める
プレイヤーの知能感受性を操作する①プレイヤーの意図の強さ= プレイヤーに勝ちたいと思わせるプレイヤーにこの手を打ちたい
こういうアクションをしたいと思わせる②プレイヤーの生存の危険度= 追い込む③人間との類似性= 人間と似た手を打つ、人間と似たアクションを行う、人間と似たアニメーションをする。

人と人の関係性とは何か？

人

人

例えばオセロが提供する盤上人と人との関係性とは何でしょう？

第２部

デジタルゲームAI実例

３つの実例①プレイヤーの意図の強さ②プレイヤーの生存の危険度

③人間との
類似性

知能

Left 4 Dead

△

〇

低

弾幕
シューティング

〇

✖

低

△

高

アストロノーカ
Killzone 2

✖
〇

高

総合

Left 4 Dead

Valve Publication
http://www.valvesoftware.com/publications.html
Michael Booth, "The AI Systems of Left 4 Dead,"
Michael Booth, "Replayable Cooperative Game Design: Left 4 Dead,"
Mike Ambinder, "Valve's Approach to Playtesting: The Application of Empiricism,"

Left 4 Dead の例「Counter Strike」の世界的成功
自分たちはなぜ成功したかを徹底的に考察

それは緩急があったからだ。
Counter Strike の「緩急＝ペース」はある程度、偶然に作られたかもしれない。
では、そういったゲームが面白くなる最適なペースを、人工的に常に作り出すことはできないだろうか？

メタAI (=AI Director)によってペースを作る。

適応型動的ペーシング[基本的発想](1) ユーザーがリラックスいている時に、ユーザーの緊張度が一定の敶居を超えるまで敵をぶつけ続ける。
(2) ユーザーの緊張度が一定の緊張度を超えると敵を引き上げる。
(3) リラックスすると敵を出現し始める(（１）へ）。

メタAI(=AI Director)によるユーザーのリラックス度に応じた敵出現度
計算によって求められた
理想的な敵出現数

ユーザーの緊張度

実際の敵出現数(1) リラックスを破るように敵を出現させる。
Build Up …プレイヤーの緊張度が目標値を超えるまで敵を出現させ続ける。
Sustain Peak … 緊張度のピークを3-5秒維持するために、敵の数を維持する。
Peak Fade … 敵の数を最小限へ減尐して行く。
Relax … プレイヤーたちが安全な領域へ行くまで、30-45秒間、敵の出現を最小限に維持する。

メタＡＩがゲームを認識する方法＝ キャラクターAIが環境を認識する方法

キャラクター用に作成されたナビゲーションメッシュを
メタＡＩがゲームの進行を認識するために使用する。

Valve Publication
http://www.valvesoftware.com/publications.html
Michael Booth, "The AI Systems of Left 4 Dead,"
Michael Booth, "Replayable Cooperative Game Design: Left 4 Dead,"
Mike Ambinder, "Valve's Approach to Playtesting: The Application of Empiricism,"

Valve Publication
http://www.valvesoftware.com/publications.html
Michael Booth, "The AI Systems of Left 4 Dead,"
Michael Booth, "Replayable Cooperative Game Design: Left 4 Dead,"
Mike Ambinder, "Valve's Approach to Playtesting: The Application of Empiricism,"メタAIが作用を行う領域(AAS=Active Area Set)

メタAIが作用を行う領域(AAS=Active Area Set)

メタAIが作用を行う領域(AAS=Active Area Set)

安全な領域までの道のり(Flow Distance)
プレイヤー群の経路をトレース・予測- どこへ来るか- どこが背面になるかAAS に対して行うこと。
メタＡＩは AAS に移動に伴い、敵の群れを生成・消滅させたりする。

プレイヤーからの可視領域可視領域では、例えば、敵のスパウニング（発生）などはできない。

敵出現領域

背後

前方

高頻度

低頻度

敵の種類、アイテムの種類ごとに出現頻度が違う。

ボス出現アルゴリズム(1) Ｎ体を予想される逃走経路上に配置(2) ３つのイベントパターン（何もいない、を含む）（例） Tank, Witch, 何もいない(3) 同じパターンのくり返しは禁止(例) Witch, 何もいない、Witch はＯＫ。
Witch, Witch はだめ。

何もいない

具体的なアルゴリズム(1) 各エリアに、出現数 N を決定する(2) 出現数Nは予想される逃走経路の長さと要求される密度によって計算される.
(3) あるエリアがAAS の中に入るとクリー
チャーがN体生成される(4) そのエリアがAAS の外に出ると生成が中止され、クリーチャーは消滅される。
(5) Ｎはそのエリアがプレイヤーから見えている場合、或いは、プレイヤーがリラックス
モードの場合には、強制的に０になる。

Valve Publication
http://www.valvesoftware.com/publications.html
Michael Booth, "The AI Systems of Left 4 Dead,"
Michael Booth, "Replayable Cooperative Game Design: Left 4 Dead,"
Mike Ambinder, "Valve's Approach to Playtesting: The Application of Empiricism,"３つの実例①プレイヤーの意図の強さ②プレイヤーの生存の危険度

③人間との
類似性

知能

Left 4 Dead

△

〇

低

弾幕
シューティング

〇

✖

低

△

高

アストロノーカ
Killzone 2

✖
〇

高

総合

（例）アストロノーカ
最初の世代

新世代（５～世代後）

最初はすぐに罠にかかるけどだんだんと罠にかからないようになる

MuuMuu, プレイステーション用ソフト「アストロノーカ」（Enix, 1998）
http://www.muumuu.com/games/astro/

どういうゲーム？
珍しい野菜を育てる

しかしバブーが野菜を食べに来るトラップを仕掛けて野菜を守れ！

高値で取引、そして野菜コンテストで優勝！

MuuMuu, プレイステーション用ソフト「アストロノーカ」（Enix, 1998）
http://www.muumuu.com/games/astro/以下の解説は
森川幸人,「テレビゲームへの人工知能技術の利用」,
人工知能学会誌vol.14 No.2 1999-3
http://www.1101.com/morikawa/1999-04-10.htmlに準拠します。

全体の流れ森川幸人, 赤尾容子, 「アリの知恵はゲームを救えるか？」,CEDEC2003
http://www.muumuu.com/CEDEC2003_ants/CEDEC2003_ants.htm

全体の流れ

１日の始まりトラップを配置する
トラップバトル開始

トラップバトル終了
トラップ成績算出
各個体の成績算出
順位を決定
下位２体を削除
適応度に応じて親を選択

子供２体を生成突然変異率を修正

新しい世代を生成

規定世代に達した？
一日の終了

世代交代数を修正

４－① 初期の個体集合を生成
個体を多数（GAにはある程度の母数が必要）用意し、各NPCに遺伝子コードを設定し、初期値を設定する。

[バブーの属性（総計５６）]

体重

身長遺伝子 腕力

耐性_かかし脚力

耐性_快光線[各ビットの重み]

1.87

6.85

16.25

25.03

25.03

16.25

6.85

1.87

0

1

2

3

4

5

6

7
５６ｘ８＝４４８ビット

４－②シミュレーションとNPCの評価
トラップを奥へと通り抜けることができるほど、評価点が高くなる。

適応度 ＝成績＋ＴＢ時間*0.3＋エンジョイ*0.5＋トラップ点＋安全点＋ＨＰ*0.5

要した時間

トラップに対する耐性

４－③ 選択
生き延びて子孫(offspring)を残せる個体を決定する

適応度比例方式（ルーレット選択）… 適応度の大きさに比例した確率で生き延びて親になれる。

４－④交叉による次世代生成
選んだ２つの親の遺伝子を交叉(crossover)させる。

切断点

遺伝子

（詳しい交叉の情報はわかりません）

４－⑤ 遺伝子操作（突然変異）
ある確率（突然変異率）で、遺伝子コード上の遺伝子（内容）をランダムに対立遺伝子に書き換える。
突然変異率 ３％ に設定
バイナリー表現
01010100110101

10100101

010100010

1010101010101

01010100110101

10110101

010100010

1010101010101

反転（１）親の遺伝子が似ているほど（ハミング距離が小さい）突然変異しやすい。
（２）突然変異が起こる場所は、トラップの置き方によってある程度限定される。

（解説）ハミング距離とは？
二つの記号列の間の異なる要素の数

１０１０１００００１
１０１０００１０１０
４箇所違う＝距離４

距離が小さい ＝ 遺伝子が似ている
距離が大きい ＝ 遺伝子が異なる

ゲームデザインにおける工夫
工夫その① 遺伝的アルゴリズムは集団に対するアルゴリズム

一体のトラップバトルの裏で他の２０体も同じトラップバトルをして、全体として世代交代をさせている。
工夫その②

遺伝的アルゴリズムは進化のスピードがプレイヤーに体感させるには遅いプレイヤーには「１世代の変化」と言っているが、実はだいたい１日５世代分進化させている。
全体の適応度の平均値

工夫その③

プレイヤーから見て毎日、同じ適応度の上昇になるように、
世代交代数を調整している

世代交代数

一日の適応度の伸び３つの実例①プレイヤーの意図の強さ②プレイヤーの生存の危険度

③人間との
類似性

知能

Left 4 Dead

△

〇

低

弾幕
シューティング

〇

✖

低

△

高

アストロノーカ
Killzone 2

✖
〇

高

総合

単純なタスクベースのシステムは機能するし、使われることも多い。しかし、近年の複雑なゲームのＡＩではよりマルチな時間・空間スケールに対応する必要があり、階層型タスクネットワーク（HTN, Hierarchical Task Network）が使用される。

Killzone 2 のAI
Based on: Alex Champandard, Tim Verweij, Remco Straatman, "Killzone 2 Multiplayer Bots",
http://files.aigamedev.com/coverage/GAIC09_Killzone2Bots_StraatmanChampandard.pdf

Killzone 2 AI (マルチプレイヤーモード)
On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/(1) Killzone 2 のAI思考(2) Killzone 2 のマップ自動解析

Killzone 2 Screen

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Killzone 2 AI (マルチプレイヤーモード)(1) Killzone 2 のAI思考(2) Killzone 2 のマップ自動解析

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Killzone2 AI
集団のＡＩのコントロールの仕方を考える

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Killzone2 AI

防衛、前進など戦術を指示

戦術の成功・失敗を報告（フィードバック）

ターゲット指示
指示の再発行要求

移動地点を指示
戦況を報告（フィードバック）

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

各ＡＩのアーキテクチャ

HTN Planner

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/HTN (Hierarchical Task Network)

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/HTN (Hierarchical Task Network)
Domain

MethodMethodMethodBranchBranchBranchBranchPrecondition

Precondition

Precondition

Precondition

Precondition

Task

Task

Task

Task

Task

Task

Task

Task

Task

Task

Task

Task

Task

Task

Task

Task を実行する順序などは決められている

Task

BranchTask
Task

HTN (Hierarchical Task Network)

Dana Nau et al., “SHOP2: An HTN Planning System”,
Journal of Artificial Intelligence Research 20 (2003) 379-404

HTN (Hierarchical Task Network)

Task はプラナーの規則によって整列される

Dana Nau et al., “SHOP2: An HTN Planning System”,
Journal of Artificial Intelligence Research 20 (2003) 379-404

HTN (Hierarchical Task Network)

Dana S. Nau,"Hierarchical Task Network Planning", Lecture slides for Automated Planning:
Theory and Practice http://www.cs.umd.edu/~nau/cmsc722/notes/chapter11.pdf

HTN (Hierarchical Task Network)

Task はプラナーの規則によって整列される

Dana S. Nau,"Hierarchical Task Network Planning", Lecture slides for Automated Planning:
Theory and Practice http://www.cs.umd.edu/~nau/cmsc722/notes/chapter11.pdf

HTN (Hierarchical Task Network)

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/HTN (Hierarchical Task Network)

Precondition
Task

Precondition
Task

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/HTN (Hierarchical Task Network)
各AIの思考On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/分岐(Branch)
分岐(Branch)
分岐リスト

TaskList

分岐リスト

TaskList

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Squad AI アーキテクチャ
On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Killzone2におけるHTN統計
On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

各ＡＩのアーキテクチャ
On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/HTN Planner

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

兵士へ命令スカッドを目的に応じて動的に構成

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Killzone2

スカッドを目的に応じて動的に構成

http://www.bungie.net/Inside/publications.aspx

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Killzone2

スカッドを目的に応じて動的に構成

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

スカッドを目的に応じて動的に構成
攻撃対象、護衛対象はゲーム内で動的に決定対象が決まれば対象からの距離など
からスカッドを形成。
或いは、既にあるスカッドに対象を割り当てる。

最初から決まっている
最初から決まっているOn the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Killzone 2 AI (マルチプレイヤーモード)(1) Killzone 2 の AI思考
(2) Killzone 2 のマップ自動解析

マップ
ＡＩの基本原則：異なる目的に、異なるデータ表現を作成する
たとえ、同じ対象物であっても、ＡＩの行動用途に応じてデータ表現を作れ。

戦術思考

戦略思考

ウェイポイント

特に、マップに関してはを「データ階層化」しておくこと（世界表現）

Killzoneにおけるマップ
ＡＩの基本原則：異なる目的に、異なるデータ表現を作成する
たとえ、同じ対象物であっても、ＡＩの行動用途に応じてデータ表現を作れ。

戦術思考

戦略思考

ウェイポイント

特に、マップに関してはを「データ階層化」しておくこと（世界表現）戦略グラフを作りたい
On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

Killzone 2 のウェイポイント

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/ウェイポイントをクラスター化
サイズと含むウェイポイント数を決めてなるべく正方形になるように形成

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

戦略グラフOn the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

戦略グラフ
各エリア間で接するポイントをピックアップして結ぶ

On the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

戦略グラフOn the AI Strategy for KILLZONE 2′s Multiplayer Bots
http://aigamedev.com/open/coverage/killzone2/

何に使うのか？ グローバルな戦況判断

影響マップの方法 <解説>

Influence Map(影響マップ)
セル分割されたマップに、問題とする性質の評価値を記録して行く方法（例）①占有度

0,2

0,4

0,6

0,4

0,2

0,0

0,4

0,6

0,8

0,6

0,4

0,2

0,6

0,8

1,0

0,8

0,6

0,4

0,4

0,6

0,8

0,6

0,4

0,2

0,2

0,4

0,6

0,4

0,2

0,0

0,0

0,2

0,4

0,2

0,0

0,0

http://www.fdaw.unimaas.nl/education/4.5GAI/slides/Influence%20Maps.ppt

Influence Map(影響マップ)
セル分割されたマップに、問題とする性質の評価値を記録して行く方法（例）①占有度② 通過可能確率

0,2

0,4

0,6

0,4

0,2

0,0

0,4

0,6

0,8

0,6

0,4

0,2

0,6

0,8

1,0

0,8

0,6

0,4

0,4

0,6

0,8

0,6

0,4

0,2

0,2

0,4

0,6

0,4

0,2

0,0

0,0

0,2

0,4

0,2

0,0

0,0

http://www.fdaw.unimaas.nl/education/4.5GAI/slides/Influence%20Maps.ppt

Influence Map(影響マップ)（例）様々なIMから計算して戦略的な位置取りを計算する

4

6

8

4

6

8

4

6

4

6

2

8

8

6

4

2

0

-1

-2

-4

8

8

8

4

2

1

0

-2

-4

8

8

8

6

3

1

0

-2

-4

8

8

8

6

6

4

1

0

-2

4

6

8

6

6

4

1

2

4

6

6

4

2

2

3

3

3

3

4

2

2

0

3

2

2

2

3

8

-4

-4

-2

-4

-2

-4

-2

-4

-4

-2

4
0
-1
-2
0,50
0,75
0,2 0,75
0,4
0,6
-4
-5
-3
-3

-4
1,00
0,4
-4

-4
-4 -2
0,75
0,50
0,2
0,0
-4
-2 -1

0

-4
-5
-5 1,00-8
0,75
0,4 1,00
0,6
0,8
-2 -4
-8
-10

-8
1,00
0,6
-10

-6
-4 0,50-2
0,75
0,4
0,2
-8
-4 -2

-10 0,75-8
1,00
0,8-10 0,75
1,0
0,8

-80,6 -4 0,25
0,50
0,4-2

-4

3

3

3

2

2

1

0

-4 0,75
-80,6

2

2

2

2

1

1

0

-3

-10

-8

1

1

1

1

0

0

-2

0,6 -8 0,75
0,8
-4 0,75-80,4 -81,00
-8

0,50
0,6
-8

0,25
0,2-8
-80,4 -8 0,00

0

0

0

0

0

-1

-1

-2

0

0

0

0

-1

-2

-2

-5
-6
-6
-6
0,75
1,00
0,75
-2 -40,2 -4 0,4 -4 0,6
-6

-8
0,50
0,4
-8

-8 -8
0,25
0,00
-80,2 -8 0,0-8

0

0

0

0

-1

-2

-2

0

0

0

0

-1

-2

-2

-2
-2
-2
-2
0,0 1,00
0,2
0,4
0,75
0,75
-2 -2
-2
-2
-2

-2
0,2
0,50
-2

-2
-2 -2
0,0
0,0
0,25
0,00
-2
-2 -2

0

0

0

0

-1

-1

-1

-1

-8

-1

-10

-1

-1

-1

-1

-8

-1

-4

-1

-2

-1

http://www.fdaw.unimaas.nl/education/4.5GAI/slides/Influence%20Maps.ppt

Age of Empire(AOE)における利用例
AOEはタイルベースのＲＴＳ（リアルタイムストラテジー）

マップは毎回、自動生成

Dave C. Pottinger，“Terrain Analysis in Realtime Strategy Games”，
http://zeniroy.springnote.com/pages/481669/attachments/212469“Terrain Analysis in Realtime Strategy Games(PPT)”，http://vr.kaist.ac.kr/courses/cs682/data/ssw.ppt

Age of Empire(AOE)における利用例①
金鉱発掘小屋の最適位置自動検出

Figure 3: Influence map around gold mines.

0.8 0.8 0.8-0.6 -0.6 -0.6

0.8 1.0 0.8-0.6 -1.0 -0.6

0.8 0.8 0.8-0.6 -0.6 -0.6

金鉱＝アトラクター(吸引源)

防壁＝デトラクター（排斥源）

ＡＩに金鉱の発掘小屋を適切な位置に置かせるには？
＝ 金鉱に近いが、近すぎてはいけないところに置く

金鉱の回りのタイル（仮想的）防壁を置いて、近すぎも遠すぎもしない点に最高点のタイルが来るようにする＝ 自動位置検出
Dave C. Pottinger，“Terrain Analysis in Realtime Strategy Games”，
http://zeniroy.springnote.com/pages/481669/attachments/212469

Age of Empire(AOE)における利用例②兵隊の配置の最適位置自動検出

0.8 0.8 0.8-0.6 -0.6 -0.6

0.8 1.0 0.8-0.6 -1.0 -0.6

0.8 0.8 0.8-0.6 -0.6 -0.6

高い場所＝アトラクター(吸引源)

家がある場所＝デトラクター（排斥源）

兵士を街からなるべく遠く、高台の場所に置かせたい＝ 高い場所(アトラクター)、家がある（デトラクター）とする
Dave C. Pottinger，“Terrain Analysis in Realtime Strategy Games”，
http://zeniroy.springnote.com/pages/481669/attachments/212469“Terrain Analysis in Realtime Strategy Games(PPT)”，http://vr.kaist.ac.kr/courses/cs682/data/ssw.ppt

Age of Empire(AOE)における利用例③
兵隊の配置の最適位置自動検出-0.6 -0.6 -0.6
-0.6 -1.0 -0.6
-0.6 -0.6 -0.6

既知の敵のビル、以前通ったルート ＝ デトラクタ（排斥源）
この排斥源が与えるコストをパス検索のコストとすると、「なるべく遠ったことにない敵の基地からみつかりにくいパス」
を見つけることが出来る。
Dave C. Pottinger，“Terrain Analysis in Realtime Strategy Games”，
http://zeniroy.springnote.com/pages/481669/attachments/212469“Terrain Analysis in Realtime Strategy Games(PPT)”，http://vr.kaist.ac.kr/courses/cs682/data/ssw.ppt

SimCity における影響マップの利用
第一層
道路や鉄道、 要素の大きさ要
素間の関係をシミュレーション
第二層「人口密度」「交通渋滞」「環境汚染度」「 ランドバリュ ー」「犯罪発生率」 をシミュ レーション

第三層
地形の影響をシミュレーション

第四層「人口増加率」「消防署」「警察署」「 消防署の影響」「警察署の影響」 をシミュレーション

Crime = Pop. Density^2 - Land Value - Police EffectLand Value = Distance[Zonetype] + Terrain + Transport“AI: A Desing Perspective” AIIDE 2005
http://www.aiide.org/aiide2005/talks/index.html
http://thesims.ea.com/us/will/

多摩 豊,角川書店, 1990
「ウィル・ライトが明かすシムシティーのすべて」,

影響マップの方法 <解説>終わり

Killzone 2 における影響マップ
ボット、砲塔、死亡ポイントの情報を反映させる
さまざまな意思決定に用いる

Killzone 2 における戦略的パス検索
スカッド毎にコストと影響マップを使って戦略パスを見出すKillzone 2 における戦略的パス検索
スカッド毎にコストと影響マップを使って戦略パスを見出すKillzone 2 における戦略的パス検索
スカッド毎にコストと影響マップを使って戦略パスを見出すKillzone 2 における戦略的パス検索
スカッド毎にコストと影響マップを使って戦略パスを見出す

危険

安全Killzone 2 における戦略的パス検索
スカッド毎にコストと影響マップを使って戦略パスを見出すKillzone 2 AIのまとめ(1) 各ＡＩ、スカッドＡＩに階層型タスクネットワークプラナー（HTN Planner） を導入した。
(2) 戦略マップを自動生成した（マップを階層化した）。
(3) 戦略マップ上に影響マップの方法を導入して、スカッドの戦略思考、戦略的パス検索を導入した。

第３部

世界のゲームAI系国際会議の最近の状況

ゲームAI業界カンファレンス・コミュニティ
GDC AI Summit(Game Developer’s
Conference)

http://www.gdconf.com/

Paris Game AI Conference
http://gameaiconf.com/

ゲームAI学会・コミュニティ
AIIDE(AI and Interactive
Digital Entertainment )http://www.aiide.org
IEEE CIG(IEEE Computational
Intelligence and Games )http://www.ieee-cig.org/

AI Game Dev.COM

IEEE CIS(IEEE Computational
Intelligence Society )http://aigamedev.com/

http://www.ieee-cis.org/

AI Game Programmers Guild
http://www.aiwisdom.com/

GDC AI Summit(Game Developer’s
Conference)

GDC AI Summit-GDC 世界最大のゲームAIカンファレンス（２万人）-５日の最初の２日間にAIチュートリアル= AI Summit- AI ゲームプログラマーズギルドが主催-２日間に渡って産学の講演者が各トピックを議論-今年で３年目。これに出ると前の年のゲーム
AIの傾向が分かる。
- 資料はすべて AIGameDev.Com で公開

GDC2011 @miyayou
2.28

3.1

3.2

ModularComponent
AI System

People inyour pocket

KEYNOTE

Navigation in
Insomniac Engine

Automated Level of
Detail Generation
in HALO:REACHAI Pr0n:
AI Debug

Using
Randomness

The animationof Halo:Reach

Biofeedback in
Gameplay

Real-time Helper
Joint System

AI
Navigation

Finding yourway with
Havok AI

Multicore Memory
Management in
MORTALKOMBAT

Crysis 2: Getting
more Interactivity
out of AnimationData

Automated Level of
Detail Generation
in HALO:REACH

Smart AI
through
Influence Map

Kynapse AI

Elite
Postmortem

DOOM
Postmortem

The SIMS3 Createa-Sim User
Expericence

Staffing theExtras

InsideDarkspore
and The Sims:
Medieval

AI & Animation in
ASSASIN’S CREED:BROTHERHOOD

Animating NPC’s
In UNCHARTEDBUNGRING BAY
Postmortem

AI
Developers
Rant !

Scriptingand AIAI Summit

3.3

3.4

Paris Game AI Conference- ゲームAI業界の産業カンファレンス- GDC と並んで、AI Programmers Guild も深く関わる。
- やはり欧州などが中心-学術との交流も志向-主催のAlexは、 AIGameDev.Com サイト主催-資料は AIGameDev.Com で公開

AI Game Dev.COM- ゲームAIの実例紹介・技術紹介- 開発インタビュー- 論文紹介- カンファレンス資料 (GDC AI Tutorial, Paris
Game AI Conference ) が掲載-非常に重要な情報源-登録が必要（無料）-有料会員記事と無料会員記事がある。
-Alex Champandard が主催（研究者からゲーム産業へ。
産業と学術を繋ぐ人物）

AI Game Programmers Guild

•
•
•
•
•
•
•

ゲームAI業界の中心人物が集まるギルド
主催 Steve Rabin (AI Game Programming Wisdom)
中心はメイリングリスト（英語）毎日２～３通は必ず届く。
各種イベント開催(AI Summit, AIIDE)の準備MLを兼ねる
入会資格は一つのタイトルでAIを担当（実はこの縛りはないので申込むとOK）
入っておくとゲームAIの動きが見えてとっても便利（発言もしよう）

AIIDE(AI and Interactive Digital Entertainment )- 学会- GDC と並んで、AI Programmers Guild も深く関わる。
- 2000年代の初頭から、序々にゲーム業界主催のセッションを拡大。
- 基調講演にその年のゲーム業界で人工知能で大きな仕事をした人を呼ぶ。
(例) ウィル・ライト、クリス・ヘッカーIEEE CIG(IEEE Computational Intelligence and Games )- ゲームAIの学会-世界１０ヵ各国から研究者が集まる（５０人ぐらい）- 産業との結び付きは模索中-各種ゲームのコンテストを行う- Mario AI コンテスト- Bot Prize コンテスト- レーシングゲームAIコンテスト- スタークラフトAIコンテスト- 論文はWebで全公開

IEEE CIG 論文はWebで全公開(IEEE Computational Intelligence and Games)

IEEE CIGゲームAIコンテスト

マリオAIコンテスト＝ステージ自動生成＋自動クリアAI

スタークラフトAIコンテスト

ミズパックマン AI コンテスト

カーシミュレーションAIコンテス
トご清聴ありがとうございました！