Представление информации
<<  Представление и кодирование информации в компьютере Представление публичного доклада  >>
Формы представления игр
Формы представления игр
Основные понятия
Основные понятия
Формы представления игр
Формы представления игр
Развернутая форма игры
Развернутая форма игры
Развернутая форма игры (продолжение)
Развернутая форма игры (продолжение)
Пример 1. Игра «Кошки-мышки»
Пример 1. Игра «Кошки-мышки»
Игра «Кошки-мышки» Первый ход
Игра «Кошки-мышки» Первый ход
Игра «Кошки-мышки» Полное дерево игры
Игра «Кошки-мышки» Полное дерево игры
Добавление информационных множеств
Добавление информационных множеств
Пример 2. Семейный спор
Пример 2. Семейный спор
Пример 2. Дерево игры
Пример 2. Дерево игры
Г = < U1, …, UN, J1, …JN > где Ui – множество стратегий i-го игрока,
Г = < U1, …, UN, J1, …JN > где Ui – множество стратегий i-го игрока,
Пример 3. Описание
Пример 3. Описание
Пример 3. Стратегии игроков
Пример 3. Стратегии игроков
Пример 3. Нормальная форма игры в виде матрицы
Пример 3. Нормальная форма игры в виде матрицы
Пример 2. Представление в нормальной форме
Пример 2. Представление в нормальной форме
Пример 2. Представление в нормальной форме
Пример 2. Представление в нормальной форме
Понятие коалиции
Понятие коалиции
Характеристическая функция (х
Характеристическая функция (х
Характеристическая функция игры – это функция, определенная на
Характеристическая функция игры – это функция, определенная на
Пример нахождения х.ф. коалиции
Пример нахождения х.ф. коалиции

Презентация: «Формы представления игр». Автор: ***. Файл: «Формы представления игр.ppt». Размер zip-архива: 129 КБ.

Формы представления игр

содержание презентации «Формы представления игр.ppt»
СлайдТекст
1 Формы представления игр

Формы представления игр

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

2 Основные понятия

Основные понятия

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

3 Формы представления игр

Формы представления игр

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

Нормальная Достоинство: большинство эффективных методов нахождения решений разработано именно для этой формы Недостаток: менее наглядна

4 Развернутая форма игры

Развернутая форма игры

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

5 Развернутая форма игры (продолжение)

Развернутая форма игры (продолжение)

множества очередностей Ii ( по количеству игроков); информационные множества Iik: информированность игроков; Партия — путь от начала игры до конечной позиции.

I0 I1 I2

(1,-1)

(3,2)

(1,0)

(-1,2)

(1,2)

(3,4)

(0,0)

(1,1)

6 Пример 1. Игра «Кошки-мышки»

Пример 1. Игра «Кошки-мышки»

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

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

Игра «Кошки-мышки» Первый ход

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

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

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

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

10 Пример 2. Семейный спор

Пример 2. Семейный спор

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

11 Пример 2. Дерево игры

Пример 2. Дерево игры

I0

Д(1/3)

Т(2/3)

Д

Д

Т

Т

Д

Т

Т

Т

Д

Т

Д

Д

(-1,-1)

(-1,-1)

(2,3)

(2,1)

(3,2)

(-1,-1)

(-1,-1)

(1,2)

12 Г = < U1, …, UN, J1, …JN > где Ui – множество стратегий i-го игрока,

Г = < U1, …, UN, J1, …JN > где Ui – множество стратегий i-го игрока,

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

Нормальная форма игры

13 Пример 3. Описание

Пример 3. Описание

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

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

Пример 3. Стратегии игроков

I : 11 12 21 22 II : 11 12 21 22

1

2

1

2

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

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

Сам Пво .

11

12

21

22

11

1

1

1

1

12

1

2

0

1

21

1

0

2

1

22

1

1

1

1

16 Пример 2. Представление в нормальной форме

Пример 2. Представление в нормальной форме

=

=

Т

Д

Т

Д

Т

-1

Т

-1

Д

-1

Д

-1

Средний выигрыш

Средний выигрыш

Средний выигрыш

Средний выигрыш

17 Пример 2. Представление в нормальной форме

Пример 2. Представление в нормальной форме

=

=

Т

Д

Т

Д

Т

2*2/3+1*1/3 = 5/3

-1

Т

3*2/3+2*1/3 = 8/3

-1

Д

-1

2*2/3+3*1/3 = 7/3

Д

-1

1*2/3+2*1/3 = 4/3

18 Понятие коалиции

Понятие коалиции

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

19 Характеристическая функция (х

Характеристическая функция (х

ф.) коалиции

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

20 Характеристическая функция игры – это функция, определенная на

Характеристическая функция игры – это функция, определенная на

множестве всех возможных коалиций, ставящая в соответствие любой коалиции ее наибольший, уверенно получаемый выигрыш в данной игре. Игра в форме характеристической функции — Г=< N,v > Х.ф. игры трех лиц: 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}, JX=XY+Z-XZ, JY=YZ+X-XY, JZ=XZ+Y-YZ Определить: v(X,Y). JX+JY=-XZ+Z+X+YZ= v(X,Y)=4

0

2

4

01

0

4

8

03

0

8

16

41

4

-2

-4

43

4

4

4

«Формы представления игр»
http://900igr.net/prezentacija/informatika/formy-predstavlenija-igr-232386.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды