ゲームAIの作成方法：初心者向けガイド

ゲームの人工知能に関する興味深い資料に出会いました。 簡単な例を使用してAIの基本的なことを説明し、内部には便利な開発と設計のための多くの便利なツールと方法があります。 それらをどのように、どこで、いつ使用するかということもあります。

ほとんどの例は擬似コードで記述されているため、プログラミングの詳細な知識は必要ありません。 カットの下に写真とgifを含む35枚のテキストがあるので、準備をしてください。

UPD。 すみませんが、 PatientZeroはすでにこの記事の翻訳をHabréで行っています。 このバージョンはここで読むことができますが、何らかの理由で記事に合格しました（検索を使用しましたが、何か問題がありました）。 そして、私はゲーム開発者のブログを書いているので、サブスクライバーに翻訳オプションを残すことにしました（私にとってはいくつかの瞬間が異なり、一部は開発者のアドバイスを意図的に逃しています）。

AIとは

ゲームAIは、オブジェクトが置かれている条件に基づいて、オブジェクトが実行するアクションに焦点を合わせます。 これは通常、「知的エージェント」の管理と呼ばれます。エージェントは、ゲームキャラクター、ビークル、ボットであり、場合によってはより抽象的なものです：エンティティのグループ全体または文明です。 いずれの場合も、周囲を見て、それに基づいて決定を下し、それらに従って行動する必要があります。 これは、センス/思考/行動サイクルと呼ばれます：

• センス：エージェントは、自分の行動に影響を与える可能性がある環境内の情報（近くの脅威、収集するアイテム、研究する興味深い場所）についての情報を検出または受信します。
• 考えてみましょう：エージェントはどのように反応するかを決定します（アイテムを収集するのが安全か、最初に戦う/隠す必要があるかを検討します）。
• 行動：エージェントは前の決定を実行するためのアクションを実行します（相手またはオブジェクトに向かって動き始めます）。
• ...キャラクターのアクションにより状況が変化したため、新しいデータでサイクルが繰り返されます。

AIは、ループのセンス部分に集中する傾向があります。 たとえば、自動運転車は道路の写真を撮り、レーダーとライダーのデータと組み合わせて解釈します。 通常、これは入力データを処理して意味を与え、「20ヤード先に別の車があります」などの意味情報を抽出する機械学習によって行われます。 これらは、いわゆる分類問題です。

データのほとんどはすでに不可欠な部分であるため、ゲームは情報を抽出するために複雑なシステムを必要としません。 画像認識アルゴリズムを実行して、先に敵がいるかどうかを判断する必要はありません。ゲームは、意思決定プロセスで情報を直接認識して転送します。 したがって、センスサイクルの一部は、多くの場合、Think and Actよりもはるかに単純です。

ゲームAIの制限

AIには、守らなければならない多くの制限があります。

• AIは、機械学習アルゴリズムであるかのように、事前にトレーニングする必要はありません。 開発中にニューラルネットワークを作成して数万人のプレーヤーを監視し、それらと対戦する最良の方法を学ぶことは意味がありません。 なんで？ ゲームはリリースされていませんが、プレーヤーはいないためです。
• ゲームは楽しませて挑戦する必要があります。したがって、エージェントは人に対する最良のアプローチを見つけるべきではありません。
• エージェントは、プレイヤーが実際の人と対戦しているように感じるように、現実的に見える必要があります。 AlphaGoは人間よりも優れていましたが、実行された手順は、ゲームの従来の理解からはほど遠いものでした。 ゲームが人間の対戦相手を模倣する場合、そのような感情はそうではありません。 アルゴリズムは、理想的な決定ではなく、もっともらしい決定を下すように変更する必要があります。
• AIはリアルタイムで動作するはずです。 これは、アルゴリズムが意思決定のために長時間プロセッサの使用を独占できないことを意味します。 ほとんどのゲームでは、すべての処理を完了してグラフィックの次のフレームに進むのに16〜33ミリ秒しかないため、10ミリ秒でも長すぎます。
• 理想的には、システムの少なくとも一部がデータ駆動型であるため、非コーダーが変更を行い、調整を迅速に行うことができます。

センス/思考/行動のサイクル全体にわたるAIアプローチを検討してください。

基本的な意思決定

最も単純なゲームであるPongから始めましょう。 目標：プラットフォーム（パドル）を動かして、ボールが飛び越えないように跳ね返るようにします。 それはテニスのようなもので、ボールを打たないと負けてしまいます。 ここで、AIには比較的簡単なタスクがあります。プラットフォームをどの方向に動かすかを決定することです。

条件文

AIの場合、Pongには最も明白なソリューションがあります-常にボールの下にプラットフォームを配置してください。

擬似コードで書かれたこのための簡単なアルゴリズム：

ゲームの実行中にすべてのフレーム/更新：
ボールがパドルの左側にある場合：
パドルを左に移動
それ以外の場合、ボールがパドルの右側にある場合：
パドルを右に動かす

