Модуль перебора

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

Модуль перебора.
Начальная глубина у нас - 0. Начальная максимальная глубина у нас - 1.
Если глубина предельная, то мы статически оцениваем позицию и возвращаем оценку. Причем, статический оценщик у нас абсолютный. Т.е. он преимущество белых отмечает как " +", а черных как "-". Но мы оценку инвертируем в зависимости от того, кто ходит. Это нужно для негамакса.
Тут есть тонкий момент. Мы оцениваем уже схоженную позицию. Т.е., если например ходили белые, то позиция в оценщик придет с флагом "ход черных".
Вообще-то мы при ходе белых оценку инвертировать не должны, но так как мы имеем уже схоженную позицию, то и инвертируем именно при ходе белых.

Запись варианта.
Когда погружаемся в вариант, на каждой глубине записываем, откуда и куда фигура ходила. Таким образом, у нас получается текущий массив ходов. В случае, если мы считаем, что оценка нам подходит мы записываем вариант. Причем, записываем от текущей до предельной глубины. Записываем лучший вариант во временный массив, по-новой создаваемый для каждого узла. Когда же мы выходим из узла, мы вновь скидываем вариант в текущий массив ходов.
Вероятно, объяснение туманное, но если посмотреть код, то все станет понятным.

Альфа бета.
Если альфа больше локальной оценки, то записываем ее в альфу.
Если бета больше или равна альфа, то выходим возвращая бету.
В функцию передаем альфу и бету, причем, меняя их местами и со знаком "минус".
Локальную оценку тоже принимаем со знаком "минус".
В начале альфа максимально большая, а бета - максимально маленькая.

Итак, мы ищем локальный минимум и если он уже меньше минимума в предыдущем более высоком узле, поиск бросаем, так как в дальнейшем локальный минимум будет только уменьшаться, а мы уже знаем, что его отбросим.
Тут слегка все путает негомакс, но если поднапрячься и посмотреть исходники, то врубиться можно.

























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