|
||
|
Самое начало - это полный перебор. Из данной позиции возможно несколько легальных ходов, мы их делаем и получаем позиции следующего уровня и все повторяется. Следует обратить внимание, что мы сначала генерируем список ходов возможных из данной позиции, а уже потом делаем эти ходы, получая новые позиции. Делается это по нескольким причинам. Во-первых, довольно накладно хранить в памяти дерево позиций. Гораздо эффективнее хранить не позиции, а ходы, которые привели к данной позиции. И, во-вторых, после генерации ходов при использовании а-б отсечения их нужно будет сортировать, и многие ходы будут отброшены без генерации позиций, т.е. без делания этого хода. Но даже при максимально компактной записи ходов мы не можем держать в памяти все дерево игры, потому что оно растет по экспоненте. Приведем цифры, потому что в данном случае они красноречивее всяких слов: Для начальной позиции Глубина перебора Количество узлов 3 9 322 4 206 603 5 5 072 212 6 124 132 536 7 3 320 034 396 (8,9,10 вычислял сам) 8 88 319 013 352 9 2 527 849 247 519 10 71 880 708 959 936 Мы знаем, что 1 Мб - это 1 048 576 байт. Допустим, у нас ход закодирован в целом числе int, а это 4 байт. Значит, в одном Мб можно сохранить 262144 ходов. Это значит, что для глубины 5 полуходов нам потребуется 19 Мб. А для 6 полуходов уже ~ 473Мб. И так далее по экспоненте. Поэтому при переборе мы держим в памяти только одну ветку ту, которую в данный момент исследуем. Тогда даже при глубине 10 нам потребуется примерно 20*10 = 400 ходов. Такое дерево легко помещается даже в кэше процессора. В результате алгоритм таков. Берем позицию и генерируем из нее список ходов, дальше берем ход из списка и делаем его, т.е. создаем позицию следующего уровня и т.д. Позиции на предельной глубине оцениваем. И в каждом узле находим лучшую оценку. Понятно, что белые будут пытаться найти максимум, а черные минимум. Поэтому алгоритм и называется минимаксом. Это все очень просто, но как это описать?! Пойду самым простым путем – приведу алгоритм полного перебора. Поиск за белых{ Оценку за белых, т.е. локальный максимум устанавливаем в минимум. Если достигли максимально заданной глубины, то вызываем статическую оценку позиции Генерируем список легальных ходов Просматриваем список { Делаем ход за белых Вызываем Поиск за черных, в результате которого получаем оценку хода Берем назад ход за белых Сравниваем оценку хода с нашим максимумом в узле, если больше, то делаем ее максимумом } Возвращаем максимум в узле } Поиск за черных { Оценку за черных, т.е. локальный минимум устанавливаем в максимум. Если достигли максимально заданной глубины, то вызываем статическую оценку позиции Генерируем список легальных ходов Просматриваем список { Делаем ход за черных Вызываем Поиск за белых, в результате которого получаем оценку хода Берем назад ход за черных Сравниваем оценку хода с нашим минимумом в узле, если меньше то делаем ее минимумом. } Возвращаем минимум в узле } Описание получилось какое то неконкретное, поэтому приведу код на си образном языке и в дальнейшем алгоритм словами описывать не буду (учите Си++!). int AlphaBetaWhite(int depth) поиск за белых { int tmp; int max = -INFINITY;// устанавливаем локальный максимум в минус бесконечность if(depth <= 0) return Evaluate();// на предельной глубине считаем оценку позиции GenerateWhite ();// генерируем список ходов за белых while(moveList) списки ходов локальные, т.е. действуют только в узле { MakeMoveWhite;//делаем ход tmp = AlphaBetaBlack(depth-1); UnMakeMoveWhite;// откатываем ход if(tmp > max) max = tmp; // белые ищут локальный максимум } return max; } int AlphaBetaBlack (int depth) поиск за черных { int tmp; int min = INFINITY; if(depth <= 0) return Evaluate(); GenerateBlack (); while(moveList) { MakeMoveBlack; tmp = AlphaBetaWhite (depth-1); UnMakeMoveBlack; if(tmp < min) min = tmp; // черные ищут локальный минимум } return min; } Очевидно, что полный перебор крайне неэффективен. И действительно для перебора за секунду на: – глубину 4 нужна скорость 206 тысяч узлов секунду; – глубину 5 нужна скорость 5 миллионов 72 тысячи узлов в секунду; – глубину 6 нужна скорость 124 миллиона 132 тысячи узлов в секунду; – глубину 7 нужна скорость 3 миллиарда (!) 320 миллионов 034 тысячи узлов в секунду. Как видно глубины поиска просто смешные, а требуемое быстродействие совершенно неприличное. И тут не поможет никакая оптимизация. На нынешних процессорах такая программа будет играть на глубине 4, а в лучшем случае 5 полуходов, т.е. смотреть на ~2 хода :) Именно поэтому на полном переборе останавливаться никак нельзя и следует идти дальше. А дальше у нас alpha-beta оптимизация перебора. Тестировать его элементарно. В интернете есть данные, сколько узлов получается на конкретной глубине для конкретной позиции. В крайнем случае, можно взять цифры, что я привел выше. Надо уточнить, что у меня схема несколько сложнее той, что приведена выше. Дело в том, что генератор списка ходов не проверяет легитимность полученных позиций, если сказать просто это значит, что в результате некоторых ходов король может оказаться под шахом. Для того что бы проверить под шахом ли король генератору пришлось бы двигать фигуры, так как есть такое явление как вскрытый шах. С рокировкой дело еще сложнее, так как при рокировке король не должен бегать через битые поля. Но так как тут не надо двигать фигуры, то легитимность рокировки проверяется внутри генератора. В результате схема несколько усложняется. int AlphaBetaWhite (int depth)// поиск за белых { int tmp; int max = -INFINITY;// устанавливаем локальный максимум в минус бесконечность if(depth <= 0) return Evaluate ();// на предельной глубине считаем оценку позиции GenerateWhite ();// генерируем список избыточных ходов за белых while(moveList)// списки ходов локальные, т.е. действуют только в узле { MakeMoveWhite;// делаем ход if (King_white_check !=0 ){// проверяем под шахом ли король UnMakeMoveWhite;// откатываем ход, так как позиция некорректная }else{ tmp = AlphaBetaBlack(depth-1); UnMakeMoveWhite;// откатываем ход if(tmp > max) max = tmp; // белые ищут локальный максимум } } return max; } Аналогично для черных. В дальнейшем изложении буду опираться на упрощенную схему. |