4.12. ИГРЫ

Подход, связанный с расчленением задачи на совокупность подзадач, может быть использован также для поиска игровых стратегий для некоторых типов игр. Мы будем рассматривать игры двух лиц с полной информацией. В них играют два игрока, делающие свои ходы поочередно. Им полностью известно все, что было сделано и что может быть сделано в этой игре. Конкретнее, мы будем интересоваться играми, в которых один из двух игроков выигрывает (а другой проигрывает) или же результат получается ничейным. Некоторыми примерами игр такого типа служат шашки, тик-так-ту, шахматы, и ним. Мы не собираемся рассматривать здесь те игры, в которых результат зависит хотя бы частично от случая: так, мы исключаем игральные кости и большинство карточных игр. (Впрочем наш анализ можно было бы обобщить, включив в рассмотрение некоторые типы игр, содержащих случайный элемент.)

В подходе, основанном на сведёнии задачи к совокупности подзадач, выигрышная стратегия ищется в процессе доказательства того, что эта игра может быть выиграна. Поэтому в описании задачи должно содержаться описание того состояния (или конфигурации) игры, про которое утверждается, что из

него достижение выигрыша может быть гарантировано. Например, в шахматах конфигурацией является полное описание положений всех фигур на доске и указание, кому принадлежит следующий ход.

Пусть именами игроков будут ПЛЮС и МИНУС. Рассмотрим задачу нахождения игровой стратегии для игрока ПЛЮС, отправляясь от некоторой конфигурации Индекс принимает значения или причем представляет собой конфигурацию, в которой следующий ход принадлежит игроку ПЛЮС, а — конфигурацию, в которой следующий ход за игроком МИНУС. Мы хотели бы иметь возможность доказать, что игрок ПЛЮС может выиграть, исходя из конфигурации X если же такого доказательства найти не удастся, то мы хотели бы иметь возможность доказать, что, исходя из конфигурации игрок ПЛЮС может по крайней мере добиться ничьей. Обозначим через задачу доказательства того, что ПЛЮС может выиграть, отправляясь от конфигурации

Допустимые в этой игре ходы порождают схему сведения игровых задач к совокупности подзадач. Предположим, что очередь делать ход в конфигурации за игроком ПЛЮС, и предположим, что имеется допустимых ходов, приводящих к конфигурациям Тогда для доказательства мы должны иметь возможность доказать ту или иную из . С другой стороны, если очередь делать ход в конфигурации за игроком МИНУС и если имеется М допустимых ходов, приводящих конфигурациям то для доказательства мы должны уметь доказывать каждую из задач Конечно, подобное сведение к подзадачам применимо и в том случае, когда мы пытаемся доказать лишь, что возможны ничьи.

Применение этих операторов сведения задачи порождает структуру, которая часто называется деревом игры. Элементарные задачи даются правилами окончания игры, а процесс доказательства продолжается до тех пор, пока не будет установлено, что решающее дерево оканчивается на элементарных задачах. (В большинстве игр, представляющих интерес, таких, как шахматы, и шашки, построить полные решающие деревья не представляется возможным. В следующей главе мы рассмотрим некоторые специализированные методы перебора на игровых деревьях, в которых строятся частичные деревья.)

Мы проиллюстрируем эти соображения на простом примере игры, называемой «игра Гранди», и применим методы сведения задачи к совокупности подзадач для поиска стратегии игрока ПЛЮС.

Правила игры Гранди таковы. Перёд двумя играющими расположена единственная кучка предметов, например стопка монет. Первый игрок делит исходную стопку на две новые стопки, которые должны быть неравными. В дальнейшем каждый из игроков, когда приходит его очередь делать ход, делает то же самое с одной из стопок монет.

Рис. 4.15. (см. скан) «И/ИЛИ» граф для игры Гранди.

Игра продолжается до тех пор, пока все стопки не будут содержать по одной-две монеты, после чего игра заканчивается, поскольку дальнейшее ее продолжение невозможно. Проигрывает тот из игроков, который первым окажется в положении, когда игра не может продолжаться.

Начнем со стопки, содержащей семь монет, и пусть первым делает ход игрок МИНУС. Конфигурацией в этой игре является последовательность чисел, отражающая числа монеток в различных стопках, плюс указание на то, чей ход. Так, — начальная конфигурация.

В положении игрока МИНУС имеются три альтернативных хода, приводящих к конфигурациям или

Имеются всего три конфигурации, в которых игрок, имеющий право наследующий ход, проигрывает:

Единственной элементарной задачей (означающей выигрыш для игрока ПЛЮС) является, таким образом,

Применив нашу процедуру сведения задачи к совокупности подзадач (отправляясь от задачи мы получаем «И/ИЛИ» граф, показанный из рис. 4.15. Жирными дугами на этом графе выделено решающее дерево, а в двойных прямоугольниках размещены элементарные задачи.

Если мы изменим игру так, чтобы первым начинал игрок ПЛЮС (отправляясь от конфигурации то окажется, что мы не можем доказать (Второй игрок всегда может выиграть.) Пытаясь доказать мы придем в конце концов к ситуации, когда невозможно будет построить новые вершины, и тогда можно было бы определить, что начальная вершина неразрешима. (Например, в соответствии с правилами игры у конфигурации нет следующих за ней конфигураций.)