Задание позиционной игры в виде дерева

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

Основными свойствами дерева игры являются:

· дерево содержит одну единственную начальную вершину (“корень” дерева), в которую не входит ни одна ветвь;

· дерево имеет не менее одной вершины, из которой не выходит ни одна ветвь. Эти вершины называются конеч­ными вершинами;

· из корня дерева имеется единственный путь к каждой из остальных вершин дерева.

Рис.3.16. Дерево игры с неполной информацией

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

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

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

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

Очевидно, если в игре нет случайных ходов, и каждый из игроков выбрал свою стратегию, то исход игры однозначно определен. Для игры со случайными ходами результат партии становится случайной величиной, поэтому необходимо случайные выигрыши заменить их математическими ожиданиями. Как совокупность всех решений, которые должен принять игрок, можно описать как одно решение – выбор стратегии, так и совокупность случайных ходов, может быть заменена одним случайным испытанием Н.

В рассматриваемомпримере (рис.3.16) случайное испытание Н может иметь следующие исходы:

Н =|(Г, 3), (Г, 2), (Р, 3), (Р, 2)|, с вероятностями , где Г – означает выпадение “герба”, Р – “решки”, а цифры 2, 3 соот­ветствуют случайному выбору на четвертом ходу.

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

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

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

При вычерчивании дерева игры классы информации обводят замкнутой линией.

Игрок всегда знает, какому классу информации соответствует состояние игры в данный момент, но не знает конкретной вершины этого класса.

Классы информации (информационные множества) должны удовлетворять следующим условиям:

1. содержать вершины только одного игрока;

2. каждая вершина может принадлежать только одному классу информации;

3. вершины класса информации соответствуют только одному временному ходу;

4. из всех вершин, составляющих класс информации, может выходить только одинаковое количество ветвей.

Дерево, изображенное на рис.3.16, соответствует следу­ющей игре:

Первый игрок выбирает одно из двух направлений (“налево” или “направо”). Ход “налево” оценивается тремя баллами, а “направо” – четырьмя. Затем бросается жребий (монета), и, если выпадает “герб”, второму игроку сообщается предыдущий выбор первого игрока. Если выпадает “решка”, то второй игрок знает лишь, что он находится в классе информации V ₁, но не знает, в какой из двух вершин этого класса он находится.

Второй игрок выбирает одно из двух направлений (“налево” или “направо”). Ход “налево” оценивается пятью баллами, а “направо” – двумя. Четвертый ход является опять случайным и состоит в выборе с равными вероятностями одного из направлений: “налево”, “направо”, которые оцениваются тремя и двумя баллами соответственно. Поскольку вероятности выбора направления при случайном ходе одинаковы (равны 0, 5), то их можно на графическом изображении дерева игры и не указывать.

Числа, выбранные в первом, третьем и четвертом ходах, складываются, и полученная сумма уплачивается вторым игроком первому, если она четная, в противном случае первый игрок платит второму.

Пространства Ф ₁ и Ф ₂ всех возможных стратегий игро­ков 1 и 2 в рассматриваемом примере следующие:

Ф ₁=|(3), (4)|;

Ф ₂=|(3, Г, 5), (3, Г, 2), (3, Р, 5), (3, Р, 2), (4, Г, 5), (4, Г, 2), (4, Р, 5),
(4, Р, 2)|,

где первое число каждой стратегии в пространстве Ф ₂ соот­ветствует выбору первого игрока, второе число – выпаданию “герба” или “решки” (“Г” – выпал “герб”; “Р” – выпала “решка”), третье – выбору второго игрока пятерки или двойки.

Очевидно, что если в игре нет случайных ходов и каждый из игроков выбрал свою стратегию, то исход игры однозначно определен.

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