Графическое представление позиционной игры

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

Деревом позиционной игры называется плоская фигура, состоящая из узлов и конечного числа направленных вверх прямолинейных отрезков, соединяющих эти узлы, каждый узел обозначается цифрой, соответствующей номеру игрока, делающего ход, и изображает ход этого игрока, поэтому каждому ходу соответствует набор узлов, расположенных на одном определенном уровне. На самом низшем уровне имеется только один узел — основание дерева, каждый узел соединяется только с одним узлом на низшем уровне, каждый прямолинейный отрезок означает выбор, сделанный игроком на данном ходе, и обозначается номером, соответствующим сделанному выбору. Если в игре используется ход, осуществляемый не игроком, а случайным механизмом, то обычно узлу, соответствующему данному ходу, присваивается номер 0 (нуль). Вершинами дерева являются окончания прямолинейных отрезков, исходящих из узлов последнего уровня. Ветвью дерева называется ломаная линия, состоящая из прямолинейных отрезков-дерева, которая начинается в самом нижнем узле и идет вверх последовательно через соответствующие узлы до вершины дерева. Каждая ветвь дерева отображает партию игры. Для изображения необходимых сведений о сделанных выборах при определенных ходах игроков на дереве игры отмечают пунктиром так называемые информационные множества узлов определенного игрока. В каждое информационное множество входят только неразличимые для игрока узлы, т. е. только те узлы, для каждой пары из которых соответствующий игрок не может точно указать, в какой точке дерева он находится, делая этот ход.

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

Рис. 16.1

Определение позиционной игры

Позиционной игрой будем называть конечную игру п игроков состоящую из:

1. Дерева Т (понятие дерева игры было дано в 3.2 этой главы).

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

3. Набора чисел , таких, что каждой точке разветвления дерева Т ставится в соответствие число, указывающее, какой игрок делает очередной ход в рассматриваемой точке (число 0 означает, что в этой точке применяется случайный ход).

4. Сопоставления каждой точке разветвления Т дерева, соответствующей случайному ходу, элемента множества где к — число альтернатив (выборов) в точке т. . число прямых, выходящих из точки полный набор вероятностей применения альтернатив.

5. Разбивки точек разветвления на непересекающиеся и полные множества (информационные множества), удовлетворяющие следующим условиям:

а) все точки разветвления, принадлежащие данному информационному множеству, относятся, согласно пункту 3, к одному игроку;

б) все точки разветвления, принадлежащие одному информационному множеству, имеют одинаковое число альтернатив, которые мы будем нумеровать справа налево;

в) если (см, пункт 3) точке разветвления поставлено в соответствие число 0, то информационное множество, в котором находится состоит из одной точки;

г) если S — партия игры, т. е. ломаная линия, идущая от основания дерева к одной из его вершин, и если А — любое информационное множество, то существует не больше одной точки разветвления, принадлежащей обоим множествам S и A,

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