問題タブ [negamax]

私は Java でチェス ゲームを作成しており、AI プレーヤー用に Negamax を正常に実装できたと思います。アルゴリズムを改善するためにこれにアルファベータプルーニングを追加するのに問題があります。次のチュートリアルとサンプル コードを試してみましたが、どのように機能するのか理解できません。

以下は、現在最善の動きを得るために必要なコードです。

そして、これが私の（作業中の）negamaxメソッドにaplha-betaプルーニングを追加する試みです：

そして最後に、コンソールがどのように見えるか

どんな助けでも大歓迎です。前もって感謝します。

LISP を使用してアルファ ベータ プルーニングを使用する negamax アルゴリズムを使用する AI を使用して、単純な CLI tic-tac-toe ゲームを作成していますが、AI がどのように動くかについて問題があります。本来あるべき 1 つの動きをする代わりに、ゲームを完全にプレイしているので、ゲームは 2 つの動きしか続きません。私はそれを（ステップ）実行しましたが、問題は、そのブロックが実行されていないと言われている場合でも、negamax 関数の (when (> value bestValue)) ブロックに bestPath 変数が設定されていることです。また、設定される値は、設定するのが適切である場合に正しい値ではありません。助言がありますか？これが私のコードです。

AI のコードは次のとおりです。

注: この投稿にコード、結果、その他の情報が不足していると思われる場合は、コメントしてください。それに応じて投稿を編集します。

注 2: このプログラムは自分で手で書きました。

私はnegamaxの実装を持っていますが、その結果は私には非常に間違っているように見えました。デバッグする多くの方法を試しましたが、まだ核心をつかむことができないようです.

まず、これは 3X3 のボードを持つ Tic Tac Toe のネガマックス実装です。

次のコードは、このアルゴリズムで発生したエラーを再現するための完全なセットです。何か見逃した場合は、以下にコメントしてください。

例では、このメインを実行できます。

これはコンピューター (完全なプレーヤー) 対コンピューター (完全なプレーヤー) であるため、ゲームは引き分けで終了すると予想されますが、次の一連の関数を使用すると、次のようなゲームが終了しました。

現在の最大移動数: 0,0、現在のスコア: -inf 現在の最大移動数: 0,2、現在のスコア: 3 現在の最大移動数: 0,1、現在のスコア: -3 現在の最大移動数: 1 ,1、現在のスコア: 3 現在の最大移動数: 2,0、現在のスコア: -3 現在の最大移動数: 1,2、現在のスコア: 3 現在の最大移動数: 2,1、現在のスコア: -3 現在の最大手数: 1,0、現在のスコア: 3 現在の最大手数: 1,0、現在のスコア: -3

XXO
XOO
XX ---

「 - 」は、そのセルで移動が行われないことを意味しますが、これは明らかに間違っているように見えます。

最初にミニマックスを実装しましたが、このネガマックスはミニマックスの実装に基づいて進化していたため、エラーが表示されない可能性があります。

ミニマックスは 2 人のプレイヤーの視点から動き、スコアも同様に評価するのに対し、ネガマックスは 2 人のプレイヤーの視点から動きますが、現在のプレイヤーの視点からのみスコアを評価します。

これが私を混乱させたビットだと思います。ここで私の実装がどのようにうまくいかなかったのかわかりません。

メインの次の関数でゲームを開始します。

これがboard.hppです：

ここにリストされているいくつかの重要な要素:

印刷:

生成する移動:

applyMovesNega:

isGameComplete:

スコアを評価します。

削除移動:

これが move.hpp です。

これが実際の NegaMax 関数です。

次の関数を使用してゲームの状態を評価します。

ネガマックスでコネクトフォーをプレイしています。私が気付いたのは、アルファベータを追加すると、「間違った」結果が得られることがあるということです。アルファベータを削除すると、想定どおりに再生されます。アルファ-ベータは、実際に実行可能なブランチをいくつか切り取ることができますか (特に深さが制限されている場合)? 念のためのコードは次のとおりです。

編集: 誰かが私の質問の重複として TicTacToe をリンクしている理由がわかりません。その中に MinMax-Algorithm さえありません。

現在、MinMax-Algorithm を使用する必要があるコンピューターに対して Connect4 ゲームに取り組んでいます。その前に、MinMax も使用する TicTacToe を作成しましたが、Connect4-Game に一致するように古いアルゴリズムを変更する方法がわかりません :/. TicTacToe では、私が書いた勝利条件で考えられる各動きを評価しました。うまくいきましたが、新しい条件ではうまくいきません。私のmakeAMoveなどはうまくいきます！

