Позиционные игры: структура игры.

многих практически важных конфликтных ситуациях, располагая той или иной информацией об их прошлом развитии, стороны-участницы совершают свой выбор не раз и навсегда, а последовательно во времени, шаг за шагом. Тем самым, они используют стратегии, отражающие как динамику конфликта, так и степень собственной информированности о фактически складывающейся обстановке в развитии этого конфликта. Структура позиционной игры Одним из классов игр, описывающих конфликты, динамика которых оказывает влияние на поведение участников, являются так называемые позиционные игры. Позиционная игра — это бескоалиционная игра, моделирующая процессы последовательного принятия решений игроками в условиях меняющейся во времени и, вообще говоря, неполной информации. Процесс самой игры состоит в последовательном переходе от одного состояния игры к другому состоянию, который осуществляется либо путем выбора игроками одного из возможных действий в соответствии с правилами игры, либо случайным образом (случайный ход). В качестве примеров позиционных игр можно привести крестики-нолики, шашки, шахматы, карточные игры, домино и др. Интересно, что право выбора первого хода в этих играх часто определяется случайным образом. Состояния игры принято называть позициями (отсюда и название — позиционные игры), а возможные выборы в каждой позиции — шътернативами. Характерной особенностью позиционной игры является возможность представления множества позиций в виде древовидного упорядоченного множества, которое называется деревом игры (рис. 1). Для определенности мы будем рассматривать позиционные игры, в каждой позиции которых, кроме окончательных, ровно две альтернативы — первая и вторая. Замечание. Символ О, А или В в кружке указывает, кто из игроков (О, А или В) делает очередной ход в заданной позиции. При этом символом О обычно обозначается ход в игре, осуществляемый не игроком, а каким-нибудь случайным механизмом (иногда его называют природой). Например, в позиционной игре, представленной на рис. 1 своим деревом, первый ход производится случайно. Пользуясь графическим описанием игры, можно сказать, что процесс игры состоит в переходе от начальной позиции к окончательной через непосредственно следующие одна задругой промежуточные позиции. Структура позиционной игры Каждая окончательная вершина определяет единственную цепь (последовательность идущих друг за другом звеньев), связывающую начальную вершину с данной (рис. 2). Такая цепь называется партией. На рис. 2 одна из партий выделена жирными линиями. Число различных партий равно числу окончательных вершин (позиций). В каждой окончательной позиции задан числовой выигрыш игрока А. Замечание. Мы будем рассматривать здесь только антагонистические позиционные игры. В шахматах функция выигрышей игрока А (белых) определяется так: +1 на выигрываемых партиях, О на ничейных партиях, -1 на проигрываемых партиях. Функция выигрышей игрока В (черных) отличается от функции выигрышей белых только знаком. Различают позиционные игры с полной информацией и позиционные игры с неполной информацией. В позиционных играх с полной информацией (пример — шашки, шахматы) каждый игрок при своем ходе знает ту позицию дерева игры, в которой он находится. В позиционных играх с неполной информацией (пример — домино) игрок, делающий ход, не знает точно, в какой именно позиции дерева игры он фактически находится. Этому игроку известно лишь некоторое множество позиций, включающее в себя его фактическую позицию. Такое множество позиций называется информационным множеством. Таким образом, в игре с неполной информацией игрок при своем ходе знает, в каком информационном множестве он находится, но ему неизвестно, в какой именно позиции этого множества. Позиции, принадлежащие одному и тому же информационному множеству, объединяются пунктирными линиями. Рассмотрим примеры двух игр, состоящих из двух ходов, которые последовательно делают участвующие в ней игроки А и В. Начинает и грок А: он выбирает одну из двух возможных альтернатив — число х, равное либо 1 (первая альтернатива), либо 2 (вторая альтернатива). На ход игрока А игрок В отвечает своим ходом, выбирая одну из двух возможных альтернатив — число у, равное либо 1 (первая альтернатива), либо 2 (вторая альтернатива). И в результате игрок А получает вознаграждение или вынужден платить штраф. Пример 13. 1-й ход. Игрок А выбирает число х из множества двух чисел {1,2}. 2-й ход. Игрок В выбирает число у из множества двух чисел {1,2}, зная выбор числа х игреком А. Функция W(x, у) выплат игроку А за счет игрока В задается так Структура позиционной игры На рис. 3 показаны дерево игры и информационные множества. Пример 14. В случае, если выполнены все условия предыдущего примера, кроме одного — хода игрока В. 2-й ход — игрок В выбирает число у из множества двух чисел {I, 2}, не зная выбора числа х игроком А, информационные множества выглядят так, как показано на рис. 4.