Формы представления игр Преподаватель: доцент каф. АОИ Салмина Нина Юрьевна. - презентация

1 Формы представления игр Преподаватель: доцент каф. АОИ Салмина Нина Юрьевна

2 Основные понятия Игрок – принимающий решение субъект (отдельный человек, группа лиц, коллектив), имеющий свои интересы. Стратегия – правило поведения игрока от начала до конца игры. Функция выигрыша игрока – функция, определяющая величину выигрыша/проигрыша игрока, зависящая от стратегий всех сторон, принимающих участие в игре.

3 Формы представления игр Развернутая (позиционная) Достоинство: лучше раскрывается последовательность событий, более наглядна для многоходовых игр Недостаток: сложность нахождения решений Нормальная Достоинство: большинство эффективных методов нахождения решений разработано именно для этой формы Недостаток: менее наглядна

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

5 Развернутая форма игры (продолжение) 5. множества очередностей I i ( по количеству игроков); 6. информационные множества I i k : информированность игроков; 7. Партия путь от начала игры до конечной позиции. I 0 I 1 I л п л п л п л п (-1,2)(1,2)(3,4)(0,0)(1,1) (1,-1)(3,2)(1,0)

6 Пример 1. Игра «Кошки-мышки» В эту игру играют два игрока – две команды. Первая команда состоит из двух женщин и одной кошки. Вторая команда – из двух мужчин и одной мышки. Ход игры: каждая команда выставляет одновременно по одному участнику. В результате один из выставленных игроков выбывает по следующему принципу: женщина устраняет мужчину, мужчина устраняет кошку, кошка устраняет мышку, мышка устраняет женщину. Игра ведется до тех пор, пока в одной из команд не останется участников только одного вида (эта команда проигрывает). Величина выигрыша (проигрыша) равна 1 очку.

7 Игра «Кошки-мышки» Первый ход Ж К ММш М 1 I II

8 Игра «Кошки-мышки» Полное дерево игры

9 Добавление информационных множеств

10 Пример 2. Семейный спор. Супруги должны решить, как им провести свободный вечер: они могут остаться дома и смотреть телевизор, а могут пойти в театр. Муж больше заинтересован остаться дома, и от этого он получит удовлетворение, равное 2, а жена – 1. При посещении театра они получают соответственно 1 и 2. В случае разногласия вечер испорчен и супруги получают по минус единице (-1). Будем считать, что никакой сговор между ними невозможен. Введем случай: пусть с вероятностью 2/3 вечер окажется лучше в театре, а с вероятностью 1/3 – дома. Соответственно, если супруги пошли в театр, и вечер удался, им обоим добавляется по 1. Если супруги остались дома и передача по телевизору действительно оказалась удачной, им также добавляется по 1.

11 Пример 2. Дерево игры I0I0 IжIж IмIм Т(2/3) Д(1/3) Т Т Т Т Т Т Д Д Д Д Д Д (3,2)(-1,-1) (2,3) (2,1) (1,2)

12 Нормальная форма игры Г = где U i – множество стратегий i-го игрока, J i – функция выигрыша i-го игрока Конечные игры 2-х лиц можно представлять в матричной форме. Антагонистические конечные игры представляются одной матрицей.

13 Пример 3. Описание. Дана антагонистическая игра. Первый игрок – сторона А, представляет собой средства ПВО. Он обороняет от воздушного налета участок территории, располагая орудиями 1 и 2, зоны действия которых не перекрываются. Каждое орудие может обстрелять только самолет, проходящий через его зону действия, но для этого оно должно заранее (до входа цели в зону) следить за ней и вырабатывать прицельные данные. Если цель обстреляна, она поражается с единичной вероятностью. Второй игрок – сторона В, имеет в распоряжении 2 самолета, каждый из которых может быть направлен в любую зону. В качестве выигрыша будем рассматривать количество сбитых самолетов.

14 Пример 3. Стратегии игроков. I : II :

15 Пример 3. Нормальная форма игры в виде матрицы. Сам Пво

16 Пример 2. Представление в нормальной форме. ТД JжJж = Т Средний выигрыш Д Средний выигрыш ТД JМJМ = Т Д Средний выигрыш

17 Пример 2. Представление в нормальной форме. ТД JжJж = Т 3*2/3+ 2*1/3 = 8/3 Д 1*2/3+ 2*1/3 = 4/3 ТД JМJМ = Т 2*2/3+ 1*1/3 = 5/3 Д 2*2/3+ 3*1/3 = 7/3

18 Понятие коалиции Коалиция – совокупность игроков в игре многих лиц, объединенная по некоторому принципу. Любое подмножество S множества N называется коалицией. Коалиция S может состоять из одного игрока или быть пустой. Множество всех возможных коалиций равно 2 N Для игры 3 лиц множество коалиций: Ø {1} {2} {3} {1 2} {1 3} {2 3} {1 2 3}

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

20 Характеристическая функция игры Характеристическая функция игры – это функция, определенная на множестве всех возможных коалиций, ставящая в соответствие любой коалиции ее наибольший, уверенно получаемый выигрыш в данной игре. Игра в форме характеристической функции Г= Х.ф. игры трех лиц: v({1}), v({2}), v({3}), v({1,2}), v({1,3}), v({2,3}), v({1,2,3})

21 Пример нахождения х.ф. коалиции Игра трех лиц в нормальной форме: X={0,4}, Y={1,3}, Z={0,2,4}, J X =XY+Z-XZ, J Y =YZ+X-XY, J Z =XZ+Y-YZ Определить: v(X,Y). J X +J Y =-XZ+Z+X+YZ= v(X,Y)=