[アーティクル]
07/15/2016

July 2016

Volume 31 Number 7

C# - マルチエージェント「ミニバスケットボール」ゲームへの AI の適用

Arnaldo Pérez Pérez | July 2016

人工知能 (AI) は、コンピューター科学において現在最も関心を集めている研究分野で、日常生活に大きな影響を与える場面が増えています。ほぼすべての分野に AI が使われていて、そのほとんどが思わぬシナリオに適用されています。たとえば、保険会社は個人間の関係の調査 (顧客が虚偽の申告をしていないかの確認) にデータマイニングアルゴリズムを適用しています。また、Facebook で友人かもしれないメンバーのリストを取得するときや、ビデオゲームをプレイするときなどにも使われています。AI が使われているアプリケーションは多く、経済、商業、天文学、医薬、軍事など多岐にわたります。

人間が行うさまざまな営みを自動化して人工意識を作るという願望が、長い時間を経て、AI と呼ばれる著名な科学形態へと進化してきました。この定義を聞けば単純です。しかし、AI はおそらくコンピューター科学の最も幅広い分野を表現することから、疑いの目を向けられることもよくあります。専門家の観点からは、AI とは、意思決定、問題解決、学習などの人間の思考や行為に関連する行動を自動化することです (『Artificial Intelligence』、 Richard E. Bellman、1978)。この定義では、AI が人間行動の自動化との関連で示されています。そこで、次の疑問が浮かびます。人間の営みを自動化するために AI を作成する必要があるのはなぜでしょう。本当に必要なのでしょうか。答えはイエスです。

人間は、最も洗練され、優雅で、複雑な生物マシンといわれています。人間という生命体の複雑で魅惑的な機能が、脳の驚くべき能力と結びついて、人間をほぼ完璧なマシンにしています。ですが、人間がほぼ完璧なマシンなのであれば、電気と鋼鉄製のマシンと AI をなぜ作るのでしょう。

まず、生命体としての機能が非常に優れているとしても、人間は超高温や超低温には耐えられず、酸素がなければ動けません。また、自然物からのダメージを受けやすく、鋼鉄ほどの頑強さはありません。そのため、電気と鋼鉄製のマシンを作ります。電気と鋼鉄製のマシンであれば、このような問題はすべて回避されます。

次に、人間の脳は、感情を理解し、非常に複雑な論理的思考が可能です。しかし、単純かつ基本的な条件での計算は、コンピューターよりもはるかに遅くなります。マシンの脳 (コンピューター) は人間の脳と違って、1 秒間に数百万の計算を実行できます。大きな領域内での検索や並べ替えなどの操作も、コンピューターは人間よりもはるかに高速に実行します。したがって、人間生活の効率を上げ、時間を短縮するために、AI が必要なのです。その例が電卓です。通常、人間の脳は大きな数の平方根をすばやく計算できません。そこで電卓を使ってほぼ瞬時に結果を求めます。つまり、電卓は、基本的には計算を仕事にすロボットといえます。

ここからは、これまで使われてきたエンティティ、AI 関連のシステム、およびそれらの相互作用について取り上げます。その説明のために、2 つのバスケットボールチーム (Bulls と Knicks) が対戦するマルチエージェントバスケットボールゲーム向けに AI を開発する方法を示します。

エージェント

エージェントという考え方がコンピューター科学にもたらされたのは 90 年代のことです。最近では、80 年代のオブジェクト指向や 70 年代の AI のように、近代的で流行の言葉になっています。エージェントとは、環境を感知し、それに基づいて行動できるエンティティです (『Artificial Intelligence: A Modern Approach』、Stuart Russell and Peter Norvig、1997)。通常のプログラムとの主な違いは、エージェントは自律型でなければならない点です。エージェントは、人間などが直接介入しなくても動作する必要があります。もう 1 つの違いは、他のエンティティ (通常はユーザーやプログラマー) の代理で具体的な仕事を行う点です。エージェントという用語は、文字通り、他の代理で行動するものを表します。

