Упрощение игр

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

Излишние стратегии бывают двух родов: дублирующие и заведомо невыгодные.

Рассмотрим, например игру И с матрицей:

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

Далее замечаем, что для противника стратегия заведомо невыгодна; вычеркиваем и ее, и матрица приведена к виду:

Таким образом, игра 4x4 сведена к игре 2x3.

Иногда удается упростить игру искусственным введением вместо чистых стратегий — смешанных. Пусть, например, имеется игра 3x4 с матрицей:

Рассматривая матрицу, замечаем, что, в силу симметрии элементов столбцов и а также строк эти стратегии, если входят в решение, то только с одинаковыми вероятностями: Отсюда возникает идея: заранее объединить стратегии в одну смешанную стратегию состоящую наполовину из наполовину из так же поступить со стратегиями т. е. объединить их в одну смешанную стратегию в которую входят с одинаковыми вероятностями 1/2. Приводим матрицу к виду:

Теперь видно, что если противник пользуется стратегиями стратегии дублируют друг друга; вычеркивая какую-либо из них (или объединяя в одну), приводим матрицу к виду 2x2:

Таким образом, игра 3X4 сведена к игре 2X2.

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

— посмотреть, нет ли в матрице седловой точки: если есть, решение уже найдено;

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

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