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

В новой игре , т.е. седловая точка отсутствует. Решение игры в смешанных стратегиях имеет вид:

Уменьшение информации, имеющейся у второго игрока на момент принятия решения, привело к уменьшению его выигрыша с 2 до .

Итак для нормализации позиционной игры необходимо:

         перечислить все возможные стратегии каждого из игроков (в таких играх, как шахматы, это пока неразрешимая задача);

         определить исходы игры при всех возможных сочетаниях стратегий игроков (выборы стратегий делаются игроками одновременно и независимо).

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

В первом рассматриваемом примере (рис.3.1.) случайное испытание Н может иметь следующие исходы:

Н=|(Г,1),(Г,2),(Г,3),(Р,1),(Р,2),(Р,3)|,

с вероятностями ,

где Г - означает выпадение “герба”, Р - “решки”, а цифры 1, 2, 3 соответствуют случайному выбору на четвертом ходу.

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

Тесты

Верно (В) или неверно (Н)?

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

2.   Позиционные игры не могут включать случайные ходы.

3.   Дерево позиционной игры имеет не более одного корня и не менее одной вершины.

4.   Из корня дерева позиционной игры к какой-нибудь его вершине могут быть несколько путей.

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

6.   Классы информации должны содержать вершины только одного игрока.

7.   Вершины класса информации могут соответствовать различным временным ходам.

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

9.   Любая позиционная игра может быть сведена к игре в нормальной форме.

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

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

(Ответы: 1-В; 2-Н; 3-В; 4-Н; 5-Н; 6-В; 7-Н; 8-В; 9-В; 10-В; 11-В.)

Задачи

Произвести нормализацию позиционных игр, у которых дерево игры имеет вид:

1.

2.

3.

4.

Нарисовать дерево следующей позиционной игры k игроков выбирают одного кандидата из множества , i k. Правило голосования таково: начиная с игрока 1, каждый игрок последовательно налагает вето на выбор кандидатуры одного из не отведенных кандидатов. Единственный оставшийся кандидат считается избранным. Заданы также функции выигрыша u1, u2, …, uk на множестве С, т.е. выигрыш каждого игрока в зависимости от того, какой кандидат победил.

Варианты:

5.   k=2;

u1={2,-5,4}; u2={-2,5,-4}

6. k=2;

u1={2,5,-4,-3,1}; u2={-2-3,4,3,-1}

7.   k=3;

u1={1,2,-3,4}; u2={3,2,1,-5}; u3={-2,-3,-1,8}.

8. k=4;

u1={1,2,-2,-3,4}; u2={3,5,1,-7}; u3={2,4,-5,-1}; u4={2,3,4,1}.

1