Можно поступить и иначе: вместо1000 шаров заложить только 10, с цифрами 0, 1, 2, .... , 9. Вынув случайным образом первый шар, получаем первый десятичный знак дроби. Вернув шар в барабан и прокрутив его, выберем случайным образом второй шар - его номер даст второй десятичный знак и т.д.
Можно доказать, что получаемые таким образом десятичные дроби будет иметь равномерное распределение от 0 до 1. Достоинством этого способа в том, что он может обеспечить любую точность задания числа R.
На практике широко применяются таблицы случайных чисел. Ниже приведен пример такой таблицы (рис.2.13). Числа сгруппированы лишь для удобства пользования таблицей. Можно начинать с любой точки таблицы, отсчитывать числа вверх или вниз, группировать числа.
Как использовать таблицу случайных чисел, чтобы получить желаемые относительные частоты? Возьмем в качестве примера оптимальную стратегию . Далее выбираем из таблицы любое однозначное случайное число. Если это число равно 0, 1, 2, 3 или 4, то используем в данной партии первую стратегию. Если число равно 5 и 6, то применяем вторую стратегию. Если это число равно 7, 8 и 9, то отбрасываем его и берем число под ним. Для следующей партии используется число ниже предыдущего.
|
11 |
16 |
43 |
63 |
18 |
75 |
6 |
13 |
76 |
74 |
40 |
60 |
31 |
61 |
52 |
|||
|
21 |
21 |
59 |
17 |
91 |
76 |
83 |
15 |
86 |
78 |
40 |
94 |
15 |
35 |
85 |
|||
|
10 |
43 |
84 |
44 |
82 |
66 |
55 |
83 |
76 |
49 |
73 |
50 |
58 |
34 |
72 |
|||
|
36 |
79 |
22 |
62 |
36 |
33 |
26 |
66 |
65 |
83 |
39 |
41 |
21 |
60 |
13 |
|||
|
73 |
94 |
40 |
47 |
73 |
12 |
3 |
25 |
14 |
14 |
57 |
99 |
47 |
67 |
48 |
|||
|
49 |
56 |
31 |
28 |
72 |
14 |
6 |
39 |
31 |
17 |
61 |
83 |
45 |
91 |
99 |
|||
|
64 |
20 |
84 |
82 |
37 |
38 |
60 |
52 |
93 |
41 |
91 |
40 |
27 |
72 |
27 |
|||
|
51 |
48 |
67 |
28 |
75 |
64 |
51 |
61 |
79 |
71 |
58 |
99 |
98 |
38 |
80 |
|||
|
99 |
75 |
62 |
63 |
60 |
41 |
70 |
17 |
31 |
17 |
40 |
68 |
49 |
99 |
48 |
|||
|
71 |
32 |
55 |
52 |
17 |
13 |
1 |
57 |
29 |
7 |
75 |
97 |
86 |
42 |
98 |
|||
|
65 |
28 |
59 |
71 |
98 |
12 |
13 |
85 |
30 |
10 |
34 |
55 |
63 |
98 |
61 |
|||
|
17 |
26 |
45 |
73 |
27 |
38 |
22 |
42 |
93 |
1 |
65 |
99 |
5 |
70 |
48 |
|||
|
95 |
63 |
99 |
97 |
54 |
31 |
19 |
99 |
25 |
58 |
16 |
38 |
11 |
50 |
69 |
|||
|
61 |
55 |
57 |
64 |
4 |
86 |
21 |
1 |
18 |
8 |
52 |
45 |
88 |
88 |
80 |
|||
|
78 |
13 |
79 |
87 |
68 |
4 |
68 |
98 |
71 |
30 |
33 |
0 |
78 |
56 |
7 |
|||
|
62 |
49 |
9 |
92 |
15 |
84 |
98 |
72 |
87 |
59 |
38 |
71 |
23 |
15 |
12 |
|||
|
24 |
21 |
66 |
34 |
44 |
21 |
28 |
30 |
70 |
44 |
58 |
72 |
20 |
36 |
78 |
|||
|
16 |
97 |
59 |
54 |
28 |
33 |
22 |
65 |
59 |
3 |
26 |
18 |
86 |
94 |
97 |
|||
|
59 |
13 |
83 |
95 |
42 |
71 |
16 |
85 |
76 |
9 |
12 |
89 |
35 |
40 |
48 |
|||
|
29 |
47 |
85 |
96 |
52 |
50 |
41 |
43 |
19 |
61 |
33 |
18 |
68 |
13 |
46 |
Рис.2.13
Часто желательно модифицировать этот способ. Например, в случае относительных частот 8:3 сумма чисел равна 8+3=11. Приходится применять двухзначные числа от 00 до 99. Но чтобы не отбрасывать числа от 11 до 99, разделим 99 на 11, получаем 9 (в общем случае это будет смешанная дробь). Далее умножаем 89=72 и 39=27. Теперь, если выбранное двухзначное число лежит в пределах от 00 до 71, используем первую стратегию, а если от 72 до 99, - то вторую. Число 99 будем отбрасывать.
Для получения R на ЭВМ применяются специальные датчики случайных чисел. Это могут быть как “физические датчики”, принцип действия которых основан на преобразовании случайных шумов, так и вычислительные алгоритмы, по которым сама машина вычисляет так называемые “псевдослучайные” числа. Один из самых простых алгоритмов вычисления псевдослучайных чисел состоит в следующем. Берут два произвольных n-значных числа a1 и a2 и перемножают их, и в полученном результате берут n средних знаков. Так получают число а3. Затем перемножают а2 и а3 и в полученном результате берут n средних чисел, получая число а4,и т.д. Полученные таким образом числа рассматриваются как последовательность двоичных дробей с n знаками после запятой. Такая последовательность дробей практически ведет себя как ряд случайных чисел R от 0 до 1.
В заключение изложения матричных игр отметим, что хотя само понятие смешанной стратегии требует многократного повторения партий игры, полученные результаты справедливы и к играм, которые играются только один раз, поскольку все изложения теории были выведены применительно к одной партии игры.
Качественно аргументировать этот тезис можно следующим образом: очевидно, что если противник узнает, какую мы выбрали стратегию, то предпримет ход, который будет иметь для нас наихудшие последствия. Поэтому единственным выходом является использование для выбора стратегии случайного механизма (жребия), результат которого противник не может предвидеть (хотя, конечно, ему может и повезти). Теория игр указывает характеристики (частоты применения стратегий), которыми должен обладать используемый случайный механизм.
ТЕСТЫ
(В - Верно, Н - Неверно)
Каждая матричная игра может быть представлена парой прямой и двойственной задач линейного программирования.
Преимуществом приближенного метода Брауна-Робинсона является то, что объем вычислений с увеличением размерности игры m*n растет существенно медленнее, чем в методах линейного программирования.
Теория игр не может дать результатов в тех случаях, когда элементы платежной матрицы заданы неточно (например, когда они только упорядочены).
Случайные числа выдаваемые датчиком случайных чисел, используемые для реализации оптимальных стратегий, должны быть распределены по равномерному закону.
Теория игр применима и для игр, которые играются только один раз.
Ответы: (1 - В; 2 - В; 3 - Н; 4 - В, 5- В).
ЗАДАЧИ
Решить матричные игры, имеющие платежные матрицы вида:
|
1. |
8 |
4 |
2 |
2. |
-1 |
1 |
1 |
3. |
1 |
2 |
-5 |
3 |
2 |
|
|
2 |
8 |
4 |
2 |
-2 |
2 |
-1 |
4 |
7 |
2 |
-4 |
||||
|
1 |
2 |
8 |
3 |
3 |
-3 |
5 |
-1 |
1 |
1 |
3 |
||||
|
4. |
0 |
-13 |
-1 |
5. |
1 |
0 |
-1 |
6. |
3 |
2 |
4 |
|||
|
13 |
0 |
-13 |
0 |
2 |
1 |
4 |
3 |
2 |
||||||
|
1 |
13 |
0 |
1 |
-1 |
3 |
2 |
4 |
3 |
||||||
|
7. |
3 |
6 |
0 |
8. |
3 |
0 |
7 |
9. |
203 |
403 |
103 |
|||
|
5 |
3 |
2 |
4 |
6 |
0 |
303 |
3 |
103 |
||||||
|
2 |
1 |
6 |
3 |
4 |
3 |
3 |
103 |
303 |
||||||
|
10. |
2 |
-11 |
1 |
11. |
7 |
5 |
4 |
12. |
16 |
0 |
14 |
|||
|
15 |
2 |
-11 |
1 |
3 |
7 |
6 |
6 |
16 |
||||||
|
3 |
15 |
2 |
2 |
7 |
4 |
6 |
12 |
2 |
||||||
|
13. |
0 |
1 |
1 |
14. |
-1 |
1 |
0 |
15. |
0 |
2 |
1 |
|||
|
1 |
0 |
1 |
0 |
-1 |
1 |
2 |
0 |
2 |
||||||
|
1 |
1 |
0 |
1 |
0 |
-1 |
1 |
2 |
0 |
|
18. |
1 |
6 |
2 |
5 |
19. |
6 |
0 |
1 |
2 |
20. |
4 |
3 |
3 |
2 |
2 |
6 |
|
|
5 |
1 |
6 |
2 |
0 |
3 |
1 |
0 |
6 |
0 |
4 |
2 |
6 |
2 |
||||
|
2 |
5 |
1 |
6 |
2 |
0 |
3 |
1 |
0 |
7 |
3 |
6 |
2 |
2 |
||||
|
21. |
0 |
-13 |
-3 |
22. |
9 |
6 |
12 |
23. |
2 |
7 |
3 |
6 |
|||||
|
13 |
0 |
-13 |
12 |
9 |
6 |
6 |
2 |
7 |
3 |
||||||||
|
1 |
13 |
0 |
6 |
12 |
9 |
3 |
6 |
2 |
7 |
||||||||
|
24. |
12 |
0 |
2 |
4 |
25. |
6 |
-10 |
4 |
26. |
104 |
304 |
4 |
|||||
|
0 |
6 |
2 |
0 |
-4 |
-4 |
6 |
204 |
-96 |
4 |
||||||||
|
4 |
0 |
6 |
2 |
-4 |
2 |
-8 |
-96 |
4 |
204 |
||||||||
|
27. |
3 |
1 |
4 |
1 |
6 |
28. |
2 |
3 |
1 |
4 |
29. |
-1 |
-2 |
-3 |
|||
|
6 |
3 |
1 |
4 |
1 |
1 |
2 |
5 |
4 |
-3 |
-1 |
-1 |
||||||
|
1 |
6 |
3 |
1 |
4 |
2 |
3 |
4 |
1 |
-1 |
-3 |
1 |
||||||
|
4 |
1 |
6 |
3 |
1 |
4 |
2 |
2 |
2 |
|||||||||
|
1 |
4 |
1 |
6 |
3 |
|||||||||||||
|
30. |
1/7 |
2/7 |
3/7 |
||||||||||||||
|
3/7 |
1/7 |
1/7 |
|||||||||||||||
|
1/7 |
3/7 |
1/7 |
3. ПОЗИЦИОННЫЕ ИГРЫ
3.1 Общие сведения
В общих играх число игроков может быть больше двух, некоторые ходы возможно являются случайными, игроки могут иметь по несколько ходов, причем информация о прошедшем может меняться от хода к ходу. Такие игры называются позиционными или играми в развернутой форме.
Пример. Выборы с правом вето.
Пусть три игрока (N=3) выбирают одного из четырех (G=4) кандидатов в президенты. Правило выбора таково: начиная с первого игрока, каждый игрок налагает вето на выбор одного из неотведенных кандидатов. Единственный оставшийся кандидат считается избранным. Функции выигрышей Ui для каждого из игроков в зависимости от выбранного в президенты кандидата имеют вид:
В развернутой форме данная игра может быть представлена в виде следующего дерева игры (рис. 3.1.), где около ветвей поставлены номера отводимых кандидатов, а у конечных вершин - номера победивших кандидатов. Если победил, например, кандидат под номером 4, то выигрыш первого игрока будет равен 7, а для второго и третьего игроков - 4.
Позиционные игры должны включать следующие элементы описания:
последовательность личных и случайных ходов игроков;
выборы, которые могут делать игроки при каждом личном ходе;
Рис.3.1
исходы случайных ходов и распределение вероятностей этих исходов;
информацию, доступную игрокам при выполнении личного или случайного хода;
правила окончания игры и подсчеты выигрыша игроков.
Число ходов в данной игре не фиксируется. В общем случае, оно зависит от последовательности выборов, исходов. Однако, правила должны гарантировать, что игра в конце концов закончится.
Относительно ходов правила игры имеют следующую структуру. Для первого хода правила указывают его вид. Если это личный ход, то правила перечисляют возможные варианты и указывают игрока, который делает выбор. Если это случайный ход, то перечисляются возможные варианты и обуславливаются вероятности их выбора.
Для последующих ходов правила определяют в зависимости от выбора и исходов предыдущих (-1) ходов, будет ли -й ход личным или случайным. Если ход личный, то перечисляются возможные варианты игрока, который будет делать выбор, и определяется информация о выборах и исходах при первых (-1) ходах, которой располагает игрок к моменту своего выбора.
Если ход случайный, то перечисляются возможные варианты и вероятности их выбора. Правила, наконец, определяют в зависимости от выборов и исходов в последовательности ходов, когда игра должна закончиться и выигрыш каждого из игроков.