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

Пусть дана игра, заданная платежной матрицей размерности m ´ n. Решить матричную игру означает определить наилучшую стратегию игрока A, а также наилучшую стратегию игрока B. Если рассматривается стратегическая игра, то предполагается, что противники одинаково разумны и каждый из них делает все, чтобы добиться своей цели. каждый из игроков должен рассчитывать на то, что противник ответит самым неблагоприятным образом, т. е. должен быть пессимистом. Именно в расчете «на худший результат» и состоит принцип минимакса.

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

где a_i – минимальный гарантированный выигрыш игрока А при применении им стратегии А_i.

Очевидно, что желающий перестраховаться игрок A должен предпочесть другим стратегиям ту, для которой гарантированный выигрыш a_i максимален. Тогда .

Величина a называется нижней ценой игры, или максимином. Соответствующая стратегия называется максиминной. Если игрок А будет придерживаться этой стратегии, то ему гарантирован выигрыш, не меньший нижней цены игры при любом поведении игрока В.

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

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

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

Максимин никогда не превосходит минимакс, т. е. a £ b.

Если нижняя цена игры равна верхней (a = b), то говорят, что игра имеет седловую точку и чистую цену игры (g = a = b). Такая игра решается в чистых стратегиях, т. е. каждому игроку рекомендуется применять одну оптимальную стратегию (максиминную для А и минимаксную для В). Если же нижняя и верхняя цены игры не равны
(a < b), то игра в чистых стратегиях не решается. Ее можно решать в смешанных стратегиях, но только в том случае, когда игра повторяется многократно. Тогда каждый игрок может применять несколько стратегий с определенными частотами (например, в 40% случаев – стратегию А ₂, а в 60% случаев – стратегию А ₄).

Дата добавления: 2015-08-26