Вычисление оптимальных стратегий на примере решения задач
Используя теорему о минимаксе, можно утверждать, что каждая антагонистическая игра имеет оптимальные стратегии.
Теорема: пусть, А — матричная игра и строки данной матрицы являются доминирующими. Тогда игрок 1 имеет такую оптимальную стратегию х, что; кроме того, любая оптимальная стратегия для игры, получающаяся в результате удаления доминирующих строк, будет также оптимальной для первоначальной игры.
Пример 1. Игра доминирования Рассмотрим игру с матрицей. Здесь второй столбец доминирует 4 и игрок 2 соответственно не будет использовать 4 стратегию. Поэтому можно рассмотреть матрицу следующего вида. В этой матрице третья строка доминирует первую. При удалении получается матрица. А в этой матрице третий столбец доминируется вторым. Следовательно, исходная матрица сводится к следующей матрице .
Пример 2. Игра на уклонение.
Предполагается, что игроки выбирают целые числа i и j между 1 и n, а игрок 1 выигрывает величину, т. е. расстояние между i и j. Пусть первый игрок придерживается стратегии, тогда для всех ((- значение игры).
Приведём теорему, по которой решалась эта игра. Теорема: для того, чтобы ситуация была равновесной в игре, а число — значение игры, необходимо и достаточно выполнение следующего неравенства.
Ситуация называется ситуацией равновесия в чистых стратегиях, если для любых выполнено двойное неравенство (*). Если каждый из игроков стремится достичь ситуации равновесия, то принцип, которому они следуют, называют принципом равновесия. Для игры, заданной матрицей равенство (т.е. верхнее значение игры равно нижнему значению) записывается в виде, а неравенство (*) — в виде, где чистые максиминная и минимаксная стратегии соответственно игроков I и I I.
Пример 3. Игра «Дуэль».
Два дуэлянта (игроки, А и В) начинают сходиться в момент времени t=0. Встреча произойдёт в момент времени t=1. У каждого есть возможность выстрелить в любой момент времени. Если одному из них удастся выстрелить раньше соперника, то он становится победителем. Если же оба выстрелят одновременно, то дуэль закончится вничью. Если игрок, А произведёт выстрел в момент времени x () то его выстрел будет успешным с вероятностью р (x). Подобным образом будет вероятным выстрел игрока В в момент времени y () c вероятностью q (y). При условии игрок, А выиграет с вероятностью р (x), а проиграет с вероятностью (1- р (x)) q (y). Тем самым его средний выигрыш при будет равен. С другой стороны, если x> y, то его средний выигрыш будет равен. При x= y средний выигрыш.
