2人から4人のプレーヤーがいる可能性のあるゲームのAIを構築することを検討しています。この分野で少し調べてみると、すべてのプレイヤーがそれを手に入れようとしていると想定し、より多くを必要とする1人のより大きな敵として効果的に扱うことができる「パラノイド」AIを構築しない限り、標準のミニマックスアプローチはどれも機能しないようです。ターンします。
ゲームの問題の一部は、ボードが非常に大きく、通常、任意のターンで任意のプレーヤーが利用できる数百の動きがあることです。さらに、特定の動きにより、プレーヤーが再び動くことができる場合があります。これにより、積極的に剪定しない限り、幅優先探索は非常にコストがかかります。
コンテキストとしては、ゲームはチェッカーにほぼ似ていますが、ボード上で約4倍の大きさでプレイされます。
この種のゲームに適したアルゴリズムはありますか？それとも、移動ツリーを検索せずにヒューリスティックを使用するのが最善の策ですか？
ここで、複数の質問があります。
簡単な質問は、「この巨大な移動スペースについてどうすればよいですか？」です。良い答えの1つは、ボード評価ヒューリスティックを使用したツリー検索です。基本的な考え方は、検索スペースが大きすぎて直接処理できないため、合理的に可能な限り前方に検索し、最後にゲーム自体の知識を使用して、どの葉が最適かを評価するというものです。
たとえば、チェスには、ポーンは1の価値があり、ビショップとナイトは3の価値があり、ルークは5の価値があり、クイーンは9の価値があるという大まかなルールがあります。したがって、検索プロセスの最後に、ボード評価関数を使用できます。両側のポイントの合計を集計し、それを評価関数として使用します。（警告：その特定の評価関数は非常に粗雑です。良い関数は、ピースの位置、チェックされていることなどに依存します。ボードの評価関数を理解するのは簡単ではありません。）
難しい質問は、「2人以上のプレーヤーにどう対処するか」です。これは非常に難しい質問です。これに対処する1つの方法は、各プレーヤーがゲームに勝つために厳密に外出していると想定し、それに応じて検索アルゴリズムを適応させることです。これは、すべての敵対するプレーヤーが協力し、調整していると仮定することとはまったく同じではありません。ラッセルとノーヴィグには、敵対的検索の章のAIMAのアイデアに焦点を当てたページがいくつかあると思います。ただし、AIMAがこのトピックに関して持っているのは、マルチプレイヤーAIの方向へのジェスチャーだけです。
マルチプレイヤー（つまり、マルチエージェント）AIは、単なるシングルエージェントAIよりもはるかに困難な取り組みです。