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

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

Пример: 3 игрока выбирают 1 из 4 кандидатов в претенденты.

Правила выбора следующие: начиная с 1 каждый игрок налагает вето на выбор кандидатов единственно оставшийся кандидат считается избранным в результате выбора каждый игрок получает выигрыш:

V1=(5,4,3,7)

V2=(6,7,5,4)

V3=(3,8,5,4)

2. Рис 2.

Дерево содержит одну единственную нормальную вершину (корень дерева)

Корень дерева не идет ни одна ветвь

1) Дерево имеет не менее 1-ой вершины из которой не выходит ни одна ветвь

Эти вершины называются конечными

2) Из корня дерева имеется единственный путь к каждой из остальных вершин дерева.

3) Вершина соответствует определенному состоянию игры перед очередным ходом

Каждую вершину занимает только один игрок.

Вершине присваивается номер равный номеру игрока.

Ходы игроков могут быть личными и случайными.

В описании игры указано какие выборы делает игрок при линейно ходе.

Если ходить случайно, то задается вероятность этих ходов.

Информация игрока задается разбиением вершин на множество.

Рассмотрим решение игры на Рис1 – это игра с полной информацией. Согласно теории игр, такая игра разрешима. И решается эта игра по принципу «доминирования»:

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

Рассмотрим принцип «доминирования» на этом примере.

Из всех вершин предшествующих конечным ходит 3 игрок.

Остальные игроки знают функцию выигрыша 3-го игрока, поэтому они могут предвидеть его решение. С учетом того что шаг 3-го однозначно определен, имеем следующую схему:

Получили новое дерево, здесь 3-ий игрок по сути не принимает решение.

Финальная вершина определяется ходами игрока 2.

Игрок,1 зная функцию решения 2-го игрока, может предвидеть его ход.

С учетом этого приходим к новому дереву.

В результате если 1-ый игрок отклонит 3-го, то 2-ой игрок вынужден будет отклонить 2-го, а 3-ий 1-го.

Процесс сведения игры к матричной называется нормализацией.

Для нормализации игры нужно перечислить все возможные стратегии игроков и для каждой совокупности стратегий определить выигрыш игроков.

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

Стратегии игроков:

1-ый:

А1- выбирает левую ветвь

А2 – выбирает правую ветвь

2-ой:

В1 – всегда левая ветвь

В2 – всегда правая ветвь

В3 – выбирать ветвь, которую выбрал 1-ый игрок

В4 – выбирать ветвь противоположную той, что выбрал 1-ый игрок

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

Ребра, имеющие одинаковые кольцевые решения называются параллельными.

Ребро, кольцевая решения, которых совпадают, называются петлей.

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

Маршрут – последовательность ребер ведущих от одной вершины к другой.

Если составляющие ребра маршрута различны, то это путь

Цикл – путь, начальная коими вершины которого совпадают. Ребра(е1,е2,е4) образуют цифру, т.к. начальные и конечные вершины совпадают. Граф называется связным, если для любых двух его вершин существует путь их соединяющие.Деревом называется связный граф несодержащий циклов. Позиционные игры изображаются с помощью деревьев.