プラットフォームがボールの速度で移動する場合、これはPongのAIに最適なアルゴリズムです。 エージェントに対してあまり多くのデータと可能なアクションがなければ、何も複雑にする必要はありません。

このアプローチは非常に単純であるため、Sense / Think / Actサイクル全体はほとんど目立ちません。 しかし、彼は：

• センス部分は2つのifステートメントにあります。 ゲームはボールがどこにあり、プラットフォームがどこにあるかを知っているので、AIはこの情報を求めてボールに目を向けます。
• Think部分には、2つのifステートメントもあります。 これらは2つのソリューションを具体化していますが、この場合は相互に排他的です。 その結果、3つのアクションのいずれかが選択されます-プラットフォームを左に移動する、右に移動する、または既に正しく配置されている場合は何もしません。
• Actパートは、Move Paddle LeftステートメントとMove Paddle Rightステートメントにあります。 ゲームのデザインに応じて、プラットフォームを瞬時にまたは一定の速度で移動できます。

このようなアプローチはリアクティブと呼ばれます-世界の現在の状態に対応して行動するルールの単純なセット（この場合、コード内のifステートメント）があります。

決定木

Pongの例は、実際にはデシジョンツリーと呼ばれる正式なAIコンセプトと同等です。 アルゴリズムは、「リーフ」に到達するためにこれを渡します-実行するアクションに関する決定。

プラットフォームのアルゴリズムの決定木のブロック図を作成しましょう。



ツリーの各部分はノードと呼ばれます— AIはグラフ理論を使用してそのような構造を記述します。 ノードには2つのタイプがあります。

• 決定ノード：各代替が個別のノードとして提示される特定の条件のチェックに基づいて、2つの代替から選択します。
• 終了ノード：最終決定を表す実行するアクション。

アルゴリズムは、最初のノード（ツリーの「ルート」）から始まります。 どの子ノードに移動するかを決定するか、ノードに保存されているアクションを実行して完了します。

決定木が前のセクションのifステートメントと同じ仕事をする場合の利点は何ですか？ ここには、各ソリューションが1つの条件と2つの可能な結果しか持たない一般的なシステムがあります。 これにより、開発者は、ハードコーディングを回避して、ツリー内の決定を表すデータからAIを作成できます。 テーブルの形を想像してください：



コード側では、文字列を読み取るためのシステムを取得します。 それぞれにノードを作成し、2番目の列に基づいて決定ロジックを接続し、3番目と4番目の列に基づいて子ノードを接続します。 条件とアクションをプログラムする必要がありますが、ゲームの構造はより複雑になります。 その中に、追加の決定とアクションを追加し、ツリー定義でテキストファイルを編集するだけでAI全体を構成します。 次に、ファイルをゲームデザイナーに転送します。ゲームデザイナーは、ゲームを再コンパイルしてコードを変更することなく動作を変更できます。

デシジョンツリーは、多数の例に基づいて自動的に構築される場合（ID3アルゴリズムを使用する場合など）に非常に役立ちます。 これにより、受信したデータに基づいて状況を分類するための効果的で高性能なツールになります。 ただし、エージェントがアクションを選択するための単純なシステムを超えています。

シナリオ

事前に作成された条件とアクションを使用するディシジョンツリーシステムを分解しました。 AIデザイナーはツリーを好きなように配置できますが、それでもすべてをプログラミングしたエンコーダーに依存する必要があります。 独自の条件またはアクションを作成するためのデザイナーツールを提供できるとしたらどうでしょうか。

プログラマーが「パドルを左に置く」および「パドルを右に置く」条件のコードを記述できないようにするために、これらの値をチェックするための条件をデザイナーが記録するシステムを作成できます。 次に、決定ツリーのデータは次のようになります。



本質的に、これは最初の表と同じですが、内部のソリューションには独自のコードがあり、ifステートメントの条件部分に少し似ています。 コード側では、これは決定ノードの2番目の列で読み取られますが、満たすべき特定の条件（パドルのボールが左）を探す代わりに、条件式を評価し、それぞれtrueまたはfalseを返します。 これは、スクリプト言語LuaまたはAngelscriptを使用して行われます。 開発者はこれらを使用して、ゲーム内のオブジェクト（ボールとパドル）を取得し、スクリプト（ball.position）で使用できる変数を作成できます。 さらに、スクリプト言語はC ++よりも簡単です。 完全なコンパイル段階を必要としないため、ゲームロジックをすばやく調整するのに理想的であり、非コーダーが必要な機能を作成できるようになります。

上記の例では、スクリプト言語は条件式の評価にのみ使用されていますが、アクションにも使用できます。 たとえば、パドルを右に移動するデータは、スクリプトステートメント（ball.position.x + = 10）になります。 Move Paddle Rightをプログラミングすることなく、アクションもスクリプトで定義されます。

さらに進んで、スクリプト言語で完全な決定木を書くことができます。 これは、ハードコーディングされた（ハードコーディングされた）条件ステートメントの形式のコードになりますが、外部スクリプトファイルに配置されます。つまり、プログラム全体を再コンパイルせずに変更できます。 多くの場合、ゲーム中にスクリプトファイルを修正して、さまざまなAI反応をすばやくテストできます。

