ТЕОРИЯ ИГР

Чем занимается теория игр

Что такое теория игр?

Это — математическая теория конфлик­тов.

А что такое конфликт?

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

Самые простые примеры конфликтов — это игры (шашки, шахматы, различные спор­тивные игры). Они отличаются тем, что ведутся по определенным правилам. Правила игры — это система условий, указывающих, какие воз­можности предоставляются игрокам (перечень возможных ходов); к какому результату (вы­игрышу, проигрышу) приводит каждая данная совокупность ходов.

Далеко не каждый встречающийся на прак­тике конфликт протекает по правилам. Чтобы сделать возможным математический анализ конфликта, нужно представить конфликт в игровой форме, т. е. указать стратегии (об­разы действий), возможные для участников, и уточнить, к какому результату приведет игра, если каждый из игроков выберет определен­ную стратегию. Таким образом, игра есть кон­фликт с четко сформулированными условиями.

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

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

Мы будем предполагать, что в любом конфликте выигрыш (проигрыш) каждого из игро­ков выражается числом. Тогда основную зада­чу теории игр можно сформулировать так: как должен вести себя (какую, стратегию при­менять) разумный игрок в конфликте с разум­ным противником (или противниками), что­бы обеспечить себе в среднем наибольший воз­можный выигрыш?

Парная игра с нулевой суммой. Цена игры

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

Каждую игру будем рассматривать как конфликт между двумя игроками: К («красные») и С («синие»). Для удобства рассуж­дений, чтобы иметь какую-то определенную точку зрения, будем обычно становиться на сторону одного из игроков (пусть это будет К) и говорить о нем «мы», а о другом — «про­тивник». Это не означает, что сторона К будет иметь какое-нибудь реальное преимущество. Просто нам так будет удобнее.

Игра называется игрой с нулевой суммой, если одна сторона выигрывает то, что проигрывает другая, т. е. сумма выигры­шей К и С равна нулю. В жизни часто встре­чаются конфликты, в которых это условие не соблюдается. Например, в военном столкнове­нии вполне возможно, что проигрывают обе стороны. Однако во многих случаях можно, не слишком искажая сущность явления, рас­сматривать парные конфликты как игры с ну­левой суммой.

Итак, допустим, что интересы К и С стро­го противоположны и что сумма выигрышей их равна нулю. Это будет для нас очень удобно в вычислительном смысле. Еще бы! Ведь если выигрыш К равен по величине и противополо­жен по знаку выигрышу С, то можно рассмат­ривать выигрыш только одного из игроков: выигрыш другого определится автоматически.

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

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

Если цена игры равна нулю, значит, это справедливая игра, т. е. она в одинаковой мере выгодна или невыгодна той и другой стороне. Если цена игры положительна, значит, игра выгодна для К. Если отрицательна, придется признать, что она выгодна для С...

Решить игру — это значит найти пару оптимальных стратегий (для К и С) и

цену игры, т. е. средний выигрыш игрока К, если оба — и К и С — будут вести себя разумно.

А если разумно будет вести себя только К, а не С? Ну что же — тем хуже для С! Вы­игрыш К от этого уменьшиться не может. В худшем случае он останется таким же, а в лучшем — увеличится.

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

Мы будем рассматривать только конечные игры, т. е. такие, в которых каждый участник располагает конечным числом стра­тегий.

Если у игрока К имеется в распоряжении т стратегий, а у игрока С имеется n стратегий, игра называется игрой т X п.

Правила игры можно записать в виде таблицы

(или матрицы), в которой m строк и n столбцов. Строки соответствуют стратегиям «красных», которые мы обозначим: K1, К2, ..., Кm, а столбцы — стратегиям «синих»: C1,C2 ...Cn.

В клетках таблицы помещены выигрыши (или средние выигрыши) «красных» при соот­ветствующей паре стратегий. Например, k12 — выигрыш, который получат «красные», если вы­берут стратегию К1, а «синие» — C2; вообще, kij — выигрыш «красных» при комбинации стратегий Кi и Cj.

Такая таблица называется платежной матрицей или просто матрицей игры.

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

Примеры конечных игр. Принцип минимакса

Приведем несколько примеров конечных игр. Каждую из них мы запишем в нормаль­ной форме.