合理的エージェントとは、最善の結果を実現するエージェント、または不確実性がある場合でも、期待される最善の結果を実現するエージェントです (『Artificial Intelligence: A Modern Approach』、Stuart Russell and Peter Norvig、1997)。「合理的」とは、適切な推測を行い、(可能な場合は常に) 論理的帰結に基づいて、希望する目標の実現につながる行動を選択することを指します。人間は合理的エージェントです。目、耳、舌、鼻を使って環境を感知し、通常はある程度論理的な推論を当てはめて、希望する目標につながる行動を選んでから、最終的には手足を使って行動します。

知覚とは、特定の瞬間にエージェントが感知した入力のことです。知覚シーケンスとは、エージェントがその存続期間に感知または把握した知覚の完全なシーケンスのことです。エージェント関数は、任意の知覚シーケンスを行動にマッピングすることで、エージェントの動作を表現します。この関数は、単なる抽象表現です。エージェントプログラムが実際に実装するのがこの抽象表現です。図 1 は、バスケットボールプレイヤーに関するエージェント関数の一部を示します。「知覚シーケンス」列はプレーヤーの状態、「行動」列は対応する「知覚シーケンス」に従って行う行動を表します。

図 1 バスケットボールプレーヤーに関するエージェント関数の一部

知覚シーケンス	行動
(ゴールに近い、ガードがいない)	シュート
(敵が近い、敵がシュートする)	ブロック
(敵がボールを放す)	スティール
(ガードされている、フリーの味方がいる)	パス
(味方がゴール近くにいる、その味方はガードされていない、その味方はダンクシュートがうまい、アイコンタクトできた)	アリウープパス

エージェントのアーキテクチャに応じて、エージェントを以下のカテゴリに分類できます。

反応型エージェントは、環境と継続的対話し、起こった変化に応じてタイムリーに反応できるエージェントです。この用語は、シンボリックな表現や推論を含まないシステムを示すために広く使われるようになっています。このようなエージェントは、行動の長期的な効果を反映せず、他のエージェントとの行動の調整を考慮しません。したがって、反応型エージェントは、常に外部からの刺激にタイムリーに反応するため、イベント駆動型です。このエージェントは、簡単な if-then 規則で実装できます。エージェントの目標が規則によってのみ暗黙的に表現されるため、希望する動作を確保するのは困難です。すべての状況をそれぞれ事前に考慮しておく必要があります。そのため、複雑な環境での反応型システムは、通常何百もの規則を含むことになります。反応型エージェントは環境の内部モデルを持たないため、抽象的な方法で環境について推論することはできません。繰り返しになりますが、エージェントは単に入力を受け取り、簡単な規則に従ってその入力に反応します。
能動型エージェントは、自発的に行動できます。イベント駆動型ではありません。目標を生み出し、その目標を実現するために合理的に行動できます。ある意味、目標駆動型の反応型エージェントとも考えられます。
熟考型エージェントは、知識を象徴的に表現し、信念、意図、願望、選択などの精神観念を使用します。このエージェントは、論理表現を使って、人間の推測、分散行動、動作のモデル化を試みます。通常、信念 (belive)、願望 (desire)、意図 (intention) という BDI アーキテクチャを用いて実装します。このアーキテクチャは、過去を推測し、将来を計画します。この種のアーキテクチャでは、計画の立案が不可欠です。
ハイブリッドエージェントとは、さまざまなアーキテクチャの一部が混在するエージェントです。

エージェントのもう 1 つの分類方法として、学習型エージェントと非学習型エージェントに分ける方法があります。学習型エージェントは、適切に実行するためになんらかのトレーニングを必要とするエージェントです。このエージェントは、以前の経験に基づいて現在の動作を選択するため、時間の経過とともに進化します。非学習型エージェントは、以前の経験によって進化することも、以前の経験に関連して動作することもありません。エージェントは、ハードコードされ、プログラミングとは無関係です。

