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

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

МАХ(х)

MIN(0)

х

	х

		х

		х

х

	х

		х

х

	х

х		о

х
о

х	о

МАХ(х)

х	о	х

х	о
х

х	о
	х

MIN(0)

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

х	о	х
	о	х
	о

х	о	х
о	о	х
х	х	о

х	о	х
	х
х	о	о

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

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

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

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

МАХ 3

MIN

d3

b3

c3

D

C

В

2 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 не играл оптимальным образом? В таком случае можно легко показать, что игрок МАХ добился бы еще большего. Могут существовать другие стратегии игры против соперников, играющих неоптимальным образом, которые позволяют добиться большего, чем минимаксная стратегия; но эти стратегии обязательно действуют ху­же против соперников, играющих оптимально.