На этом шаге мы перечислим другие улучшения минимакса.
В рассмотренных шагах представлены глубоко изученные алгоритмы, и за последние годы для них было найдено много улучшений. Некоторые из этих улучшений относятся к конкретной игре, например "битовая доска" в шахматах, которая позволяет сократить время на генерирование правильных ходов, но большинство являются общими методами, которые можно использовать для любой игры.
Одним из распространенных методов является итеративное углубление. В этом случае функция поиска выполняется сначала с максимальной глубиной, равной 1. Затем она запускается с максимальной глубиной 2, 3 и т. д. По истечении указанного времени поиск прекращается и возвращается результат поиска для последней выбранной глубины.
Примеры, приведенные в рассмотренных шагах, были жестко закодированы до определенной глубины. Это нормально, если игра идет без применения часов и ограничений по времени или если нам все равно, сколько времени потребуется компьютеру на "подумать". Итеративное углубление позволяет задать для ИИ фиксированное время поиска следующего хода вместо фиксированной глубины поиска с переменным количеством времени на выполнение хода.
Другое потенциальное улучшение - поиск покоя. При использовании этой технологии минимаксное дерево поиска дополнительно расширяется в тех направлениях, которые вызывают наибольшие изменения в положении (например, в шахматах), а не в тех, которые имеют относительно "тихие" позиции. Таким образом, в идеале алгоритм поиска не будет тратить время на вычисления скучных позиций, которые вряд ли принесут игроку значительное преимущество.
Два наилучших способа улучшить минимаксный поиск - это пройти большую глубину за отведенное время или улучшить функцию, применяемую для оценки позиции. Перебор большего количества позиций за неизменное время позволяет тратить меньше времени на каждую позицию. Это может быть связано с повышением эффективности кода или использованием более быстрого аппаратного обеспечения, но может происходить и за счет второго способа - улучшения оценки каждой позиции. Применение большего количества параметров или эвристики для оценки позиции может занять больше времени, но в итоге привести к созданию лучшего механизма, которому требуется меньшая глубина поиска, чтобы найти хороший ход.
Некоторые функции оценки, используемые для поиска минимакса с альфа-бета-отсечением в шахматах, имеют десятки эвристик. Для настройки эвристик даже применялись генетические алгоритмы. Сколько стоит ход со взятием коня в шахматах? Равно ли данное значение стоимости взятия слона? Эти эвристики могут быть тем секретным соусом, который отличает отличный шахматный движок от хорошего.
На следующем шаге мы подведем некоторые итоги.
