2i.SU
Математика

Математика

Содержание раздела

Теория игр

Игра в нормальной форме. Матрица игры

Мы будем рассматривать только конечные игры, т. е. такие, в которых каждый участник располагает конечным числом стратегий. Если у игрока К имеется в распоряжении m стратегий, а у игрока С - п стратегий, игра называется игрой т х п. Правила игры можно записать в виде следующей таблицы (или матрицы), в которой m строк и п столбцов:

3440-1.jpg

Игра "Осада и оборона города"

"Красные" стремятся занять город, "синие" обороняют его. У "красных" -два отряда, каждый из которых они могут направить по любой из двух дорог - I и II, ведущих к городу. У "синих" три отряда, которые могут разместиться произвольным образом на любой из двух дорог. Никто из противников не осведомлен об образе действий другого. Условия таковы: если на дороге встречаются равные силы "красных" и "синих", то в 50% случаев "красные" побеждают и занимают город, в 50% -отступают. Если "красные" встречаются с превосходящими силами "синих" (один отряд - с двумя или два - с тремя), они отступают. Определить, как должны распорядиться своими отрядами "красные" и "синие", чтобы обеспечить себе наилучшие возможные результаты игры. Решение. У "красных" три стратегии: K1 -послать оба отряда по дороге I, К2- послать оба отряда по дороге II, К3 - послать на каждую дорогу по одному отряду.

У "синих" - четыре стратегии: С1 - поставить все три отряда на дорогу I, С2 - поставить все три отряда на дорогу II, С3 - поставить два отряда на дорогу I, а один - на дорогу II, С4 - поставить два отряда на дорогу II, а один - на дорогу I. Выигрышем будем считать процент случаев, когда "красным" удается занять город. Матрица игры будет иметь вид (а = 50 %, Р = 100%; об а и бета см. стр. 434):

  С1 С2 C3 C4 Минимумы строк
К1 0% 100% 50% 100% 0%
K2 100% 0% 100% 50% 0%
K3 100% 100% 50% 50% 50%
Максимумы столбцов 100% 100% 100% 100%  

Ищем решение в смешанных стратегиях. Сразу же замечаем, что стратегии К1и K2 симметричны и, значит, должны входить в решение с одинаковыми частотами : P1=P2

Объединим эти две стратегии в одну К12, которая состоит в применении К1и К2 с одинаковыми частотами. Выигрыш будет средним арифметическим соответствующих строк. Матрица примет вид:

3440-2.jpg

Строки соответствуют стратегиям "красных", которые мы обозначим: К1, K2>, ... Km, а столбцы - стратегиям "синих": C1, С2, ... Сп В клетках таблицы помещены выигрыши (или средние выигрыши) "красных" при соответствующей паре стратегий. Например, k12 - выигрыш, который получат "красные", если выберут стратегию К1, а "синие"-С2; вообще, kij -выигрыш "красных" при комбинации стратегий Ki и Сj.. Такая таблица называется платежной матрицей или просто матрицей игры. Если конечная игра записана в виде такой матрицы, то говорят, что она приведена к нормальной форме.

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

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

перейти к началу страницы


2i.SU ©® 2015 Яндекс.Метрика Рейтинг@Mail.ruРейтинг@Mail.ru