Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

8.4. ДРУГИЕ УЛУЧШЕНИЯ МИНИМАКСА
В.этой.главе.представлены.глубоко.изученные.алгоритмы,.и.за.последние.годы.
для.них.было.найдено.много.улучшений..Некоторые.из.них.относятся.к.конкрет-
ной.игре,.например.«битовая.доска».в.шахматах,.которая.позволяет.сократить.
время.на.генерирование.правильных.ходов,.но.большинство.—.это.общие.методы,.
которые.можно.использовать.для.любой.игры.
Один.из.распространенных.методов.—.это.
итеративное углубление
..В.этом.случае.
функция.поиска.выполняется.сначала.с.максимальной.глубиной,.равной.1..Затем.
она.запускается.с.максимальной.глубиной.2,.3.и.т..д..По.истечении.указанного.
времени.поиск.прекращается.и.возвращается.результат.поиска.для.последней.
выбранной.глубины.
Примеры,.приведенные.в.этой.главе,.были.жестко.закодированы.до.определенной.
глубины..Это.нормально,.если.игра.идет.без.применения.часов.и.ограничений.по.
времени.или.если.нам.все.равно,.сколько.времени.потребуется.компьютеру.на.
«подумать»..Итеративное.углубление.позволяет.задать.для.ИИ.фиксированное.
время.поиска.следующего.хода.вместо.фиксированной.глубины.поиска.с.пере-
менным.количеством.времени.на.выполнение.хода.
Другое.потенциальное.улучшение.—.
поиск покоя
..При.использовании.этой.
технологии.минимаксное.дерево.поиска.дополнительно.расширяется.в.тех.на-
правлениях,.которые.вызывают.наибольшие.изменения.в.положении.(например,.
в.шахматах),.а.не.в.тех,.которые.имеют.относительно.тихие.позиции..Таким.об-
разом,.в.идеале.алгоритм.поиска.не.будет.тратить.время.на.вычисление.скучных.
позиций,.которые.вряд.ли.принесут.игроку.значительное.преимущество.
Два.наилучших.способа.улучшить.минимаксный.поиск.—.это.пройти.б

ольшую.
глубину.за.отведенное.время.или.улучшить.функцию,.применяемую.для.оценки.

---

8.5. Реальные приложения
241
позиции..Перебор.большего.количества.позиций.за.неизменное.время.позволяет.
тратить.меньше.времени.на.каждую.позицию..Это.может.быть.связано.с.повы-
шением.эффективности.кода.или.использованием.более.быстрого.аппаратного.
обеспечения,.но.может.происходить.и.за.счет.второго.способа.—.улучшения.
оценки.каждой.позиции..Применение.большего.количества.параметров.или.эв-
ристики.для.оценки.позиции.может.занять.больше.времени,.но.в.итоге.привести.
к.созданию.лучшего.механизма,.которому.требуется.меньшая.глубина.поиска,.
чтобы.найти.хороший.ход.
Некоторые.функции.оценки,.используемые.для.поиска.минимакса.с.альфа-бе-
та-отсечением.в.шахматах,.имеют.десятки.эвристик..Для.настройки.эвристик.
даже.применялись.генетические.алгоритмы..Сколько.стоит.ход.со.взятием.коня.
в.шахматах?.Равно.ли.данное.значение.стоимости.взятия.слона?.Эти.эвристи-
ки.могут.быть.тем.секретным.соусом,.который.отличает.отличный.шахматный.
движок.от.хорошего.