Лекция: Оптимальные стратегии.

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

МАХ(х)

MIN(0)

МАХ(х)

MIN(0)

……… .................

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

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

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

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

МАХ 3

MIN

3 12 8 2 4 6 14 5

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

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

минимаксное значение каждого узла, которое можно записать как 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. Можно также определить по­нятие минимаксного решения, принимаемого в корне дерева: действие а1 является оптимальным выбором для игрока МАХ, поскольку ведет к преемнику с наивыcшим минимаксным значением.

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