問題タブ [alpha-beta-pruning]

そこで、チェス ベースのパズル ゲームにミニマックス検索を実装しました。この場合、検索によって AI ピースの次の動きが決まります。

ミニマックス自体は正常に動作し、予想される動きを返しますが、アルファベータ剪定を実装すると、ミニマックスは各ターンごとに同じ 2 つの値を返します。たとえば、現在 (0,0) にある AI Rook は、ミニマックスから移動すると (1,0) を受け取り、次にミニマックスに移動を要求すると (0,0) を受け取ります。このループは、評価関数で何を変更しても発生します。

ゲームの状態は、ユーザーの位置、駒の位置、およびボード自体を表すタイルの配列で構成されます。ここでは、評価関数によって与えられたそれぞれの値で各タイルを格納するために、独自のノード クラス (実際にはペアと呼ばれる必要があります) を使用します。

アルファ ベータ プルーニングの実装方法に問題はありますか? どんなアドバイスでも大歓迎です。さらに情報が必要な場合は、お問い合わせください。できる限りの情報を提供します。

アルファ/ベータ プルーニングを使用して MiniMax アルゴリズムを実装しようとしています。完全に立ち往生していて、どこが間違っているのかわかりません。クラス MiniMax には State と Action が含まれています。メソッド getAction は Action を返します (おそらく実行するのに最適なアクションです)。Game オブジェクトには 2 つのメソッドがあります。isTerminal は、状態が「終了状態」の場合、つまり、その状態の子がこれ以上ない場合に true を返します。getUtility は、終了状態に関連付けられた値を返します。

カウンターラウンドを使って最大ターンか最小ターンかを決めようとしています。現在、アルゴリズムは正しいアクションを返しません。この段階では、展開の順序を正しくして、プルーニング ビットを機能させることに集中しています。

}

転置テーブルで強化されたアルファベータ最小最大プルーニングを実装しようとしています。この疑似コードを参照として使用します。

http://people.csail.mit.edu/plaat/mtdf.html#abmem

このアルゴリズムに対する 3 つの質問:

1. 保存された各転置テーブル エントリに深さ (= リーフ レベルまでの距離) を格納し、entry.depth>=currentDepth (= エントリがリーフ レベルからほぼ等しい) の場合にのみエントリを使用する必要があると思います。それは上記の疑似コードには示されておらず、そこでは議論されていません。それを正しく理解していることを確認したかったのです。

2. 各ポジションのベストムーブを保存して、ムーブオーダーに使用し、検索が停止した後にベストムーブを抽出したいと考えています。純粋な最小値と最大値では、どちらの動きが最適かは明らかですが、アルファ ベータ カットオフで反復する場合、どの動きが最適でしょうか? 特定の位置での最良の動きは、ループが終了したときに見つかった最良の動きであると仮定できますか (カットオフの有無にかかわらず)?

3. このアルゴリズムを反復深化スキームで実行する場合、各深さが増加する前に転置テーブルをクリアする必要がありますか? 前回の反復から保存された位置を使用したいと思いますが、情報がより深い検索に適しているかどうかはわかりません (テーブル エントリの深さを確認するときである必要があります)。

置換テーブルを追加してから MTD(f) をチェスの純粋なアルファ ベータ プルーニングに追加すると、期待されるパフォーマンスの向上はどのくらいですか?

私のピュア アルファ ベータ プルーニングでは、次の移動順序を使用します。

• 主変動 (以前の反復深化反復から)
• 転置表からの最良の移動 (存在する場合)
• キャプチャ: 最高のキャプチャ、次に最低のキャプチャ
• キラームーブ
• 履歴ヒューリスティック

上記の設定で、深さ 9 の平均結果は次のようになります。

• ピュア アルファ ベータ: X ノードを訪問
• alpha beta+TT: 0.5*X ノードを訪問
• MTDF(f): 0.25*X ノードを訪問

私はより良い結果を期待していましたが、それが得られるのと同じくらい良いかどうか、または実装に問題があるかどうかを確認したかったのですか?

0.1 ポーンの精度で検索します。

私は自分のチェス ゲームにアルファ ベータ アルゴリズムを実装しましたが、最終的にかなりばかげた動きをするのに多くの時間 (4 プライの場合は数分) がかかります。

私は2日間間違いを見つけようとしてきました（間違いを犯したと思います）。私のコードに外部からの入力をいただければ幸いです。

getMove 関数: ルート ノードに対して呼び出され、すべての子ノード (可能な移動) に対して alphaBeta 関数を呼び出し、最高スコアの移動を選択します。

alphaBeta 関数:

編集：evaluateBoardはピースの可動性のみを評価することに注意してください（可能な移動の数、キャプチャされたピースに応じてキャプチャの移動はより高いスコアを取得します）

ありがとうございました。

私は、ミニマックス アルゴリズムを、アルファ ベータ プルーニングを使用したコネクト フォー ゲームでどのように使用できるかを調べています。

そこで、Connect4 プレーヤー戦略に関するソース コードを調べていたところ、次の評価関数が見つかりました。

このコードはすべてこの PDF で見つかりました: http://ryanmaguiremusic.com/media_files/pdf/ConnectFourSource.pdf

この評価関数がどのように機能し、行うべき最善の動きを決定するかを理解したいだけです...誰か助けてもらえますか? それは大歓迎です。