これらは私の古い条件と TicTacToe の MinMax です。

//プレイヤー1の勝ち

}

// プレイヤー 2 の勝利

}

私が言ったように、私は次のように MinMax にこれらの条件を使用しました:

...

これを新しい条件で機能させる方法がわかりません：

たとえば、これをチェックする評価関数を作成する必要があると思います（これは行の勝利条件です）：

私はそれがたくさんのテキストであることを知っていますが、誰かが私にいくつかの役に立つヒントを教えてくれるかもしれません:)

ありがとう！

マックス

無敵の AI を使用して Tic-Tac-Toe ゲームを開発しようとしていますが、ほとんどの場合、negamax 関数が正しい出力を返すようになっています。ただし、予測可能な特定の条件下では、コンピューターが意味をなさないボードの動きを選択し、ユーザーの勝利をブロックできない場合があります。

私が行った調査に基づいて、negamax アルゴリズム自体は問題ないようです。評価関数に何か問題があるのではないかと心配しています。言い換えれば、ヒューリスティック値が計算される方法です。私のエネルギーのほとんどはネガマックスに取り組むことに向けられていたので、他の機能はほとんど後付けでした.

以下は、私が説明していることのほんの一例です。

このシナリオに直面した場合、正方形 1 (上部中央: 配列のインデックスはゼロ) を選択してユーザーが勝利を収めるのをブロックするのではなく、negamax 関数は 5 を出力します。これは、どちらのプレーヤーにもすぐには使用されない正方形です。ただし、テストでは、引数として userNum を使用して同じシナリオで negamax を呼び出すと、negamax はその仕事を行い、ユーザーの勝利の正方形 1 を見つけます。

一見シンプルなものが欠けていることはわかっています。それは、userNum と compNum を設定した方法と、それらがハードコードされている方法に関連していると感じています。Minimax のアイデアをネガマックスに変換することに失敗した可能性があります。つまり、ユーザーとコンピューターの両方の価値を最大化していない可能性があります。または、間違ったプレイヤーの視点から最大化を行っている可能性があります。誰かが親切に正しい方向へのプッシュを提供してくれたら、私は感謝します.

完全な動作バージョンとテストは、https ://repl.it/CnGD/4 で入手できます。

圧倒的な量をここに投稿したくはありませんが、リクエストがあれば、このサイトでスニペットを作成できます。

ネガマックス関数

評価関数

JavaでNine Men's MorrisというゲームのNegamax検索を実装しようとしています。

プレーヤーが 3 つの駒を続けて持っている場合 (ここではミルと呼ばれます)、ターンを切り替える前に相手の駒を取り除きます (「追加の」移動)。

さらに、すべての最初の駒が配置された後、セット ピースフェーズとムーブ ピースフェーズがあります。

私の実装は次のようになります。

基本的なネガマックス アルゴリズムを変更せず、石の設定と石の移動を 1 つの操作でカプセル化して、アルゴリズム自体で 2 つを区別しないようにすることをお勧めしますが、私の理解では、それでもこのように機能するはずです。

関数 negamaxRemove は、基本的には negamaxSet と同じですが、ミル (不可能) をチェックせず、削除する部分を探しません。

呼び出し元の関数と同じパラメーターを使用して negamaxRemove を呼び出し、符号を切り替えない (それによって再び最大化する) のは正しいですか?

どういうわけか、AI プレイヤーは対戦相手がミルを形成するのを妨げません (ただし、可能であれば自分でミルを形成します)。

アルゴリズムはこのように正しいのでしょうか?コードの他の場所でエラーを探す必要がありますか? それとも、ネガマックスの仕組みを誤解したのでしょうか? (alpha-beta pruning をコメントアウトしたので、alpha または beta を間違って設定しても、ここでは違いはありません)

いくつかの指針を本当に感謝します！

プレーヤーが実行中の合計に 1 つまたは 2 つ追加する単純なゲームにネガマックスを実装しようとしています。合計を21に増やしたプレーヤーが勝ちです。

ここで疑似コードを使用しています: https://en.wikipedia.org/wiki/Negamax#Negamax_base_algorithm

人間のプレイヤーが最初に動くので、合計が 0 mod 3 に一致する数を追加することで、コンピューターが簡単に勝つはずです。

私は動的な動きの生成を行っていません。現在の合計に 1 を追加する場合の negamax スコアと、現在の合計に 2 を追加する場合の negamax スコアを比較するだけです。

ネガマックス関数:

最大方法:

AI が毎回 2 を追加する理由がわかりません。