1

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

私は低レベルのマシンで実行していて、9 を超える深さを追加することができません。次のテスト ケースを使用してプログラムをチェックしましたが、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 内での効率を証明できるテスト ケースをいくつか提供してください。

4

1 に答える 1

0

あなたの質問は非常にオープンエンドですが、ここにいくつかのヒントがあります。

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

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

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

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

  5. 実際に最善の手が何であるかを知っている独自のテスト ケースを作成し、アルゴリズムがそれを見つけられることを確認します。たとえば、1 人のプレーヤーが 3 つの手で勝つことがわかっている終盤の状況などです。

于 2014-01-05T13:16:01.683 に答える