1

アルファベータアルゴリズムでノードの子をランダムに選択すると、順番に選択するよりもカットオフを取得する可能性が高くなりますか?

*** でマークされた追加の疑似コードを次に示します。

function alphabeta(node, depth, α, β, maximizingPlayer)
     if depth = 0 or node is a terminal node
         return the heuristic value of node
     arrange childs of node randomly ***
     if maximizingPlayer
         v := -∞
         for each child of node
             v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
             α := max(α, v)
             if β ≤ α
                 break (* β cut-off*)
         return v
     else
         v := ∞
         for each child of node
             v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
             β := min(β, v)
             if β ≤ α
                 break (* α cut-off*)
         return v

コネクト フォー ゲームでこれを使用して小さなサンプルを実行したところ、少し速く実行されたように見えますが、実際にランダム性の有無にかかわらずカットオフをカウントすると、ランダム性のないカットオフの方が多くなります。それは少し奇妙です。

それが速い（または遅い）ことを証明することは可能ですか？

4

1 に答える 1

1

アルファベータアルゴリズムでノードの子をランダムに選択すると、順番に選択するよりもカットオフを取得する可能性が高くなりますか?

場合によります。明示的にランダム化されていない場合、子供はどのような順序になりますか?

最良のカットオフ (最高量のアルファ ベータ プルーニング) は、ムーブ リストが既にスコア順に並べられている場合に発生します。つまり、最良のムーブが最初に発生し、次に 2 番目に優れたムーブが続きます。

もちろん、最善の手が何かをすでに知っていれば、そもそもそれを探す必要はありません。

そのため、多くのゲーム エンジンは、特定の位置の以前の評価をキャッシュし、以前のスコアに基づいて移動テーブルを並べ替えます (位置が以前に評価されていると仮定します)。このようなキャッシュされたスコアは通常、事象の地平線が遠く離れているため正確ではなくなりますが、それらを使用することは検索の優れたガイドラインとして役立ちます。

于 2016-04-30T12:44:21.710 に答える