Итеративный метод решения игр

Матричная игра порядка всегда имеет решение. Это решение выражается либо через чистые стратегии, если матрица имеет седловую точку, либо через смешанные стратегии, если седловой точки нет. Во втором случае точное решение игровой задачи может оказаться очень громоздким, поэтому иногда ограничиваются приближенными решениями игр. В частности, если нижняя цена игры α мало отличается от верхней цены β, то можно чистые максиминную и минимаксную стратегии считать решениями игры. Если α сильно отличается от β, то приближенное решение задачи можно найти методом итераций, который предложил в 1951 г. американский математик Браун. Он так и называется метод Брауна.

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

Пусть в игре было сделано r партий и игрок A обобщив свои наблюдения, обнаружил, что игрок B применял свою первую стратегию k ₁ раз, вторую – k ₂ раз и так далее. На основании этого он считает, что вероятность выбора игроком B стратегии B_j равна . Это эквивалентно тому, что игрок B будет применять смешанную стратегию . Делая такое предположение игрок A выбирает в(r + 1)-ой партии такую чистую стратегию, которая дает ему максимум выигрыша при стратегии противника Y^r. Игрок B рассуждая аналогично выбирает в (r + 1)-ой партии такую чистую стратегию, которая дает ему минимальный проигрыш при смешанной стратегии X^r игрока A. Каждый игрок делает свой ход и проводит аналогичное рассуждение для очередной партии игры.

Доказано, что если каждый из игроков имеет единственную оптимальную смешанную стратегию, то при неограниченном увеличении числа партий приближенные смешанные стратегии стремятся к оптимальным стратегиям обоих игроков. Средний выигрыш игрока A и средний проигрыш игрока B стремится при этом к цене игры v.

Проиллюстрируем метод Брауна на примере.

Пример. Пусть платежная матрица имеет вид

bj ai
				α =1 β =3

Легко установить, что матрица седловой точки не имеет. Нижняя цена игры α = 1, верхняя цена β = 3. Проделаем ряд партий фиктивной игры, которая проводится по методу Брауна.

Партия 1. Совершенно произвольно предположим, что в первой партии игроки выбирают стратегии A ₁ и B ₁. Запишем номер партии, выбранные игроками стратегии и результат игры при любом ответе противника в таблицу.

Партия 2. Игрок A установил, что игрок B использовал в первой партии стратегию B ₁ и согласно методу Брауна он считает, что во второй партии игрок B поступает точно также, а поэтому он выбирает стратегию A ₁, которая делает ему наибольший выигрыш, равный 4. С другой стороны, игрок B хочет минимизировать свой проигрыш (и он тоже проводит рассуждения аналогичные рассуждениям игрока A). Он знает, что в первой партии игрок A выбрал стратегию A ₁ и (согласно методу Брауна) он считает, что во второй партии игрок A выбирает ту же стратегию A ₁. Поэтому игрок B выбирает стратегию, которая даст ему при этом наименьший проигрыш, то есть стратегию B ₂ или B ₃ с одинаковым проигрышем равным 1. Будем считать, для определенности, что игрок B выбирает стратегию с меньшим номером, то есть B ₂.

Запишем суммарный итог двух партий во второй строке таблицы. Выигрыш игрока A будет равен 8, если игрок B раз выберет стратегию B ₁; ну а если игрок B оба раза выберет стратегию B ₂ или B ₃, то выигрыш игрока A будет равен 2.

Проигрыш игрока B: если в ответ на стратегию игрока B: B ₁ и B ₂, игрок A оба раза ответит стратегией A ₁ или A ₂, то проигрыш будет равен 5, а если стратегией A ₃, то проигрыш равен 2.

Партия 3. Каждую чистую стратегию выбирает игрок A в третьей партии. Игрок A анализирует смешанную стратегию игрока B: и выбирает ту, которая в ответ на смешанную стратегию даст ему максимальный выигрыш. Для этого игрок A рассматривает вторую строку (три последних числа), и видит, что наибольший проигрыш в 5 единиц соответствует стратегии A ₁ и A ₂, пусть игрок A выбирает стратегию с наименьшим номером, то есть стратегию A ₁. Игрок B аналогично анализирует смешанную стратегию игрока A: X ² =(1; 0; 0) и замечает, что наименьший выигрыш у игрока A будет в том случае, если игрок B выбирает стратегию B ₂ или B ₃.

Итак, в третьей партии игрок A выбирает стратегию A ₁, а B – B ₂. Запишем эти стратегии и ожидаемый накопленный за три партии выигрыш игрока A (при любой чистой стратегии игрока B) и накопленный проигрыш игрока B (для каждой чистой стратегии игрока A) в третью строку таблицы.

И, так далее, в таблице записаны 20 партий фиктивной игры. Из таблицы видно, что игрок A использовал стратегию A ₁ – 3 раза; A ₂ – 6 раз и A ₃ – 11 раз. Оценка его оптимальной смешанной стратегии записывается в виде: X ²⁰ = (0,15; 0,30; 0,55). Аналогично, оценка оптимальной смешанной стратегии игрока B имеет вид:

Y ²⁰ = (0,35; 0,15; 0,50). Минимальный средний выигрыш игрока A за 20 партий равен: 29/20 = 1,45; а максимальный средний проигрыш игрока B равен: 41/20 = 2,05. Это и есть, соответственно, оценки нижней и верхней цены игры.

Рассмотренный итерационный процесс сходится очень медленно. Но очень легко программируется и вычисления его просты; и даже при больших размерах матрицы он достаточно эффективен.

Поиск по сайту: