Методы и модели решения игровых задач.

Принцип минимакса.

Рассмотрим методы и модели решения игровых задач.

Рассмотрим конечную парную игру с нулевой суммой. Игрок I имеет m стратегий (А₁, А₂, ..., А_m), а игрок II — n стратегий (В₁, В₂, ..., В_n). Такая игра называется игрой размерностью m ´ n. Пусть каждая сторона определилась с выбором стратегии: игрок I — A_i (i = 1, 2, ..., m), игрок II — B_j (j = 1, 2, ..., n). Выигрыши игрока I — (A_i, B_j) и игрока II — (A_i, B_j) удовлетворяют соотношению (A_i, B_j) + (A_i, B_j) = 0.

Если игра состоит только из личных ходов, то выбор стратегии (A_i, B_j) однозначно определяет исход игры , т.е. выигрыш игрока I. Если игра содержит также случайные ходы, то выигрыш при паре стратегий (A_i, B_j) есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш — это среднее значение (математическое ожидание). Предположим, что значения a_ij известны для каждой пары стратегий (A_i, B_j). Построим таблицу, строки которой соответствуют стратегиям игрока I, а столбцы — стратегиям игрока II, т.е. платежную матрицу. Каждый элемент (a_ij > 0) матрицы определяет величину выигрыша игрока I и проигрыш игрока II. Цель игрока I — максимизировать свой выигрыш, а игрока II — минимизировать свой проигрыш. Платежная матрица имеет следующий вид:

I \ II B₁ B₂ ... B_j ... B_n

A₁ a₁₁ a₁₂ ... a_1j ... a_1n a₁

A₂ a₂₁ a₂₂ ... a_2j ... a_2n a₂

... ... ... ... ... ... ... ...

A_i a_i1 a_i2 ... a_ij ... a_in a_i

... ... ... ... ... ... ... ...

A_m a_m1 a_m2 ... a_mj ... a_mn a_m

Β_j b₁ b₂ ... b_j ... b_n

Задача состоит в определении:

1) наилучшей (оптимальной) стратегии игрока I из стратегий A₁, A₂, ..., A_m;

2) наилучшей (оптимальной) стратегии игрока II из стратегий B₁, B₂, ..., B_m.

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

Проанализируем последовательно каждую стратегию игрока I. Если игрок I выбирает стратегию А₁, то игрок II может выбрать такую стратегию B_j, при которой выигрыш игрока I будет равен наименьшему из чисел a₁_j:

Выбирая стратегию A_i, игрок I должен рассчитывать на то, что в результате разумных действий игрока II он не выиграет больше, чем a_i. Поэтому игрок I должен выбрать ту стратегию, для которой a_i максимально:

Величина a — гарантированный выигрыш, который может обеспечить себе игрок I при любом поведении игрока II. Величина a называется нижней ценой игры или максимином, а стратегия А_i игрока I, обеспечивающая получение нижней цены игры, называется максиминной чистой стратегией. При этом игрок I при любом поведении игрока II обеспечивает себе выигрыш, не меньше a: a_i ³ a (i = 1, 2, ..., m).

Игрок II заинтересован в том, чтобы уменьшить свой проигрыш, т.е. обратить выигрыш игрока I в минимум. Для выбора оптимальной стратегии он должен найти максимальное значение выигрыша в каждом столбце:

и среди этих значений выбрать наименьшее: .

Величина b называется верхней ценой игры или минимаксом. Стратегия игрока II, обеспечивающая получение верхней цены игры, называется минимаксной чистой стратегией. Применяя ее, игрок II проиграет не больше b при любых действиях игрока I:

b_j £ b (j = 1, 2, ..., n), причем всегда справедливо неравенство a £ b.

Таким образом, придерживаясь максиминной стратегии A_i, игрок I желает получить выигрыш не менее a не зависимо от действий игрока II, а игрок II, придерживаясь минимаксной стратегии B_j, гарантирует себе проигрыш не больше b.

Принцип, диктующий игрокам соответствующих стратегий (максиминной и минимаксной), в теории игр называется принципом минимакса. Этот принцип был впервые сформулирован Дж. фон Нейманом в 1928 году.

Пример 1. Дана платежная матрица. Найти решение игры: определить нижнюю и верхнюю цены игры и минимаксные стратегии:

I \ II B₁ B₂ B₃ B₄ a

A₁ 5 3 8 2 2

A₂ 1 6 4 3 1

A₃ 9 5 4 7 4

Β_j 9 6 8 7

Таким образом, нижней цене игры (a = 4) соответствует стратегия A₃ игрока I. Выбирая эту стратегию, игрок I достигнет выигрыша не меньше 4 при любом поведении игрока II. Верхней цене игры (b = 6) соответствует стратегия игрока II — В₂. Эти стратегии являются минимаксными. Если обе стороны будут придерживаться этих стратегий, выигрыш будет равен а₃₃= 4.

Существуют матричные игры, для которых нижняя цена игры равна верхней, т.е. a = b. Такие игры называются играми с седловой точкой.

В этом случае g = a = b называется чистой ценой игры, а стратегии игроков и , позволяющие получить это значение — оптимальными. Пара называется седловой точкой матрицы, так как элемент одновременно является минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии и и чистая цена являются решением игры в чистых стратегиях, т.е. без привлечения механизма случайного выбора.