Alpha-beta (Альфа-бета оптимизация полного перебора)

на главную страницу


Для начала напомню, что описание строится на основании MiniMaxa, а не NegaMaxa. Я до сих пор думаю, что NegaMax мутит воду, и сокращение кода ведет к трудности понимания, тестирования и падению скорости. В свое время я со скрипом перешел с NegaMaxa на MiniMax и думаю что это надолго. Конечно, это часть религиозной войны, и я четко обозначил свою позицию :)
Ну да ладно перейдем к алгоритму.

int AlphaBetaWhite(int alpha, int beta, int depth)// поиск за белых
{
  int tmp;
  int max = -INFINITY;// устанавливаем локальный максимум в минус бесконечность
  if(depth <= 0) return Evaluate();// на предельной глубине считаем оценку позиции
  GenerateWhite ();// генерируем список ходов за белых
  while(moveList) списки ходов локальные, т.е. действуют только в узле
  {
    MakeMoveWhite;// делаем ход
    tmp = AlphaBetaBlack (alpha, beta, depth-1);
    UnMakeMoveWhite;// откатываем ход
    if(tmp > max) max = tmp; // белые ищут локальный максимум
    if(tmp > alpha) alpha = tmp; // ищем усиления alpha
    if(max >= beta) return max; // если max >= beta, то дальше перебирать бесполезно, ведь в результате перебора мы будем только увеличивать
                                              // max, а его черные уже считают больше, чем найденный, и этот вариант будет откинут.
  }
  return max;
}

int AlphaBetaBlack (int alpha, int beta, int depth)// поиск за черных
{
  int tmp;
  int min = INFINITY;
  if(depth <= 0) return Evaluate();
  GenerateBlack ();
  while(moveList)
  {
    MakeMoveBlack;
    tmp = AlphaBetaWhite (alpha, beta, depth-1);
    UnMakeMoveBlack;
    if(tmp < min) min = tmp; // черные ищут локальный минимум
    if(tmp < beta) beta = tmp; //
    if(min <=alpha) return min; // если min <=alpha то дальше перебирать бесполезно ведь в результате перебора мы будем только уменьшать
                                             // min, а его белые уже считают меньше чем найденный , и этот вариант будет откинут.
  }
  return min;
}

Alpha - это максимум белых, который был найден в проведенном до этого поиске, beta - это найденный минимум черных. Следует сказать, что распространяются они только вниз, т.е. в глубину поиска. Если сделать их глобальными, то схема работать не будет.
Первый вызов вида AlphaBetaWhite (-INFINITY, INFINITY, DepthMax), т.е. alpha = минус бесконечности, а beta = плюс бесконечности. Во время поиска белые стремятся увеличить альфу, а черные уменьшить бету.
Допустим, в текущем узле ход белых. Они перебирают возможные ходы и стремятся найти лучший ход, т.е. с максимальной оценкой. Текущая альфа содержит найденный до этого максимум. Теперь мы порождаем узел следующей глубины, в котором уже ход черных. Туда же мы передаем текущую альфу. Черные в свою очередь перебирают ходы и ищут минимум. Кроме того, они сравнивают свою оценку с альфой. Если эта оценка меньше альфы, то перебор можно досрочно прекратить, ведь дальнейший поиск будет только уменьшать оценку, а она и так меньше альфы, т.е. будет отброшена белыми. Другими словами, найденного опровержения черных уже хватает, что бы белые отбросили этот ход, ведь у них есть лучший, конечно продолжая поиск, черные, возможно, смогут найти ход еще лучше для них и еще более неприемлемый для белых, но это будет бесполезная работа. То же самое и для черных.
Сортировка ходов имеет принципиальное значение для а-б, потому что чем раньше мы найдем лучший ход, тем больше будет отсечений и тем меньше надо перебирать. В худшем случае, т.е. если лучший ход будет найден последним, мы получим полный перебор.
Описанная мной схема, т.е. когда вверх идут оценки, а альфа с бетой только вниз называется схемой с амортизацией отказов. И именно эту схему я считаю корректной. Другие схемы хоть и работают, но при определенных условиях должны давать сбой. Надо сказать, что я пробовал и то и другое и, честно говоря, нестабильности не замечал. И все-таки, если следовать теории, то видимо нужно использовать схему с амортизацией отказов.

