Дерево ходов и Альфа-бета отсечение
Альфа-бета отсечение это оптимизация алгоритма обхода дерева ходов, основанное на знании текущих лучших результатов полученных на предыдущих уровнях дерева.Дерево ходов
Идея обхода проста мы смотрим, какие есть ходы из текущей ситуации. Затем для каждого своего хода смотрим, как на него может ответить соперник, для каждого возможного хода соперника смотрим, как мы можем ответить и т.д. Человек обычно неспособен рассмотреть дерево всех возможных ходов даже на глубину три. Но отдельные варианты развития событий он может продумать на 10 и более ходов. Отсечение "мало перспективных с первого взгляда" вариантов и другие эвристические идеи оптимизации просмотра дерева ходов рассматриваются в AlphaBetaOptimisationHeurictics?. Идея альфа-бета отсечения является оптимизацией просмотра дерева ходов без потери качества.
![]() |
- Score(position, 0) = HeuriscticScore?(position)
- Score(position, depth) = MAX { (Score(p, depth-1) }, если d нечётное;
- Score(position, depth) = MIN { (Score(p, depth-1) }, если d чётное;
- где p пробегает все возможные позиции, в которые можно попасть из позиции position.
- Score(4) = MAX ( MIN (MAX (MIN ( оценка ситуации листа ), ..), ..), ..)
Score (depth)
:
position X; // данные, описывающие текущую позицию int score0 = 0; // эвристическая оценка текущей ситуации, то есть Score(0) int score_simple(int depth) { if (depth == 0) return score0; // добрались до листка дерева // возвращаем эвристическую оценку int score_best = -MAX_VALUE; int score; vector<move> moves; // массив возможных ходов generate_moves (moves); // заполняем moves, узнаем кол-во ходов forall(moves, move) { do_move (move]); // вносит изменения в позицию и // эвристическую оценку score0 score = -Score_simple (depth-1); // рекурсивно вызываем себя undo_move (move); // восстанавливаем исходную позицию // и значение score0 if (score > score_best) { score_best = score; // обновляем лучшую оценку } } return score_best; }
Альфа-бета отсечение
Идея оптимизации работы функцииScore(depth)
начинается со следующих рассуждений:
- S1: Пусть мы рассмотрели уже один свой ход MOVE1 и все возможные ответы соперника и начали рассматривать свой второй ход MOVE2. Как только среди ответов соперника, появится такой ход, который ставит нас в ситуацию хуже, чем самая плохая ситуация, в которую может нас поставить соперник, если мы сходим ходом MOVE1, то можно прекращать перебор возможных ответов соперника на ход MOVE2 и переходить к рассмотрению следующего нашего хода MOVE3.
- S2: Рассуждение S1 можно проводить на каждом уровне, рассуждая как за себя так и за соперника
- S3: По сути для реализации идеи S2 мы должны помнить лучший результат, достигнутый на предыдущем уровне. Назовём лучший результат с предыдущего уровня параметром
alpha
. - S4: А можно ли использовать в своих целях лучший результат с пред-предыдущего уровня? Да можно! Это будет параметром
beta
.
score_alphabeta(int depth, int alpha, int beta)
кроме глубины продумывания получает ещё два параметра alpha
и beta
.
Её смысл можно пояснить так:
Найти оценку текущей ситуации (некая глобальная переменная X), в предположении,
что она находится между alpha
и beta
. Если это предположение не верно,
и реальная оценка cитуации есть A, лежащая вне [alpha, beta]
, то
- вернуть
beta+1
, если A >= beta; - вернуть
alpha-1
, если A <alpha
.
[alpha, beta]
лежит правильный ответ.
Функцию score_alphabeta можно вызывать с параметрами alpha=-infty, beta=+infty и получить точное значение. При вычислении этого значения будут выполнятся рекурсивные вызовы, для которых значения параметров уже не бесконечны. Тем глубже уровень рекурсии, тем сильнее в среднем сближаются аргумены alpha
и beta
.
/* Обход дерева с альфа-бета отсечением Функция score_alphabeta вычисляет score(depth) более оптимально, нежели score_simple: score_alphabeta(-INFTY, +INFTY, depth ) = score (depth). */ position X; int score0 = 0; int score_alphabeta(int depth, int alpha, int beta,) { // CHANGED! if (depth == 0) return score0; int score_best = alpha; // CHANGED ! int score; vector<move> moves; generate_moves (moves); forall(moves, move) { do_move(move); score = -score_alphabeta (depth - 1, beta, -best); // CHANGED! undo_move (move); if (score > score_best) { score_best = score; if (score_best >= beta) break; // ADDED! } } return score_best; }
Дальнейшие оптимизации
Дальнейшие рассуждения о альфабета отсечении приводят нас к такой идее:- S5: Чем уже коридор, тем чаще происходит отсечение, и тем меньше
времени тратится на вычисление. Если бы мы могли примерно оценить
значение оценки и вызывать процедуры с некоторыми alpha и beta,
между которыми, по нашему мнению должна лежать точная оцненка Score(depth),
то отсечение происходило бы быстрее, начиная уже с первой вершины.
Если мы ошибёмся в выборе [alpha, beta], то функция скажет нам, в какую
именно сторону мы ошиблись, после чего мы можем сместить
"коридор" [alpha, beta] в эту сторону.
Если опять не угадали, коридор
можно снова сместить и, возможно, увеличить его размер.
Есть целый ряд идей связанных с игрой с коридором [alpha, beta]. Его можно делать изначально узким, но делать несколько попыток, вызова alphabeta процедуры, пока Score(depth) не попадет в [alpha, beta]. Если коридор будет достаточно широким, то попыток будет меньше, но они будут более долгими по времени.
Смотрите улучшения альфабета отсечения: AlgorithmSSS, AlgorithmMTDf.
Вот посканенная версия статьи из журнала "Программист": Алгортимы: поиск в играх.doc -- AntonMalykh - 05 Mar 2004
Related topics