Методические указания к практическим занятиям по дисциплине «Методы и алгоритмы принятия решений», страница 18

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

- стратегия 1-го игрока (предельной осторожности);

- стратегия 2-го игрока (гарантированного результата).

 - G с седловой точкой,  - чистая цена игры.

 - решение в чистых стратегиях (стратегии выбираются игроками без привлечения случайных механизмов).

<2,2,4> - решение игры.

Решение в чистых стратегиях устойчиво. Игрокам нет необходимости скрывать свои намерения.

 - безобидная игра.

Теорема. Игра с полной информацией (шахматы, шашки) имеет седловую точку, решение в чистых стратегиях. Исход такой игры предопределен.

8.6. Игры без седловых точек.

.  - область неопределенности.

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

Смешанная стратегия – сложная стратегия, состоящая в случайном чередовании двух и более чистых стратегий с определенными частотами.

 - смешанная стратегия 1-го игрока;   - частота (вероятность) использования x_i.

 - смешанная стратегия 2-го игрока; ,  - частота (вероятность) использования y_j.

 - решение игры с ,  - цена игры.

Чистая стратегия является частным случаем смешанной стратегии. Чистая стратегия с  называется активной.

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

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

; ; ; .

Решение: ; ; ; ;

; .

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

Пусть 2-й игрок использует чистую стратегию y_j. Тогда средний выигрыш 1-го игрока:

 , .

Т.к. ищется оптимальная стратегия, то , т.е.

Обозначения: , .

Получаем задачу линейного программирования:

; ; .

 - средний проигрыш 2-го игрока.  - стратегия 2-го игрока. Если 1 использует стратегию x_i, тогда

Обозначения: ; .

Задача линейного программирования:

; ; .

Получено две двойственных задачи.

8.8. Имитационный метод Брауна-Джонсона.

Начинает 1-й игрок и выбирает произвольно одну из своих стратегий, например, x_i. Противник отвечает на нее той своей стратегией y_j, которая наиболее невыгодна для  1-го игрока при x_i, т.е. обращает выигрыш при x_i в минимум. На этом заканчивается первая партия.

Во второй партии 1-й игрок выбирает стратегию x_k, которая дает максимальный средний выигрыш при применении противником y_j. Далее следует второй ход противника. Он отвечает своей стратегией y_j, которая дает 1-му игроку наименьший средний выигрыш при двух стратегиях (x_i и x_k) и т.д.

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