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

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

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

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

Рис. 16.1