Как выбрать узел с помощью Alpha Beta

Question

Я реализую AI для игры Othello, используя MiniMax с обрезкой Alpha Beta. Я реализовал алгоритм Alpha Beta, который сообщает мне значение, которое я могу получить, но не тот узел, который я должен выбрать? Поэтому мой вопрос заключается в том, как я могу использовать Alpha-Beta, чтобы указать мне, какой узел я должен выбрать, а не то, что получилось бы в результате. Вот псевдокод для моего алгоритма Alpha-Beta.

01 function alphabeta(node, depth, α, β, maximizingPlayer) 
02  if depth = 0 or node is a terminal node 
03   return the heuristic value of node 
04  if maximizingPlayer 
05   v := -∞ 
06   for each child of node 
07    v := max(v, alphabeta(child, depth – 1, α, β, FALSE)) 
08    α := max(α, v) 
09    if β ≤ α 
10     break (* β cut-off *) 
11   return v 
12  else 
13   v := ∞ 
14   for each child of node 
15    v := min(v, alphabeta(child, depth – 1, α, β, TRUE)) 
16    β := min(β, v) 
17    if β ≤ α 
18     break (* α cut-off *) 
19   return v 

Answer 1

Если вы хотите знать, лучший ход в корневой позиции, достаточно вспомнить, которые перемещаются в корневой позиции имели самый высокий балл. Для этого достаточно просто вернуть счет. Никаких изменений в псевдокоде не требуется.

Как вы спрашиваете о пути к критическому узлу, я думаю, вы спрашиваете о способе восстановления principal variation, который дает представление о серии ходов, ожидаемых поиском.

В теории вы можете просто вернуть значение и главный вариант из рекурсивного вызова. Это позволяет вам восстановить путь. Triangular PV-Tables - это структуры данных, оптимизированные для этой цели.

Если ваш поиск использует transposition table, более простой подход - это просто начать корневую позицию и найти лучший ход в таблице транспонирования. Затем сделайте это движение и повторите (найдите лучший ход, сделайте лучший ход, найдите еще раз и т. Д.), Пока игра не закончится или запись не будет найдена. В конце концов, ходы, которые были сделаны, являются главной вариацией.

Подход таблиц транспозиции не так точен, как явное отслеживание основного варианта, но его просто реализовать и не добавлять накладные расходы во время поиска.