3

ウィキペディアでアルファ ベータ プルーニング用に見つけたこの疑似コードを理解するのに苦労しています。

function alphabeta(node, depth, α, β, Player)         
    if  depth = 0 or node is a terminal node
        return the heuristic value of node
    if  Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break (* Beta cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break (* Alpha cut-off *)
        return β

私を混乱させているのはifPlayer = MaxPlayer条件です。not(Player)で関数を再帰的に呼び出して最小値を取得する全体を理解しています。次に、で関数を再帰的に呼び出しPlayer、深さの制限に達するか、目標の状態が見つかるまで繰り返します。しかし、私は理解していません

if β ≤ α
    break

声明。それについての私の理解は、前の呼び出しで見つかった最小値 ( β) よりも高い 2 番目の値が見つかったということです。これが使用される値です。しかし、これは関数の MAX 部分なので、ベータよりも大きい任意の値ではなく、HIGHEST 値が必要ではないでしょうか?

4

1 に答える 1

7

これは、MaxPlayer句のアルゴリズムのトリミング フェーズです (このノードでプレーヤーの最大値を確認する場合):

ベータは、「トリミング係数」である関数のパラメーターです。これまでに見つけた最小スコアを表します。これは、最小化ノードである現在のノードの親が、ベータ版の解を既に見つけていることを意味します。

ここで、すべての子を反復し続けると、少なくとも現在のアルファと同じくらい良いものが得られます。最小化ノードである親ノードは、このbeta <= alphaアルファ (またはそれより大きい値) を決して選択しないため、ベータ以下の値を選択し、現在のノードはそのような値を見つける機会がないため、次のことができます。計算をトリムします。

例：

     MIN
    /   \
   /     \
  /       \
 /         \
5          MAX
          / | \
         /  |  \
        /   |   \
       6    8    4

MAX ノードを評価するとき、通常の min-max アルゴリズムを適用すると、8 が返されます。ただし、MIN 関数が実行することはわかっていますmin(5, MAX(6, 8, 4))。6 を読み取った後に がわかっているmax(6, 8, 4) >= 6ので、上位レベルの MIN 計算が になるため、計算を続行せずに 6 を返すことができますmin(5, MAX(6, 8, 4)) = min(5, 6) = 5。

これは 1 つのレベルの直感です。もちろん、同じ考えですべてのレベルに "流れる" ように再帰的に行われます。

MIN 頂点のトリミング条件についても同じ考えが成り立ちます。

于 2012-10-20T17:37:13.913 に答える