Главная » Алгоритмы, Игры » Alpha-beta

0

Сейчас мы рассмотрим основной алгоритм оптимизации перебора. Он на­зывается alpha-beta отсечениями, или просто alpha-beta. Суть его в том, что для получения оценки такой же точности, как и при полном переборе, со­вершенно не обязательно просматривать все варианты. Для определения отсекаемых вариантов не требуется знать особенностей данной игры.

В рекурсивной функции мы должны ввести две новые переменные — мак­симум для белых и максимум для черных. При начальном вызове обе эти величины равны минимально возможному значению: (-infinity). Если в какой-то позиции, например, для черных, мы получили результат, превы­шающий максимум для черных, достигнутый до этого, мы увеличиваем это значение. Теперь рассмотрим некоторую строку игры. Представим, что где- то в глубине дерева перебора мы обнаружили, что максимумы белых и чер­ных сравнялись. Надо помнить, что это инвертированные величины, и сравнивать их нужно со знаком минус:

if( -maxWhite == maxBlack) {.. . }

Допустим, мы просчитываем позицию для белых. Если мы продолжим пе­ребирать в данной позиции, то максимум для белых может еще увеличить­ся, а может остаться прежним, но он уже сравнялся с максимумом черных. Это значит, что когда программа вернется в точку (рекурсивно), в которой максимум для черных, результат будет отвергнут, т. к. он не превышает максимума для черных в этой позиции. Также это значит, что в данной по­зиции для белых мы можем прекратить перебор и вернуть полученный ре­зультат досрочно. Дальше считать нет смысла. Рассмотрим программный код, иллюстрирующий сказанное:

int Search(int color, int Depth, int maxWhite, int maxBlack) {

if(Depth == 0) return Evaluate(color); //оценка конечной точки int score     INFINITY;

int opColor = (color == BLACK7WHITE:BLACK); PMove move = GenerateAllMoves();

while(move) (

MakeMove(move);

int tmp = -Search(opColor,Depth-1,maxWhite,maxBlack); UnMakeMove(move);

if(tmp > score) {

if(color = WHITE) {

if(score > maxWhite) maxWhite = score; if(-maxWhite <= maxBlack) return maxWhite; }else{

if(score > maxBlack) maxBlack = score; if(-maxBlack <= maxWhite) return maxBlack;

}

}

move = move->next;

}

return score;

}

Пример первого вызова:

Search(WHITE, 4, -INFINITY, -INFINITY);

Переменные maxWhite и maxBlack получили название alpha и beta, а сама функция описывается без избыточного кода:

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

if(Depth == 0) return Evaluate(color); PMove move = GenerateAllMoves();

while(move && alpha < beta) {

MakeMove(move);

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

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

move = move->next;

}

return alpha;

}

Пример первого вызова:

AlphaBeta(WHITE, 6, -INFINITY, INFINITY);

При первом вызове функция вызывается с максимальным окном. При ре­курсивных вызовах переменные alpha и beta меняются местами с инверсией знака. Как видите, все очень просто, но требует некоторого осмысления. алгоритм, при наилучшем порядке ходов, построит значительно меньшее дерево перебора. Это примерно равно корню квадратному из числа позиций, просматриваемых при полном переборе. Нужно учесть, что при наихудшем порядке ходов, т. е. когда отсечку за beta вызывает последний ход, alpha-beta просмотрит столько же позиций, что и NegaMax. Это гово­рит о том, что alpha-beta очень чувствителен к порядку ходов. Скорость просчета еще сильно зависит на практике от возможного диапазона оценок. Если мы в шахматах считаем только материал, то оценка всем ходам, кроме взятий, равна нулю. Это значит, что отсечек будет очень много, особенно если взятия мы будем рассматривать первыми. Это очень схематично, но на практике верно. Если же мы, кроме материальной, учитываем еще и пози­ционную оценку, нам намного труднее получить дерево, близкое к мини­мальному. Примерная оценка, с учетом позиционной составляющей:

?     пешка — 1000

?    слон и конь — 3000

?    ладья – 5000

?    ферзь — 9000

?     король — 90 000

Позиционная оценка — от —500 до 500.

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

алгоритм является основой всех современных шахматных про­грамм.

Литература:

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

По теме:

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