|
||
|
Для начала напомню, что описание строится на основании 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 (эвристика нулевого хода), но о ней в другом месте. |