Теория игр

27

3. Тымеладзе

Теория игр

Верда или Калимна?

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

ПОТЕРИ АРОКЕРОВ
СТРАТЕГИЯ ФИОЛЕТОВЫХ НАША СТРАТЕГИЯ
АТАКА НА КАЛИМНУ
ОБСТРЕЛ ВЕРДЫ
ЗАЩИТА ВЕРДЫ
6
3
ЗАЩИТА КАЛИМНЫ
1
5

Генералиссимус Дор покосился на табличку «Здесь молибден не описляют», но не стал взрывать к ней, а лишь молча кивнул Мотсу, представляя ему слово.

— У филотовых может быть только два плана: или звездолетаная атака на Калимну, или обстрел… — генерал Мотс заказаллся («угробит его в конце концов это присутствие к молибдену», — подумал Дор, но Мотс уже продолжал) — … или обстрел Верды. По моему мнению, мы должны все силы бросить на оборону Верды. Тогда, если противник атакует ее, мы потеряем лишь три боевых джокера.

— А если филотовые сунутся на Калимну? — нетерпelinво вместе Луд. — Тогда не сдобровать шести нашим джокерами.

Он самодовольно забросил в себя очередную порцию молибдена и продолжал:

— Калимна — вот наша главная опора. Все силы на ее защиту! Тогда атака на Калимну принесет филотовым в добьучу всего один джокер.

28

— А Верда? — подавился возмущением Мотс. — Мы потеряем там пять докеров!

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

Нахит неохотно ответил:

— У нас пока еще нет точных данных. Но, надо думать, противник тоже коллебляется. Иначе говоря, мы можем считать, что веряностъ принятия противником каждой плана равна $1/2$. Не беспокоятесь, господа, я так же, как и вы, не знаком с теорией веряностой. Из всей этой мудреной науки я знаю лишь, что веряностъ $1/2$ означает один шанс из двух, да еще правило для исчисления ожидаемых потерь. К примеру, если веряностъ наладения на Калимну составляет $1/2$, а наш потери в результате такого наладения будет равны шести докерам, то ожидаемые потери в Калимне составят $6 \times \frac{1}{2} = 3$. А если бы, скажем, веряностъ наладения составляла $1/3$, то это означает бы ожидаемые потери $6 \times \frac{1}{3} = 2$.

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

| СТРА-ТЕГИЯ | ОЖИДАЕМЫЕ ПОТЕРИ АРОКЕРОВ |
| :— | :— |
| в Калимне | в Верде | Итого |
| ЗАЩИТА ВЕРДЫ | $6 \times \frac{1}{2} = 3$ | $3 \times \frac{1}{2} = 1.5$ | $3 \times \frac{1}{2} = 1.5$ |
| ЗАЩИТА КАЛИМНЫ | $1 \times \frac{1}{2} = 1.5$ | $5 \times \frac{1}{2} = 2.5$ | $5 \times \frac{1}{2} = 2.5$ |

Вы видите, что при зашите Калимны мы потеряем на целых полтора докера меньше.

— Недурная осведомленность для начального разведки, — сызывил Луд, снова закладывая в себя молибden.

— А почему вы решили, что веряностъ наладений на Верду и Калимну равны? Мне так не кажется. По-моеу, фиолетовые скорее всего ринутся на Верду. Ведь они уже один раз ее брали. И если они атакуют Калимну в одном случае из четырех, то есть с веряностью $1/4$, а Верду — с веряностью $3/4$, то ваш расчет совсем к другому выводу:

Разве не ясно, что нам выгоднее защищать Верду?

— Личное мне не ясно, — возразил Дор. — Эти расчеты были оправданы, если бы можно было как-то обосновать оценки шансов наладения на Верду и Калимну. Но пока это один договора. А строить рассуждения на договора — это вредная привычка, вроде описания молибдена. И нам пора от нее избавляться.

Генералы скучно переглянулись—Дор один среди их пребегреgal молибдом.

— Нельзя ли принять правильный план, не делая заранее предположений о шансах принятии противником того или иного плана? Что думате вы, Рол, как ведущий военный теоретическ?

— Я читал в «Межпланетном вестике», что где-то на далекой планете построили теорию, позволяющую это сделать. Давайте предположим, что нам нужно использовать не один план, а оба, с неизвестными пока веряностями $p_1$ и $p_2$. Если, скажем, $p_1 = 0,2$, а $p_2 = 0,8$, то в двух случаях из десяти нужно защищать Верду, а восьми — Калимну. Иначе говоря, давайте ответим на неопределенность службыности.

