Изменить минимакс на псевдо-код обрезания альфа-бета

Question

Я изучаю псевдо-код Alpha-Beta, и я хочу написать простейший псевдокод для Alpha Beta обрезка.

Я написал псевдокод для Минимакс:

function minimax(node, depth) 
    if node is a terminal node or depth ==0 
      return the heuristic value of node 
    else 
      best = -99999 
    for child in node 
      best = max(best, -minimax(child, depth-1)) 
    return best 

Однако, я не знаю, как изменить его в альфа-бета обрезку. Может ли кто-нибудь помочь?

Answer 1

В Alpha-Beta вы отслеживаете свой гарантированный результат на одну позицию. Вы можете немедленно остановиться, если нашли ход, который лучше, чем оценка, которую оппонент уже гарантировал в своей предыдущей позиции (за один шаг до этого).

Технически каждая сторона отслеживает свой нижний балл (альфа), и у вас есть доступ к нижнему счету противника (бета).

Следующая псевдо-код не тестировался, но вот идея:

function alphabeta(node, depth, alpha, beta) 
    if node is a terminal node or depth ==0 
      return the heuristic value of node 
    else 
      best = -99999 
    for child in node 
      best = max(best, -alphabeta(child, depth-1, -beta, -alpha)) 
      if best >= beta 
       return best 
      if best > alpha 
       alpha = best 
    return best 

В начале поиска, вы можете установить альфа до минус бесконечностью и бета до + INFINITY. Строго говоря, набросанный алгоритм не является альфа-бета, а Negamax. Оба они идентичны, так что это всего лишь деталь реализации.

Обратите внимание, что в Alpha-Beta порядок перемещения имеет решающее значение. Если большую часть времени вы начинаете с наилучшего движения или, по крайней мере, очень хорошего хода, вы должны увидеть огромное улучшение по сравнению с Minimax.

Дополнительная оптимизация для запуска с закрытыми альфа-бета-версиями (не -INFINITY и + INFINITY). Однако, если ваше предположение окажется неправильным, вам необходимо перезапустить поиск с более открытым search window.