Величина b называется верхней ценой игры. Она представляет собой максимально возможный выигрыш первого игрока или проигрыш второго игрока при любой стратегии первого игрока.
Замечание. Для любой матрицы A = ai j выполняется неравенство b > a.
Если для двух игроков b = a, то соответствующие чистые стратегии называются оптимальными, а про игру говорят, что она имеет седловую точку. Эта точка является точкой равновесия игры, однозначно определяющей оптимальные стратегии для обоих игроков. Оптимальность в этом случае означает, что ни один игрок не стремится изменить свою стратегию, потому что его соперник может на это ответить другой стратегией, дающей худший для игрока результат.
Величина C = b = a называется ценой игры. Она определяет средний выигрыш игрока А и средний проигрыш игрока В при использовании ими оптимальных стратегий.
5.2.3. Пример решения задачи
Пример 5.1
Для двух игроков задана платежная матрица, которая определяет выигрыши игрока А:
27 |
6 |
9 |
193 |
9 |
4 |
11 |
7 |
46 |
2 |
1 |
115 |
Определить нижнюю и верхнюю цены этой игры. Решение. Представим игровую модель в виде табл. 5.1.
Таблица 5.1
Решение для игровой матрицы
Стратегии |
Стратегии 2-го игрока |
min ai |
maxmin a |
||||
1-го игрока |
B1 |
B2 |
B3 |
B4 |
|||
|
|
||||||
A1 |
9 |
4 |
11 |
7 |
4 |
— |
|
A2 |
7 |
6 |
9 |
19 |
6 |
6 |
|
A3 |
6 |
2 |
1 |
11 |
1 |
— |
|
max bj |
9 |
6 |
11 |
19 |
|
|
|
minmax b |
— |
6 |
— |
— |
|
|
|
Игрок А, исходя из максиминного критерия, выбирает стратегию A2, которая будет его гарантированным выигрышем при любых стратегиях игрока В. a = 6 д. е. — нижняя цена игры.
Игрок В выбирает стратегию B2, которая минимизирует его максимальные проигрыши. Величина b = 6 д. е. — верхняя цена игры, которая будет
46
максимально возможным проигрышем игрока В при любых стратегиях игрока А. Так как b = a, то седловая точка c = 6 д. е.
Пример 5.2
Игроки А и В, каждый, записывают одно из чисел 1, 4, 6 или 9, затем они одновременно показывают написанное. Если оба числа оказались одинаковой четности, то игрок А выигрывает столько очков, какова сумма этих чисел, если разной четности — сумму чисел выигрывает игрок В. Составить платежную матрицу, найти нижнюю и верхнюю цены игры, максиминную и минимаксную стратегии игроков А и В соответственно.
Решение. Чистыми стратегиями игрока А будут: A1 — записать число 1, A2 — записать число 4, A3 — записать число 6, A4 — записать число 9. У игрока В чистыми будут аналогичные стратегии (табл. 5.2).
Таблица 5.2
Платежная матрица игры
Стратегии |
Стратегии 2-го игрока |
minai |
maxmina |
|||
1-го игрока |
B1(1) |
B2(4) |
B3(6) |
B4(9) |
||
A1(1) |
2 |
5 |
7 |
10 |
7 |
7 |
A2(4) |
5 |
8 |
10 |
13 |
13 |
— |
A3(6) |
7 |
10 |
12 |
15 |
15 |
— |
A4(9) |
10 |
13 |
15 |
18 |
15 |
— |
maxbj |
10 |
10 |
12 |
18 |
|
|
minmaxb |
10 |
10 |
— |
— |
|
|
Элемент a11 = 2, так как в ситуации (A1, B1) оба игрока записывают нечетное число 1. Выигрыш игрока А равен 1 + 1 = 2. Элемент a12 = 5, так как в ситуации (A1, B2) игрок А записывает число 1, а игрок В — число 4, т.е. числа разной четности. Выигрыш игрока В равен 5, а выигрыш игрока А соответственно составит 5. Аналогичным образом вычисляются остальные элементы платежной матрицы. После определения ai и bj отмечаем, что нижняя цена игры a = max ai = 7 не равна верхней цене игры b = minbj = 10,
i |
j |
поэтому данная игра не имеет седловой точки. Максиминной для игрока А будет чистая стратегия A1. Пользуясь такой стратегией, игрок А выигрывает не менее 7 очков (проигрывает не более 7). Минимаксными для игрока В будут чистые стратегии B1 и B2, при которых он проигрывает не более 10 очков.
Вариант задания выбирается по номеру бригады в журнале группы.
47
Задание 1
Задана платежная матрица. Найти цены игры, определить наличие седловой точки и стратегии игроков согласно номеру своего варианта (табл. 5.3).
Таблица 5.3
Варианты задания. Платежные матрицы игры
№ вар. |
|
|
|
Матрица |
|
|
|
|
№ вар. |
|
Матрица |
|
|
||||||||
|
|
|
7 |
|
9 |
|
7 |
2 |
|
|
5 |
|
|
|
|
|
1 |
7 |
2 |
|
|
1 |
|
|
|
|
|
|
3 |
|
2 |
|
24 |
3 |
13 |
|
|||||||
|
|
0 |
|
1 |
|
2 |
1 |
|
|
3 |
|
|
|
||||||||
|
|
2 |
|
7 |
|
9 |
7 |
|
|
9 |
|
|
|
|
3 |
1 |
2 |
|
|
||
|
|
|
1 |
|
|
|
|
5 |
|
|
|
60 |
3 |
17 |
|
||||||
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
7 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
5 |
|
|
|
|
|
|
4 |
|
1 |
2 |
4 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
2 2 3 4 23 |
|
|
|
2 3 |
6 5 |
|
|||||||||||||
3 |
|
6 |
7 |
6 2 8 |
|
|
4 |
21 2 |
7 33 |
||||||||||||
|
|
8 |
|
9 |
4 |
67 |
|
|
|
5 |
4 |
3 |
0 |
|
|||||||
|
|
6 |
|
|
|
|
|
|
|
7 |
|
|
4 |
|
|
|
5 |
||||
|
|
6 |
7 |
|
5 |
3 |
57 |
|
|
|
|
|
|||||||||
|
|
6 |
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
||
|
|
4 |
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
||
|
|
2 |
5 |
|
0 |
|
3 |
|
|
2 |
|
|
|
3 |
4 |
5 |
8 |
9 |
|
||
5 |
|
7 |
|
5 |
|
4 |
|
|
93 |
|
6 |
24 |
5 |
5 |
2 |
23 |
|||||
|
|
4 |
6 8 1 05 |
|
|
43 4 5 7 35 |
|||||||||||||||
|
|
|
2 |
|
1 |
|
2 |
4 |
|
|
5 |
|
|
|
1 |
3 |
|
4 |
2 |
||
7 |
|
21 4 1 3 23 |
|
8 |
2 1 4 |
|
8 1 3 |
||||||||||||||
|
|
43 2 1 0 25 |
|
|
4 6 1 2 105 |
||||||||||||||||
|
|
|
5 |
2 |
1 |
3 |
|
3 |
|
|
|
2 |
1 |
|
3 |
0 |
|
||||
9 |
|
26 3 2 2 |
|
|
10 |
22 4 1 53 |
|||||||||||||||
|
|
42 4 0 35 |
|
|
45 |
7 4 35 |
|||||||||||||||
|
7 |
|
9 |
|
7 |
|
5 |
6 |
|
12 |
|
|
2 |
4 |
|
1 |
5 |
|
|||
|
|
|
|
|
|
21 1 3 23 |
|||||||||||||||
11 |
9 10 |
6 5 8 9 |
3 |
12 |
|||||||||||||||||
|
2 |
|
|
5 |
|
2 |
|
3 |
1 |
|
4 |
|
|
5 |
2 |
|
4 |
0 |
|
||
|
8 |
|
|
|
|
|
|
|
62 |
5 |
|
|
47 |
||||||||
|
4 |
|
|
|
|
|
|
|
|
|
|
5 |
|
6 |
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
5 |
|
|
|
3 |
|
2 |
3 |
|
|
|
|
2 |
3 |
|
4 |
2 |
1 |
|
||||
|
|
|
|
|
|
|
|
5 |
|
2 |
0 |
3 |
|
||||||||
13 |
|
|
2 |
6 5 |
23 |
|
14 |
7 |
|
4 |
3 53 |
||||||||||
|
|
|
6 |
3 |
|
0 |
5 |
|
|
|
|
6 |
2 |
|
3 |
5 |
27 |
||||
|
|
|
2 |
|
|
1 |
47 |
|
|
6 |
|
1 |
|
7 |
|||||||
|
|
|
6 |
|
|
|
|
|
|
7 |
|
|
6 |
0 |
|
3 |
47 |
||||
|
|
|
4 |
|
|
|
|
|
|
|
5 |
|
|
6 |
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
5 |
|
|
|
|
9 |
|
9 |
|
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
20 |
|
3 |
|
5 |
43 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
4 |
|
5 |
|
7 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
65 |
|
1 |
|
3 |
97 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
6 |
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
48
Задание 2
Построить игровую модель индивидуальной задачи. Провести эксперименты ситуаций.
1.Игроки А и В записывают цифры 1 и 2. Игра заключена в том, что, кроме цифры 1 или 2, каждый игрок записывает еще и ту цифру, которую, по его мнению, записал партнер. Если оба игрока угадали или оба ошиблись, то партия заканчивается вничью; если же угадал только один игрок, то он получает столько очков, какова сумма записанных им цифр. Составить платежную матрицу, найти нижнюю и верхнюю чистые цены, максиминную и минимаксную стратегии игроков.
2.Игрок А может записать одну из цифр: 2, 4 или 7; игрок В может записать 1, 3, 4 или 8. Если обе цифры окажутся одинаковой четности, то игрок А получает столько очков, какова сумма записанных цифр; если разной четности — то очки достаются игроку В. Составить платежную матрицу, найти нижнюю и верхнюю чистые цены, максиминную и минимаксную стратегии игроков.
3.Участники парной игры независимо друг от друга могут записать одну из цифр: 3, 5 или 8. Если разность между цифрами, записанными игроками A и В, окажется положительной, то игрок А выигрывает столько очков, какова получившаяся разность; если разность будет отрицательной, то соответствующее количество очков выигрывает игрок В; если же разность окажется равной нулю, то и выигрыш игроков будет равен нулю. Составить платежную матрицу, найти максимин и минимакс.
4.Каждый из игроков А и В может показать один или два пальца. Если число одновременно показанных пальцев у обоих игроков одинаково, то игрок А получает одно очко; если же число пальцев разное, то очко получает игрок В. Составить модель игровой ситуации и провести эксперимент.
5.Два игрока поочередно бросают по одной игровой кости. Если сумма очков, выпавших на двух игровых костях, четная, то на выпавшую сумму увеличивается счет первого игрока, если нечетная, то — второго. На игровой кости 6 граней с количеством точек от 1 до 6. Составить модель игровой ситуации и провести эксперимент.
6.Игроки А и В записывают цифры 2 и 4. Игра состоит в том, что, кроме цифры 2 или 4, каждый игрок записывает еще и ту цифру, которую, по его мнению, записал партнер. Если оба игрока угадали или оба ошиблись, то партия заканчивается вничью; если же угадал только один игрок, то он получает столько очков, каково произведение записанных им цифр. Составить платежную матрицу, найти нижнюю и верхнюю чистые цены, максиминную и минимаксную стратегии игроков.
49
7.Игрок А может записать одну из цифр: 1, 2 или 3; игрок В может записать 4, 5, 6 или 7. Если обе цифры окажутся одинаковой четности, то игрок А получает столько очков, какова сумма записанных цифр; если разной четности — то очки достаются игроку В. Составить платежную матрицу, найти нижнюю и верхнюю чистые цены, максиминную и минимаксную стратегии игроков.
8.Игрок А может записать одну из цифр: 2, 3 или 6; игрок В может записать 1, 4 или 5. Если обе цифры окажутся разной четности, то игрок А получает столько очков, каково произведение записанных цифр; если одной четности — то очки достаются игроку В. Составить платежную матрицу, найти нижнюю и верхнюю чистые цены, максиминную и минимаксную стратегии игроков.
9.Участники парной игры независимо друг от друга могут записать одну из цифр: 9, 5 или 3. Если разность между цифрами, записанными игроками A и В, окажется отрицательной, то игрок А проигрывает столько очков, какова получившаяся разность; если разность будет положительной, то соответствующее количество очков проигрывает игрок В; если же разность окажется равной нулю, то и выигрыш игроков будет равен нулю. Составить платежную матрицу, найти максимин и минимакс.
10.Игра «Камень, ножницы, бумага». Два игрока показывают одновременно один из трех предметов: камень, ножницы или бумагу. Камень побеждает ножницы, ножницы побеждают бумагу, бумага побеждает камень. Победившему игроку присуждается очко. Составить модель игровой ситуации и провести эксперимент.
Листинг 5.1
|
|
|
Пример реализации кубика в Octave |
1 |
% |
ГЕНЕРАТОР |
Бросания КУБИКА равномерный( закон распределения) |
2 |
% |
k = k (1) |
k (2) - выпадающие значения пары кубиков |
3 |
|
|
|
4 |
k= randi ([1 |
6],1, 2) |
|
|
|
|
|
1.Изучить теоретический материал по теме работы (практикум, лекции, учебники).
2.Выписать согласно своему номеру варианта исходные данные для выполнения практической работы.
3.Выполнить постановку задачи и представить аналитическое решение своего варианта заданий 1 и 2.
4.Проанализировать полученные результаты и сделать выводы.
5.Оформить отчет в печатном виде согласно рекомендациям преподавателя. В отчете должны быть подробно расписаны исходные данные задачи
50