У а-б есть неприятная особенность. Достоверной является только оценка лучшей линии и тех линий, что были рассмотрены до нахождения лучшей. Все остальные обрываются досрочно и оценены слишком оптимистично для исследующей стороны.

И еще один момент – в начале поиска alpha должна быть меньше beta, иначе последуют отсечки и поиска не получится. Другими словами, будет вытащен первый попавшийся вариант, а все остальное будет отсечено. И не важно какая оценка, все остальное все равно отсечет alpha или beta.
Поэтому для белых вместо
if(max >= beta) return max;
можно смело писать
if(alpha >= beta) return alpha;
а для черных вместо
if(min <=alpha) return min;
пишем
if(alpha >= beta) return beta;
Здесь alpha и beta используются для отсечки, и их поднятие на уровень вверх никак не отражается на стабильности.
В данный момент я считаю, что эти схемы эквивалентны.

Как можно протестировать а-б? Я считаю, что при отсутствии сортировки и одинаковой глубине лучший ход, найденный а-б, должен совпадать с лучшим ходом, найденным полным перебором. Ходы нельзя сортировать по той причине, что есть много отличных позиций с одинаковой оценкой. Понятно, что и полный перебор и а-б схватят первую попавшуюся позицию, но из-за сортировки они часто оказываться разными.

С помощью альфа-бета оптимизации можно увеличить глубину перебора максимум в два раза. Так если у нас полный перебор из начальной позиции достигал за секунду глубины 4-5, то при идеальной сортировке а-б позволит достичь глубины 8-10 (скорости перебора от 206 603 до 5 072 212 узлов в секунду)
На данный момент Ifrit_b2_5 показывает следующие результаты:
Для полного перебора:
4/4      00:00    197.281         573.897   +0,07   e2e4 Ng8f6 e4e5 Nf6e4
5/5      00:10    4.865.609      517.731   +0,26   e2e4 Ng8f6 e4e5 Nf6e4 d2d4

Для а-б со всеми сортировками:
7/7      00:00    406.924         844.151   +0,27   e2e4 Ng8f6 e4e5 Nf6d5 Qd1f3 c7c6 d2d4
8/8      00:02    705.079         559.051   +0,12   e2e4 e7e5 Ng1f3 Ng8f6 d2d4 e5xd4 Qd1xd4 Bf8e7
9/9      00:15    8.484.952      742.262   +0,29   e2e4 e7e5 Ng1f3 Bf8d6 d2d4 e5xd4 Qd1xd4 Ng8f6 Bf1c4
10/10  01:33    34.110.652    564.277   +0,04   d2d4 d7d5 Nb1c3 Bc8f5 Bc1f4 Nb8c6 Ng1f3 Ng8f6 e2e3 Qd8d7

Видно, что достигается 7 глубина при скорости ~400 kN/c. Выдаваемые скорости в таблице оставлю на совести таймера. Гораздо надежнее взять количество узлов из третьего столбца и поделить на время счета из второго. Эти данные надежны, а вот скорость в четвертом столбце вызывает вопросы.
Идеальная сортировка не достижима и 7 для такой скорости вроде не очень плохо. В любом случае, что есть - то есть. Хотя если вспомнить, что это на Core 2 Duo 3000 то становиться грустно.
Главное, что следует запомнить - 10 глубина за секунду перебора в начальной позиции, это абсолютный потолок для а-б на современных процах.
Но что такое 10 для современных движков? Считать надо гораздо глубже, так что и на а-б останавливаться никак нельзя. Это значит, что мы должны априорно решать, какие ветки нам интересны и их надо бы просматривать глубже, а какие можно и сократить. Самая известная эвристика - это конечно Null-move (эвристика нулевого хода), но о ней в другом месте.





















Сайт создан в системе uCoz