Главная » Алгоритмы, Игры » Alpha-beta с амортизацией отказов

0

Мы рассмотрели alpha-beta алгоритм. Он всегда возвращает значение из alpha-beta диапазона. Если мы, например, вызвали функцию поиска из кор­ня дерева с параметрами alpha = — 1, beta = 1, то, каким бы ни был истин­ный результат, наша функция вернет значение из заданного промежутка alpha и beta. Можно модернизировать функцию таким образом, чтобы воз­вращаемое значение не ограничивалось этим промежутком. Представим, что мы в некоторой точке дерева. Функция перебрала все перемещения, но так и не смогла улучшить alpha. В таком случае можно вернуть не alpha, а мак­симальное полученное значение для этого узла. Это никоим образом не скажется на конечном результате. Точность просчета будет такой же. Alpha- beta перебор с возвратом максимального полученного результата каждой функции называется alpha-beta с амортизацией отказов. Приведем его код:

int AlphaBeta(int color, int Depth, int alpha, int beta) {

if(Depth == 0) return Evaluate(color);

int score = -INFINITY;

PMove move = GenerateAllMoves(color);

while(move) (

MakeMove(move);

int tmp = -AlphaBeta(color==WHITE?BLACK:WHITE, Depth-1, -beta, -alpha);

UnMakeMove(move); if(tmp > score) score = tmp; if(score > alpha) alpha = score; if(alpha >= beta) return alpha; move = move->next;

}

return score;

}

В практических реализациях используется, как правило, эта схема. Скорость работы обоих вариантов alpha-beta примерно одинакова. В шахматах мы,

например, можем легко определить пат с заданной схемой. Если мы видим, что сгенерированы только перемещения короля, а по максимальной оценке видно, что он бьется на следующем полуходе, то вместо полученной оценки функция должна возвратить ноль — ничья. Вариант alpha-beta с амортиза­цией отказов используется также в некоторых алгоритмах, например, NegaScout.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии