Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Рисунок 8 - Пример стандартного отсечения
Рассмотрим пример стандартного альфа бета отсечения. В позиции А ход выбираем мы, следовательно выберем наибольшее значение из позиций В и С. Значение В уже посчитано - это 10. При расчете позиции С выяснилось, что один из узлов имеет значение 5. В позиции С ход будет делать наш соперник, а значит выберет наименьшее значение. Из этого следует что значение позиции С будет от 5 и ниже, следовательно мы всегда выберем В-вариант. Поэтому расчет остальных узлов С мы не проводим.
3.1.2 Пример углубленного отсечения
Рисунок 9 - Пример углубленного отсечения
Рассмотрим пример глубокого отсечения. В позиции А мы будем выбирать между ходами в позиции В и С. Значение В=15. Мы начинаем расчет С. В позиции Е один из узлов дал значение 5. В позиции Е выбор хода принадлежит сопернику, а значит итоговое значение Е будет от 5 и ниже. Если значение С окажется равным Е, то мы выберем вариант В, так как он более привлекательный. Следовательно нам не обязательно знать точное значение позиции Е, поэтому все остальные ветви выходящие из него обрезаются.
3.2 Итерационное погружение (Iterated Deepening)
Смысл веера перебора или итерационного углубления заключается в повторяющемся вызове процедуры перебора на фиксированную глубину с увеличением глубины, пока установленный лимит времени не превышен или максимальна глубина поиска не достигнута. Преимущество этого метода состоит в том, что вы не должны выбирать глубину поиска заранее; кроме этого вы можете всегда использовать результат последнего законченного поиска. Значения, возвращенные от каждого поиска могут использоваться, чтобы корректировать окно стремления следующего поиска[10].
В общем случае, альфа-бета отсечение вызывается из вершины дерева на интервале (-?;+?). Однако используя итерационное погружение мы можем его поменять.
Предположим что Х - значение оптимального хода найденное на предидущей итерации, а числом Epsilon обозначим предполагаемую разницу в результатах между поиском на глубину D-1 и глубину D. Далее мы просто вызываем альфа-бета отсечение из вершины дерева с предполагаемым интервалом: alphabeta(D, x-epsilon, x+epsilon).
Далее могут произойти два случая:
.Значение вернется в интервале (x-epsilon, x+epsilon) - это корректное значение, мы можем его использовать.
.Значение вернется вне интервала (x-epsilon, x+epsilon) необходимо повторить вычисление с измененным интервалом.
Даже если допустить, что метод альфа-бета отсечений не даст никакого выигрыша, общее увеличение времени анализа на самом деле окажется относительно небольшим. Действительно если предположить, что среднее число вариантов на каждом уровне равно D, а количество анализируемых уровней составляет p, то итеративный поиск до первого уровня, затем до второго и т.д. до уровня p, эквивалентен (без альфа-бета отсечений) просмотру D + + ...+ позиций[20].
Эта сумма равна , тогда как количество позиций, просматриваемых при обычном анализе, равно . Соотношение между этими двумя числами при больших p примерно равно и, следовательно, близко к 1 в случаях, когда D достаточно велико
Также при использование итеративного поиска можно ввести контроль времени, что позволит компьютеру в любой момент предложить удовлетворительное решение. Таким образом, если время на размышление ограничено 5 секундами, он рассмотрит все позиции до уровня 2, например, за 0.001 секунду, до уровня 3 - за 0.01 секунду, до уровня 4 - за 1 секунду, а затем, после начала анализа на уровне 5 будет вынужден прерваться из-за нехватки времени. Однако при этом у компьютера уже будет достаточно хорошее решение, найденное на уровне 4.
В результате компьютер способен дать ответ в указанное время (например, сделать 50 ходов за 2 часа). Также очевидно, что программа, поддерживающая подобный метод, будет играть с разной силой на разных компьютерах[20].
Несмотря на то, что некоторые ветки дерева придется проверять несколько раз этот метод дает достаточное количество отсечений.
3.3 Сортировка ходов
На результаты альфа-бета отсечения очень сильно влияет в каком порядке проверяются ходы. Рассмотрим это на примерах:
В первом случае проведем расчет рассортировав ходы от худшего к лучшему
Рисунок 10 - Альфа-бета отсечение с ходами от худшего к лучшему
Как видно из примера, не было отсечено ни одно ветви дерева.
Теперь отсортируем ходы от лучшего к худшему
Рисунок 11 - альфа-бета отсечение с ходами от лучшего к худшему
При оптимальных обстоятельствах перебор с альфа-бета отсечением должен просмотреть W^((D+1)/2) + W^(D/2) - 1 позицию. Это намного меньше чем минимакс.
Для повышения эффективности альфа-бета отсечения, необходимо задуматься над тем, какие ходы надо исследовать в первую очередь. Для этих целей используется так называемая эвристика убийцы.
Идея состоит в том, что если ход был хорошим в одной части дерева, то, если он возможен, его стоит попробовать проверить и в других (на одинаковой глубине). Для этого вводится массив куда заносятся несколько лучших ходов для каждой глубины, если в позиции для текущей глубины есть ходы из этой таблицы - они проверяются первыми.
Для остальных ходов алгоритм отдает предпочтение ходам с шахами и взятиями.
3.4 Нега-Скаут (NegaScout)
- надстройка над альфа бетой. Это направленный алгоритм поиска для вычисления минимаксного значения узла.- самый попу