バスケットボールゲームは、複雑な要素のない限られた環境で、有限個の規則によって定義されます。そこで、今回は非学習型エージェントを使用します。

マルチエージェントシステム

あるエージェントが 1 つ環境内で他のエージェントと共存する場合、つまり、互いに協調や競争を行う場合、その環境はマルチエージェントシステム (MAS) とみなされます。MAS 環境では、各エージェントには環境について独自の見方があります。各エージェントは、環境の内部状態や、他のエージェントがその環境をどのように捉えているかについての知識は持ちません。したがって、MAS とは、以下の特徴を備えた、ある種の分散システムを表します。

エージェントが持つシステムについての情報は不完全です。エージェントが自発的にタスクを解決する能力は不十分です。
システムをグローバルに制御することはできません。
データは分散されています。

連合とは、環境内でのエージェントのサブセットを表します。バスケットボールゲームには、チーム A とチーム B という 2 つの連合が存在します。この 2 つの連合に共通するエージェントは存在せず、どちらにも同じ数のエージェントが所属し、その数は 1 以上です。

戦法は関数です。この関数は、環境の現在状態を受け取り、連合が実行する行動を出力します。通常、チーム A の戦法は、チーム B に所属する各エージェントが実行する現時点での行動によって変わります。

MAS での対話は、コミュニケーション手段によって行われます。エージェントが利用できるコミュニケーション手段にはさまざまな形式があります。エージェント間のコミュニケーションのもっとも簡単な形式はおそらく単純なサインで、各サインにはそれぞれ固有の解釈が結び付けられます。コミュニケーション形式の 1 つに黒板構造があります。この構造は、環境のさまざまな領域に分割された共有リソースから構成され、エージェントは自身の行動についての重要な情報を読み取ったり、書き込んだりすることができます。もう 1 つのコミュニケーション形式は、エージェント間で受け渡されるメッセージです。この形式では、エージェントが特定の構文やプロトコルを使ってメッセージを交換しますが、その意味合いは不十分です。そのため、メッセージを受け取ったエージェントは、メッセージの意図を推測しなければなりません。最後に、1969 年にアメリカ人哲学者 John R. Searle が執筆した『Speech Acts: An Essay in the Philosophy of Language』や、1994 年にカナダ人論理学者 Daniel Vanderveke が執筆した『Foundations of Speech Act Theory』で大きく取り上げられた言語行為論では、エージェントが 2 つのレベルで対話を行うことで、メッセージの受け渡しのデメリットは克服できるとされています。この 2 つのレベルとは、メッセージに含める情報と、メッセージの意図です。このアプローチでは、発話の行為 (単語、文章)、発話の意図 (通知、要求、命令など)、発話の目的 (侮辱、説得など) の違いを明確にします。

MAS においては調整が不可欠です。調整により、システムの動作に一貫性がもたらされ、チーム (連合) の目標実現に貢献します。調整とは、個々のエージェントまたは複数のエージェントに対応する行動を計画または実行する際に、他のエージェントの行動を考慮することを意味します。多くの場合、調整には協力や競争という意味もあります。バスケットボールゲームではその両方の意味があります。

協力は、エージェントが互いのスキルを補完するため、エージェントどうしの行動に相互依存性があるため、さらには成功の条件を満たすために避けられないものとして必要になります。協力モデルは、エージェント全体に動機付けをしたり、同じ方向に関心を向けるためのものです。このモデルにより、共通目標実現に向けてエージェントが行動します。考えられるモデルがもう 1 つあります。それは、各エージェントに個別の目標があるため、エージェントの動機や関心がそれぞれ異なり、各エージェントが目標を実現するためにシステム内で他のエージェントとの競争が起こるモデルです。この場合の競争は、特定のタスクの実現または分散を指すことがあります。このようなモデルでは、エージェントは他のエージェントと行動を調整し、一貫した動作を保証する必要があります。協力環境でも競争環境でも、調整プロセス中に衝突が起こる可能性があります。この衝突は、交渉によって解決します。交渉とは、コミュニケーションに基づいて対話を特定し、他のエージェントの状態と意図を推測するプロセスと考えられます。

