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

Question

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

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 β

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

if β ≤ α
    break 

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

Answer 1

Это фаза обрезки алгоритма, в 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 верхнего уровня будет min(5, MAX(6, 8, 4)) = min(5, 6) = 5,

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

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