問題タブ [alpha-beta-pruning]

ゲームチェッカー用にアルファベータプルーニングを使用してミニマックスアルゴリズムを作成しましたが、現在、ネガマックスアプローチを使用してそれを書き直そうとしています。negamax はミニマックスを記述するための単なる手法であるため、2 つが同等であると期待しています。しかし、何らかの理由で、2 つのアルゴリズムの動作が異なります。両方を同じ入力で実行すると、negamax バージョンの方がより多くの状態を評価するように見えるので、アルファ ベータの剪定に何か問題があるに違いないと思います。

以下のコードは両方のアルゴリズム (minimaxとnegamax関数) を示しており、一番下playにはそれらを呼び出す関数が示されています。evaluate関数は、両方のアルゴリズムで状態を評価するために使用する基本的なヒューリスティックです。

エラーを見つけるための助けは非常に高く評価されます。

チェスゲームの AI を作っています。

これまでのところ、Alpha-Beta Pruning Minimax アルゴリズムの実装に成功しました。これは次のようになります (ウィキペディアから)。

これには時間がかかりすぎるため (すべてのツリーを 1 つずつ調べていく)、「履歴ヒューリスティック」と呼ばれるものに出会いました。

元の論文のアルゴリズム:

したがって、基本的には、以前の「移動」のハッシュテーブルまたは辞書を追跡するという考え方です。

ここで、この「移動」が何を意味するのか混乱しています。それが文字通り単一の動きを指しているのか、それとも各動きの後の全体的な状態を指しているのかはわかりません.

たとえば、チェスでは、このハッシュテーブルの「鍵」は何であるべきでしょうか?

1. 個々の動きは (Queen to position (0,1)) or (Knight to position (5,5))?

2. それとも、個々の動きの後のチェス盤の全体的な状態ですか?

1 の場合、履歴テーブルに「移動」を記録するときに、他のピースの位置が考慮されていないと思いますか?

Connect Four ゲームのアルファ ベータ プルーニングのコードに取り組んでいますが、うまくいかないようです。最初は正しく実装したと思っていましたが、アルゴリズムは毎回列 1 を返します。2 つintの val があり、nodeValそれを使用してアルファ値とベータ値を決定します。アルゴリズム内でそれらを 0 としてインスタンス化するとalphaBetaPruning()、メソッドによって返される列alphaBetaSearch()は常に 1 になります。これらの値をアルゴリズム外でインスタンス化するalphaBetaPruning()と、alphaBetaSearch()アルゴリズムの結果はNull Pointer Exception

.

注:ConnectFourBoardクラスはボード状態の最良の子を保持します。

どんな助けでも大歓迎です！

私は 4x4 tic-tac-toe ゲームで小さなプロジェクトを行っています。次善の策を見つけるために Alpha Beta Search を使用しています。アルファベータ検索では、以下のアルゴリズムの「ユーティリティ」関数で呼び出されているカットオフ評価関数を使用しています

すべてを正常に実装しましたが、問題はユーティリティ関数が負の値を返さないことであり、その理由が本当にわかりません! 以下は機能です

isMinMinValue 関数から呼び出されると、true に設定されます

isMinは O の動きで、AI の動きは X です。O が勝った場合、ユーティリティは -50 を返すことになっています。しかし、それは 0 だけを返します。プログラムをデバッグしたところ、実際には -50 が割り当てられますnodeValue(nodeValueデバッガーで -50 に変更されます) が、Min 関数または Max 関数で受け取るとゼロになります。

注: プロジェクト全体で使用されるすべての int はsigned int. unsigned関数呼び出し元が署名されていないと考えている場合は、キーワードは使用されません

アルファベータ検索の完全なコードはこちら: http://pastie.org/8538015

友達、できるだけ早く助けてください。

Cでチェッカーの最適なゲームを実装しようとしています.

マシンが実行できるチェッカー ボードの最適な動きを見つけるために、現在のチェッカー ボードの状態に基づいて、C の (GLib) を使用して深さを固定してn-ary ゲーム ツリーを生成しました。

そして、ゲーム ツリーに存在するすべてのリーフ ノードについてヒューリスティック値が計算されます。これは、ボードに残っているマシンのピースの数からプレイヤーの対戦相手のピースの数を差し引いたものとして定義されます。これは、キングがポーンよりも強力な能力を持っているためです。各キングは 2 つの通常のポーンとして使用され、アルファ ベータ検索が適用されます。

ゲーム ツリーの深さを増やすと、最終的に最適化された動きが生成される可能性が高くなります。深さを増やそうとすると、ツリーの生成とヒューリスティック検索に時間がかかります。

私の考えは、ツリーの最初のレベルを個別に生成し、MPI を使用してさらに実行するために、使用可能なプロセッサ間で子ノードを分散することですか?

出来ますか？はいの場合、MPI を使用してツリー生成とヒューリスティック検索を並列化するにはどうすればよいですか?

また、効率的でない場合は、それを実装する方法について他の方法を提案してください。ありがとう。

マシンが実行できる最適な動きを見つけるために、アルファ ベータ プルーニングを使用して、並列化されたチェッカー (英語のドラフト) ゲームを開発しました。ゲーム ツリーの深さ/レベルを増やし、アルファ ベータ プルーニング アルゴリズムを使用してそれを検索することが、必ずしも可能な限り最良の動きを進化させるかどうかを知りたいですか?

私は低レベルのマシンで実行していて、9 を超える深さを追加することができません。次のテスト ケースを使用してプログラムをチェックしましたが、1 から 9 までの深さを考慮して、同じ可能な動きを得ています。次のように。

解釈がどこにあるか、

キングはポーンよりも強力な能力を持っているため、ボードに残っている機械のピースの数から対戦相手のピースの数を差し引いて、ゲーム ツリーのリーフ ノードのヒューリスティック値を計算しました。どのアルファ ベータ検索が適用されるかを使用します。

私のプログラムは正常に動作すると思いますが、深さを 9 まで増やしても、ゲーム ツリーのリーフ ノードに対して計算されたヒューリスティック値は最終的に変化しませんでした (さらに深さを増やせば変化する可能性があります)。深さ 9 内での効率を証明できるテスト ケースをいくつか提供してください。

アルファベータ剪定を使用して、三目並べのミニマックス アルゴリズムを実装しようとしています。現在、プログラムを実行していますが、機能していないようです。実行するたびに、すべてのマスにゴミが入力されているようです。ミニマックス関数がボードの状態を取り、その状態を変更して、終了時にボードの状態に次善の動きが含まれるように実装しました。次に、「this」を変更されたボードと等しくなるように設定します。ミニマックスアルゴリズムの私の関数は次のとおりです。

そして、誰かがそれを実行したい場合は、ここに私の完全なファイルがあります:

.cpp : http://pastebin.com/ydG7RFRX .h : http://pastebin.com/94mDdy7x