イベント応答

上記の例はPongに最適です。 彼らは継続的にセンス/思考/行動のサイクルを実行し、世界の最新の状態に基づいて行動します。 しかし、より複雑なゲームでは、個々のイベントに応答する必要があり、すべてを一度に評価する必要はありません。 ポンはすでに失敗した例です。 別のものを選択してください。

プレイヤーが見つかるまで敵が動かないシューティングゲームを想像してください。その後、彼らは「専門化」に応じて行動します。誰かが「押しつぶす」ために走り、誰かが遠くから攻撃します。 これは基本的なレスポンシブシステムです-「プレーヤーに気づいたら、何かをする」-しかし、論理的にPlayer Seenイベント（プレーヤーに気づく）と反応（答えを選択して実行する）に分けることができます。

これにより、感覚/思考/行動のサイクルに戻ります。 センスパーツをエンコードできます。各パーツは、プレイヤーのAIが表示されるかどうかを確認するためにチェックします。 そうでない場合は何も起こりませんが、見える場合はPlayer Seenイベントが発生します。 コードには、「Player Seenイベントが発生したときに実行します」という別のセクションがあります。ここで、ThinkとActの部分を参照する必要があります。 したがって、Player Seenイベントへの反応を設定します。「成長中」のキャラクターにはChargeAndAttack、狙撃兵にはHideAndSnipeです。 これらの関係は、再コンパイルせずにすばやく編集できるようにデータファイルに作成できます。 また、スクリプト言語を使用することもできます。

難しい決定を下す

単純な反応システムは非常に効果的ですが、十分ではない多くの状況があります。 エージェントが現在何をしているかに基づいてさまざまな決定を下す必要がある場合がありますが、この状態を想像するのは困難です。 決定ツリーまたはスクリプトで効果的に表すには条件が多すぎる場合があります。 次のステップを決定する前に、状況の変化を事前に評価する必要がある場合があります。 これらの問題を解決するには、より複雑なアプローチが必要です。

有限状態マシン

有限状態マシンまたはFSM（状態マシン）は、エージェントが現在いくつかの可能な状態の1つにあり、ある状態から別の状態に移動できることを示す方法です。 そのような状態の特定の数があります-したがって、名前。 人生の最良の例は、信号機です。 異なる場所では異なるライトシーケンスがありますが、原理は同じです。各状態は何か（スタンド、ゴーなど）を表します。 信号機は、常に1つの状態にあり、単純なルールに基づいて1つの状態から別の状態に移動します。

ゲーム内のNPCについても同様の話です。 たとえば、次の条件でガードを行います。

• パトロール
• 攻撃する
• 逃げる

そして、彼の状態を変えるためのそのような条件：

• ガードが敵を見ると、攻撃します。
• ガードが攻撃したが、敵が見えなくなった場合、パトロールに戻ります。
• ガードが攻撃したが、ひどく負傷した場合、彼は逃げます。

ガード状態変数とさまざまなチェックを使用してifステートメントを記述することもできます。近くに敵がいるか、NPCのヘルスレベルは何かなど、さらにステートを追加しましょう。

• 不活動（アイドリング）-パトロールの間。
• 検索（Searching）-気づいた敵が消えたとき。
• 助けを求めてください（助けを見つける）-敵が発見されたが、強すぎて一人で戦えないとき。

それぞれの選択肢は限られています-例えば、ガードが体調が悪い場合、隠れている敵を探しに行きません。

最終的に、「if <x and y、but not z>、then <p>」という膨大なリストが面倒になる可能性があるため、状態と状態間の遷移を念頭に置いておくことができる方法を形式化する必要があります。 これを行うには、すべての状態を考慮し、各状態の下で、他の状態へのすべての遷移を、それらに必要な条件とともにリストします。



この状態遷移表は、FSMを表す包括的な方法です。 図を描いて、NPCの動作がどのように変化するかについての完全な概要を取得しましょう。



このグラフは、現在の状況に基づいたこのエージェントの意思決定の本質を反映しています。 さらに、各矢印は、その隣の条件が真である場合の状態間の遷移を示します。

更新ごとに、エージェントの現在の状態を確認し、遷移のリストを確認し、遷移の条件が満たされた場合、新しい状態を取ります。 たとえば、各フレームは10秒タイマーが期限切れになっているかどうかを確認し、期限が切れている場合は、ガードがアイドルからパトロールに切り替わります。 同様に、攻撃状態はエージェントの健康状態をチェックします-低い場合は逃走状態になります。

これは状態間の遷移を処理していますが、状態自体に関連する動作はどうですか？ 特定の状態の実際の動作の実装に関して、通常、アクションをFSMに割り当てる「フック」には2つのタイプがあります。

• 現在の状態に対して定期的に実行するアクション。
• ある状態から別の状態に移行するときに行うアクション。

最初のタイプの例。 パトロール状態各フレームは、パトロールルートに沿ってエージェントを移動します。 攻撃状態は、すべてのフレームが攻撃を開始しようとするか、可能な場合は状態になります。

