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

В этой главе были проанализированы самые разные игры с тем, чтобы можно было понять, что означают слова "оптимальная игра", а также узнать, как научиться хорошо играть на практике. Ниже изложены наиболее важные идеи, которые рассматривались в данной главе.

•    Любая игра может быть определена с помощью начального состояния (которое показывает, как осуществляется подготовка доски к игре), допустимых действий в каждом состоянии, проверки терминального состояния (позволяющей определить, когда игра окончена) и функции полезности, которая применяется к терминальным состояниям.

•    В играх с двумя игроками и нулевой суммой, характеризующихся полной информацией, для выбора оптимальных ходов с помощью перебора узлов в глубину в дереве игры может использоваться алгоритм минимаксного поиска.

•    Алгоритм альфа-бета-поиска вычисляет такие же оптимальные ходы, как и алгоритм минимаксного поиска, но позволяет достичь гораздо большей эффективности, удаляя поддеревья, которые, по всей вероятности, не нужны для поиска решения.

•    Обычно не представляется возможным рассматривать все дерево игры (даже с помощью альфа-бета-поиска), поэтому необходимо в какой-то точке останавливать поиск и применять функцию оценки, позволяющую определить приближенное значение полезности некоторого состояния.

•    Ведение игр с элементами случайности можно осуществить с помощью расширения алгоритма минимаксного поиска, в котором оцениваются узлы жеребьевки путем определения средней полезности всех их дочерних узлов с учетом вероятности каждого дочернего узла.

•   Для определения оптимальных ходов в играх с неполной информацией, таких как бридж, необходимо формировать рассуждения о текущем и будущем доверительных состояниях для каждого игрока. Одна из простых аппроксимаций может быть получена путем усреднения значения данного действия по всем возможным конфигурациям недостающей информации.

•    Программы способны соревноваться на равных или побеждать лучших игроков-людей в шашках, игре "Отелло" и в нардах, а также вплотную приблизились к ним в бридже. Программа победила чемпиона мира по шахматам в одном показательном матче. В игре го программы до сих пор остаются на любительском уровне.