2. Представление игры в матричной форме

П

Рисунок 1 – Матрица игры

усть имеется игра, в которой у игрока А существуетm стратегий, а у игрока В – п стратегий. Обозначим эти стратегии соответственно А_ь А₂,…, А_т и В_ь В₂,…, В_п. Такая игра называется игрой (т * п). Обозначим а^ выигрыш игрока А при использовании им стратегии A_i? А игроком В – стратегий Bj. Если для каждой пары стратегий Aj,Bj выигрыш а^ известен, то можно построить матрицу игры (платежную матрицу), изображенную на рисунке 1. В этом случае говорят, что игра представлена в матричной форме.

Рассмотрим антагонистическую игру двух сторон (m.n), представленную в матричной форме. Поиск оптимальных стратегий игроков осуществляется, используя так называемый «принцип минимакса». По этому принципу для игрока А оптимальной является максиминная стратегия, т.е. стратегия, максимизирующая минимальный выигрыш игрока А. Этот гарантированный выигрыш называется нижней ценой игры. Обозначим его а.

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

Можно показать, что в общем случае а <= р. Если а = р = V, то имеем игру с седловой точкой, а выигрыш V называется ценой игры. Стратегии А*, В* дающие выигрыш V называются оптимальными, чистыми стратегиями, а их совокупность называется решением игры. При наличии седловой точки в игре говорят, что игра решается в чистых стратегиях.

Рисунок 2 – Матрица игры с седловой точкой

Седловых точек может быть несколько, в этом случае имеется несколько оптимальных стратегий. При этом во всех седловых точках платежи одинаковы и равны цене игры V . На рисунке 2 приведена матрица игры (3x4) с седловой точкой.

3. Представление игры в виде игрового дерева

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

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

Игровое дерево это семантическое дерево, в котором узлы обозначают игровые ситуации, а ветви обозначают ходы.

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

Минимах процедура

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

Рисунок 3 – Дерево игры

Процедура, реализующая данную стратегию следующая:

• Если достигнута предельная глубина поиска, то провести статическое оценивание игровой ситуации и вернуть оценку

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

• Иначе применить процедуру минимакса ко всем детям текущего узла, вернуть наибольший результат