2番目のタイプについては、「敵が見えており、敵が強すぎる場合は、ヘルプの検索状態に移行する」という移行を検討してください。 エージェントは、ヘルプの検索ステータスがどこに行くべきかを知るために、どこに行くかを選択し、この情報を保存する必要があります。 ヘルプが見つかるとすぐに、エージェントは攻撃状態に戻ります。 この時点で、彼は脅威について同盟国に伝えたいので、NotifyFriendOfThreatアクションが発生する可能性があります。

そして再び、感覚/思考/行動サイクルのプリズムを通してこのシステムを見ることができます。 センスは、遷移ロジックで使用されるデータに変換されます。 考えてください-各状態で利用可能な遷移。 そして、行為は、州内または州間の遷移で定期的に実行されるアクションによって実行されます。

遷移条件の継続的なポーリングには、コストがかかる場合があります。 たとえば、各エージェントがフレームごとに複雑な計算を実行して敵を認識し、パトロール状態から攻撃に切り替えることができるかどうかを判断する場合、これには多くのプロセッサ時間がかかります。

世界の状態の重要な変化は、出現したときに処理されるイベントと見なすことができます。 FSMが遷移条件をチェックする代わりに、「エージェントはプレーヤーを見ることができますか？」各フレームで、チェックをそれほど頻繁に実行しないように個別のシステムを構成できます（たとえば、1秒に5回）。 その結果、チェックに合格するとPlayer Seenが表示されます。

これはFSMに渡され、FSMはPlayer Seenイベント受信状態に入り、それに応じて対応する必要があります。 結果の動作は、応答する前にほとんど感知できない遅延を除いて同じです。 しかし、センス部分をプログラムの別の部分に分離した結果、生産性が向上しました。

階層的な有限状態マシン

ただし、大規模なFSMを使用することは必ずしも便利ではありません。 MeleeAttacking（近接）とRangedAttacking（遠隔）に置き換えて攻撃状態を拡張したい場合は、攻撃状態（現在および将来）につながる他のすべての状態からの遷移を変更する必要があります。

確かに、この例では多くの重複した遷移があることに気づきました。 アイドリング状態のほとんどの遷移は、パトロール状態の遷移と同じです。 特に同様の状態を追加する場合は、繰り返さないことをお勧めします。 アイドリングとパトロールを共通のラベル「非戦闘」の下にグループ化するのは理にかなっています。ここでは、戦闘状態への移行の共通セットは1つだけです。 このラベルを状態として提示すると、アイドリングとパトロールはサブステートになります。 新しい非戦闘サブステートに個別の変換テーブルを使用する例：

主な条件：


非戦闘状態：


そして、チャート形式で：



これは同じシステムですが、アイドリングとパトロールを含む新しい非戦闘状態があります。 サブ状態を持つFSMを含む各状態（およびこれらのサブ状態は、独自のFSMを含む-など）を使用して、階層有限状態マシンまたはHFSM（階層状態マシン）を取得します。 非戦闘状態をグループ化して、冗長な移行の束を切り取りました。 共通の遷移を持つ新しい状態に対しても同じことができます。 たとえば、将来、攻撃状態を近接攻撃状態とミサイル攻撃状態に拡張すると、敵までの距離と弾薬の存在に基づいて互いに交差するサブ状態になります。 その結果、動作の複雑なモデルと動作のサブモデルを、最小限の重複した遷移で表すことができます。

行動ツリー

HFSMは​​、簡単な方法で動作の複雑な組み合わせを作成します。 ただし、現在の状態に密接に関連する移行規則の形で意思決定を行うことはほとんど困難ではありません。 そして、多くのゲームでこれはまさにあなたが必要とするものです。 また、状態の階層を慎重に使用すると、移行中の反復回数を減らすことができます。 ただし、現在の状態に関係なく、またはほぼすべての状態に適用されるルールが必要な場合があります。 たとえば、エージェントの健康状態が25％に下がった場合、彼が戦い、くつろいでいる、または話しているかどうかにかかわらず、彼に逃げてもらいたいのです。この状態を各状態に追加する必要があります。 また、設計者が後で低ヘルスのしきい値を25％から10％に変更する場合は、これを再度処理する必要があります。

理想的には、この状況では、「どの状態に留まるか」という決定が状態自体の外側にあり、1つの場所でのみ変更を行い、移行条件に触れないシステムが必要です。 行動ツリーがここに表示されます。

それらを実装する方法はいくつかありますが、すべての本質は決定ツリーとほぼ同じであり、アルゴリズムは「ルート」ノードから始まり、ツリーにはソリューションまたはアクションを表すノードが含まれます。 確かに、いくつかの重要な違いがあります。

• これで、ノードは、成功（作業が完了した場合）、失敗（開始できない場合）、または実行中（まだ実行中で最終結果がない場合）の3つの値のいずれかを返します。
• 2つの選択肢から選択するソリューションノードはありません。 代わりに、1つの子ノードを持つデコレーターノード。 それらが成功した場合、それらの唯一の子ノードを実行します。
• アクションを実行するノードは、実行中のアクションを表すRunning値を返します。

