Инструменты пользователя

Инструменты сайта


examination:mo:question27

Решение игр в смешанных стратегиях

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

Пусть задана матричная игра (17.2). В дальнейшем мы будем называть стратегии чистыми, чтобы отличать их от смешанных стратегий, определение которых будет дано ниже.

Смешанной стратегией игрока называется произвольное распределение вероятностей на множестве его чистых стратегий.

Смешанная стратегия игрока I в игре Г есть вектор где — вероятность выбора им i-й чистой стратегии, , а поскольку одна из m чистых стратегий будет обязательно выбрана, представляет собой вероятность полной группы событий и, следовательно, Аналогично смешанная стратегия игрока II есть вектор где — вероятность выбора им j-й чистой стратегии, и Чистые стратегии являются частным случаем смешанной стратегии, задаваемой единичным вектором.

Множества смешанных стратегий игроков I и II будем обозначать соответственно через :

Итерационный метод Брауна-Робинсона

В ряде случаев более целесообразным является отыскание решения матричных игр не методом приведения к 2-м ЗЛП, а другими методами, обеспечивающими менее точное решение, но являющиеся более простыми и не требующими громоздких вычислений. Наибольшее распространение среди матричных игр получил метод Брауна-Робинсон который основан на «мыслительном эксперименте», где игроки многократно разыгрывают игру и пытаются выявить те стратегии, которые дают им больший накопленный выигрыш. Одно разыгрывание игры — партия. Число партий может быть сколько угодно большим. Данный процесс также называется итерационным, поскольку в каждой партии (итерации) игроки используют один и тот же алгоритм выбора наилучшей стратегии.

Итерации метода предст-ся в виде таблицы

img267.imageshack.us_img267_6166_table1w.jpg

К — номер партии (итерации) I — чистые стратегии игрока, А В1, В2, …, Вn — накопленный выигрыш игрока A при чистых стратегиях B ύ1 (k) — аналог нижней цены игры (ύ1 (k) = min (В1, В2, …, Вn)/k) J — чистая стратегия игрока В A1, A2, …, An — копленный проигрыш игрока A при стратегиях игрока B ύ2 (k) — аналог верхней цены игры (ύ2 (k) = max (A1, A2, …, An)/k) ύ(k) — аналог цены игры (ύ(k) = (ύ1 (k) + ύ2 (k)) / 2)

Оптимальные смешанные стратегии игроков определяются частотами выбора чистых стратегий, а в качестве цены игры применяют значение Ню, полученное на последнем шаге.

Данный итерационный процесс сходится, т. е. с ростом числа итераций точность решения увеличивается и после достаточного числа итераций можно получить решение с заданной точностью, но скорость сходимости довольна мала. Т. е. для получения оптимальных стратегий часто необходимо провести 10 или 100 операций. Однако сложность и объем вычислений сравнительно слабо возрастают по мере увеличения числа стратегий игроков.

Для определенности считают, что первый ход делает игрок, А и выбирает свою осторожную стратегию.

Если несколько стратегий игрока дают один и тот же результат, то с т.з. его накопленного выигрыша (проигрыша) выбирается стратегия с меньшим номер.

Оптимальные стратегии игроков определяются частотами выбора их чистых стратегий. Приближенное значение цены игры — результатом ύ(k) на последней итерации.

img687.imageshack.us_img687_7827_table2l.jpg

examination/mo/question27.txt · Последние изменения: 2014/01/15 12:19 (внешнее изменение)