Прекращение поиска
Следующий этап состоит в том. что алгоритм Alpha-Beta-Search должен быть модифицирован так, чтобы он вызывал эвристическую функцию Eval, когда возникает необходимость остановить поиск. С точки зрения реализации необходимо заменить две строки в листинге 6.2, в которых упоминается функция Terminal-Test, следующей строкой:
if Cutoff-Test(state, depth) then return Eval(state)
Необходимо также предусмотреть выполнение определенных технических операций для того, чтобы текущее значение глубины depth наращивалось при каждом рекурсивном вызове. Наиболее прямолинейный подход к управлению объемом поиска состоит в том, что должен устанавливаться фиксированный предел глубины, чтобы функция Cutoff-Test (state, depth) возвращала значение true при всех значениях depth, превышающих некоторую фиксированную глубину d. (Она должна также возвращать true для всех терминальных состояний, как было предусмотрено и в функции Terminal-Test.) Глубина d выбрана таким образом, чтобы используемое время не превышало допустимое по правилам игры.
Более надежный подход состоит в использовании метода итеративного углубления, который определен в главе 3. По окончании отведенного времени программа возвращает ход, выбранный по итогам наиболее глубокого завершенного поиска. Однако подобные подходы могут приводить к ошибкам, обусловленным приближенным характером функции оценки. Еще раз рассмотрим простую функцию оценки для шахмат, основанную на учете преимущества в материале. Предположим, что программа выполняет поиск до предела глубины, достигая позиции, приведенной на рис. 6.6, б, где черные имеют перевес на одного коня и две пешки. Программа сообщила бы об этом как об эвристическом значении данного состояния, объявив тем самым, что это состояние, по всей вероятности, приведет к победе черных. Но на следующем ходу белые берут ферзя черных без компенсации. Поэтому в действительности данная позиция является выигрышной для белых, но об этом можно было бы узнать, только заглянув вперед еще на один полуход.
Очевидно, что требуется более сложная проверка останова. Функция оценки должна применяться только к позициям, которые являются спокойными, т.е. характеризующимися низкой вероятностью того, что в них в ближайшем будущем произойдут резкие изменения в стоимости. Например, в шахматах такие позиции, в которых могут быть сделаны желательные взятия фигур, не являются спокойными для такой функции оценки, в которой учитывается лишь материал. Неспокойные позиции могут быть дополнительно развернуты до тех пор, пока не будут достигнуты спокойные позиции. Подобный дополнительный поиск называется поиском спокойных позиций; иногда он ограничивается тем, что в нем рассматриваются только ходы определенных типов, такие как ходы со взятием фигур, что позволяет быстро устранять все неопределенности в этой позиции.
Задача устранения эффекта горизонта является более сложной. Этот эффект возникает, если программа сталкивается с каким-то ходом противника, который причиняет серьезный ущерб и в конечном итоге является неизбежным. Рассмотрим шахматную позицию, приведенную на рис. 6.7. Черные превосходят белых по количеству материала, но если белые смогут продвинуть свою пешку с седьмой горизонтали на восьмую, то пешка станет ферзем и обеспечит легкую победу белых. Черные могут отсрочить этот итог на 14 полуходов, объявляя шах белым с помощью ладьи, но пешка неизбежно станет ферзем. Одним из недостатков поиска на фиксированную глубину является то, что применяемый при этом алгоритм не позволяет определить, что такие отвлекающие ходы не способны предотвратить ход с превращением пешки в ферзя. В этом случае принято считать, что отвлекающие ходы выводят неизбежный ход с превращением пешки в ферзя "за пределы горизонта поиска" — в то место, где опасный ход невозможно обнаружить.
По мере того как совершенствование аппаратных средств, применяемых для ведения игры в шахматы, приводит к увеличению глубины поиска, становится все более возможным то, что эффект горизонта будет возникать не так часто, поскольку очень длинные последовательности ходов, позволяющие отсрочить выполнение нежелательного хода, возникают крайне редко. Для предотвращения эффекта горизонта без слишком значительного увеличения стоимости поиска оказалось также весьма эффектным использование одинарных расширений. Одинарным расширением называется ход, который "безусловно лучше" по сравнению со всеми другими ходами в данной конкретной позиции. Поиск с одинарным расширением позволяет выйти за обычные пределы глубины поиска без внесения значительных издержек, поскольку в нем коэффициент ветвления равен 1. (Поиск спокойной позиции может рассматриваться как один из вариантов одинарных расширений.) На рис. 6.7 поиск с одинарным расширением позволяет найти выполняемый в конечном итоге ход превращения пешки в ферзя, при условии, что ходы черных с объявлением шаха и ходы белых королем могут быть определены как "безусловно лучшие" по сравнению с другими вариантами.
До сих пор речь шла о том, что прекращение поиска на определенном уровне и выполнение альфа-бета-отсечения, по-видимому, не влияет на результат. Существует также возможность выполнять предварительное отсечение, а это означает, что некоторые ходы в данном конкретном узле отсекаются немедленно, без дальнейшего рассмотрения. Очевидно, что большинство людей, играющих в шахматы, рассматривают лишь несколько ходов из каждой позиции (по крайней мере, сознательно). К сожалению, этот подход является довольно опасным, поскольку нет никакой гарантии того, что не произойдет отсечение лучшего хода. А если отсечение применяется недалеко от корня, результат может оказаться катастрофическим, поскольку слишком часто возникают такие ситуации, что программа пропускает некоторые "очевидные" ходы. Предварительное отсечение может использоваться безопасно в особых ситуациях (например, если два хода являются симметричными или эквивалентными по каким-то другим признаками, то необходимо рассматривать только один из них) или при анализе узлов, которые находятся глубоко в дереве поиска.
В результате совместного использования всех методов, описанных выше, появляется возможность создать программу, которая неплохо играет в шахматы (или другие игры). Предположим, что реализована функция оценки для шахмат, предусмотрена разумная проверка останова в сочетании с поиском спокойной позиции, а также предусмотрена большая таблица транспозиций. Кроме того, предположим, что, затратив целые месяцы на скрупулезную разработку программ, функционирующих на уровне битов, мы получили возможность формировать и оценивать примерно миллион узлов в секунду на новейшем персональном компьютере, что позволяет выполнять поиск приблизительно среди 200 миллионов узлов в расчете на каждый ход при стандартном контроле времени (три минуты на каждый ход). Коэффициент ветвления для шахмат составляет в среднем примерно 3 5, а 355 равно приблизительно 50миллионам, поэтому при использовании минимаксного поиска мы получим возможность заглядывать вперед лишь приблизительно на пять полуходов. Такая программа, хотя и не совсем некомпетентная, может быть легко обманута человеком, игроком в шахматы среднего уровня, который иногда способен планировать на шесть или восемь полуходов вперед. Альфа-бета-поиск позволяет достичь глубины приблизительно в 10 полуходов, что приводит к усилению игры до уровня мастера. В разделе 6.7 описаны дополнительные методы отсечения, которые позволяют увеличить эффективную глубину поиска примерно до 14 полуходов. Чтобы достичь уровня гроссмейстера, требуется тщательно настроенная функция оценки и большая база данных с записями оптимальных ходов в дебюте и эндшпиле. Не мешало бы также иметь суперкомпьютер для эксплуатации на нем такой программы!