negamaxアルゴリズムをどのように使用できるのか疑問に思いました。ゲームマンカラのエージェントをC＃で作成しようとしています。ゲームノードが与えられると、アルゴリズムは単一の番号を与えます。
私のAIプレーヤーが動きをしたいとします。negamax関数は単一の数値を返します。だから、それはその時点からの最高の動きのスコアが何であるかを教えてくれます。この1つの番号をどのように使用できますか？
プレイヤーAの番なら、彼の可能な動きを作って、それぞれのネガマックスをチェックしてみました。ただし、最初に移動してからネガマックスを確認すると、ネガマックスが実行されているときに（まだ1レベルの深さであると仮定します）、移動が評価され、次の移動はプレーヤーBである必要があります。
私はこれについて本当に混乱しています。（ウィキペディアのページなどで）negamax擬似コードを見ると、そのプレーヤーの動きを試すように言われます。そうすると、どの手がそのスコアを獲得したかを教えずに、最高のスコアを返します。
negamaxはどのように使用されることになっていますか？
これは楽しいものです。
それはすべて、可能な動きのツリー内の各ノードを探索することです。アルファベータプルーニングを使用する場合は、ツリーの一部のブランチを「プルーニング」（評価ではない）することで、アルゴリズムをより効率的にすることができます。剪定を使用していないと仮定し、ツリー全体を確認します。
MancalaがTic-Tac-Toeのような非常に単純なゲームである場合、「評価関数」を必要とせずにアルゴリズムを実装できます。三目並べでは、可能なすべての動きを実行すると、勝ち、負け、または引き分けのいずれかになります。可能な移動の数は非常に限られており、AIエンジンはすべての最後まで可能性。
一方、チェスでは、「評価関数」（以降、EF）が不可欠です。これは、この惑星のハードウェアでは、ゲームの最後までチェスのすべての可能なシーケンスを計算できるわけではないためです。そのため、ほとんどのチェスAIは12〜14レベルの深さになり、結果の位置を評価して、クイーンに8ポイント、ルークに5ポイント、ビショップまたはナイトに3ポイント、ポーンに1ポイントを割り当て、さらに次のポイントを割り当てます。制御された正方形（制御された中央の正方形のポイントが増える）、キングの安全性など。
マンカラの場合、私が知る限り、評価関数が必要になるほど複雑かもしれませんが、まだ所有しているシードの数など、評価関数は単純であり、高度な位置。（Wiki Mancalaを調べたところ、考えられるバリエーションはたくさんあるようです。どのバリエーションを使用しているかわかりません。）
したがって、negamaxアルゴリズムは、特定の深さ（つまり、すべての可能なプレイを使用してゲームが終了するまで）で、単純なEFを使用して実装する必要があります。5つの動きを深く見せるAIを実装すると仮定します。negamaxの良いところは、完全に対称でゼロサムであるということです。つまり、AIの位置が5と評価された場合、人間のプレーヤーの位置は-5と評価されます。そして、人間のプレイヤーの場合は13に評価され、AIの場合は-13に評価されます。それが議論されている「単一の数」です。このすべてを念頭に置いて、AIアルゴリズムは次のようになります（ここでも、剪定はありません）。
1）可能なAIの動きをそれぞれ調べます
2）これらの動きのそれぞれについて、考えられる各対戦相手の反応を調べます
3）考えられる応答のそれぞれについて、考えられるAIの動きをそれぞれ調べます
4）それらの可能なAIの動きのそれぞれについて、それぞれの可能な敵の反応を調べます
5）最後に、それらの可能な敵の反応のそれぞれについて、それぞれの可能なAIの動きを調べます
これで深さ5に到達し、5つのレベル、おそらく数千または数百万の葉（最下層ノード）を持つツリーを構築しました。これは、各ノードがその親ノードへの参照と、そのすべての子ノードへの参照を持つようにコーディングします。これにより、親から子へ、そしてその逆へとツリーを簡単にトラバースできます。
ツリーを適切に設定したら、次のようにnegamaxアルゴリズムを実装します（AIプレーヤーのスコアが高いほど良いと仮定します）。
6）4レベルの対戦相手の応答ごとに、すべてのAIの子供たちの動きの中で最も高い評価を見つけ、他のすべての子供たちを剪定します。あなたは、可能性のある4番目から4番目の対戦相手の応答に応じて、AIがどの5番目からの移動を再生するかを決定しています。したがって、各第4レベルの応答には、想定される第5レベルの応答が1つだけあります。次に、5レベルの子で作成した評価スコアを4レベルの親に割り当てます。これは、その4レベルの対戦相手の動きに到達すると、AIがこの特定の5レベルの動きを行い、ボードがそのスコアを評価することを意味します。
7）次に、各3レベルのAIの動きを評価し、それぞれについて、4番目から4番目のすべての対戦相手の動きの中で最も低い評価を見つけ、他のすべての子供を剪定し、4番目のレベルのスコア（最高の5番目から来た）を割り当てますレベルノード）を第3レベルに。子スコアが最も低いことを除いて、手順6と同じように実行します（b / cこれはAIの動きであり、対戦相手の動きではありません）。
8）ステップ6と同じことを2番目のレベルで行い、すべての3番目から3番目の移動の中で最も高い評価を見つけ、2番目のレベルのノードにそれらの最も高い評価を割り当てます。
9）ステップ7と同じことを第1レベルで行い、すべての2番目から2番目の移動の中で最も低い評価を見つけ、第1レベルのノードにそれらの最も低い評価を割り当てます。
10）すべての第1レベルのノードを確認すると、AIはスコアが最も高いノードを再生する必要があります。
明らかに、深さを5にハードコーディングするのではなく、パラメーターにし、これを実現するために（Wikiのように）再帰を使用します。深さを選択するには、実行にかかる時間を確認し、nを最大の深さに設定します。これにより、AIの応答が速くなります。ここで基本を構築したら、後で剪定戦略を追加して、明らかに正しい動きではない木の枝全体を評価しないことで、より深い深さを可能にすることができますが、これは私があなたのためにレイアウトした完全な基本的なネガマックスです。
幸運を祈ります、それはプログラムするのが楽しいものでなければなりません！
Onemancatは非常に徹底的な説明をします-+1。
あなたの質問に対する簡単な答えは、negamaxが特定の位置のスコアを返すということです。したがって、最初のプライですべての動きを再生し、結果の位置ごとにnegamaxを呼び出して評価し、最高のスコアの動きを選択します。結果として。