本記事は『戦略ゲームAI 解体新書 ストラテジー＆シミュレーションゲームから学ぶ最先端アルゴリズム』（三宅陽一郎）の「第4章 指揮官としての人工知能─「メンバーやユニットを指揮するゲーム」」から「4.1 チーム・空間・時間の階層化」「4.2 チームの階層化」「4.3 空間の階層化」を抜粋したものです。掲載にあたって一部を編集しています。
指揮官としての人工知能─「メンバーやユニットを指揮するゲーム」
「指揮官としての人工知能」について解説していきます。ゲームの型としては、プレイヤーが指揮官となって、自分のユニットの部隊やメンバーに命令をするゲームです。
チーム全体を動かす場合には、ストラテジーゲームには2つのパターンがあります。1つは、プレイヤーが指揮官となって各メンバーや小隊に命令を与えるパターンです。この場合、人工知能は、指揮官の部下の各メンバーや小隊の頭脳として作っておく必要があります。
もう1つは各メンバーが自由にコミュニケーションをとって連携するパターンです。こちらはマルチエージェント技術に属するものです。多くの場合、ストラテジーゲームでは前者が選択されます。ここで必要とされる構造は、上から下に向けての命令系統、そして下から上に向けてのレポート報告があることです。このような上下構造を持つ組織における人工知能技術について説明します。
チーム・空間・時間の階層化
指揮官からメンバーへ、上から下へ命令を下すストラテジーゲームにおいては3つの階層化が必要になります。すなわち、
（a）チームの階層化
（b）空間の階層化
（c）時間の階層化
です。そして、ストラテジーゲームの人工知能では、この3つの階層を同期させることが設計上必要となります（図4.1）。
なぜなら、指揮官はストラテジーゲームの時空間を自分のチームによって統率することがファースト・ミッションであり、そのためには時空間の階層構造をチームの階層構造によって制御することが必要となるからです。その最もシンプルな解決策が、時空間の階層構造をチームの階層構造に同期させることなのです。それでは、この3つの階層化について順に説明しましょう。
まず（a）「チームの階層化」はとてもわかりやすいかと思います。指揮官から中間層のリーダー、さらに末端のキャラクターたちに至る縦の構造です。ここではどのようなメッセージがやり取りされるか、そして、それぞれの層にどれだけの権限が委譲されるかがポイントとなります。
次に（b）（c）「時間、空間の階層化」は、チームの階層化とも密接に関係します。指揮官が思い描く作戦は常にイマジナリー（想像上）のものです。それを具現化するのは、実際に世界に直面している（＝接地している）キャラクターたちです。しかし、指揮官はグローバルで長期的なプランを立てるのが役割であり、各キャラクターは自分の身体の周りの空間と短い時間の中で活動します。
つまり、階層の上では、長期・大局的なプランの作成の思考を指揮官がしており、階層の下では短期・局所的な反射的な行動をキャラクターがしています。その中間層にあるリーダーは中期的で一定の領域についての指揮を行います。このような3つの階層化はチーム全体に構造を与えます。チームの階層化はチーム全体の運動に秩序を与え、空間の階層化は空間への作用の仕方を定義し、時間の階層化は時間方向のチーム全体の運動を定義します。3つの階層が互いに絡み合いながらチームとしての全体運動を生み出します。さらに、この3つの階層化を詳細に見ていきましょう。
チームの階層化
チーム階層化の基本となるのが、組織の階層図（階層グラフ）です。指揮官を頂点としたヒエラルキー（階層）が形成されるようにソーシャルネットワークは形成される必要があります。そのような組織図には多様な可能性があります。「堅い組織」「柔らかい組織」「縦に深い組織」「横に広い組織」などです。たとえば堅い組織の場合には、指揮官を頂点として各分隊の隊長、その下に各メンバーのような関係があります（図4.2）。
動物の場合には、ボスを頂点とした複雑な社会構造があります。それ以外にも、政治組織の場合には主要人物間のパワーバランスがあります。このような階層図を人工知能が理解するためには、グラフ構造として表現される必要があります。グラフ構造とは図4.2のようなノードとその関係性が示された図です。
このようなグラフ構造を通して、全体を制御する人工知能は各メンバーの関係性を把握することができます。そして、このような関係性を理解したあとは、各エージェントに役割を与えます。役割を与えることを英語ではアサイン（assign）と言いますので、役割を付与することをロール・アサインメント（role assignment）と言います。
ロール・アサインメントは静的にゲームの最初で決められることもあれば、ゲーム進行中に状況の変化に応じて動的に行われることもあります。後者のことを特にダイナミック・ロールアサインメント（動的役割付け）と言います。
たとえば指揮官であれば全体の戦局を理解し、各分隊長に対して戦略的情報を伝達します。また、その情報を受けた各分隊長の役割は、各兵卒に向けた戦術的命令を与えることです。指揮官としての人工知能には、このように役割をアサインするという機能が必要とされます。また、このような複数のエージェントを連携して行動させる技術を「マルチエージェント技術」と言い、ストラテジーゲームでは欠かせない技術となっています。
ただ、このような階層が持つ時間的・空間的階層性を考慮に入れなくてはなりません。組織が大きくなるということは、それぞれのエージェントが把握する時間幅、空間領域が異なるということです。
たとえば、指揮官は大局的な空間の状況を把握し、長時間にわたる過去から未来へ向かったプランを考えねばなりません。その下のサブリーダーは、中程度の時間幅と空間領域を把握し、プランを立てる必要があります。その下のメンバーは、極めて短い時間と、自身の周囲の局所的空間の思考を行う必要があります。つまり、ストラテジーゲームは時間を階層化した認識と、空間を階層化した認識が必要です。このような時間・空間を階層化した意思決定を行う必要があります。
MEMO 参考文献
チームの階層については、以下の記事を参考にしました。
Remco Straatman, Tim Verweij, Alex Champandard, Robert Morcus,and Hylke Kleve, “Hierarchical AI for Multiplayer Bots in Killzone 3”, GAME AI PRO, Chapter 29, pp.377-390, A K Peters/CRC Press
空間の階層化
ストラテジーゲームの人工知能が空間全域を認識するには、空間の階層が必要となります。つまり大局的スケールから徐々により小さな領域へ分割を続けることで、マルチスケールで空間を認識するのです。空間の階層化はナビゲーションAIとして準備しておく必要があります。以下に例を並べて説明していきましょう。
空間階層化の具体例
『HALO』（Bungie, 2001）シリーズはFPS（ファーストパーソン・シューター、1人称視点シューティングゲーム）ですが、敵チームの制御を戦術的に行うために、大きな1つのゾーンが、前衛、中衛、後衛のエリアに分割されています。それぞれのエリアに、「スタンディング・ポイント」（立ち位置）というキャラクターの移動先のポイントが存在します。
それぞれのエリアには「戦い方」がビヘイビアツリーの形で定義されています。ビヘイビアツリーはキャラクターの動作を定義するための最もよく使われる手法の1つで、ツリー状にノードを展開したグラフの形式を持ちます（詳しくは三宅陽一郎『人工知能の作り方──「おもしろい」ゲームAIはいかにして動くのか』（2016、技術評論社）の第4章「ビヘイビアベースAI」P.145-150を参照）。
敵キャラクターは新しいエリアに移動すると、そこに定義されたビヘイビアツリーを自分の意思決定モジュールとして用いることで、そのエリアに応じた戦い方をするのです。ではエリア間をどう移動するかと言えば、自分のチームの状態によっているべき場所が決まっています。たとえば3体以上味方キャラクターが倒されると後ろのエリアに下がる、あるいは、3体以上相手のキャラクターを倒すと前方のエリアに上がるなどです。
このように空間を分割しておくと、集団の指揮を空間ベースで行うことができるため、より行動を定義しやすくなるのです。また各エリアにはキャラクターが位置するべきスタンディング・ポイントが多数セッティングされています（図4.3）。
特にストラテジーゲームにおいては（『Halo』はストラテジーゲームではありませんが）、空間をいかに用いるか、ということが人工知能の賢さの見せ所となります。『KILLZONE 2』（Guerrilla Games、2009年）は、指揮官の人工知能がマップ全域を認識できるように、マップ全体にまずウェイポイントを均等に散りばめます。もしマップが十分に小さければ、すべてのポイントにおけるゲーム状態を集めることで、指揮官の人工知能はゲームの全体像を把握できるでしょう。
しかし実際には、マップは広大です。そこで、敷き詰められたウェイポイントをまずなるべく正方形になるように平均200個のウェイポイントを1ノードとして集団化します（図4.3）。さらに、そのノードを階層化して1つの上位ノードを作成し、グローバルマップを生成します。
このように階層化しておいて、下層から上層に向かって情報を抽象化していきます。ポイントと同じスケールであれば、各ポイントに敵メンバーがいるか、味方メンバーがいる、砲台があるかなどの情報です。1つ上のノードになると、そのノードが含むウェイポイント全体における敵・味方勢力が足し合わされた数値を所持します。
グローバルになると、ある領域が含むノードの敵・味方勢力が足し合わされた数値を所持します。すると、指揮官としての人工知能は大局的なゲーム状況を認識したいときは、グローバルマップの勢力を見ることで、敵・味方の勢力分布を見ることができます。さらに特定の領域の詳細を見たい場合にはノードごとの状態を確認すれば良い、ということになります。いずれの場合も「階層化」がキーとなっています。ストラテジーゲームの人工知能では、階層的な空間の認識は必須の技術となっています。
MEMO 参考文献
空間階層化については、以下の記事を参考にしました。
Damian Isla, “GDC 2005 Proceeding: Handling Complexity in the Halo 2 AI”, Gamasutra,2005.3.11
占有度マップ
影響マップはストラテジーゲームでよく使われる技術です。ここでは、空間的認識としての影響マップの用い方について説明します。
たとえば、『KILLZONE 2』では、影響マップを使って戦局における勢力バランスを検出することで戦略を立てます。近年のFPSはマップが広くなったこともあり、戦略的要素が含まれるようになり、ストラテジーゲームの技術が使われています。
『KILLZONE 2』のマルチプレイヤーモードでは、16対16のNPCが広大なマップで戦います。その中にプレイヤーが1人入り、仲間キャラクターAIと協調しながら敵チームと戦います。各チームは3階層構造の組織図を持ち、順番に上から「指揮官AI」「スカッドAI」「インディビジュアルAI」と呼ばれます。
日本語で言えば、総指揮官、部隊長、各兵士ということです。これらのキャラクターの階層間には、情報網が張られていて、下のキャラクターは上のキャラクターへ成果を報告し、上のキャラクターは集めた情報から戦局全体を把握し、戦略決定を行います。指揮官AIとスカッドAIは、階層型タスクネットワークという意思決定手法を用いています。
ここでは、指揮官AIが戦局全体を把握する方法について解説します。指揮官AIが対象とするのは戦場全体です。戦場全体の状態を把握することで、どこにどの部隊を派遣するかを決定します。そのためにマップを自動解析します。マップを解析する際には、さまざまなスケールで見る必要があります。以下で用いる「ノード」という言葉は各層で用いる「単位」のことです。
まず、マップに敷き詰められたウェイポイントと呼ばれるポイントデータがあります。このデータは兵士を動かすためのポイントです。上記で解説したようにポイント群をなるべく正方形に近い形で、かつ200個ほど含まれるようにウェイポイント群を分割します。この分割された領域を1戦術ノードとして、戦術ノード間を連結したグラフを戦術グラフと呼びます。さらにそれらの戦術グラフを連結させ、1つの戦略ノードとしてみなし、戦略ノードを連結したグラフ構造を戦略グラフと言います。このように各階層では、それより下位の層のノードを一まとまりにしたものを単位として考えます。
さて、この準備のもとに影響マップが使用されます。影響マップにはいくつかの作り方がありますが、ストラテジーゲームの場合には、そのノードをどちらの勢力が支配しているか「占有度」（Occupancy）という考え方があり、占有度を用いた影響マップを作る場合が多くあります。
占有度は、味方の影響力や、敵の影響力がどれぐらいかを数値で表します。占有度マップには占有度を1、0で表すバイナリ占有度マップと、確率的占有度マップ(probabilistic occupancy map)があります。確率的占有度マップは、たとえば味方のいる位置は1.0で、その周囲が0.8、さらにその周囲が0.6のような形で、距離に応じてどんどん影響度が下がっていきます。占有度を一体一体重ね合わせると、敵がたくさんいる所は、敵の占有度が高く、たとえば黒く表示されます（図4.4）。
味方はマイナス値なので、たとえば青く表示されます。ウェイポイントを1ノードとしてクラスター化した各ノードに対して、占有度を計算します。たとえば、青い丸は味方チームの占有度、黒い丸が敵のチームの占有度になります。
自分の勢力が厚い所もあれば薄い所もあります。たとえば、指揮官は自分の勢力が薄い所に兵を向かわせるように命令を出します。ただ、その場所に至るまでの経路に関しては、安全な経路をたどるように命令します。つまり占有度をコストとしてノード上のパス検索を行うのです。このような経路のことを戦略的パス（strategic path）と言います。
MEMO 参考文献
『KILLZONE 2』に関しては、以下のカンファレンス資料を参考にしました。
Remco Straatman, Tim Verweij, Alex Champandard, “Killzone 2 Multiplayer Bots”, Paris Game/AI Conference, 2009
