Как пример применения понятий графа и дерева рассмотрим дискретную игру двух лиц А и В с открытой информацией. Игра представляет собой:
- множество ситуаций Н = {Hi} (среди них - начальная ситуация Н0);
- правила игры, определяющие возможные переходы из одной ситуации в другую: для каждой ситуации Нi определено множество Тi={ Hi1, Нi2 ,..., Hik } ситуаций, в которые можно перейти ходом одного из игроков;
- для некоторых ситуаций Hj множество Tj пустое - такие ситуации называются заключительными; каждой из них приписан один из символов А или В, называемых результатом игры (возможен вариант: один из трех символов А, В, 0). Партия (тур) игры состоит в том, что игроки по очереди (будем считать что первый ход принадлежит игроку А) делают допустимые правилами ходы и, начиная с ситуации Н0, переводят игру в очередную ситуацию. При попадании в любую заключительную ситуацию игра заканчивается, и результат определяет, какой из игроков - А или В - выиграл в этой партии (результат 0, если он является допустимым, означает ничью).
Дискретная игра может быть представлена орграфом {Н, T): H - множество вершин, Т(Нi) задает множество дуг, исходящих из Hi. Партия (тур) представляет собой траекторию с началом в Н0 и концом в одном из заключительных состояний; однако возможен вариант, когда партия бесконечна, если, например, в графе имеется контур. В дальнейшем будем рассматривать только конечные игры.
Примером конечной игры (с возможностью ничейного исхода) являются шахматы. Правила шахматной игры определяют допустимые ходы и обеспечивают конечность игры: ничья после троекратного повторения позиции, а также после 50 ходов без взятий, превращении и ходов пешек.
Отметим кстати, что позиция фигур на шахматной доске (даже с указанием очередности хода) не определяет, вообще говоря, ситуации полностью; иногда необходимо знание предыстории партии: двигался ли король - для возможности рокировки и др.
Для исследования игры удобно использовать развернутую форму ее графа - в виде корневого дерева. Н0 - корень дерева; ситуации Т(Н0) соответствует множество вершин 1-го яруса; для каждой вершины множество Т(
) составляет множество соседних с ней вершин 2-го яруса и т.д В вершинах четных ярусов (0, 2, 4,...) ход принадлежит 1-му
игроку (А), в нечетных (1,3, 5,..) - 2-му (В). При таком представлении игры одна и та же ситуация соответствует многим вершинам, если в нее можно попасть из Н0 различными путями: в дереве в каждую вершину ведет единственный путь из Н0, определяемый начальным отрезком партии до этой ситуации. Для конечной игры дерево имеет конечное число ярусов, и все концевые вершины (они могут находиться на разных ярусах) соответствуют заключительным ситуациям: им приписаны значения А или В (или 0 при возможности ничейного исхода). Длину максимального пути назовем длиной игры.
Существенное свойство рассматриваемого нами типа игр: игрок при своем ходе знает, в какой ситуации он находится и в какие ситуации ведет каждый из допустимых ходов. К такому типу игр не относится большинство карточных игр и домино, поскольку игроку обычно не известен расклад; тем самым при выборе хода он не знает текущей ситуации. По другой причине к этому типу игр не относятся, например, нарды или лото, т. к. возможность выбора хода зависит от результат стохастического эксперимента - бросания игральных костей. Стратегия f игрока А - это некоторое соответствие f(Hi) = H'i e Ti назначающее для каждой ситуации Hi, в которой может оказаться игрок A один определенный ход. Аналогично определяется стратегия игрока B.
Стратегия f игрока А - это некоторое соответствие f(Hi) = H'i Ti назначающее для каждой ситуации Hi, в которой может оказаться игрок A один определенный ход. Аналогично определяется стратегия игрока B.
Если выбрана стратегия f игрока А и стратегия g игрока В, то тем самым определена партия (f, g), поскольку в каждой не заключительной ситуации однозначно определен переход в следующую ситуацию. Исход игры определяется заключительной ситуацией, в которую приходит, партия.
Выбор стратегии игроком А (соответственно, игроком В) означает указание для каждой вершины четного (соответственно, нечетного) яруса ровно одной исходящей дуги. Выбор пары стратегий (f, g) выделяет ровно один путь из Н0 в одну из заключительных вершин.
Стратегия f игрока А называется выигрышной (соответственно, беспроигрышной), если для любой стратегии g игрока В партия (f, g) заканчивается выигрышем игрока А (соответственно, выигрышем или ничьей). Выигрышная и беспроигрышная стратегии игрока В определяются симметрично.
![]() | Замечание. Выигрышная стратегия может быть только у одного из игроков. Беспроигрышная стратегия может быть как у одного, так и у обоих игроков. |
Чтобы проиллюстрировать понятие стратегии рассмотрим игру НИМ. На столе лежат N спичек. Игрокам разрешается по очереди удалять 1,2 или 3 спички. Проигрывает тот, кто удаляет последнюю спичку. Примерами стратегий начинающего игрока могут быть такие:
- при каждом ходе брать 1 спичку;
- при первом ходе взять 2 спички, а затем брать столько же, сколько взял второй игрок при предыдущем ходе, пока на столе больше 5 спичек; далее - брать 1 спичку.
При N = 20 начинающий игрок обладает выигрышной стратегией: взять при первом ходе 3 спички, и в дальнейшем, при своем ходе брать (4 - b) спичек, где b - число спичек, взятых игроком В на предыдущем ходе. При такой стратегии после хода игрока А на столе будет оставаться последовательно 17, 13, 9, 5, 1 спичек, и игрок В вынужден взять последнюю. Если же N = 25, то выигрышная стратегия имеется у игрока В: брать всегда (4 - а) спичек, где а - число спичек, взятых игроком А на предыдущем ходе. Тогда после его хода на столе будет оставаться последовательно 21, 17, 13, 9, 5, 1 спичек, и последнюю спичку берет игрок А.
На рисунке 8 приведено дерево игры для N = 5. В кружках - число спичек на столе в данной ситуации. Заштрихованные кружки -заключительные позиции с указанием результата (выигрыш А или В). Двойными стрелками обозначены наилучшие стратегии игроков (не указан первый ход А и переходы в заключительные позиции, когда нет выбора). Во всех вершинах первого яруса у игрока В есть выигрышные ходы, поэтому при любом первом ходе А игрок В выигрывает, если придерживается указанной стратегии. Для игры НИМ, где результат определяется тем, кто из игроков сделал заключительный ход, все концевые вершины четных ярусов свидетельствуют о выигрыше А, а нечетных ярусов - В. В общем случае игр - это не так.
Для конечной игры справедливы две следующих теоремы.
Теорема 1. Если игра не допускает ничейного исхода, то для одного из игроков существует выигрышная стратегия.
Теорема 2. В игре, допускающей ничейный исход, хотя бы один из игроков обладает беспроигрышной стратегией.
![]() | Замечание. Обратите внимание, что в теоремах утверждается не тот очевидный факт, что каждая партия заканчивается в первом случае победой одного из игроков, а во втором - победой или ничьей; смысл первой теоремы - в наличии такой стратегии, следование которой приводит к победе при любой стратегии противника (во втором случае, по крайней мере к ничьей). |
Доказательство теоремы 1 будем вести индукцией подлине игры t.
Если t = 1, то дерево игры имеет вид, изображенный на рисунке 9а.
Возможны два варианта
- среди ситуаций Н1,..., Hk (все они - заключительные) имеется! ситуация Н, помеченная символом А, означающим выигрыш игрока А; в этом случае начинающий имеет выигрышную стратегию f(H0) = Нi , т.е. выбор хода из Н0 в Нi;
- все ситуации Н1,..., Hk помечены символом В; тогда выигрышная стратегия (пустое множество ходов) - у игрока В: начинающий сам при любом своем ходе попадает в заключительную позицию с выигрышем игрока В.
Пусть теперь t > 1 (рисунок 9 6). Если удалить корень и исходящие из него дуги, то останется некоторое количество корневых поддеревьев, в каждом из которых корнем является вершина 1-го яруса первоначального дерева. Эти поддеревья представляют варианты игры, возникающие после того или иного первого хода игрока А, но начинающим в каждой из ветвей является уже игрок В. Все эти подыгры имеют длину меньше t; поэтому, по предположению индукции, в каждой из них у одной из сторон имеется выигрышная стратегия. Возможны два варианта:
- во всех подыграх выигрышная стратегия у начинающего игрока, (В); тогда в исходной игре выигрышная стратегия у игрока В: какой бы первый ход ни выбрал игрок А, его противник В может выбрать свою выигрышную стратегию в полученной подыгре;
- хотя бы в одной из подыгр есть выигрышная стратегия у не начинающего игрока (т.е. А); тогда в исходной игре выигрышная стратегия - у игрока А: она состоит в том, чтобы первым ходом попасть именно в эту подыгру, в ней выбрать свою выигрышную стратегию; в остальных подыграх можно выбрать стратегию произвольно - все равно партия в эти подыгры не переходит. Теорема доказана.
Доказательство теоремы 2 проводится таким же образом. При этом может оказаться, что беспроигрышная стратегия имеется у обоих игроков.
![]() |
Замечание. Для шахматной (а также шашечной) игры справедлива 1теорема 2, т.е. либо белые, либо черные, либо обе стороны имеют беспроигрышную стратегию. Однако в настоящее время не известно, у какой именно стороны имеется беспроигрышная стратегия и имеется ли у какой-либо из сторон выигрышная стратегия. |
![]() |
Tест для самоконтроля |