ここからは、現在のビデオゲームの多くで採用されているビヘイビアツリーを取り上げます。これは、いままでにない、興味深いデータ構造です。

有限ステートマシンとビヘイビアツリー

有限ステートマシン (FSM) とは、ゲーム内でのエージェントの意思決定、行動選択、および動作の実行をモデル化するために以前から使われている方法です。FSM は、有限個の状態と状態遷移関数に従う数学モデルを表現します。FSM は、反応型の動作についての単純で直感的なメカニズムを提供し、イベントや入力の連続ストリームに反応して処理を行います。

図 2 は、ゴールまでの距離が「近い」と見なされる距離にエージェントが近づいたときの動作をモデル化する簡単な FMS を示しています。これが発生すると、エージェントはシュート動作に移ります。今回のシナリオでは、状態が動作に対応し、状態遷移がイベントに対応します。FSM の主なデメリットは、機能を拡張したり、より複雑な動作を実装する必要が生じた場合に感じられます。このような状況では、状態遷移の数が飛躍的に増加し、FSM に理解および処理させることが極めて難しくなる可能性があります。

図 2 簡単な有限ステートマシンモデル

ビヘイビアツリー (BT) とは、AI の複雑な動作を表現するための、シンプルでスケーラブルなモジュール型のソリューションです。BT は、メンテナンスやセットアップが容易なロジックを提供します。ここ数年、ゲーム業界では BT を使用するゲームが増えています。“Halo3”、“Spore”、“BioShock”、“SWAT 4” などの作品は、動作をモデル化するツールとして BT が組み込まれています。BT は目標指向で、各ツリーが大まかなレベルの個別の目標に関連付けられます。BT は相互にリンクすることができます。そのため、最初は比較的小さな動作を定義し、それらをリンクして、複雑な動作を実装することができます。

BT 内の各ノードは、基本構造または複合構造のいずれかになります。基本構造はツリーのリーフを形成し、複合構造は子ノード間の関係を表す方法を表現します。

基本構造には 2 つの種類があります。行動 (Actions) には、エージェントに関連するメソッド (移動、シュートなど) の実行をまとめます。状態 (Conditions) は、環境の状態 (敵にとどく、移動できる、ゴールに近いなど) を照会します。

図 3 は、状態 C と行動 A という 2 つの子ノードを持つ BT を示しています。

図 3 2 つの子ノードを持つビヘイビアツリー

複合構造体には 4 つの種類あります。セレクター (Selectors) は、実行する子ノードを 1 つ選択します。この選択はランダムに行うか、なんらかの優先順位に従って行います。セレクターの値は、実行される子ノードが成功した (true を返した) かどうかによって異なります。

シーケンス (Sequences) は、子ノードの実行順序を決定します。図 3 の赤い点線は、シーケンスツリーの実行の順序を示しています。この種のノードが成功するには、すべての子ノードもそれぞれ同様に成功しなければなりません。

デコレーター (Decorators) は、プログラミングの設計パターンからヒントを得たもので、プログラミングのプロセスを簡素化する方法を提供し、ノードに機能を追加することで動作を拡張できるようにします。タイマーデコレーターは、デコレーターの一種で、名前の通り、一定の時間が経過したら子ノードを実行します。カウンターデコレーターは、子ノードまたは動作を複数回実行できるようにします。図 3 のカウンターデコレーター D は、定義に従って、ノードのシーケンスを 10 回実行します。

ここからは、今回用に考えたバスケットボールゲームの簡易版と、このようなゲーム向けに提案する AI を紹介します。

バスケットボールゲームと AI の実装

