Игра в нормальной форме. Матрица игры
Мы будем рассматривать только конечные игры, т. е. такие,
в которых каждый участник располагает конечным числом стратегий.
Если у игрока К имеется в распоряжении m стратегий, а у игрока
С - п стратегий, игра называется игрой т х п. Правила
игры можно записать в виде следующей таблицы (или матрицы), в
которой m строк и п столбцов:
Игра "Осада и оборона города"
"Красные" стремятся занять город, "синие" обороняют его. У "красных"
-два отряда, каждый из которых они могут направить по любой из двух
дорог - 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
с одинаковыми частотами. Выигрыш будет средним арифметическим
соответствующих строк. Матрица примет вид:
Строки соответствуют стратегиям "красных", которые мы обозначим:
К1, K2>, ... Km,
а столбцы - стратегиям "синих": C1, С2,
... Сп В клетках таблицы помещены выигрыши (или средние
выигрыши) "красных" при соответствующей паре стратегий. Например,
k12 - выигрыш, который получат "красные", если выберут
стратегию К1, а "синие"-С2;
вообще, kij -выигрыш "красных" при комбинации
стратегий Ki и Сj.. Такая таблица
называется платежной матрицей или просто матрицей игры.
Если конечная игра записана в виде такой матрицы, то говорят,
что она приведена к нормальной форме.
Но попробуйте, например, записать в нормальной форме обыкновенные
шахматы! Вы сразу столкнетесь с тем, что количество возможных стратегий
необозримо велико - настолько велико, что их перечисление выходит
за пределы возможностей не только человека, но и современной вычислительной
машины.
А жаль! Потому что, если бы построение матрицы шахматной игры было
возможно, это имело бы очень любопытные последствия... Но не будем
забегать вперед.
|