Пример 1. Рассматривается игра, ко­торую назовем «Поиск». В ней участвуют две стороны: К и С. К хочет найти С; С, наоборот, хочет спрятаться от К.

У С есть два места — убежища I и II, где он может прятаться. Выбирает он себе любое убежище. Игрок К по правилам игры тоже может искать С, где ему вздумается. Если он нашел С, С проиграл одно очко, если не нашел, т. е. пошел не в то убежище, где спрятался Г, то, наоборот, К проиграл одно очко. Тре­буется записать игру в нормальной форме.

Решение. У К — две стратегии:

К1— искать в убежище I,

К2— искать в убежище II.

У С — тоже две стратегии:

С1 — прятаться в убежище I,

С2 — прятаться в убежище II. Игра конечная — 2x2, матрица игры будет:

К этой игре мы еще вернемся в дальнейшем и найдем ее решение. А пока что просто порас­суждаем за игрока К. Представим себе, что мы игрок К и что нам предлагается выбрать себе стратегию. Что ж, попробуем! Выберем, на­пример, K1, т. е. будем искать всегда в убе­жище I. Но тогда разумный противник через несколько партий догадается о нашей страте­гии и будет прятаться там, где мы его не ищем,

т. е. в убежище II. Плохо! Выберем стратегию К2. Ничуть не лучше: противник снова дога­дается и будет прятаться в убежище I. Что же нам делать? Попробуем применять стратегии К1 и K2 попеременно, через одну партию игры. Но ведь противник и об этом может догадать­ся и будет прятаться каждый раз не там, где мы его ищем. Как ни кинь — все клин! Что же, значит, наше положение безвыходно? При лю­бом выборе стратегии нам придется проигры­вать? Выходит, что так.

Давайте теперь встанем на точку зрения противника. С удивлением мы обнаружим, что его положение — ничуть не лучше нашего! Какую бы стратегию он ни выбрал — все ему невыгодно.

Позже мы с вами решим эту игру, т. е. найдем пару оптимальных стратегий К и С. Впрочем, о них можно по секрету сообщить заранее: каждому игроку надо будет чере­довать свои стратегии, но не регулярно (че­рез одну), а случайным образом (например, подбросить монету и, если она упа­дет гербом, искать в убежище I, а если цифрой — в убежище II). Аналогично должен будет дей­ствовать и С. При этом в среднем на одну пар­тию будет приходиться нулевой выигрыш (цена этой игры будет равна нулю): К не будет ни выигрывать, ни проигрывать. Не очень при­ятно, но все-таки много лучше, чем всегда быть в проигрыше!

Здесь мы впервые столкнулись с одним из важных понятий теории игр — с понятием смешанной стратегии, т. е. чере­дования нескольких «чистых» стратегий по слу­чайному закону в определенных пропорциях, или, как говорят, с определенными часто­там и. В данном примере каждая из страте­гий применяется с частотой 1/2.

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

Пример 2. Игра «Три пальца».

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

Решение. Перенумеруем стратегии по числу показанных пальцев. Игра 3x3. Матрица игры будет:

Поразмыслим немного над стратегиями каж­дой стороны. Станем сначала на сторону К. Предположим, что мы выбрали стратегию К1. Что будет делать противник? Он разумен и хо­чет отдать поменьше. Ясно, он выберет страте­гию C2; наш выигрыш при этом будет равен -3, т. е. мы потеряем 3 очка. Плоховато! За­пишем число -3 против первой строки в доба­вочном столбце (см. матрицу (3).

Попробуем другую стратегию — К2. На нее разумный противник ответит С3. Мы тогда потеряем 5 очков. Еще хуже! Третья страте­гия — К3 — дает точно тот же результат: вы­игрыш (-5).

Что же делать? Пожалуй, лучше других будет все-таки стратегия К1 — при ней мы по крайней мере не проиграем больше 3 очков! Ведь против этой стратегии стоит максималь­ное число дополнительного столбца — мы его отметили звездочкой.

Выбрав стратегию К1, мы гарантируем себе, что, как бы ни вел себя противник, мы никак не проиграем больше 3 очков (т. е. не выиграем мень­ше (-3) очков). Величина (-3) есть макси­мальный гарантированный выигрыш, который мы («красные») можем себе обеспечить, приме­няя только одну-единственную стратегию. Та­кой стратегией должна быть К1.

Как мы получили (-3)? Нашли минимум каждой строки и из этих минимумов взяли мак­симальный. Эта величина называется максимином или нижней ценой игры. Будем обозначать ее a.

Подумаем теперь за противника. Он тоже хочет отдать поменьше, а получить побольше. Но, какую бы он стратегию ни выбрал, мы («красные») поведем себя таким образом, чтобы получить с него побольше. Значит, противник («синие») должен в каждом столбце выписать не минимальное, а максимальное число (см. ниж­нюю добавочную строку в матрице (3).

Из этих максимумов он должен найти ми­нимальный, так называемый минимакс или верхняя цена игры, которую мы обозначим b. Эта величина в нашем случае равна 4 и отмечена звездочкой. Чтобы не проиграть больше 4, «синие» должны придерживаться любой из своих двух стратегий С1, С2.

Значит, если каждому участнику предлагается выбрать одну-единственную стратегию, то эти стратегии должны быть: К1 для «крас­ных» и С1 или C2 для «синих».

Как мы выбрали эти стратегии? Руководствуясь принципом осторожности, который говорит: в игре веди себя так, чтобы получить наибольшую выгоду при наихудших для тебя действиях противника. Этот принцип называется принципом минимакса и является в теории игр основным.

Применяя этот принцип, мы пока что реко­мендовали игроку К показывать один па­лец, игроку С — показывать один или два пальца.

Но нашли ли мы решение игры, т. е. та­кую пару стратегий, которая является равновесным положением? Легко убедиться, что нет. Найденные нами стратегии обладают досадным свойством: они неустойчивы. Действительно, пусть оба игрока дер­жатся рекомендованных чистых стратегий: К1 и, скажем, С1. Пока оба держатся этих стратегий, выигрыш будет равен 2, т. е. на каж­дую партию игры С проигрывает К два очка. К, может быть, и доволен, но С досадно. Он не хочет проигрывать. Допустим, он откуда-то узнал, что мы придерживаемся стратегии К1. Что он будет делать? Разумеется, немедленно перейдет к стратегии С2 и будет получать по 3 очка, т. е. сведет наш выигрыш к -3. А если мы теперь узнаем о поведении С? Перейдем на стратегию К2. В ответ на это С переидет на С3 и т. д.

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

Всегда ли это будет так? Оказывается, не всегда.

Седловая точка. Чистая цена игры

Рассмотрим пример. Пусть дана матрица игры (4):

Требуется найти нижнюю цену игры a, верхнюю цену игры b и минимаксные стра­тегии и проверить, являются ли они устой­чивыми.

Решение. Из анализа дополнительных столбца и строки получаем: a = 5, b=5. Максимин равен минимаксу! Случай особый. Что же из этого следует?

Возьмем пару минимаксных стратегий: К2 и С3. Если оба держатся этих стратегий, то выигрыш будет равен 5. Теперь, допустим, мы узнали о поведении противника. Что будем делать? А ничего! Мы по-прежнему будем дер­жаться стратегии К2, потому что любое отступ­ление от нее нам невыгодно. Знаем мы или не знаем о поведении противника — все равно будем держаться стратегии К2! То же относится и к «синим» — им нет смысла менять свою стратегию С3.

В данном примере пара стратегий К2 и С3 устойчива, т. е. представляет собой положение равновесия и дает решение игры.

Почему так получилось? Потому что в матрице имеется особый элемент 5; он является минимальным в своей строке и одновременно максимальным в своем столбце. Такой элемент называется седловой точкой. Если матри­ца имеет седловую точку (т. е. нижняя цена игры равна верхней), то игра имеет решение в чистых стратегиях: это — пара стратегий, пересекающихся в седловой точке. Сама же седловая точка дает цену игры — в нашем примере она равна 5.

Класс игр, имеющих седловую точку, имеет большое значение в теории игр. В частности,

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

Примерами игр с полной информацией мо­гут служить: шахматы, шашки, «крестики и нолики» и т. п.

Приведем пример игры с полной информацией, решение которой легко найти.

Два игрока — К и С — поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигры­вает тот из игроков, который положит монету последним (когда места для других уже не остается).

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

Очевидно, такая игра имеет смысл только для тех, кто не знает решения. Любопытно, что совершенно так же обстоит дело и с такой популярной игрой, как шахматы! Эта игра име­ет смысл только до тех пор, пока не найдено ее решение.

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

Наверное, любители шахмат заинтересованы в том, чтобы шахматная игра была решена еще не скоро.

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

Решение игры в смешанных стратегиях. Основная теорема теории игр

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

А если a¹b? Можно доказать, что и в этом случае решение всегда есть, только оно лежит не в области чистых, а в области смешан­ных стратегий. Решением игры называется такая пара стратегий — в общем случае смешанных, систематическое применение которых обеспечивает каждой стороне макси­мально возможный для нее по условиям игры выигрыш, определяемый ценой игры. Если же одна из сторон отступает от своей оптималь­ной стратегии (в то время как другая продол­жает придерживаться своей), то это ни в коем случае не может быть выгодно для отступаю­щего: это либо оставит его выигрыш неизменным, либо уменьшит. Таким образом, каждая конеч­ная игра имеет решение (возможно, в области смешанных стратегий). Это положение назы­вается основной теоремой теории игр.

Введем специальное обозначение для сме­шанных стратегий. Пусть К применяет свои стратегии К1, К2, К3 с частотами соответст­венно р1, р2, р3 (p1+p2+p3=1). Эту смешанную стратегию будем обозначать:

Аналогично смешанную стратегию игрока Г будем обозначать:

Очевидно, любая чистая стратегия — част­ный случай смешанной, в которой все частоты, кроме одной, равны нулю, а одна — единице.

Решение игры — пару оптимальных стра­тегий — будем обозначать S*k и S*c , а соответ­ствующий ему выигрыш (цену игры) v.

Очевидно, что цена игры v не может быть мень­ше нижней и больше верхней цены:

a£v£b.

В первом примере мы путем нестрогих соображений догадались, что решение игры должно быть:

а цена игры v = 0. Проверим это. Пусть мы («красные») держимся своей стратегии S*k, т. е. ищем С в убежище I и II одинаково часто, че­редуя эти стратегии случайным образом. Мо­жет ли С улучшить свое положение (повысить свой выигрыш), отступая любым образом от своей стратегии S*с? Очевидно, нет. А если од­ностороннее отступление от стратегии S*k при­дет в голову нам (в то время как разумный С будет держаться стратегии S*c), то это нам то­же не может быть выгодно. Значит, мы и в са­мом деле нашли решение игры и ее цену v = 0. Правда, эта игра была довольно простой! Уже второй пример дает игру, решение которой не так очевидно. Из того, что в нем a¹b, сле­дует только, что решение нужно искать в сме­шанных стратегиях.

Но каково это решение? Какова цена игры? Выгодна ли игра «красным», или «синим», или никому из них?

Ответы на эти вопросы вы можете найти в книге, указанной на стр. 509.

Решения и ответы

Решение к стр. 386. Введем обоз­начения: а — Саша, b — Костя, с — не Саша, d —18 лет, е — 21 год и f — 25 лет.

Мама сказала: «a•е», папа сказал: «b•d», а дочь сказала: «с•f». Так как часть каждой информации неверна (имеет значение 0), то a•e=b•d=c•f=0 и а+е=1, b+d=l, c+f=l. Сын Николая Ивановича не может иметь сразу два имени и два возраста; следовательно, а•b=a•с=d•e=d•e=e•f=0.

Перемножим суммы a+е=1 и b+d=l, тогда a•b+a•d+b•e+e•d=1; после выбрасывания нулевых членов останется равенство: a•d+b•e=1. Перемножим эту сумму и сумму с+f=1,что после выбрасывания нуле­вых членов даст равенство b•с•е=1, откуда следует, что b=1, с=1 и е=1 (верная информация). Значит, сына Николая Ивановича зовут не Саша (с=1), а Костя (b=1) и возраст его 21 год (е=1).

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

38/x.

Во второй раз рыбовод выловил 53 рыбы, из них две меченые. Следовательно, отношение числа меченых рыб к числу выловленных равно 2/53.

Будем предполагать, что меченые рыбы равномерно распределились сре­ди всех рыб в водоеме, тогда оба отношения одинаковы: 38/x=2/53, откуда

x=1007.

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