バスケットボールゲームは、複雑な FSM や非常に大きな BT を必要とする大規模で複雑なゲームになるため、今回は簡易版のゲームにして、ある程度基本的なオフェンスとディフェンスのプレイの戦法を含めています。このゲームには、速度とシュート精度というプロパティを持つ 2 人のプレイヤー (A1 が青、B1 が緑) が存在します。速度は環境に対するプレイヤーの反応速度を定義し、シュート精度は 1 回のシュートでゴールする確率を定義します。最初は、プレイヤーが中央からスタートします (図 4 参照)。スコアは 0 対 0 で、プレイ時間は 0 秒です。15 秒経過しても得点できなければ、ショットクロックバイオレーションが発生し、プレイヤーはボールの支配権を失います。ゲームの GUI は、Windows フォームアプリケーションで構成しています。このアプリケーションを調べれば、細かいグラフィックをチェックできます。[Start] ボタンはゲームを開始します。[Stop] ボタンはゲームを停止します。

図 4 AI を実装したバスケットボールゲーム

黄色の正方形はゴール、白い丸はボールを表します。では、バスケットボールコートに相当する Court クラスを分析してみましょう。このクラスは、図 5 にリストしたフィールドを含んでいます。

図 5 Court クラス

public class Court
{
public int Height { get; set; }
public int Width { get; set; }
public Point BallPos { get; set; }
public int ScoreTeamA { get; set; }
public int ScoreTeamB { get; set; }
private readonly string[,] _grid;
public Court(int h, int w)
  {
Height = h;
Width = w;
_grid = new string[h,w];
  }
...
}

フィールド Height と Width については文字どおりの意味です。BallPos は、コート上のボールの位置を示します。ScoreTeamA および ScoreTeamB は、各プレイヤーの得点を表し、_grid はコートのロジックを含む文字列の行列です。プレイヤー A1 がセル (0,0) に位置し、ボールを支配している場合、_grid [0, 0] の値は A1,B になります。B1 にも同じ考えが当てはまるため、グリッド上のセルの値は、A1、B1、A1,B、B1,B のいずれかになります。このクラスに実装されるインデクサーメソッドは以下のようになります。このインデクサーは、グリッド上の要素のインデックスを提供し、コート上のボールの位置も更新します。

public string this[int i, int j]
{
get { return _grid[i, j]; }
set
  {
    _grid[i, j] = System.String.Format("{0}", value);
if (IsBall(value))
    BallPos = new Point(i, j);
}
}

メソッド IsBall は、指定した文字列がボールを支配しているかどうか判断します。

private bool IsBall(string s)
{
  return s.Split(',').Contains("B");
}

メソッド IsEmpty は、グリッド上のセルが空かどうかを判断します。

public bool IsEmpty(int i, int j)
{
  return string.IsNullOrEmpty(_grid[i, j]);
}

最後に、メソッド ToWallGrid は、PathNode 行列を返します (図 6 参照)。簡単に説明すると、このメソッドはルート検索アルゴリズムで使用されます。

図 6 ToWallGrid メソッド

public PathNode[,] ToWallGrid()
{
var wallGrid = newPathNode[Height, Width];
for (var i = 0; i < Height; i++)
  {
for (var j = 0; j < Width; j++)
 {
wallGrid[i, j] = new PathNode
  {
    IsWall = !string.IsNullOrEmpty(_grid[i,j]),
    X = i,
    Y = j,
  };
}
} 
return wallGrid;
}

このメソッドの wallGrid 行列は、ルート検索アルゴリズムが機能する前に、特定のセルが障害になるかどうかを示します。

BehaviorTree クラスとそのすべての子孫クラスは、図 7 のダイアグラムに従って構造化されています。

図 7 BehaviorTree クラスの構造

BehaviorTree に関連するすべてのクラスのコードを、図 8 に示します。

図 8 BehaviorTreeに関連するすべてのクラスのコード

