6.12. Игра двух лиц

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

Рассмотрим ситуацию, в которой два лица поочередно вносят частичные изменения в некоторую структуру. (Например, в систему размещения фигур на шахматной доске.) Пусть имеется некое стандартное начальное состояние (например, исходное положение фигур шахматистов) и «Книга правил», которая полностью определяет список допустимых ходов, т. е. допустимые изменения состояния каждого игрока за 1 шаг. Если существует конечное число различных состояний игры, то правила игры можно полностью характеризовать конечным направленным графом с двумя типами дуг. При этом каждое состояние рассматривается как вершина Вершины соединены дугой типа 1 (или 2) тогда и только тогда, когда игра может быть переведена из состояния в состояние с помощью некоторого допустимого хода первого (второго) игрока. Полная партия игры представляется на графе в виде пути, который состоит из дуг чередующихся типов и начинается в вершине начального состояния дугой, соответствующей ходу начинающего игру лица.

Предположим, что рассматриваемая игра такова, что ни одно из ее состояний не повторяется, т. е. соответствующий ей граф не имеет контуров. В этом случае

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

Замечание. Необходимо четко различать партию игры и полную игру. Например, в играх более общего вида некоторый игрок может находиться в «выигрывающем состоянии» и проиграть игру в конечном итоге. И, наоборот, он может находиться в «проигрывающем состоянии» и выиграть в конце игры. Рассматриваемый здесь частный вид игры можно назвать «игрой двух лиц с полной информацией, двумя исходами (проиграл — выиграл), заданной в полной форме».

Рис. 6.26.

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

1. Ни одна пара вершин, принадлежащих не связана дугой.

2. Любая вершина, не принадлежащая связана дугой, по крайней мере, с одной вершиной из

3. Все выигрывающие состояния принадлежат Свойства 1 и 2 иногда называются внутренней и внешней устойчивостью соответственно. Множество

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

Таким образом, если структура игры полностью определена и выделено ядро то игрок 1 в принципе имеет выигрышную стратегию при начальном состоянии вне (Если начальное состояние принадлежит то игрок 2 имеет выигрышную стратегию.) На практике структура нетривиальных игр оказывается, конечно, слишком сложной для представления в виде такого полного графа переходов. Однако, если правила игры таковы, что соответствующий граф, несмотря на сложность, имеет систематическую структуру, то можно найти методы получения элементов как и требуется в окрестности текущего состояния игры.

Замечание. Читателям, знакомым с игрой «Ним» и с выигрышными стратегиями этой игры, рассмотренные действия помогают определить принадлежность текущего состояния, т. е. оставшегося числа палочек в каждой кучке, к множеству кроме того, найти переход в если текущее состояние не принадлежит этому множеству.

Игра типа «переключение»

Рассматриваемая ниже игра была впервые сформулирована Шенноном, а ее решение предложено Леманом [58]. Игра проводится на графе двумя игроками. Оба игрока по договоренности выделяют две вершины, называемые конечными. Затем они поочередно делают ходы.

В соответствии с правилами ходов один из игроков на каждом ходе удаляет из графа одно из ребер и

стремится в конечном итоге разорвать все цепи, связывающие конечные вершины. Другой игрок на каждом ходе помечает одно из ребер. При этом помеченное ребро не может быть удалено из графа. Цель его состоит в сохранении хотя бы одной цепи между конечными вершинами. Игра, в которой может выиграть первый игрок, независимо от того, кто делает первый ход, называется игрой 1-го типа. Игра, в которой может выиграть второй игрок, — игрой 2-го типа. Игра, в которой может выиграть любой из игроков, сделавший первый ход, называется нейтральной. Далее мы остановимся кратко только на условиях, определяющих игру 2-го типа.

Теорема 6.8. Игра принадлежит ко типу тогда и только тогда, когда соответствующий граф содержит 2 дерева без общих ребер, все вершины которых одинаковы и имеют в своем составе обе конечные вершины.

Условие теоремы является достаточным. Действительно, если второй игрок может выиграть, делая второй ход, то, очевидно, он может выиграть и пойдя первым. Его ход должен всегда сохранять ребро, которое связывает две компоненты одного дерева, получающиеся в результате удаления некоторого ребра первым игроком. Так как оба дерева имеют одинаковое число ребер, второй игрок всегда сможет соединить две образовавшиеся компоненты одного дерева ребром, принадлежащим другому дереву.

Необходимость доказывается гораздо сложнее. Это доказательство здесь не рассматривается.

Разновидностью рассмотренной игры является игра «Gale» или «Bridgeit» (перекидывание мостов), которая описана в работах [27], [58]. Граф этой игры аналогичен показанному жирными линиями на рис. 6.27. Для большего удобства выполнения ходов игра делается симметричной. При такой форме первый игрок делает ходы на графе, показанном тонкими линиями, а второй — на графе, показанном жирными линиями. Цель первого состоит в построении цепи, соединяющей а цель второго — соединить цепью На каждом шаге игрок помечает одно из непомеченных ребер на своем графе (в начальный момент все ребра не помечены) такое, что оно не пересекает ни одно из ребер, помеченных его соперником. Графы, показанные на

рисунке, с небольшой погрешностью можно считать двойственными (чем вызвана погрешность?).

Рис. 6.27.

Для данного частного вида игры О. Гросс предложил простую выигрышную стратегию [2.7]. Эта игра относится к типу нейтральных, поэтому выигрышной оказывается «парная стратегия», при которой первый игрок всегда выбирает ребро, противоположное соответствующему (парному) ребру, выбранному вторым игроком (за исключением случая, когда это противоположное ребро уже выбиралось).