Определение дискретно-позиционной игры двух игроков по Оуэну:
позиционная игра определена, если задано 6 элементов игры:
1) связный ориентированный граф-дерево игры с выделенной вершиной А, являющийся начальной позицией игры. Каждая вершина графа называется позицией игры и соответствует ее определенному состоянию.
Каждое ребро графа называется альтернативой в развитии игры и соответствует определенному ходу в игре.
Вершину Х будем называть конечной позицией игры, если она не предшествует никакой другой позиции игры.
Реализацией или партией игры будем называть любую цепь AX, проходящую по ребрам и вершинам графа-дерева игры и соединяющую начальную позицию игры A с любой из конечных позиций X.
2) вектор – функция выигрыша
которая каждой конечной позиции игры 
ставит в соотв. два числа 
, являющиеся выигрышем первого и второго игрока при условии, что игра заканчивается в позиции 
3) разбиение множества S всех вершин графа, кроме конечных, на три подмножества очередности хода 
– множество вершин граф-дерева игры, в которых производится случайный ход;
– множество вершин графа, в которых ход делает первый игрок;
– множество вершин графа, в которых ход делает второй игрок;
– множество конечных вершин графа, в которых вместо хода игроки получают свои выигрыши.
Подмножества 
, взаимно не пересекаются.
4) для каждой вершины 
задано вероятностное распределение:
на множестве ребер-альтернатив 
, исходящих из 
, такое, что:
– количество ребер 
, соединяющих вершину 
с непосредственно следующими за вершинами графа:
|
|
|
|
|
Т.о. четвертый элемент игры определяет в вероятностном смысле развитие игры, если реализация игры попала в вершину 
.
|
|
Это означает, что реализация игры может из позиции пойти по любому из ребер , 
, причем вероятность случайного события, состоящая в том, что реализация игры пойдет по ребру равна 
5) разбиение каждого из множеств 
очередности хода первого и второго игрока на области информированности игроков 
(
Необходимость в таком разбиении возникает при наличии у игроков неполной информации о состоянии игры, что соответствует случаю, когда игрок, принимая решение на очередной ход, не знает точно позиции игры, в кот. он в рассм. момент находится, а знает только подмножество позиции игры, среди кот. он находится достоверно. Такое подмножество позиции игры и назыв. областью информированности игрока перед очередным ходом.
Основные свойства области информированности:
1. все позиции из одной и той же области информированности имеют одинаковое количество исходящих ребер альтернатив.
2. никакая позиция игры в графе не может следовать непосредственно за другой позицией из той же области информированности.
В играх с полной информацией о состоянии игры область информированности каждого игрока сужается до одной вершины графа.
6) для каждой из вершин, принадлежащих одной и той же области информированности игроков, задана единая нумерация, исходящих из нее ребер целыми числами .
Каждый номер S (
ребра альтернативы соответствует одному из 
возможных решений, применяемых игроком в области информированности 
(или 
в качестве своего хода в партии игры.
Лекция 8. Примеры дискретных позиционных игр
|
|
I. Игра в шахматы.
Элементы:
1. Множество вершин графа-дерева игры является множеством всех возможных позиций на доске.
Множество ребер-альтернатив, исходящих из графа-дерева игры – множество возможных ходов того игрока, чей ход в данной позиции
Начальная позиция – начальная позиция шахматной игры с ходом белых.
Конечными позициями являются такие позиции, в которых для стороны, делающей ход на доске стоит мат, а также все возможные известные ничейные позиции (патовые, с одной легкой фигурой и т.п.).
2. Вектор-функцией выигрыша является для всех позиций мата черным пара чисел (1,0), для всех позиций мата белым – (0,1) и для всех ничейных – (1/2,1/2).
3. Игра без случайных ходов 
(пустое множество вершин).
В множество включаются все позиции с ходом белых, в – с ходом черных.
4. Отсутствует, т.к. нет случайных ходов.
5. Область информированности для каждого игрока сводится к единственной фактической позиции, т.к. шахматы – игра с полной информацией.
6. Вместо нумерации альтернатив для каждой позиции можно воспользоваться шахматной нотацией для записи ходов в партии.