public abstract class BehaviorTree
  {
public List<BehaviorTree> Children { get; set; }
public BehaviorTree Value { get; set; }
public Court Court { get; set; }
protected BehaviorTree(Court court)
{
  Court = court;
}
public abstract bool Exec();
  }
public abstract class Primitive : BehaviorTree
  {
protected Primitive(Court court) : base(court)
{
}
  }
public class Action: Primitive
  {
public delegate bool Act();
public Act Function { get; set; }
public Action(Court court):base(court)
{
}
public override bool Exec()
{
return Function();
}
  }
public class Conditional : Primitive
  {
public delegate bool Pred();
public Pred Predicate { get; set; }
public Conditional(Court court)
  : base(court)
{
}
public override bool Exec()
{
return Predicate();
}
  }
public abstract class Composite : BehaviorTree
  {
protected Composite(Court court):base(court)
{
}
  }
public class Sequence: Composite
  {
public Sequence(Court court)
  : base(court)
 {
}
public List<int> Order { get; set; }
public override bool Exec()
{
if (Order.Count != Children.Count)
throw new Exception("Order and children count must be the same");
foreach (var i in Order)
{
if (!Children[i].Exec())
return false;
}
return true;
}
  }
public class Selector : Composite
  {
public Selector(Court court)
  : base(court)
{
}
public int Selection { get; set; }
public override bool Exec()
{
return Children[Selection].Exec();
}
  }

すべてのクラスはわかりやすく、コードも一目瞭然なので、これらについての説明は省略します。各クラスの目的や、上記の概念に関連するしくみは簡単に理解できると思います。

このアプリケーションの最も重要なクラスは、エージェントを表現し、その動作とすべての AI コードをカプセル化する Player クラスです。プレイヤーの動作は、オフェンスとディフェンスに分かれています。オフェンスは FSM を使ってモデル化し、ディフェンスは 図 3 で示したような簡単な BT を使ってモデル化しています。Player クラスは、図 9 にリストしたフィールドを含んでいます。

図 9 Player クラスのコードフィールド

public class Player
{
public Point Position { get; set; }
public string Name { get; set; }
public int Number { get; set; }
public int Speed { get; set; }
public double ShootingAccuracy { get; set; }
public bool BallPossession { get; set; }
public LinkedList<PathNode> Path;
private readonly Court _court;
private readonly Random _random;
public Player(Court court, Point basket)
  {
    ScoringBasket = new Point(basket.X, basket.Y);
    _court = court;
    Path = new LinkedList<PathNode>();
    _random = new Random();
  }
}

Position は、コート上のプレイヤーの位置を定義します。ScoringBasket は、プレイヤーがコート上で得点する位置です。Path は、1 つの始点から別の点までの最短ルートを、障害物を考慮して見つけるために使用する PathNode のリストです。_random はシュートの確率を求めるために使用する Random オブジェクトです。残りのフィールドはその名の通りの意味です。

このクラスは、以下の列挙型を使用します。

public enum Percept
{
  Guarded,
  CloseToBasket,
  BallLoose,
  BallInPossession,
  OnDefense,
  None
}
public enum Direction
{
  Up, Down, Left, Right
}

Player クラスは行動の基準となるメソッドと行動のメソッドに分かれています。行動の基準となるメソッドは 3 つあります。

private bool IsBallLoose()
{
return _court[_court.BallPos.X, _court.BallPos.Y] == "B";
}
private bool IsCloseToBasket()
{
return Math.Abs(Position.X - ScoringBasket.X) <= 1 &&Math.Abs(
  Position.Y - ScoringBasket.Y) <= 1;
}

メソッド IsBallLoose は、ボールがコート外に出たかどうかを単純に判断します。メソッド IsCloseToBasket は、プレイヤーがゴールに近づき、得点可能圏内に入ったかどうかを判断します。

private bool IsOpponentReachable()
{
var opponents = FindOpponents();
var factor = ScoringBasket.Y == 0 ? 1 : -1;
foreach (var opponent in opponents)
  {
if ((Position.Y - opponent.Y) * factor >= 0)
return true;
  }
return false;
}

