10.6. Игры с полной информацией и двумя участниками.

В данном разделе речь идет об играх с двумя игроками, которые будут именоваться МАХ и MIN по причинам, которые вскоре станут очевидными. Игрок МАХ ходит пер­вым, после чего игроки делают ходы по очереди до тех пор, пока игра не закончится. В конце игры игроку-победителю присваиваются очки, а на побежденного налагает­ся штраф. Игра может быть формально определена как своего рода задача поиска с описанными ниже компонентами.

• Начальное состояние, которое включает позицию на доске и определяет игро­ка, который должен ходить.

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

• Проверка терминального состояния, которая определяет, что игра закончена.

Состояния, в которых игра закончена, называются терминальными состояниями.

• Функция полезности (называемая также целевой функцией, или функцией воз­награждения), которая сообщает числовое значение терминальных состояний. В шахматах результатом является победа, поражение или ничья, со значениями + 1, -1 или 0. Некоторые игры имеют более широкий диапазон возможных результатов; например, количество очков в нардах может составлять от +192 до -192.

Начальное состояние и допустимые ходы каждой стороны определяют дерево игры для данной игры. На рис. 10.22 показана часть дерева игры в крестики-нолики. Из начального состояния игрок МАХ имеет девять возможных ходов. Ходы чередуют­ся так, что МАХ ставит значок Х, а MIN значок О, до тех пор пока не будут достигнуты листовые узлы (вершины), соответствующие терминальным состояниям, таким, что один игрок поставил три своих значка в один ряд или заполнены все клетки. Число под каждым листовым узлом указывает значение полезности соответствующего терминального состояния с точки зрения игрока МАХ; предполагается, что высокие значения явля­ются благоприятными для игрока МАХ и неблагоприятными для игрока MIN (именно поэтому в теории этим игрокам присвоены такие имена). Задача игрока МАХ состоит в использовании дерева поиска (особенно данных о полезности терминальных со­стояний) для определения наилучшего хода.

10.6.1. Оптимальные стратегии.

При решении обычных задач поиска оптимальное решение для игрока МАХ должно представлять собой последовательность ходов, ведущих к цели - к терми­нальному состоянию, которое соответствует выигрышу. С другой стороны, в игре участвует также игрок MIN, который имеет другое мнение по этому поводу. Это оз­начает, что игрок МАХ должен найти надежную стратегию, позволяющую опреде­лить ход игрока МАХ в начальном состоянии, затем ходы игрока МАХ в состояниях, ставших результатом любого возможного ответа игрока MIN, а затем ходы МАХ в со­стояниях, ставших результатом любого возможного ответа MIN на те ходы, и т.д. Грубо говоря, оптимальная стратегия приводит к итогу, по меньшей мере, такому же благо­приятному, как и любая другая стратегия, в тех условиях, когда приходится играть с противником, не допускающим ошибок. Прежде всего рассмотрим, как найти эту оп­тимальную стратегию, даже притом что для МАХ часто будет неосуществимой задача ее исчерпывающего вычисления в играх, более сложных, чем крестики-нолики.

МАХ(х)

MIN(0)

х

	х

		х

		х

х

	х

		х

х

	х

х		о

х
о

х	о

....................... МАХ(х)

х	о	х

х	о
х

х	о
	х

.......................... MIN(0)

....... ......... ....... .................

х	о	х
	о	х
	о

х	о	х
о	о	х
х	х	о

х	о	х
	х
х	о	о

........ Заключительное состояние TERMINAL

-1 0 +1 Полезность

Рис. 10.21. (Частичное) дерево поиска для игры крестики-нолики. Верхний узел представляет собой начальное состояние, а первым ходит игрок МАХ, ставя значок Х в пустой клетке. На этом ри­сунке показана часть дерева поиска, в которой демонстрируются чередующиеся ходы игроков MIN (значок О) и МАХ (значок Х). Ходы выполняются до тех пор, пока в конечном итоге не будет дос­тигнуто одно из терминальных состояний, которым могут быть назначены данные о полезности в соответствии с правилами игры

