チェッカーでのアルファベータプルーニング（効率を証明するテストケース） - アルゴリズム、テストケース、アルファベータプルーニング

並列化されたチェッカー（英語ドラフト）マシンで実行できる最適な動きを見つけるためにアルファベータ剪定を使用するゲーム。ゲームツリーの深さ/レベルを増やし、アルファベータ剪定アルゴリズムを使用してそれを検索することで、必然的に最善の動きが得られるかどうか知りたいのですが？

私は低レベルのマシンで実行していますが、そうではありません次のテストケースを使用してプログラムをチェックしましたが、次のように1から9までの深さを考慮して、同じように移動できます。

case 1
+B+B+B+B
B+B+B+B+
+B+B+B+B
O+O+O+O+
+O+O+O+O
A+A+A+A+
+A+A+A+A
A+A+A+A+           output: (5, 0) => (4, 1)

case 2
+B+B+B+B
O+O+B+B+
+O+O+B+B
O+B+O+O+
+O+O+O+O
A+A+A+O+
+O+O+O+O
O+O+O+O+           output: (5, 2) => (4, 3)

case 3
+O+O+O+O
O+O+O+O+
+B+O+O+O
O+O+O+O+
+B+B+O+O
O+A+A+O+
+O+O+O+O
O+O+A+A+           output: (5, 2) => (3, 4)

case 4
+k+O+O+O
O+B+O+O+
+O+O+O+B
O+O+O+B+
+O+O+B+O
O+O+O+O+
+O+O+O+O
A+A+A+A+           output: (0, 1) => (2, 3)

case 5
+B+B+B+B
O+O+O+O+
+O+O+O+O
O+O+O+O+
+B+B+K+O
O+A+O+O+
+O+O+O+O
A+A+O+A+           output: (5, 2) => (3, 0)

case 6
+k+O+O+O
B+O+O+O+
+O+O+O+O
O+O+O+O+
+O+O+O+O
O+O+O+O+
+O+O+O+O
O+O+O+O+           output: (0, 1) => (1, 2)

解釈がどこにあるか、

O- Empty dark square
+- Empty white square
A- Machine"s pawn
B- Opponent"s pawn
k- Machine"s king
K- Opponent"s king

のヒューリスティック値を計算しましたボードに残っているマシンの駒の数からプレーヤーの対戦相手の駒の数を差し引いた、ゲームツリーのリーフノード適用されました。

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

回答：

あなたの質問はかなり自由回答ですが、ここにいくつかのヒントがあります。

1. リーフノードに対して計算されたヒューリスティック値リーフノードであるため、検索深度に依存しません。したがって、「リーフノードに対して計算された値...変更されなかった」というコメントはあまり意味がありません。おそらく、ルートノードの値が変更されなかったということです。

2. 通常、検索深度を大きくすると、動きがよくなります。すべての検索深度1..9で同じ「最良の」動きが得られる場合は、どこかにバグがあります。

3. 評価関数が最も重要ですアルファベータ検索ソリューションの一部。特に深い検索ができない場合は、単純な方法で材料を数えるだけの関数よりも優れた評価関数が必要です。

4. 通常、人々はプレーンアルファベータを使用しませんが、アルゴリズムの実用的な効率を高めるために、主変分検索、反復深化、ヌル移動ヒューリスティックなどを使用します。

5. あなたが何を知っているあなた自身のテストケースを構築します最善の方法は実際にあり、アルゴリズムがそれを見つけられることを確認します。たとえば、1人のプレーヤーが3つの手で勝利できることがわかっているゲーム終了の状況です。