Методы решения простейших игровых задач

Если игра m´n не имеет седловой точки, то нахождение решения есть вообще довольно трудная задача, особенно при больших m и n.

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

Излишние стратегии бывают: а) дублирующие и б) заведомо невыгодные. Рассмотрим, например, игру с матрицей:

Нетрудно убедиться, что стратегия А₃ в точности повторяет ("дублирует") стратегию А₁ поэтому любую из этих двух стратегий можно вычеркнуть.

Далее, сравнивая почленно строки А₁ и А₂, видим, что каждый элемент строки А₂ меньше (или равен) соответствующего элемента строки А₁. Очевидно, что мы никогда не должны пользоваться стратегией А₂; она является заведомо невыгодной. Вычеркивая А₃ и А₂, приводим матрицу к более простому виду:

Далее замечаем, что для противника стратегия В₃ заведомо невыгодна; вычеркивая ее, приводим матрицу к окончательному виду. Таким образом, игра 4´4 вычеркиванием дублирующих и заведомо невыгодных стратегий сведена к игре 2´3:

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

Наиболее простыми случаями конечных игр, которые всегда можно решить элементарными способами, являются игры 2´2 и 2´m.

Рассмотрим игру 2´2 с матрицей:

Здесь могут встретиться два случая:

1) игра имеет седловую точку;

2) игра не имеет седловой точки.

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

Пусть седловой точки нет и, следовательно, нижняя цена игры не равна верхней, a¹b. Требуется найти оптимальную смешанную стратегию игрока А:

Она отличается тем свойством, что, каковы бы ни были действия противника (если только он не выходит за пределы своих "полезных" стратегий), выигрыш будет равен цене игры n. В игре 2´2 обе стратегии противника являются "полезными", иначе игра имела бы решение в области чистых стратегий (седловую точку) Значит, если мы придерживаемся своей оптимальной стратегии то противник может пользоваться любой из своих чистых стратегий В₁, В₂, не изменяя среднего выигрыша v. Отсюда имеем два уравнения:

из которых, принимая во внимание, что p₁+р₂=1, получим

a₁₁p₁+ a₂₁(1–p₁)= a₁₂p₁+ a₂₂(1–p₁),

Цену игры v найдем, подставляя значения р_1, р₂ в любое из уравнений системы.

Если цена игры известна, то для определения оптимальной стратегии противника S_B^*= достаточно одного уравнения,

например:

a₁₁q₁+a₁₂q₂=v,

откуда, учитывая, что q₁ + q₂ = 1, имеем:

Пример 1. Найдем решение игры 2´2, рассмотренной в примере с матрицей:

1 Игра не имеет седловой точки (а = –1, b = +1), и, следовательно, решение должно лежать в области смешанных стратегий:

Нужно найти p_l, p₂, q₁ и q₂

Для p_l имеем уравнение:

1×p₁+(–1)×(1–p₁)=(–1)×p₁+1×(1–p₁),

откуда:

Аналогично найдем:

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

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

Пример 2. Игра состоит в следующем. Имеются две карты туз и двойка Игрок А наугад вынимает одну из них, В не видит, какую карту он вынул Если А вынул туза, он заявляет "у меня туз", и требует у противника 1 тенге. Если А вынул двойку, то он может либо (A₁) сказать "у меня туз": и потребовать у противника 1 тенге, либо (А₂) признаться, что у него двойка, и уплатить противнику 1 тенге.

Противник, если ему добровольно платят 1 тенге, может только принять его. Если же у него потребуют 1 тенге, то он может либо (В₁) поверить игроку А, что у него туз, и отдать ему 1 тенге, либо (В₂) потребовать проверки с тем, чтобы убедиться, верно ли утверждение А. Если в результате проверки окажется, что у А действительно туз, В должен уплатить А 2тенге. Если же окажется, что А обманывает и у него двойка, игрок А уплачивает игроку В 2тенге.

Требуется проанализировать игру и найти оптимальную стратегию каждого из игроков.

Решение. Игра имеет сравнительно сложную структуру, она состоит из одного обязательного случайного хода — выбора игроком А одной из двух карт — и двух личных ходов, которые, однако, необязательно осуществляются. Действительно, если А вынул туза, то он не делает никакого личного хода: ему предоставлена только одна возможность —потребовать 1 тенге, что он и делает. В этом случае личный ход — верить или не верить (т.е. платить или не платить 1 тенге.) — передается игроку В. Если А в результате первого случайного хода получил двойку, то ему предоставляется личный ход: уплатить 1 тенге или попытаться обмануть противника и потребовать 1 тенге (т.е. "не обманывать" или "обманывать"). Если А выбирает первое, то В остается только принять 1 тенге; если А выбрал второе, то игроку В предоставляется личный ход: верить или не верить А (т.е. уплатить А 1тенге или требовать проверки).

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

Очевидно, у А только две стратегии:

А₁ — обманывать, А₂ — не обманывать.

У В — тоже две стратегии:

В₁ — верить, В₂ — не верить.

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

1. А₁ B₁ (А обманывает, В верит).

Если А получил туза (вероятность этого 1/2), то ему не предоставляется личного хода; он требует 1 тенге, и игрок В верит ему; выигрыш А в тенге равен 1.

Если А получил двойку (вероятность этого тоже 1/2), он согласно своей стратегии обманывает и требует 1 тенге; В ему верит и уплачивает; выигрыш А также равен 1. Средний выигрыш:

2. А₁ В₂ (А обманывает, В не верит).

Если А получил туза, у него нет личного хода; он требует 1 тенге; В согласно своей стратегии не верит и в результате проверки уплачивает 2 тенге (выигрыш А равен +2).

Если А получил двойку, он согласно своей стратегии требует 1 тенге; В согласно своей стратегии не верит; в результате А уплачивает 2 тенге (выигрыш А равен –2). Средний выигрыш равен:

3. А₂ В₁ (А не обманывает, В верит).

Если А вынул туза, он требует 1 тенге; В согласно своей стратегии уплачивает; выигрыш А равен +1. Если А вынул двойку, он согласно своей стратегии платит 1 тенге; В остается только принять (выигрыш А равен –1). Средний выигрыш равен:

4. А₂ В₂ (А не обманывает, В не верит).

Если А вынул туза, он требует 1 тенге; В проверяет и в результате проверки уплачивает 2 тенге (выигрыш равен +2).

Если А вынул двойку, он уплачивает 1 тенге; В остается только принять (выигрыш равен –1).

Средний выигрыш равен:

Строим матрицу игры (см. ниже). Матрица не имеет седловой точки. Нижняя цена игры a = 0, верхняя цена игры b =1/2. Найдем решение игры в области смешанных стратегий.

Применяя формулу для р₁, получим:

т.е. игрок А должен в одной трети всех случаев пользоваться своей первой стратегией (обманывать), а в двух третях — второй (не обманывать) При этом он будет выигрывать в среднем цену игры

Значение v = 1/3 свидетельствует о том, что в данных условиях игра выгодна для А и невыгодна для В. Пользуясь своей оптимальной стратегией, А всегда может себе обеспечить положительный средний выигрыш.

Заметим, что, если бы А пользовался своей наиболее осторожной (максиминной) стратегией (в данном случае обе стратегии А₁ и А₂ являются максиминными), он имел бы средний выигрыш, равный нулю. Таким образом, применение смешанной стратегии дает А возможность реализовать свое преимущество над В, возникающее при данных правилах игры.

Определим оптимальную стратегию В. Имеем: