Принцип минимакса:
- стратегия 1-го игрока (предельной осторожности);
- стратегия 2-го игрока (гарантированного результата).
- G с седловой точкой, - чистая цена игры.
- решение в чистых стратегиях (стратегии выбираются игроками без привлечения случайных механизмов).
xi\yj |
y1 |
y2 |
y3 |
|
x1 |
1 |
3 |
10 |
1 |
x2 |
6 |
4 |
5 |
4 |
x3 |
8 |
3 |
2 |
2 |
8 |
4 |
10 |
<2,2,4> - решение игры.
Решение в чистых стратегиях устойчиво. Игрокам нет необходимости скрывать свои намерения.
- безобидная игра.
Теорема. Игра с полной информацией (шахматы, шашки) имеет седловую точку, решение в чистых стратегиях. Исход такой игры предопределен.
8.6. Игры без седловых точек.
. - область неопределенности.
Минимаксные стратегии неустойчивы. Область неопределенности можно использовать для увеличения выигрыша (уменьшения проигрыша) за счет чередования нескольких стратегий, т.е. применения смешанных стратегий.
Смешанная стратегия – сложная стратегия, состоящая в случайном чередовании двух и более чистых стратегий с определенными частотами.
xi\yj |
y1 |
y2 |
|
x1 |
6 |
2 |
2 |
x2 |
4 |
8 |
4 |
6 |
8 |
- смешанная стратегия 1-го игрока; - частота (вероятность) использования xi.
- смешанная стратегия 2-го игрока; , - частота (вероятность) использования yj.
- решение игры с , - цена игры.
Чистая стратегия является частным случаем смешанной стратегии. Чистая стратегия с называется активной.
Теорема. Если первый игрок придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры независимо от того, как играет второй игрок, если только он не выходит за пределы своих активных стратегий.
8.7. Сведение игры в смешанных стратегиях к задаче линейного программирования.
; ; ; .
Решение: ; ; ; ;
; .
Считаем, что , что выполнимо, если , если нет, можно добавить к достаточно большое число М, увеличив цену игры, оптимальные стратегии от этого не изменятся.
Пусть 2-й игрок использует чистую стратегию yj. Тогда средний выигрыш 1-го игрока:
, .
Т.к. ищется оптимальная стратегия, то , т.е.
Обозначения: , .
Получаем задачу линейного программирования:
; ; .
- средний проигрыш 2-го игрока. - стратегия 2-го игрока. Если 1 использует стратегию xi, тогда
Обозначения: ; .
Задача линейного программирования:
; ; .
Получено две двойственных задачи.
8.8. Имитационный метод Брауна-Джонсона.
Начинает 1-й игрок и выбирает произвольно одну из своих стратегий, например, xi. Противник отвечает на нее той своей стратегией yj, которая наиболее невыгодна для 1-го игрока при xi, т.е. обращает выигрыш при xi в минимум. На этом заканчивается первая партия.
Во второй партии 1-й игрок выбирает стратегию xk, которая дает максимальный средний выигрыш при применении противником yj. Далее следует второй ход противника. Он отвечает своей стратегией yj, которая дает 1-му игроку наименьший средний выигрыш при двух стратегиях (xi и xk) и т.д.
На каждом шаге итерационного процесса каждый игрок отвечает на любой ход другого противника той своей стратегией, которая является оптимальной относительно всех предыдущих ходов противника, рассматриваемых как некоторая смешанная стратегия, в которой чистые стратегии представлены в пропорциях, соответствующих частоте их применения. Такой способ представляет собой как бы модель реального практического взаимного обучения игроков, когда каждый игрок на опыте прощупывает способ поведения противника. Доказано, что этот процесс сходится к решению игры.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.