Даже такие простые игры, как крестики-нолики, являются слишком сложными, чтобы можно было привести здесь для них полное дерево игры, поэтому пе­рейдем к описанию тривиальной игры, показанной на, рис: 10.22. Возможные коды иг­рока МАХ из корневого узла обозначены как а₁, а₂ и а₃. Возможными ответами на ход а₁ для игрока MIN являются b₁, b₂, b₃ и т.д. Данная конкретная игра заканчива­ется после того, как каждый игрок, МАХ и MIN, сделают по одному ходу. (Согласно терминологии теории игр, это дерево имеет глубину в один ход и состоит из сделан­ных двумя участниками ходов, каждый из которых называется полуходом.) По­лезности терминальных состояний в этой игре находятся в пределах от 2 до 14.

А

МАХ 3

а₁

а₂

а₃

3

MIN

C

В

D

b₃

c₃

d₃

2 2

c₁₃

d₁

b₁

c₂

b₂

d₂

2

3 12 8 2 4 6 14 5

Р ис. 10.22. Дерево игры с двумя полуходами. Узлы представляют собой "узлы МАХ", в которых очередь хода принадлежит игроку МАХ, а узлы , рассматриваются как "узлы MIN". Терминальные узлы показывают значения полезности для МАХ; остальные узлы обозначены их мини­максными значениями. Лучшим ходом игрока МАХ от корня является а₁, поскольку ведет к преемнику с наибольшим минимаксным значени­ем, а наилучшим ответом MIN является b₁ поскольку ведет к преем­нику с наименьшим минимаксным значением.

При наличии дерева игры оптимальную стратегию можно определить, исследуя

минимаксное значение каждого узла, которое можно записать как Minimax­-Value (п). Минuмаксным значением узла является полезность (для МАХ) пребывания в соответствующем состоянии, при условии, что оба игрока делают ходы оптималь­ным образом от этого узла и до узла, обозначающего конец игры. Очевидно, что ми­нимаксным значением терминального состояния является просто его полезность.

Более того, если есть выбор, игрок МАХ должен предпочесть ход, ведущий в состояние с максимальным значением, а игрок MIN - ведущий в состояние с минималь­ным значением. Поэтому имеет место приведенное ниже соотношение.

Состояние (п), если п - терминальное состояние

Max Minimax-Value(s), если s- узел МАХ

Minimax-Value(п) = s € Преемник (п)

Min Minimax-Value(s), если s- узел MIN

s € Преемник (п)

Применим эти определения к дереву игры, показанному на рис. 10.22. Терминаль­ные узлы на низшем уровне уже обозначены числами, которые указывают их полез­ность. Первый узел MIN, обозначенный как В, имеет трех преемников со значениями 3, 12 и 8, поэтому его минимаксное значение равно 3. Аналогичным образом, другие два узла MIN имеют минимаксное значение, равное 2. Корневым узлом яв­ляется узел МАХ; его преемники имеют минимаксные значения 3, 2 и 2, поэтому сам корневой узел имеет минимаксное значение 3. Можно также определить по­нятие минимаксного решения, принимаемого в корне дерева: действие а₁ является оптимальным выбором для игрока МАХ, поскольку ведет к преемнику с наивыcшим минимаксным значением.

В этом определении оптимальной игры для игрока МАХ предполагается, что игрок MIN также играет оптимальным образом: он максимизирует результат, соответст­вующий наихудшему исходу игры для МАХ. А что было бы, если игрок MIN не играл оптимальным образом? В таком случае можно легко показать, что игрок МАХ добился бы еще большего. Могут существовать другие стратегии игры против соперников, играющих неоптимальным образом, которые позволяют добиться большего, чем минимаксная стратегия; но эти стратегии обязательно действуют ху­же против соперников, играющих оптимально.