Позиционные игры с полной информацией

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

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

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

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

Теперь сформулируем теорему 16.1 о существовании точки равновесия.

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

Позиционные игры с идеальной памятью

Игры с идеальной памятью являются интересным обобщением игр с полной информацией.

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

Например, всякая игра двух игроков, в которой могут играть лишь два человека (а не команда), способные помнить всю информацию о выборах в любом ходе, является игрой с идеальной памятью. Используя понятие информационного множества, игру с идеальной памятью можно определить более точно. Позиционная игра — это игра с идеальной памятью, если для нее выполняются следующие условия: пусть и — любые два хода, выполняемые одним игроком и такие, что в некоторой партии игры ход Р предшествует ходу ;

и V — информационные множества, содержащие соответственно и ; каждая точка множества дает альтернатив;

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

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

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