— Мы не можем ставить судьбы сависимость от службы-

29

ности, — просипел Мотс. — Ведь речь идет … кхе-кхе… не о результате матча в брастул, а о судьбе государства, и…

— Продолжайте, Рол. Мне кажется, в ваших словах есть нечто интересное, — вместе рассудительный Дор.

— Теперь нам нужно найти эти вероятности $p_1$ и $p_2$. Разумеется, сумма их должны быть равна единице — ведь какое-то решение нам так или иначе придется принять:

$$p_1 + p_2 = 1.$$

(1)

— Интересно, как это вам удалось найти два неизвестных из одного уровня, — не успокаивался Луд.

— Давайте теперь потребуем, чтобы в любом случае среднее число потерянных докеров не превысило величины $v$, пока еще неизвестной, — продолжал Рол.

— Третье неизвестное! — с возможением заменил Луд, но Рол увлеченно продолжал, не обращая внимание ни на Луд, ни на других генеральов.

— Допустим, что филотовые направления на Калимну. Если бы мы приняли план защиты Верды, то потерялы бы брокеров, но поскольку мы защищаем Верду лишь с вероятностью $p_1$, то и потеряем на этом $6p_1$ докеров. С вероятностью $p_2$ мы защищаем Калимну, и это приведет к потере $1 \times p_2 = p_2$ докеров. Итого в результате направления противника на Калимну мы потеряем $6p_1 + p_2$ докеров. Чтобы не превысили величины $v$, должно выполнять неравенство:

$$6p_1 + p_2 \leq v.$$

(2)

— Но противник может напасть и на Верду, — напомнил Нахит.

— Да, и это дает нам еще такое неравенство:

$$3p_1 + 5p_2 \leq v.$$

(3)

Мне, как, найдесь, и вам всем, хотите бы чтобы величина $v$ была помещше. Однако она все же будет положительной: $v > 0$, — поскольку какое-то количество докеров нам придется потерять. Обозначим $x_1 = p_1/v$, $x_2 = p_2/v$, $L = 1/v$. Тогда неравенства (2) и (3), условия неотрицательности $p_1$ и $p_2$ и уравне-

напишутся так:

$$\begin{cases} 6x_1 + x_2 \leq 1, \\ 3x_1 + 5x_2 \leq 1, \\ x_1 \geq 0, \\ x_2 \geq 0, \\ L(x_1, x_2) = x_1 + x_2. \end{cases}$$

(4)

Нас интересует наименьшее значение $v$, поэтому $L$ должно быть наиболее низким. Задача отыскания из системы (4) $x_1$ и $x_2$, при которых функция $L(x_1, x_2)$ принимает наиболее низкое значение, называется життями той далекой планеты задачей линейного прораммирования *). При двух неизвестных $x_1$ и $x_2$ эту задачу можно решать графически. Каждый из неравенств системы (4) задает на координатной плоскости $x_1Ox_2$ полуплоскость, пересечение этих полуплоскостей образует четырехугольник (см. рис. 1), а уравнение $L = x_1 + x_2$ задает прямую, пересекающую оси координат в точках $x_1 = L$ и $x_2 = L$. При разных $L$ получаются параллельные прямые. Наибольшее $L$, при котором прямая $x_1 + x_2 = L$ пересекает четырехугольник (то есть система (4) имеет решение), соответствует точке $A$ (4/27; 1/9) и дает $L = 4/27 + 1/9 = 7/27$, поэтому $v = 27/7 = 3^6/7$, $p_1 = 4/7$, $p_2 = 3/7$. Таким образом, в четырех

*) См., например, статьи 3. Я. Тьмеладе «Физика и линейные неравенства» («Кваант», 1975, № 10), Б. Алейнкова, П. Бузыцкого, М. Дубсона «Симплекс-метод» («Кваант», 1976, № 7).

30

случаях из семи мы должны зашищать Верду, а в трех — Калимну. И наши потери составят в среднем менее четырехров.

— Но заметьте, — вмешался Мотс из-за облачка паров молибдена, — равные мы ожидали меньших потерь — только 3 или $3^3/4$ дрокера.
— Недвижительное, — возразил Нахит. — Ведь нам пришлось что-то заплаать за недостающую информацию.

Но тут не выдержал Луд.

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

Атмосфера снова начала накаплять, но вместество Дора неало разрастись взаимным упреком.

— Скажите, Рол, а как в этих условиях будет действовать противник? Есть ли у него оптимальная стратегия?

— Да, есть. Противник не знает наших планов, но ему известны последствия нападения на Верду и Калимну — его разведка обычно не подводит; поэтому он со своей стороны должен стать нанести нам наибольший урон. Если обозначить наш урон через $w$, а вероятности нападения противника на Калимну и Верду через $q_1$ и $q_2$, то $q_1 + q_2 = 1$, $6q_1 + 3q_2 \geq w$, $q_1 + 5q_2 \geq w$, $y_1 = q_1/w$, $y_2 = q_2/w$, $M = 1/w$, и противник придет к следующей за-

$$\begin{cases} 6y_1 + 3y_2 \geq 1, \\ y_1 + 5y_2 \geq 1, \\ y_1 \geq 0, \\ y_2 \geq 0, \\ M(y_1, y_2) = y_1 + y_2, \end{cases}$$

причем надо искать наименьшее значение $M$. Когда противнику удался решить эту задачу линейного противников, он получит: $y_1 = 2/27$, $y_2 = 5/27$, $M = 7/27$, откуда $q_1 = 2/7$, $q_2 = 5/7$, $w = 3^6/7$ (рис. 2).

To есть противник для достижения наибольшего уровня наимнимой в двух случаях из семи должны наладать на Верду, а в пяты — на Калимну. И его добиться будет равна тем же $3^6/7$ дрокера. Разумеется, он должен наладать так, чтобы мы не знали определенно, какое наладение предстоит.

— Учитывая работу нашей разведки, — не удержался Луд, — это нетрудно.

— Скажите, Рол, —ointересовался Дор, а что будет, если противник не станет следовать своей наличищей стратегии?

— В «Межпланетном вестнике» пишут, что всякое уклонение от нее может привести лишь к уменьшению успехов.

Рол закончил свою жестом победителья, но у Дора она не имела успеха.

— Я волне согласился бы с вами, Рол, если бы нам предстояло несколько стольконовей с филолетовыми. Но насжет лишь одна битва. Какое решение нам принять?

— Независимо от числа битв мы должны бросать своеобразный жеребий. Если бы оптимальная стратегия имела вид $p_1 = 1/2$, $p_2 = 1/2$, то достаточно было бы бросить монетку, загадывая на куху и кору. Стратегию $p_1 = 4/7$, $p_2 = 3/7$ реализовать несколько труднее. Но можно. Например, так: 4/7 — это примерно 34/60, а 3/7 — это 26/60. Можно взглянуть на часы, и если секундная стрелка будет между 0 и 34 секундами, принять решение оборонять Верду, а если между 34 и 60 — Калимну. Я считают, что так и нужно поступать, даже если битва всего одна.

31

Я не согласен! — возразил Мотс, и по многим причинами. Так стоило бы действовать, если бы нам противостоял разумный противник, равный нам по интеллекту — например, бордовые. Но филотовые принадлежат к низшей категории… кхекxe… их можно рассматривать просто как силы природу. Подумать только! Вместо молибдена эти варвары употребляют всему! Они никогда не допумаются…

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

Первое возвращение на Землю

Участики военного конфликта наделкой планете использвали математическую теорию, хорошо известную у нас на Земле, — теорию церр. Ее применяют в тех случаях, когда нет информации о замыслах противника. Первоначально эта теория развивалась применительно к азартным играм, от чего и получила свое название. Но затем ее приложения стали весьма многообразными — от экономики до военноного дела. Следует отметить, что исходные положения теории церр не бесспорны. И применима она, строго говоря, лишь тогда, когда игра повторяется достаточно много раз. Однако находится стороники ее применения и к однократным решением (в их числе — генерал Рол).

В числе многих интересных проблем теории игры — проблема смешанных стратегий. Нередко информация, имеющаяся в распоряжении того, кто принимает решение, недостаточная. В этих условиях невозможно указыть какую-то одну безусловно лучшую стратегию, и приходится прибегать к использованию смешанной стратегии — с некоторыми верятностями применения нескольких вариантов, как предложил впервые французский математик Эмиль Борель (1871—1956). Воспледствии для отыскания оптимальных смешанных стратегий стали применять линейное программирование.

