Понимание условия отсечки в алгоритме сокращения альфа-бета

У меня проблемы с пониманием этого псевдокода, который я нашел для альфа-бета-обрезки в Википедии:

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 β

Меня смущает условие if Player = MaxPlayer. Я понимаю весь рекурсивный вызов функции с not(Player) для получения минимального значения, которое затем будет рекурсивно вызывать функцию с Player, повторяя до тех пор, пока не будет достигнут предел глубины или не будет найдено целевое состояние. Однако я не понимаю,

if β ≤ α
    break

утверждение. Насколько я понимаю, найдено второе значение, превышающее минимальное значение, найденное в предыдущем вызове (β), то есть используемое значение. Но поскольку это МАКСИМАЛЬНАЯ часть функции, разве нам не нужно НАИБОЛЕЕ ВЫСОКОЕ значение, а не просто ЛЮБОЕ значение, превышающее бета?


search artificial-intelligence algorithm alpha-beta-pruning
person user1427661    schedule 20.10.2012    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Это фаза обрезки алгоритма в предложении MaxPlayer (при проверке максимального значения для игрока в этом узле):

Бета — это параметр функции, который является «коэффициентом обрезки». Он представляет собой минимальный балл, который вы нашли на данный момент. Это означает, что родитель текущего узла, который является минимизирующим узлом, уже нашел решение, которое является бета-версией.

Теперь, если мы продолжим перебирать все дочерние элементы, мы получим что-то не хуже текущей альфы. Так как beta <= alpha — родительский узел — который минимизирует узел — НИКОГДА не выберет эту альфу (или любое значение, превышающее его) — он выберет значение, которое является бета или ниже — и у текущего узла нет шансов найти такое, поэтому мы можно сократить расчет.

Пример:

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

При оценке узла MAX мы вернем 8, если применим обычный алгоритм min-max. Однако мы знаем, что функция MIN будет выполнять min(5, MAX(6, 8, 4)). Поскольку после считывания 6 мы знаем max(6, 8, 4) >= 6, мы можем вернуть 6 без продолжения вычислений, потому что МИН. вычисление верхнего уровня будет min(5, MAX(6, 8, 4)) = min(5, 6) = 5.

Это интуиция для одного уровня, это, конечно, делается рекурсивно, чтобы «перетекать» на все уровни с одной и той же идеей.

Та же идея справедлива для условия обрезки в вершине MIN.

person amit    schedule 20.10.2012
comment
Возможно, моя путаница заключается в значениях инициализации. Альфа и бета инициализируются пустыми или они инициализируются соответственно -бесконечностью и бесконечностью? - person user1427661; 20.10.2012
comment
@ user1427661: Да, они инициализируются до бесконечности и -бесконечности и модифицируются во время рекурсивных вызовов. - person amit; 21.10.2012