問題タブ [alpha-beta-pruning]

Python を使用してゲーム 2048 の AI を作成しています。思っていたよりずっと遅いです。深度制限を 5 に設定しましたが、回答を得るまでに数秒かかりました。最初は、すべての関数の実装がくだらないと思っていましたが、その本当の理由を突き止めました。検索ツリーには、本来あるべきよりもはるかに多くの葉があります。

典型的な結果は次のとおりです (葉、枝、および展開の数を数えました)。

もう1つは、適切な尺度です。

ご覧のとおり、単純なミニマックスを使用した場合よりもはるかに多くの葉が検索ツリーにあります。ここで何が起こっているのですか？私のアルゴリズムは以下に掲載されています：

誰か私を助けてください。このコードを何度も見直しましたが、何が問題なのか特定できません。

私はチェスの Minimax アルゴリズムを書いています。

アルファ ベータ枝刈りなしのミニマックスとアルファ ベータ枝刈りありのミニマックスでは、異なる最終結果値が得られます。

私の擬似コードは以下です。誰でも私を助けることができますか？

ミニマックス()

アルファベット()

Board はボードを表します。移動ごとに、渡された Board オブジェクトのコピーに対して移動を行い、この一時的な Board をさらに呼び出しに渡します。

evaluateBoard(Board b) は Board を受け取り、指定された Board シナリオに基づいてスコアを計算します。

私は現在、チェス用のアルファ ベータ プルーニングを使用したミニマックス アルゴリズムを作成しています。

私が見たすべての例から、ミニマックス アルゴリズムは、最良の動きから生じる最良のスコアまたはボードの状態を表す int 値を返します。

私の質問は、スコアの戻り値に関連付けられている最善の手をどのように返すことができるかということです。

たとえば、以下の疑似の私の alphabeta() ...

私の minimax / alphabeta の実装では、チェス盤を表す Board オブジェクトがあり、駒はその上を移動して、さまざまなボードのテクスチャ / ゲームの状態を表すことができます。

私の関数evaluateBoard(Board b)は Board を受け取り、パラメーター Board のボード状態の値を計算します。

基本的に、evaluateBoard() は、最善の手の値として、alphabeta() の最終的な int 結果値を提供します。ただし、evaluateBoard() が最終スコアの結果となった移動を返す方法がわかりません。スコア値と駒の情報を保持する Object を返すとしても、最終的に最高のスコアを与えたツリーの一番上にある駒の情報をどのように取得できるかわかりません。

最高のスコア値を与える最高の動きの情報にアクセス/返す方法を知っている人はいますか? ミニマックスアルゴリズムに重要な要素がありませんか、またはalphabeta()を別の方法で実装する必要がありますか?

編集：

たとえば、minimax が e4、e5、nf3、nc6 の動きから最高のスコアを返すとします。私が持っているものは盤面状況の数値を返します。「e4」を返すにはどうすればよいですか? E4 は最高値をもたらす手です。

ありがとう。

チェスのようなゲーム用に negamax アルゴリズムを作成しましたが、最終的なボード値の結果を使用する方法を知りたいです。ネガマックス アルゴリズムの最終リターンは、プレイヤーが最善の手を打った後のボードの値を表していることは理解していますが、それは正確には有用な情報ではありません。私はその動きが何であるかを知る必要があります。

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

bestValue が決定された後、現在の一致状態の子を再評価することを考えました。次に、それらを反復処理して、stateScore が bestValue に等しい子を見つけます。しかし、それらの多くはとにかく同じstateScoreを持つため、それは機能しません。それは、それらがどのカウントにつながるかです...

Connect Four タイプのゲームにコンピューター プレーヤーを実装しようとしています。これを達成するには、アルファ ベータ プルーニングが最善の方法のように思えましたが、何が間違っているのかわかりません。

以下は私が思いついたコードです。初期ルート状態から始まります。可能性のあるすべての有効な移動について (およびプルーニングが発生しない場合)、アルゴリズム: 状態のディープ コピーを作成し、状態を更新します (深さを増やし、ターンを切り替え、ピースを追加し、ヒューリスティックな値を設定します)、この新しい状態を後継者のルートのリスト。

新しい状態がリーフでない場合 (つまり、最大深度の場合)、再帰的に続行します。リーフの場合、アルゴリズムはルートの値と適切なローカル アルファ/ベータ値をチェックし、それに応じて更新します。考えられるすべての有効なオプションがチェックされた後、アルゴリズムは適切なローカル アルファ/ベータ値を返します。

少なくとも、それは私が意図したことです。すべての実行で値 0 が返されます。ここで要求されているのは、初期化コードです。

誰かが、アルファ ベータ プルーニング アルゴリズムの使用方法を理解するのを手伝ってくれませんか? コネクトフォーに似たゲームを作っています。唯一の違いは、斜めの勝利がないことと、プレイヤーはいつでもマスをマークできることです (もちろん、すでに占有されている場合を除きます)。アルゴリズムのコーディング方法は理解していると思いますが、使い方が間違っていると思います。私がやっていることは、このようなforループを持つことです

私が抱えている問題は、alphabeta の最初の実行が最大値を返すため、次の値はどれも大きくなく、ボードは単にボード [0] [0] に設定されることです。私が間違っていることを誰かが知っていますか？

これが動きを作る機能です

だからここに私の更新されたコードがありますが、まだ機能していません

アルゴリズムを少し変更して、最小値と最大値で何が起こっているかを明確に確認できるようにしましたが、それでも正しく再生されません