Как пример применения понятий графа и дерева рассмотрим дискретную игру двух лиц А и В с открытой информацией.

Игра представляет собой:

- множество ситуаций Н={Н_i } (среди них – начальная ситуация Н0);

-правила игры, определяющие возможные переходы из одной ситуации в другую: для каждой ситуации Нi определено множество Тi={Н_(i_1 ),Н_(i_2 ),….,Н_(i_k ) }ситуаций, в которые можно перейти ходом одного из игроков;

- для некоторых ситуаций Нj множество Тj пустое – такие ситуации называются заключительными; каждой из них приписан один из символов А или В, называемых результатом игры (возможен вариант один из трех символов А, В, 0).

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

Дискретная игра может быть представлена орграфом {H,T}:H – множество вершин, Т(Нi) задает множество дуг, исходящих из Нi. Партия (тур) представляет собой траекторию с началом в Н0 и концом в одном из заключительных состояний; однако возможен вариант, когда партия бесконечна, если, например, в графе имеется контур. В дальнейшем будем рассматривать только конечные игры.

Для исследования игры удобно использовать развернутую форму ее графа – в виде корневого дерева. Н0 – корень дерева; ситуации Т(Н0) соответствует множество вершин 1-го яруса; для каждой вершины множество Т(α) составляет множество соседних с ней вершин 2-го яруса и т.д. в вершинах четных ярусов (0, 2, 4, …) ход принадлежит 1-му игроку (А), в нечетных (1, 3, 5,…) - 2-му (В). При таком представлении игры одна и та же ситуация соответствует многим вершинам, если в нее можно попасть из Н0 различными путями: в дереве в каждую вершину ведет единственный путь из Н0, определяемый начальным отрезком партии до этой ситуации.

Стратегия f игрока А – это некоторое соответствие f(H_i)=H_i^/∈T_i, назначающее для каждой ситуации Нi, в которой может оказаться игрок А, один определенный ход. Аналогично определяется стратегия игрока В.

Если выбрана стратегия 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 спичек, и последнюю спичку берет игрок А.

Литература.

Н.Кристофидес ”Теория графов, алгоритмический подход” Мир 1978

К.Берж «Теория графов и ее применение», Иностр.лит.,1985г