39. Позиционные игры. Дерево принятия решений. Виды позиционных игры.

Позиционные игры.

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

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

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

Право выбора первого хода в этих играх определяется случайно (разыгрывается).

Состояния игры принято называть узлами или позициями, обозначаются кружочками:

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

Пример дерева:

Деревья ПР.

В ПИ возможные позиции представляются графически в виде упорядоченного множества – дерева игры.

Если указан выигрыш только для одного из игроков, то игра сводится к матричной.

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

Виды ПИ.

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

Существует класс игр с неполной информацией. В них (к примеру, карты или домино) игрок не знает точной позиции дерева игры, где он находится на момент совершения хода. Ему известно лишь некоторое множество позиций, включающее его собственную. Такое множество позиций принято называть «информационное множество». Позиции, принадлежащие одному и тому же информационному множеству, объединяют пунктирными линиями.

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

40. Нормализация позиционной игры. Привести пример для двухходовой двухпозиционной игры с полной информацией.

Нормализация ПИ.

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

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

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

Это позволяет сводить позиционную игру к матричной или биматричной игре. Процесс сведения называется нормализацией ПИ.

Общий пример.

Рассмотри ПИ двух лиц, каждое из которых делает по одному ходу. Игрокам известны ходы противника, т. е. перед нами двухходовая игра с полной информацией.

Пусть у каждого игрока имеются всего по 2 альтернативы.

A выбирает число

B выбирает число

a, b, c, d – выигрыши игрока A

В результате игры A получается выигрыши a, b, c, d.

Нормализуем данную позиционную игру. Укажем множество стратегий.

Игрок A имеет лишь две стратегии.

У игрока B имеется 4 стратегии. Зададим стратегии игрока B упорядоченной парой чисел:

– альтернатива игрока B при условии

– альтернатива игрока B при условии

[2,1] – эта стратегия игрока B означает, что на первом ходе A выбрал стратегию , тогда B выбирает , если же A выбирает , то B выбирает .

Составим платежную матрицу игры.

Пусть – функция выигрыша, тогда:

Получим матрицу P:

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