Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 62
Текст из файла (страница 62)
° ъ Проверка терминального состояния, которая определяет, что игра закончена. Состояния, в которых игра закончена, называются терминальными состояниями. ° Функция полезности (называемая также целевой функцией, или функцией вознаграждеиия), которая сообщает числовое значение терминальных состояний. В шахматах результатом является победа, поражение или ничья, со значениями +1, -1 илн О. Некоторые игры имеют более широкий диапазон возможных результатов; например, количество очков в нардах может составлять от +192 до -192. В настоящей главе в основном рассматриваются игры с нулевой суммой, хотя будут также кратко упоминаться игры с ненулевой суммой. Начальное состояние и допустимые ходы каждой стороны определяют «в дерево игры для данной игры.
На рис. 6.1 показана часть дерева игры в крестики-нолики. Из начального состояния игрок млх имеет девять возможных ходов. Ходы чередуются так, что МЛХ ставит значок Х, а М1М значок О, до тех пор пока не будут достигнуты листовые узлы, соответствующие терминальным состояниям, таким, что один игрок поставил три своих значка в один ряд или заполнены все клетки.
Число под каждым листовым узлом указывает значение полезности соответствующего терминального состояния с точки зрения игрока млх; предполагается, что высокие значения являются благоприятными для игрока млх и неблагоприятными для игрока м1М (именно поэтому в теории этим игрокам присвоены такие имена). Задача игрока Мдк состоит в использовании дерева поиска (особенно данных о полезности терминальных состояний) для определения наилучшего хода. Оптимальные стратегии При решении обычных задач поиска оптимальное решение для игрока мдх должно представлять собой последовательность ходов, ведущих к цели — к терминальному состоянию, которое соответствует выигрышу. С другой стороны, в игре 243 Глава 6.
Поиск в условиях противодействия участвует также игрок М1М, который имеет другое мнение по этому поводу. Это означает, что игрок МАХ должен найти надежную 'в. стратегию, позволяющую определить ход игрока МАХ в начальном состоянии, затем ходы игрока МАХ в состояниях, ставших результатом любого возможного ответа игрока МТМ, а затем ходы МАХ в состояниях, ставших результатом любого возможного ответа МТМ на те ходы, и т.д. Грубо говоря, оптимальная стратегия приводит к итогу, по меньшей мере, такому же благоприятному, как и любая другая стратегия, в тех условиях, когда приходится играть с противником, не допускающим ошибок.
Прежде всего рассмотрим, как найти эту оптимальную стратегию, даже притом что для млх часто будет неосуществимой задача ее исчерпывающего вычисления в играх, более сложных, чем крестики-нолики. МАХ (Х) М(Н (0) МАХ (Х) М!М (0) Закяючнтея ХОХ ХОХ ХОХ состояние ТЕКМПЧАЕ Полезность — 1 О ь1 Рис. б.). (Частичное) дерево поиска для игры крестики-нолики. Верхний узел представляет собой начальное состояние, а первым ходит игрок МАХ, ставя значок Х в пустой клетке. На атом рисунке показана часть дерева поиски, в которой демонстрируются чередующиеся ходы игроков мгм (значок О) и млх (значок х). Ходы выполняются до тех пор, пока в конечном итоге не будет достигнуто одно из терминальных состояний, которым могут быть назначены данные о полезности в соответствии с правилами игры Даже такие простые игры, как крестики-нолики, являются слишком сложными, чтобы можно бьшо привести в этой книге для них полное дерево игры, поэтому перейдем к описанию тривиальной игры, показанной на рис.
6.2. Возможные коды игрока МАХ из корневого узла обозначены как а,, а, и а,. Возможными ответами на ход а, для игрока М1И являются Ь„, Ь„Ь, и т.д. Данная конкретная игра заканчивается после того, как каждый игрок, МАХ и М1М, сделают по одному ходу. (Согласно терминологии теории игр, это дерево имеет глубину в один ход и состоит из сделанных двумя участниками ходов, каждый из которых называется сь полуходом.) Полезности терминальных состояний в этой игре находятся в пределах от 2 до 14. Глава 6.
Поиск в условиях противодействия 245 В этом определении оптимальной игры для игрока млх предполагается, что игрок М1М также играет оптимальным образом: он максимизирует результат, соответствующий наихудшему исходу игры для млх. А что было бы, если игрок мгм не играл оптимальным образом? В таком случае можно легко показать (упр. 6.2), что игрок млх добился бы еще большего. Могут существовать другие стратегии игры против соперников, играющих неоптимальным образом, которые позволяют добиться большего, чем минимаксная стратегия; но эти стратегии обязательно действуют хуже против соперников, играющих оптимально. Мнннмаксный алгоритм 'ск Мнннмаксный алгоритм (листинг 6.1) вычисляет минимаксное решение из текущего состояния. В нем используется простое рекурсивное вычисление минимаксных значений каждого состояния-преемника с непосредственной реализацией определяющих уравнений.
Рекурсия проходит все уровни вплоть до листьев дерева, а затем минимаксные значения Ъ. резервируются по всему дереву по мере обратного свертывания рекурсии. Например, в дереве, показанном на рис. 6.2, алгоритм вначале выполнил рекурсию с перехолом на нижние уровни до трех нижних левых узлов и применил к ним функцию полезности цС111Су, чтобы определить, что значения полезности этих узлов соответственно равны 3, 12 и 8.
Затем алгоритм определяет минимальное из этих значений, 3, и возвращает его в качестве зарезервированного значения узла в. Аналогичный процесс позволяет получить зарезервированные значения 2 для узла Си 2 для узла ел Наконец, берется максимальное из значений 3, 2 и 2 для получения зарезервированного значения 3 корневого узла.
Листинг 6.1. Алгоритм вычисления мипимаксиых решений. Ои возвращает действие, соответствующее наилучшему возможному ходу, т.е. действие, ведущее к результату с наилучшей полезностью, в соответствии с предположением, что противник играет с целью минимизации полезности. Функции мах-ча1ие и нлп-чазие используются для прохождения через все дерево игры вплоть до листьев, что позволяет определить зарезервированное значение некоторого состояния Еииосзоп мгпьщах-Пес1ягоп(ясасе) гесигпв действие асслоп Еприев: ясаее, текущее состояние игры и г- мах-ча1ие(ясасе) гесигп действие асслоп в множестве яиссеяяогя(ясасе) со значением т ЕипоСЕоп Мах-Ча1ие(ясасе) гееигпв значение полезности ее тегщьпа1-теяс(ясасе) еьеп гесигп цсШсу(ясасе) Ъ +- Еог а, я Еп яиссеявогз(ясаее) оо и ь- Мах(ч, Мьл-уа).ие(я)) гееигп ЕипоСЕоп Мьп-Ча1ие(ясасе) гееигпв значение полезности Ее тегщьпа1-теяс(ясасе) сноп гесигп цс111су(ясасе) ч г— Еог а, я Еп Биссевзогя(ясасе) Ло и <†Мьп(ъ, Мах-Ча1ие(я)) гееигп ч Часть П.
Решение проблем 246 Этот минимаксный алгоритм выполняет полное исследование дерева игры в глубину. Если максимальная глубина дерева равна ж и в каждом состоянии имеются Ь допустимых ходов, то временная сложность этого минимаксного алгоритма составляет 0(Ь 1. Для алгоритма, который формирует сразу всех преемников, пространственная сложность равна 0(1ла), а для алгоритма, который формирует преемников по одному, — 0(га) (см. с, 131).
Безусловно, в реальных играх такие затраты времени полностью неприемлемы, но данный алгоритм служит в качестве основы математического анализа игр, а также более практичных алгоритмов. Оптимальные решения в играх с несколькими игроками Многие популярные игры допускают наличие больше чем двух игроков.
Рассмотрим, как можно распространить идею минимаксного алгоритма на игры с несколькими игроками. С точки зрения технической реализации это сделать несложно, но при этом возникают некоторые новые и интересные концептуальные проблемы. Вначале необходимо заменить единственное значение для каждого узла вектором значений. Например, в игре с тремя игроками, в которой участвуют игроки л, и и 0, с каждым узлом ассоциируется вектор <ь;, ью >",>.
Для терминальных состояний этот вектор задает полезность данного состояния с точки зрения каждого игрока. (В играх с двумя игроками и нулевой суммой двухэлементный вектор может быть сокращен до единственного значения, поскольку значения в нем всегда противоположны.) Простейшим способом реализации такого подхода является применение функции ((с111су, которая возвращает вектор значений полезности. Теперь необходимо рассмотреть нетерминальные состояния. Рассмотрим узел в дереве игры, показанном на рис.
6.3, который обозначен как х В этом состоянии игрок с выбирает, что делать. Два варианта ведут к терминальным состояниям с векторами полезности <ъл=1, ъ;=2, ь,=б> и <т>=4, ь;=2, ~г;-3>. Поскольку б больше чем 3, игрок 0 должен выбрать первый ход. Это означает, что если достигнуто состояние х, то дальнейшая игра приведет к терминальному состоянию с полезностями <~„=1, т,=2, тс-б>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
