Метод последовательных приближений
В этом методе используется математическое моделирование игры. На каждом ходе каждый игрок выбирает такую чистую стратегию, которая является наилучшей с учетом всех предыдущих ходов противника, рассматриваемых как некоторая «смешанная» стратегия.
Относительные частоты применения этих стратегий определяют приближенное значение оптимальной смешанной стратегии, а средний выигрыш - приближенное значение цены игры.
Идея метода состоит в следующем. Пусть 1-й игрок выбирает чистую стратегию , на что 2-й игрок отвечает стратегией , которая наименее выгодна для первого. На этом ход противника 1-й игрок отвечает стратегией xk , которая дает ему максимальный выигрыш. Далее, 2-й игрок отвечает на пару ходов 1-го той, стратегией, которая дает ему наименьший средний проигрыш за пару ходов и т. д.
По-сути, метод реализует некоторую модель взаимного обучения игроков, когда каждый из них на опыте «прощупывает» поведение противника и старается ответить наилучшим для себя образом. Доказано, что процесс последовательного приближения сходится, хотя очень медленно. При большом числе партий средний выигрыш приближается к цене игры, относительные частоты применения игроками своих стратегий – к оптимальным значениям вероятностей. Трудоемкость метода практически линейно зависит от размеров исходной матрицы. Рассмотрим пример. Пусть дана матрица игры следующего вида:
|
|
|
|
|
2 |
1 |
0 |
|
2 |
0 |
3 |
|
-1 |
3 |
-3 |
Cведем все результаты вычислений в таблицу:
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
1 |
0 |
0 |
|
0 |
3 |
-3 |
3 |
1,5 |
2 |
|
4 |
1 |
3 |
0,5 |
|
1 |
3 |
0 |
1,5 |
1 |
3 |
|
6 |
1 |
6 |
0,333 |
|
2 |
3 |
3 |
1 |
|
4 |
|
8 |
1 |
9 |
0,25 |
|
3 |
3 |
6 |
1,5 |
1,875 |
5 |
|
7 |
4 |
6 |
0,8 |
|
4 |
3 |
9 |
|
1,3 |
6 |
|
6 |
7 |
3 |
0,5 |
|
4 |
6 |
6 |
1 |
0,75 |
7 |
|
8 |
7 |
6 |
0,857 |
|
4 |
9 |
3 |
1,286 |
1,072 |
8 |
|
10 |
7 |
9 |
0,857 |
|
5 |
9 |
6 |
1,125 |
1 |
9 |
|
12 |
7 |
12 |
0,778 |
|
6 |
9 |
9 |
1 |
0,889 |
10 |
|
14 |
7 |
15 |
0,7 |
|
7 |
9 |
12 |
1,2 |
0,95 |
11 |
|
13 |
10 |
12 |
0,9 |
|
8 |
9 |
15 |
1,364 |
1,137 |
12 |
|
12 |
13 |
9 |
0,75 |
|
8 |
12 |
12 |
1 |
0,875 |
– номер партии (партия = 2 полухода);
– номер чистой стратегии первого игрока, выбранной в партии ;
– общий
платеж 1-му игроку после
партий, если 2-й все время применяет
стратегию
;
– наименьший
средний выигрыш 1-го за
ходов, равный
;
– номер чистой стратегии 2-го игрока в -ой партии;
– общий
платеж 1-му игроку, если он все время
использует стратегию
;
– наибольший
средний выигрыш 1-го за
ходов, равный
.
– приближенное
значение цены игры, равное
.
После
12 ходов получаем:
,
.
Для
сравнения точное значение ν = 1,
,
.
Отметим, что важно знать заранее приближенное значение цены игры, чтобы вовремя остановить процесс компьютерного моделирования игры. Подходящим условием останова для метода последовательных приближений является достижение положения «равновесия», при котором все общие платежи или совпадают между собой.
Доказано,
что процесс сходится при
.
При этом приближенное значение ν
стремится к цене игры, а ξ и η могут
колебаться около значения оптимальных
стратегий. Трудоемкость метода снижается,
если в ходе каждого приближения определять
не только номер очередной чистой
стратегии, но и то, сколько раз подряд
она должна применяться.