Раздел «Алгоритмы».AlgorithmAlphaBeta:

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

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

Дерево ходов

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

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

Edit drawing 'tree' (requires a Java enabled browser)

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

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

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

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

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

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

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

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

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

Таким образом, процедура score_alphabeta(int depth, int alpha, int beta) кроме глубины продумывания получает ещё два параметра — alpha и beta.

Её смысл можно пояснить так: Найти оценку текущей ситуации (некая глобальная переменная X), в предположении, что она находится между alpha и beta. Если это предположение не верно, и реальная оценка cитуации есть A, лежащая вне [alpha, beta], то

Таким образом, если мы угадаем промежуток, в котором лежит реальная оценка ситуации, то получим верную оценку, а иначе мы узнаем лишь с какой стороны от промежутка [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;
}

Дальнейшие оптимизации

Дальнейшие рассуждения о альфабета отсечении приводят нас к такой идее:

-- ArtemVoroztsov - 11 Mar 2004


Вот посканенная версия статьи из журнала "Программист": Алгортимы: поиск в играх.doc

-- AntonMalykh - 05 Mar 2004


Related topics