メソッド IsOpponentReachable は、コート内の敵の 1 人に手がとどく距離かどうかを示します。変数 factor は、敵に手がとどく距離にいるかどうかの判断を補佐します。「敵に手がとどく」とは、敵が (オフェンスモードのときに) 得点するためにゴールに向かって移動するとき、そのプレイヤーのセルを通り過ぎないことを意味します。

行動 (Actions) ブロックのコードを見る前に、エージェントが行動を実行した直後に呼び出される 2 つのメソッドを見ておきます。

public void Action()
{
var percepts = GetPercepts();
if (percepts.Contains(Percept.CloseToBasket))
Shoot();
elseif (percepts.Contains(Percept.BallLoose))
MoveToBall();
elseif (percepts.Contains(Percept.BallInPossession))
MoveToBasket();
elseif (percepts.Contains(Percept.OnDefense))
Defend();
}

このメソッドはエージェントの機能を表します。一連の知覚や反応を受け取り、知覚を考慮して取るべき行動の判断します (図 10 参照)。

図 10 エージェントの機能

private IEnumerable<Percept> GetPercepts()
{
var result = new List<Percept>();
if (IsCloseToBasket())
result.Add(Percept.CloseToBasket);
if (IsBallLoose())
result.Add(Percept.BallLoose);
if (IsCloseToBasket())
result.Add(Percept.CloseToBasket);
if (BallPossession)
result.Add(Percept.BallInPossession);
else
result.Add(Percept.OnDefense);
return result;
}

メソッド GetPercepts は、複数の行動基準を利用して、実行する行動を決定する際に使用されることになる一連の知覚を返します。

まず、メソッド FeasibleMoves がフィルターとして働きます。エージェントが特定の方向への移動を決めたら、FeasibleMoves の方向のリストをチェックして、エージェントがその方向に移動できるかどうかを確認します。移動できなければ、何の行動も取りません。メソッド FeasibleMoves への呼び出しを含む Move メソッドを、図 11 に示します。

図 11 Move メソッド

private void Move(Direction direction)
{
if (!FeasibleMoves().Contains(direction))
return;
  _court[Position.X, Position.Y] = "";
switch (direction)
  {
case Direction.Left:
Position = new Point(Position.X, Position.Y - 1);
break;
case Direction.Right:
Position = new Point(Position.X, Position.Y + 1);
break;
case Direction.Up:
Position = new Point(Position.X - 1, Position.Y);
break;
case Direction.Down:
Position = new Point(Position.X + 1, Position.Y);
break;
  }
// To write his correct value on the grid
_court[Position.X, Position.Y] =
(_court.BallPos.X == Position.X && _court.BallPos.Y == Position.Y) || BallPossession
? Name + ",B"
: Name;
if (_court[Position.X, Position.Y].Split(',').Contains("B"))
BallPossession = true;
}

メソッド MoveToBall は、コード上で放たれたボールに向かってプレイヤーを移動します。

private void MoveToBall()
{
var ballPos = _court.BallPos;
if (ballPos.X == Position.X)
Move(ballPos.Y>Position.Y ? Direction.Right : Direction.Left);
elseif (ballPos.Y == Position.Y)
Move(ballPos.X>Position.X ? Direction.Up : Direction.Down);
}

図 12 に示したように、MoveToBasket はアアプリケーションで独特のメソッドを表します。このメソッドは、計画を含み、エージェントをハイブリッド (反応型と熟考型) にする唯一のメソッドです。

図 12 MoveToBasket メソッド

private void MoveToBasket()
{
if (Path.Count == 0)
  {
    Path = new LinkedList<PathNode>(PathFinding(Position, ScoringBasket));
    Path.RemoveFirst();
  }
// Already have a strategy
if (Path.Count > 0)
  {
var nextMove = Path.First();
    Path.RemoveFirst();
// Check if move still available
if (string.IsNullOrEmpty(_court[nextMove.X, nextMove.Y]))
MoveDecision(nextMove);
else
Path.Clear();
  }
}