この小さなノードのセットを組み合わせて、多数の複雑な動作パターンを作成できます。 前の例のHFSMガードを動作ツリーとして想像してください。



この構造では、アイドリング/パトロール状態から攻撃中またはその他の状態への明示的な移行はありません。 敵が見え、キャラクターの健康状態が悪い場合、パトロール、アイドリング、攻撃など、以前に実行したノードに関係なく、実行はFleeingノードで停止します。



ビヘイビアツリーは複雑です-それらを構成する方法は多数あり、デコレータと複合ノードの適切な組み合わせを見つけることには問題があります。 また、ツリーを頻繁にチェックする方法についての質問もあります。すべての部分を通過するのか、それとも条件の1つが変更された場合にのみ実行するのですか？ ノードに関連する状態を保存する方法-10秒間アイドリング状態になったときを見つける方法、またはシーケンスを正しく処理するために最後に実行されたノードを見つける方法

それが多くの実装がある理由です。 たとえば、一部のシステムでは、デコレータノードが組み込みのデコレータに置き換えられています。 デコレータの条件が変更されたときにツリーを再評価し、ノードを結合し、定期的な更新を提供します。

ユーティリティベースのシステム

一部のゲームにはさまざまなメカニズムがあります。 単純で一般的な遷移規則のすべての利点を得ることが望ましいが、必ずしも完全な動作ツリーの形ではありません。 明確な選択肢や可能なアクションのツリーを用意する代わりに、すべてのアクションを調べて、現時点で最適なアクションを選択する方が簡単です。

ユーティリティベースのシステムがこれに役立ちます。 これは、エージェントに多くのアクションがあり、それぞれの相対的な有用性に基づいて、実行するアクションを選択するシステムです。 ユーティリティは、このアクションがエージェントにとってどれだけ重要または望ましいかを示す任意の尺度です。

現在の状態と環境に基づいて計算されたアクションのユーティリティは、エージェントはいつでも最適な他の状態をチェックして選択できます。 これはFSMに似ていますが、現在の状態を含む各潜在的な状態の推定値によって遷移が決定される場合を除きます。 移行に最も役立つアクションを選択することに注意してください（既に完了している場合はそのままにしてください）。 より多様な場合、これはバランスの取れた小さなリストからのランダムな選択かもしれません。

システムは、ユーティリティ値の任意の範囲を割り当てます。たとえば、0（完全に望ましくない）から100（完全に望ましい）までです。 各アクションには、この値の計算に影響する多くのパラメーターがあります。 ガーディアンの例に戻ります：



アクション間の遷移はあいまいです。どの状態でも他の状態に従うことができます。 優先アクションはユーティリティの戻り値にあります。 敵が見えており、この敵が強く、キャラクターの健康状態が低い場合、FleeingHelpとFindingHelpの両方がゼロ以外の高い値を返します。 FindingHelpは常に高くなります。 同様に、非戦闘アクションは50を超える値を返さないため、常に戦闘よりも低くなります。 アクションを作成し、その有用性を計算するとき、これを考慮に入れる必要があります。

この例では、アクションは固定定数値または2つの固定値のいずれかを返します。 より現実的なシステムには、連続した値の範囲から推定値を返すことが含まれます。 たとえば、エージェントのヘルスが低い場合、逃亡アクションは高いユーティリティ値を返し、敵が強すぎる場合、攻撃アクションは低い値を返します。 このため、エージェントが敵を倒すのに十分な体力がないと感じる状況では、逃げることは攻撃よりも優先されます。 これにより、任意の数の基準に基づいてアクションの優先順位を変更できるため、このアプローチはビヘイビアツリーまたはFSMよりも柔軟で多様になります。

各アクションには、プログラムを計算するための多くの条件があります。 スクリプト言語または一連の数式として記述できます。 キャラクターの日常生活をモデル化するThe Simsでは、追加の計算レベルが追加されます。エージェントは、ユーティリティの推定値に影響する多くの「動機」を受け取ります。 キャラクターが空腹の場合、時間が経つとさらに飢え、キャラクターが満たすまでEatFoodアクションの有用性の結果が増加し、空腹のレベルを下げてEatFood値をゼロに戻します。

評価システムに基づいてアクションを選択するという考え方は非常に単純であるため、ユーティリティベースのシステムは、完全な代替としてではなく、AIの意思決定プロセスの一部として使用できます。 決定木は、2つの子ノードのユーティリティスコアを要求し、より高いノードを選択する場合があります。 同様に、ビヘイビアツリーには、実行する子を決定するためにアクションの有用性を評価する複合ユーティリティノードを含めることができます。

移動とナビゲーション

前の例では、左右に移動するプラットフォームと、パトロールまたは攻撃する警備員がいました。 しかし、一定期間にわたってエージェントの動きをどのように正確に処理するのでしょうか？速度を設定する方法、障害物を回避する方法、目的地までの移動が直線で移動するよりも難しい場合のルートの計画方法を教えてください。それを見てみましょう。

