Оптимальные стратегии
При решении обычных задач поиска оптимальное решение для игрока МАХ должно представлять собой последовательность ходов, ведущих к цели — к терминальному состоянию, которое соответствует выигрышу. С другой стороны, в игре участвует также игрок MIN, который имеет другое мнение по этому поводу. Это означает, что игрок МАХ должен найти надежную стратегию, позволяющую определить ход игрока МАХ в начальном состоянии, затем ходы игрока МАХ в состояниях, ставших результатом любого возможного ответа игрока MIN, а затем ходы МАХ в состояниях, ставших результатом любого возможного ответа MIN на те ходы, и т.д. Грубо говоря, оптимальная стратегия приводит к итогу, по меньшей мере, такому же благоприятному, как и любая другая стратегия, в тех условиях, когда приходится играть с противником, не допускающим ошибок. Прежде всего рассмотрим, как найти эту оптимальную стратегию, даже притом что для МАХ часто будет неосуществимой задача ее исчерпывающего вычисления в играх, более сложных, чем крестики-нолики.
Даже такие простые игры, как крестики-нолики, являются слишком сложными, чтобы можно было привести в этой книге для них полное дерево игры, поэтому перейдем к описанию тривиальной игры, показанной на рис. 6.2. Возможные коды игрока МАХ из корневого узла обозначены как al9 а2 и а3. Возможными ответами на ход а1 для игрока MIN являются Ьх, Ь2, Ь3 и т.д. Данная конкретная игра заканчивается после того, как каждый игрок, МАХ И MIN, сделают по одному ходу. (Согласно терминологии теории игр, это дерево имеет глубину в один ход и состоит из сделанных двумя участниками ходов, каждый из которых называется полуходом.) Полезности терминальных состояний в этой игре находятся в пределах от 2 до 14.
При наличии дерева игры оптимальную стратегию можно определить, исследуя минимаксное значение каждого узла, которое можно записать как Minimax-Value (п). Минимаксным значением узла является полезность (для МАХ) пребывания в соответствующем состоянии, при условии, что оба игрока делают ходы оптимальным образом от этого узла и до узла, обозначающего конец игры. Очевидно, что минимаксным значением терминального состояния является просто его полезность. Более того, если есть выбор, игрок МАХ должен предпочесть ход, ведущий в состояние с максимальным значением, а игрок MIN — ведущий в состояние с минимальным значением. Поэтому имеет место приведенное ниже соотношение.
Применим эти определения к дереву игры, показанному на рис. 6.2. Терминальные узлы на низшем уровне уже обозначены числами, которые указывают их полезность. Первый узел MIN, обозначенный как в, имеет трех преемников со значениями 3, 12 и 8, поэтому его минимаксное значение равно 3. Аналогичным образом, другие два узла MIN имеют минимаксное значение, равное 2. Корневым узлом является узел МАХ; его преемники имеют минимаксные значения 3, 2 и 2, поэтому сам корневой узел имеет минимаксное значение 3. Можно также определить понятие минимаксного решения, принимаемого в корне дерева: действие а1 является оптимальным выбором для игрока МАХ, поскольку ведет к преемнику с наивысшим минимаксным значением.
В этом определении оптимальной игры для игрока МАХ предполагается, что игрок MIN также играет оптимальным образом: он максимизирует результат, соответствующий наихудшему исходу игры для МАХ. А что было бы, если игрок MIN не играл оптимальным образом? В таком случае можно легко показать (упр. 6.2), что игрок МАХ добился бы еще большего. Могут существовать другие стратегии игры против соперников, играющих неоптимальным образом, которые позволяют добиться большего, чем минимаксная стратегия; но эти стратегии обязательно действуют хуже против соперников, играющих оптимально.