Моделирование в условиях противодействия, игровые модели

Для иллюстрации этого метода рассмотрим предыдущий пример игры с несколько видоизмененной матрицей.

Таблица 3.7

Повторим метод рассуждений, использованный для предыдущего примера.

· Мы никогда не выберем стратегию S₁, поскольку она при любом ответе конкурента принесет нам значительные убытки.

· Из двух оставшихся разумнее выбрать S3, так как при любом ответе конкурента мы получим прибыль.

· Выбираем в качестве оптимальной стратегии S3.

Рассуждения нашего конкурента окажутся примерно такими же по смыслу. Понимая, что мы никогда не примем S₁ и выберем, в конце концов, S3, он примет решение считать оптимальной для себя стратегию C₁ — в этом случае он будет иметь наименьшие убытки.

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

· при стратегии S₁ минимальный (min) "выигрыш" составит - 4000 гривен;

· при стратегии S₂ минимальный (min) "выигрыш" составит - 1000 гривен;

· при стратегии S3 минимальный (min) выигрыш составит + 1000 гривен.

Выходит, что наибольший (max) из наименьших (min) выигрышей — это 1000 гривен и сам бог велел полагать стратегию S3 оптимальной, с надеждой на ответный ход конкурента его стратегией C₁. Такую стратегию и называют стратегией MaxiMin.

Если теперь попробовать смоделировать поведение конкурента, то для него:

· при стратегии C₁ максимальный (max) проигрыш составит 1000 гривен;

· при стратегии C₂ максимальный (max) проигрыш составит 2000 гривен.

Значит, наш конкурент, если он будет рассуждать здраво, выберет стратегию C₁, поскольку именно она обеспечивает наименьший (min) из наибольших (max) проигрышей. Такую стратегию и называют стратегией MiniMax.

Легко заметить, что это одно и то же — вы делаете ход S3 в расчете на ответ C₁, а ваш конкурент — ход C₁ в расчете на S3.

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

В двух рассмотренных примерах оптимальные стратегии "противников" совпадали, принято говорить — они соответствовали седловой точке матрицы игры.

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

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

Но, даже при использовании компьютера, писать программу для реализации всех возможных If... Then придется на специальных языках программирования (например — язык Prolog). Эти языки великолепны для решения логических задач, но практически непригодны для обычных вычислений.Если же использовать метод минимакса, то весь алгоритм поиска седловой точки займет на языке Pascal или C++ не более 5...10 строк программы.

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

Таблица 3.8

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

Пусть мы приняли решение половину ходов в игре делать с использованием S₁, а другую половину — с S₂. Конечно, мы не можем знать, какую из своих двух стратегий будет применять конкурент, и поэтому придется рассматривать два крайних случая его поведения.

Если наш конкурент все время будет применять C₁, то для нас выигрыш составит 0.5·(-3000)+0.5·(+6000 ) = 1500 гривен.

Если же он все время будет применять C₂, то на выигрыш составит 0.5·(+7000)+0.5·(+1000 ) = 4000 гривен.

Ну, это уже повод для размышлений, для анализа. В конце концов, можно прикинуть, а что мы будем иметь в случае применения конкурентом также смешанной стратегии? Ответ уже готов — мы будем иметь выигрыш не менее 1500 гривен, поскольку выполненные выше расчеты охватили все варианты смешанных стратегий конкурента.

Поставим вопрос в более общем виде — а существует ли наилучшая смешанная стратегия (комбинация S₁ и S₂) для нас в условиях применения смешанных стратегий (комбинации C₁ и C₂) со стороны конкурента? Математическая теория игр позволяет ответить на этот вопрос утвердительно — оптимальная смешанная стратегия всегда существует, но она может гарантировать минимум математического ожидания выигрыша. Методы поиска таких стратегий хорошо разработаны и отражены в литературе.

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

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

Завершим рассмотрение последнего примера демонстрацией поиска наилучшей смешанной стратегии.

Пусть мы применяем стратегию S₁ с частотой e, а стратегию S₂ с частотой (1 - e).

Тогда мы будем иметь выигрыш