運営管理

, , , . , , . . Sense/Think/Act, , Think , Act . , , . — , . , , . :

desired_travel = destination_position – agent_position

2D-. (-2,-2), - - (30, 20), , — (32, 22). , — 5 , (4.12, 2.83). 8 .

. , , 5 / ( ), . , .

— , , , . . steering behaviours, : Seek (), Flee (), Arrival () . . , , , .

. Seek Arrival — . Obstacle Avoidance ( ) Separation () , . Alignment () Cohesion () . steering behaviours . , Arrival, Separation Obstacle Avoidance, . .

, — , - Arrival Obstacle Avoidance. , , . : , .

, , - .

Steering behaviours ( ), — . pathfinding ( ), .

— . - , , . . , ( , ). , Breadth-First Search BFS ( ). ( breadth, «»). , , — , , .



, . (, pathfinding) — , , .

, , steering behaviours, — 1 2, 2 3 . — , — . - .

BFS — «» , «». A* (A star). , - ( , ), , , . , — «» ( ) , ( ).



, , , . , BFS, — .

, . . ? — , — , .

, — . A* BFS . : , — , . (waypoint), , .


1: . , , .


2: ( ). , , .

. , waypoint, . , .

navigation mesh navmesh ( ). 2D- , — , . , .

Unity — navmesh ( - ). navmesh — , . , — , , .



, A*. , .

Pathfinding — , . , .

pathfinding, — , . : , , , , . . Pathfinding . Sense/Think/Act, , Think Act .

Magic: The Gathering. :

• Swamp — 1 ( ).
• Forest — 1 ( ).
• Fugitive Wizard — 1 .
• Elvish Mystic — 1 .

, . 1 , «» , , ( ) . - , Forest, «» 1 , Elvish Mystic. ?

— , . , , Swamp. . ? Elvish Mystic, Fugitive Wizard, , Swamp . Forest, Swamp. , , . .

, . , ( pathfinding), . , .

, « , ». , :

1. Swamp (: Swamp )
2. Forest (: Forest )

, . , Swamp — Swamp ( ), Forest ( ). — 1 , . Tap the Swamp, 1 .

1. Swamp (: Swamp )
1.1 «» Swamp (: Swamp «», +1 )
–
2. Forest (: Forest )

, . . Forest, « 1 », — Elvish Mystic.

1. Swamp (: Swamp )
1.1 «» Swamp (: Swamp «», +1 )
–
2. Forest (: Forest )
2.1 «» Forest (: Forest «», +1 )
2.1.1 Elvish Mystic (: Elvish Mystic , -1 )
–

, , .

. , , - . , . 1 3 . Swamp , 1 . Forest → Tap the Forest → Elvish Mystic — 4 .

Magic: The Gathering, . , , . , XCOM . , .

, . Magic: The Gathering: , — . .

— backwards chaining ( ). , . , — . .

1 , « 1 ». :

1. — .
2. — .
3. — .
4. — .

— best-first search ( ). , . . A* — — , .

best-first search Monte Carlo Tree Search. , , , ( ). «» . , , , ( , ).

Goal-Oriented Action Planning GOAP ( ). , , , backwards chaining, . « », , : → → .

, . ( « », ), .

, , . , - . , - . , . , -, . .

複雑な例に移る前に、いくつかの簡単な測定を行い、それらを使用して決定を下すことにより、どこまで進むことができるかを推定します。 たとえば、リアルタイム戦略-プレーヤーがゲームの最初の数分で攻撃を開始できるかどうか、およびこれに対してどのような防御策を講じるべきかを判断するにはどうすればよいでしょうか？ プレイヤーの過去の経験を調べて、将来の反応がどうなるかを理解できます。 そもそも、このような初期データはありませんが、それらを収集できます。AIが人と対戦するたびに、彼は最初の攻撃の時間を記録できます。 数回のセッションの後、プレイヤーが将来攻撃する平均時間を取得します。

平均値には問題があります：プレイヤーが20回「決定」し、20回ゆっくりとプレイする場合、必要な値は中間のどこかになり、これは何も役に立ちません。 1つの解決策は、入力データを制限することです-最後の20個を検討できます。

プレイヤーの過去の好みが将来的に同じであると仮定して、特定のアクションの可能性を評価するために同様のアプローチが使用されます。 プレイヤーが火の玉で私たちを5回、稲妻で2回、白兵戦で1回攻撃すると、彼は火の玉を好むことは明らかです。 さまざまな武器を使用する確率を推定します：火の玉= 62.5％、稲妻= 25％、近接= 12.5％。 私たちのゲームAIは、防火に備える必要があります。

もう1つの興味深い方法は、Naive Bayes Classifier（単純ベイズ分類器）を使用して大量の入力データを調査し、AIが正しい方法で応答するように状況を分類することです。 ベイジアン分類器は、電子メールスパムフィルターを使用することで最もよく知られています。 そこで、彼らは単語を調べ、これらの単語が以前に出現した場所（スパムかどうか）と比較し、着信文字について結論を導きます。 少ない入力でも同じことができます。 AIが見るすべての有用な情報（たとえば、どの敵ユニットが作成されるか、どのスペルを使用するか、どの技術を探索したか）および最終結果（戦争または平和、「崩壊」または防御など）に基づいて-目的のAI動作を選択します。

これらのトレーニング方法はすべて十分ですが、テストのデータに基づいて使用することをお勧めします。 AIは、プレイテスターが使用したさまざまな戦略に適応することを学習します。 リリース後にプレーヤーに適応するAIは、予測が難しくなりすぎたり、逆に複雑になりすぎて勝つことができない場合があります。

価値ベースの適応

ゲームの世界のコンテンツとルールを考慮して、入力データを使用するだけでなく、意思決定に影響を与える一連の値を変更できます。 これを行います：

• AIがゲームの世界の状態とキーイベントに関するデータを収集できるようにします（上記のとおり）。
• このデータに基づいていくつかの重要な値を変更しましょう。
• これらの値の処理または評価に基づいて決定を実現します。

たとえば、エージェントには、マップ上の一人称シューティングゲームを選択するための部屋がいくつかあります。 各部屋には独自の価値があり、訪れる価値を決定します。 AIは、valueの値に基づいて、どの部屋に行くかをランダムに選択します。 次に、エージェントはどの部屋で殺されたかを記憶し、その値（彼がそこに戻る確率）を減らします。 同様に、逆の状況でも-エージェントが多くの敵を破壊すると、部屋の価値が上がります。

マルコフモデル

収集したデータを予測に使用するとどうなりますか？ 一定の時間、プレイヤーがいるすべての部屋を覚えている場合、プレイヤーがどの部屋に移動できるかを予測します。 部屋でのプレイヤーの動き（値）を追跡して記録することで、それらを予測できます。

赤、緑、青の3つの部屋を取り上げましょう。 ゲームセッションを見ているときに記録した観察結果：



各部屋の観測数はほぼ同じです-待ち伏せに適した場所をどこで作るべきかはまだわかりません。 統計の収集は、マップ全体に均等に表示されるプレイヤーの復活によって複雑になります。 ただし、マップに表示された後に入力する隣の部屋のデータはすでに有用です。

緑の部屋はプレイヤーに適していることがわかります。赤からの人のほとんどがそこに行き、その50％がそこに残ります。 それどころか、青い部屋は人気がなく、ほとんど訪れることはなく、もしそうなら、それは長続きしません。

しかし、データはもっと重要なことを示しています-プレイヤーが青い部屋にいるとき、彼が目にする可能性が最も高い隣の部屋は緑ではなく赤になります。 緑の部屋は赤の部屋よりも人気があるという事実にもかかわらず、プレイヤーが青の場合は状況が変わります。 次の状態（つまり、プレイヤーが入る部屋）は、前の状態（つまり、プレイヤーが現在いる部屋）に依存します。 依存関係の研究により、観測を互いに独立して単純に計算する場合よりも正確に予測を行います。

過去の状態データに基づいて将来の状態を予測することはマルコフモデルと呼ばれ、そのような例（部屋を含む）はマルコフチェーンと呼ばれます。 モデルは連続する状態間の変化の確率を表すため、各遷移の近くに確率を持つFSMとして視覚的に表示されます。 以前は、FSMを使用してエージェントが存在する動作状態を表しましたが、この概念は、エージェントに関連しているかどうかに関係なく、どの状態にも適用されます。 この場合、状態はエージェントが占有する部屋を表します。



これは、状態変化の相対的な確率の表現の単純なバージョンであり、AIに次の状態を予測する機会を与えます。 数ステップ先を予測できます。

プレーヤーが緑の部屋にいる場合、次の観察中に50％の確率でそこに留まる可能性があります。 しかし、彼がまだそこにいる可能性はどうですか？ プレイヤーが2回観察した後に緑の部屋に留まる可能性があるだけでなく、彼が立ち去って戻ってくる可能性もあります。 新しいデータを含む新しいテーブルを次に示します。



2回の観察後に緑の部屋にいるプレーヤーを見る可能性は51％-21％であり、彼は赤い部屋から来て、そのうちの5％、プレーヤーはその間の青い部屋を訪問し、25％はプレーヤーがいないことを示しています緑の部屋を離れます。

テーブルは単なる視覚的なツールです。手順では、各ステップでの確率の乗算のみが必要です。 これは、1つの修正で未来を遠くまで見ることができることを意味します。部屋に入る機会は、現在の部屋に完全に依存していると仮定します。 これはマルコフ特性と呼ばれます—将来の状態は現在のみに依存します。 しかし、これは完全に正確ではありません。 プレイヤーは、他の要因に応じて決定を変更できます：健康レベルまたは弾薬の量。 これらの値は修正されないため、予測の精度は低下します。

N-gram

格闘ゲームの例とプレイヤーのコンボの予測はどうですか？ 同じこと！ ただし、単一の状態またはイベントではなく、コンボヒットを構成するシーケンス全体を調べます。