Смешанные стратегии нуждаются вdamчикке случайных чисел (простейшие варианты таких датчиков — монета, часы с секундной стрелкой; размещется, существуют и более совершенные датчики случайных чисел, реализуемые на ЭВМ). Если смешанная стратегия не будет доставлять датчиком случайных чисел, а будет назначаться, есть опасность, что противник отгадает, какой варнант его ждет, и получит возможность действовать более эффективно. Но против случайной смешанной стратегии у противника только одно средство — использование своей оптимальной смешанной стратегии, также определяемой случайным образом.

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

Способ расужdenя, которое предложил генерал Нахит, — не зная, что сделает противник, считать все варнаntenы равноверятными — принимает англійскому математнику XVIII века Т. Бейесу.

Как мы уже отмечали, в теории игры нет единого, обоснованного решения действия, что дает простор для творчества. Именено это остояльство и определило дальнейший ход совещания при штабе сгенёвых после вынужденного перерыва, вызванного скверной привчкой генерала Мотса.

Калимна или Верда?

— Ну как, скоро? — торопил Дор врача.

Врач откинул спинной кожух Мотса и показал паяльником на пыльное хитросплетение тронутых ржавчиной транзисторов.

— Боюсь, что…

— Составьте дефектную ведомость, — коротко приказал Дор, — и дайте мне на утверждение.

32

Генералы понимающее мигнули — они знали закон сиреневых: после составления дефектной ведомости большого разбиали на запчасти, если стоимость ремонта превышала стоимость нового индивидума. А здесь, по-видимому, дело шло к этому.

Дор невозмутино продолжал.

— Я должны согласиться с генеральом Мотсом. Рекомендуемая стратегия сликом рациональная. Между тем даже в нашем обществе, которое по своей морали и интеллектуку куда выше общества филологически, не все действуют разумно. Иначе откуда бы развилось это губительное пространство к молибdenу, которое вдвое сокращает жизнь?

— Да будет позволено мнеставить слово, — снова вмешался Нахит. — К чему мы, собственно говоря, стремемся? Мы стремемся потерять как можно меньше докеров. Мы могли бы, разумется, принять превосходное решение, если бы знали в точности, на что решится противник. Но узнать это мы не можем, несмотря на то, что наша разведка прикладывает геронческие услуги.

— Вот именно, — выравлось у Луда.

— Давайте же действовать так, чтобы добиться наименьшего ущерба от возможных ошибок в выборе стратегии. Взглянем еще раз на таблицу. Если бы противник атаковал Калимну и мы зашищали Калимну, то противили бы всего один докер. Это было бы верное решение. А если бы стали зашищать Верdy, то противили бы лиших 6—1=5 докеров. Аналогично при обстреле Верды, зашищая Калимну, мы противили лиших 5—3=2 докера. Это позволяет составить следующую таблицу лиших потерь от неправильных решений:

| Стратегия филологических | Атака на Калимну | Обстрел Верды |
| :— | :— | :— |
| Защита Верды | 5 | ○ |
| Защита Калимны | ○ | 2 |

А теперь остается составить задачу линейного программирования: $5p_1 \leq v$, $2p_2 \leq v$, $p_1+p_2=1$, $z_1=p_1/v$, $z_2=p_2/v$, $K=1/v$, откуда получаем систему

$$\begin{cases} 5z_1 \leq 1, \\ 2z_2 \leq 1, \\ z_1 \geq 0, \\ z_2 \geq 0, \\ K(z_1, z_2) = z_1 + z_2. \end{cases}$$

Наименьшее $v$, то есть наиболее $K$, будет при $z_1=1/5$, $z_2=1/2$, откуда $K=7/10$, $v=10/7$, $p_1=2/7$, $p_2=5/7$. Смотрите-ка, было $p_1=4/7$, $p_2=3/7$, то есть $p_1>p_2$, а теперь наборот: $p_2>p_1$. По этому критерию зашита Верды к менее привлекательна. Вы были правы, генерал Луд.

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

— Так какой жребий вы предлагали, Рол? — спросил Дор, которое подход Нахита понравился больше, чем подход Рола, хотя Нахит решал совсем другую задачу: минимизировать не потери, а последствия ошибки. — Да, вспомним: часы. Прикинем: 2/7 — это 17/60. Всего семнадцать секунд решают судьбу планеты! Дор поднял к фотореле шестое шупальце с часами. Секундная стрелка была вблизи 47 секунд.

— Подготовиться к зашите Калимны! — приказал он. — Совещание объявляю закрытым! Посор филолетовым!

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

Второе возвращение на Землю

Да, такой исход трудно было предвидеть. Вся стратегия сиреневых стратегics на отсутствии информации у общих противников, в то время как филолетовые теперь будут принять