MoveToBasket は、プレイヤーの位置からゴールまでのルートを構築します。計画が失敗した場合、実現不可能になった場合、ルートを削除して、再計算します。PathFinding アルゴリズムは、検索アルゴリズムで、今回は A* アルゴリズムを使用しています。ルート検索アルゴリズムは AI で頻繁に実装され、ゲームではごく一般的に使われます。

前述のように、ディフェンスの動作は BT によって開発しています (図 13 参照)。

図 13 ビヘイビアツリーを使用したディフェンスの動作

private void Defend()
{
DefensiveBehavior(_court).Exec();
}
private BehaviorTree DefensiveBehavior(Court court)
{
var isReachableNode = new Conditional(court)
{
  Predicate = IsOpponentReachable
};
var blockNode = new Action(court)
{
  Function = BlockPath
};
var defenseBehavior = new Sequence(court)
{
  Order = new List<int> {0,1},
  Children = new List<BehaviorTree>
    {
isReachableNode,
blockNode
    }
};
return defenseBehavior;
}

メソッド BlockPath は、プレイヤーが最も近い敵に対して、ゴールまでのルートをブロックしようとする戦法を表します。これは、マンハッタン距離を使用して最も近い敵を特定する Closest メソッドを利用しています (図 14 参照)。

図 14 BlockPath メソッド

private bool BlockPath()
{
var closestOppPos = Closest(FindOpponents());
// Move to same row
if (closestOppPos.X > Position.X)
Move(Direction.Down);
elseif (closestOppPos.X < Position.X)
Move(Direction.Up);
// Move to same column
elseif (closestOppPos.Y > Position.Y)
Move(Direction.Right);
elseif (closestOppPos.Y < Position.Y)
Move(Direction.Left);
return true;
}

まとめ

今回は、マルチエージェントのバスケットボールゲーム向けにハイブリッドエージェントを開発する方法を説明しました。新しい機能を組み込み、今回紹介した AI を強化するのは皆さんです。今後のコラムでは、バスケットボールゲーム用に学習型エージェントを作成する際に生じる問題に対処します。学習型エージェントは、時間の経過とともに進化し、新しくプレイするたびに戦法が強化されるエージェントです。

Arnaldo Pérez Castaño は、キューバを拠点とするコンピューター科学者です。彼は、『JavaScript Fácil』(Marcombo S.A、2013 年)、『HTML y CSS Fácil』(Marcombo S.A、2014 年)、『Python Fácil』(Marcombo S.A、2015 年) というプログラミング書籍シリーズを執筆し、VisualStudioMagazine.com と Smashing Magazine で記事を執筆しています。Visual Basic、C#、.NET Framework、および人工知能を専門とし、nubelo.com (英語) でフリーランサーとして独自のサービスを提供しています。映画や音楽にも情熱を注いでいます。連絡先は arnaldo.skywalker@gmail.com (英語のみ) です。

この記事のレビューに協力してくれたマイクロソフト技術スタッフの James McCaffrey に心より感謝いたします。
Dr.James McCaffrey は、ワシントン州レドモンドの Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。Dr.McCaffrey の連絡先は jammc@microsoft.com (英語のみ) です。

次の方法で共有

C# - マルチエージェント「ミニバスケットボール」ゲームへの AI の適用

エージェント

マルチエージェントシステム

有限ステートマシンとビヘイビアツリー

バスケットボールゲームと AI の実装

まとめ

その他のリソース

次の方法で共有

C# - マルチエージェント「ミニバスケットボール」ゲームへの AI の適用

エージェント

マルチエージェント システム

有限ステート マシンとビヘイビア ツリー

バスケットボール ゲームと AI の実装

まとめ

その他のリソース

マルチエージェントシステム

有限ステートマシンとビヘイビアツリー

バスケットボールゲームと AI の実装