Позиционная игра
Позицио́нная игра́, бескоалиционная игра, моделирующая процессы последовательного принятия игроками решений в условиях, вообще говоря, неполной и, кроме того, меняющейся во времени информации. Примерами позиционных игр служат шашки, шахматы, домино, покер, а также задачи последовательного статистического анализа.
Процесс игры состоит в последовательном переходе от одного состояния игры к другому состоянию, который осуществляется либо путём выбора некоторым игроком одного из возможных действий в соответствии с правилами игры, либо случайным механизмом (случайный ход). Состояния игры называются позициями, а возможные выборы в каждой позиции – альтернативами. В классической позиционной игре множество состояний является конечным. Характерная особенность позиционной игры состоит в том, что множество позиций можно представить в виде древовидно упорядоченного множества, которое называют деревом игры, а процесс игры состоит в переходе от начальной позиции к окончательной через непосредственно следующие друг за другом промежуточные позиции. В каждой окончательной позиции задан числовой выигрыш каждого игрока.
Различаются позиционные игры с полной и неполной информацией. В играх с полной информацией каждый игрок при своём ходе знает ту позицию дерева игры, в которой он находится. В играх с неполной информацией игроку при своём ходе известно лишь некоторое множество позиций, называемое информационным множеством и содержащее позицию, в которой игрок фактически находится. Игры с полной информацией соответствуют случаю, когда каждое информационное множество каждого игрока состоит из одной позиции. Так, шашки и шахматы являются позиционными играми с полной информацией без случайного хода, а домино и покер, напротив, – играми с неполной информацией и со случайным ходом.
В позиционной игре предполагается, что все позиции, принадлежащие одному информационному множеству любого игрока, имеют одно и то же число альтернатив. Поэтому между множествами альтернатив позиций любого информационного множества можно установить взаимно однозначное соответствие. Класс эквивалентности по этому соответствию называют альтернативой информационного множества. Стратегией игрока называется функция, ставящая в соответствие каждому его информационному множеству альтернативу этого множества. Ввиду возможного наличия случайного хода каждая ситуация определяет некоторое распределение вероятностей на множестве партий, и, следовательно, на множестве окончательных позиций. Под значением функции выигрыша игрока в любой ситуации понимается математическое ожидание его выигрышей по этому распределению. Эта конструкция позволяет свести позиционную игру к игре в т. н. нормальной форме.
Имеются различные обобщения классической позиционной игры на случай бесконечного множества позиций и альтернатив (см. Динамическая игра), а также множеств позиций, которые невозможно древовидно упорядочить (при зацикливании процесса разыгрывания игры).