Дерево ходов и Альфа-бета отсечение

Альфа-бета отсечение — это оптимизация алгоритма обхода дерева ходов, основанное на знании текущих лучших результатов полученных на предыдущих уровнях дерева.

Дерево ходов

Идея обхода проста — мы смотрим, какие есть ходы из текущей ситуации. Затем для каждого своего хода смотрим, как на него может ответить соперник, для каждого возможного хода соперника смотрим, как мы можем ответить и т.д. Человек обычно неспособен рассмотреть дерево всех возможных ходов даже на глубину три. Но отдельные варианты развития событий он может продумать на 10 и более ходов. Отсечение "мало перспективных с первого взгляда" вариантов и другие эвристические идеи оптимизации просмотра дерева ходов рассматриваются в AlphaBetaOptimisationHeurictics?.

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

На рисунке показано дерево возможных ходов. В круглых узлах делаем выбор мы, а в квадратных — наш соперник.

К какой-то момент процесс рассмотрения возможных ответных ходов прекращается. Дерево ходов имеет конечный размер и для его листьев делается некоторая эвристическая оценка.

Оценочная функция в шахматах может быть основана на том, какие фигуры остались на доске (взвешенная сумма фигур белых минус взвешенная сумма фигур черных).

Если ситуация хороша для белых — оценочная функция положительна, если для черных — отрицательна. Мы будем считать, что в других играх тоже один игрок является "белым", а другой "черным". Например, в крестиках-ноликах "белым" игроком назначим крестика.

Среди возможных ходов мы ("белый") будем выбирать тот ход, который приводит нас в позицию с максимумом оценки, а думая за соперника, естественно выбирать ход приводящий в ситуацию с самой маленькой оценкой.

* Score (position, depth) — оценка ситуации position при глубине продумывания depth.

Её удобно определить рекурсивно:

• 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.

Таким образом, если просматриваем дерево ходов до глубины 4 (4 полухода), то

• Score(4) = MAX ( MIN (MAX (MIN ( оценка ситуации листа ), ..), ..), ..)

Первый максимум ищется по возможным нашим ходам; следующий минимум ищется по возможным ответам соперника на наш ход; следующий максимум ищется по возможным нашим ответам на ответ соперника и т.д. Приведем схематичный код на C, в котором вычисляется 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.

-- ArtemVoroztsov - 11 Mar 2004

-- AntonMalykh - 05 Mar 2004

Related topics

• AlphaBetaLinks