これを行う1つの方法は、各入力（キック、パンチ、ブロックなど）をバッファーに保存し、バッファー全体をイベントとして書き込むことです。 そのため、プレーヤーはKick、Kick、Punchを繰り返しクリックしてSuperDeathFist攻撃を使用し、AIシステムはすべての入力をバッファーに保存し、各ステップで使用された最後の3つを記憶します。


（プレイヤーがSuperDeathFist攻撃を開始すると、太線が表示されます。）

プレイヤーがキックを選択し、その後に別のキックを選択すると、AIはすべてのオプションを表示し、次の入力が常にパンチであることを確認します。 これにより、エージェントはSuperDeathFistコンボ受信を予測し、可能であればブロックすることができます。

これらのイベントシーケンスはN-gramと呼ばれます。Nは保存されたアイテムの数です。 前の例では、3グラム（トライグラム）でした。つまり、最初の2つのレコードは3番目のレコードを予測するために使用されます。 したがって、5グラムでは、最初の4つのレコードが5番目のレコードを予測します。

開発者は、N-gramのサイズを慎重に選択する必要があります。 数値Nが小さいほど、必要なメモリは少なくなりますが、保存される履歴も少なくなります。 たとえば、2グラム（バイグラム）はKick、KickまたはKick、Punchを記録しますが、Kick、Kick、Punchを保存できないため、AIはSuperDeathFistコンボに応答しません。

一方、数字が大きいほど多くのメモリが必要になり、AIの学習は難しくなります。多くのオプションがあるからです。 キック、パンチ、またはブロックの3つの可能な入力があり、10グラムを使用した場合、約6万の異なるオプションがあります。

バイグラムモデルは単純なマルコフチェーンです。「過去の状態/現在の状態」の各ペアはバイグラムであり、最初の状態に基づいて2番目の状態を予測できます。 3グラム以上のNグラムもマルコフ連鎖と見なすことができ、すべての要素（Nグラムの最後を除く）が一緒に最初の状態を形成し、最後の要素が2番目の状態を形成します。 戦闘の例は、キックとキックの状態からキックとパンチの状態に移行する可能性を示しています。 入力履歴のいくつかのエントリを1つのユニットと見なすと、本質的に、入力シーケンスを状態全体の一部に変換します。 これにより、マルコフプロパティが得られます。これにより、マルコフチェーンを使用して次の入力を予測し、次のコンボの動きを推測できます。

おわりに

人工知能の開発における最も一般的なツールとアプローチについて話しました。 彼らはまた、それらが適用されるべき状況とそれらが特に有用である状況を調査しました。

これは、ゲームAIの基本的なことを理解するのに十分なはずです。 しかし、もちろん、これらはすべての方法とはほど遠いものです。 あまり人気はありませんが、それほど効果的ではありません：

• 登山、勾配降下、遺伝的アルゴリズムを含む最適化アルゴリズム
• 競争力のある検索/計画アルゴリズム（ミニマックスおよびアルファ-ベータプルーニング）
• 分類方法（パーセプトロン、ニューラルネットワーク、参照ベクトルマシン）
• 知覚と記憶エージェントを処理するシステム
• AIへのアーキテクチャアプローチ（ハイブリッドシステム、アーキテクチャのサブセット、およびAIシステムを課す他の方法）
• アニメーションツール（モーションプランニングと調整）
• パフォーマンス要因（詳細レベル、いつでもアルゴリズム、タイムスライス）

関連リソース：

1. GameDev.netには、 AIに関する記事とチュートリアルのセクションと フォーラムがあります。
2. AiGameDev.comには、関連する幅広いAIゲーム開発に関する多くのプレゼンテーションと記事が含まれています。
3. GDC VaultにはGDC AIサミットのトピックが含まれており、その多くは無料で利用できます。
4.役に立つコンテンツは、 AI Game Programmers Guildの Webサイトでも見つけることができます。
5. AIの研究者およびゲーム開発者であるTommy Thompsonは、AIおよびゲームのYouTubeチャンネルで、商用ゲームでAIを説明および学習するビデオを作成しています。

関連書籍：

1. Game AI Proブックシリーズは、特定の機能を実装する方法または特定の問題を解決する方法を説明する短い記事のコレクションです。

Game AI Pro：ゲームAIプロフェッショナルの知恵を集めました
Game AI Pro 2：ゲームAIプロフェッショナルの知恵を集めました
Game AI Pro 3：ゲームAIプロフェッショナルの知恵を集めました

2. Series AI Game Programming Wisdom-シリーズGame AI Proの前身。 古い方法もありますが、今日でもほとんどすべてが関連しています。

AIゲームプログラミングの知恵1
AIゲームプログラミングの知恵2
AIゲームプログラミングの知恵3
AIゲームプログラミングの知恵4

3. 人工知能：モダンアプローチは、人工知能の一般的な分野を理解したいすべての人にとって基本的なテキストの1つです。 この本はゲーム開発に関するものではなく、AIの基本的な基礎を教えています。