Дискретно-непрерывная математика (стр. 74 )

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

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

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

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

Рис. 5.26.

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

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

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

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

3. Все выигрывающие состояния принадлежат S.

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

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

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

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

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

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

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

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

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

Разновидностью рассмотренной игры является игра «Gale» или «Bridge-it» (перекидывание мостов. Граф этой игры ана­логичен показанному жирными линиями на рис. 5.27.

Рис. 5 27.

Для большего удобства выполнения ходов игра делает­ся симметричной. При такой форме первый игрок дела­ет ходы на графе, показанном тонкими линиями, а вто­рой —- на графе, показанном жирными линиями. Цель первого состоит в построении цепи, соединяющей w' и w", а цель второго — соединить цепью v' и v". На каж­дом шаге игрок помечает одно из непомеченных ребер на своем графе (в начальный момент все ребра не по­мечены) такое, что оно не пересекает ни одно из ребер, помеченных его соперником. Графы, показанные на рисунке, с небольшой погрешностью можно считать двойственными (чем вызвана погрешность?).

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

5.13. Игры на шахматной доске

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

Рис. 5.28.

Сопос­тавляя с каждой клеткой вершину графа, можно полу­чить матрицу смежности вершин V для соответствующе­го графа.

Упражнение 17. С помощью элементов седьмой строки и третьего столбца матрицы V4 найти число способов, которыми можно перейти из седьмой клетки в третью за четыре хода. Найти элемент (7, 3) из V+V2+... +V5 и определить число способов перехода из седьмой клетки в третью при числе ходов меньше чем шесть. Наконец, поль­зуясь диагональными элементами V5, определить число способов воз­врата фигуры в исходное положение за пять ходов.

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

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

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