Главная arrow книги arrow Копия Глава 6. Поиск в условиях противодействия arrow Прекращение поиска
Прекращение поиска

Следующий этап состоит в том. что алгоритм Alpha-Beta-Search должен быть модифицирован так, чтобы он вызывал эвристическую функцию Eval, когда возникает необходимость остановить поиск. С точки зрения реализации необходимо заменить две строки в листинге 6.2, в которых упоминается функция Terminal-Test, следующей строкой:

Необходимо также предусмотреть выполнение определенных технических операций для того, чтобы текущее значение глубины depth наращивалось при каждом рекурсивном вызове. Наиболее прямолинейный подход к управлению объемом поиска состоит в том, что должен устанавливаться фиксированный предел глубины, чтобы функция Cutoff-Test (state, depth) возвращала значение true при всех значениях depth, превышающих некоторую фиксированную глубину d. (Она должна также возвращать true для всех терминальных состояний, как было предусмотрено и в функции Terminal-Test.) Глубина d выбрана таким образом, чтобы используемое время не превышало допустимое по правилам игры.

Более надежный подход состоит в использовании метода итеративного углубления, который определен в главе 3. По окончании отведенного времени программа возвращает ход, выбранный по итогам наиболее глубокого завершенного поиска. Однако подобные подходы могут приводить к ошибкам, обусловленным приближенным характером функции оценки. Еще раз рассмотрим простую функцию оценки для шахмат, основанную на учете преимущества в материале. Предположим, что программа выполняет поиск до предела глубины, достигая позиции, приведенной на рис. 6.6, б, где черные имеют перевес на одного коня и две пешки. Программа сообщила бы об этом как об эвристическом значении данного состояния, объявив тем самым, что это состояние, по всей вероятности, приведет к победе черных. Но на следующем ходу белые берут ферзя черных без компенсации. Поэтому в действительности данная позиция является выигрышной для белых, но об этом можно было бы узнать, только заглянув вперед еще на один полуход.