25. Нетранзитивные механизмы и матрицы выплат

В этой главе

• Нетранзитивные механизмы.

• Поиск решения для нетранзитивных механизмов.

Нетранзитивные механизмы

Ничто не побьет старый добрый камень!

Барт Симпсон в 19-м эпизоде 4-го сезона сериала «Симпсоны» непосредственно перед тем, как Лиза выиграла у него, выбросив бумагу

В главе 8 мы уже говорили о транзитивных механизмах, в которых игровые объекты балансируются относительно кривой, соотносящей все их издержки со всеми их преимуществами. То есть в данном случае чем лучше та или иная вещь, тем больше она стоит. Такая балансировка неявно подразумевает, что один объект может быть лучше другого, то есть вы можете сравнить два игровых объекта и установить, что один из них однозначно лучше другого.

Однако таким образом работают не все игровые механизмы. В некоторых из них каждый объект может быть сильным по сравнению с одной вещью и слабым — по сравнению с другой. Таким образом, степень его полезности — не абсолютная, а относительная величина, определяемая по отношению к другому объекту (и она разная для каждого следующего объекта). Такие механизмы принято называть заумным словом «нетранзитивные». Наиболее простой и самый известный пример такого механизма — игра «Камень, ножницы, бумага». В ней бессмысленно говорить об абсолютном преимуществе или ценности, скажем, варианта «камень», поскольку она будет целиком зависеть от того, какой вариант выбросит противник.

Вы можете спросить: если нетранзитивные механизмы представляют собой что-то вроде игры «Камень, ножницы, бумага», то зачем вообще их применять? Никто не станет приглашать компанию друзей, чтобы провести несколько часов за этой игрой, почему же кто-то будет получать удовольствие от игры, использующей те же базовые механизмы в другой упаковке?

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

Нетранзитивные механизмы в той или иной форме используются в играх самых разных типов.

• В играх жанра «файтинг», таких как Street Fighter или Mortal Kombat, типичен следующий паттерн: обычную атаку может остановить блокировка, с блокировкой справляется бросок, а выполнение броска способна предотвратить обычная атака.

• Во многих стратегиях реального времени, таких как игры серии Warcraft, лета­ющие юниты легко уничтожают пехоту, пехотные — эффективно противостоят юнитам дальнего боя, а последние хорошо справляются с летающими юнитами.

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

• В шутерах от первого лица, позволяющих игроку использовать транспортные средства, например в серии игр Halo, могут существовать нетранзитивные отношения между транспортными средствами и оружием. Так, тяжелые виды оружия наподобие ракетомета хорошо справляются с большими танками, поскольку в силу значительного размера и неповоротливости их легко поражать с дальней дистанции. Танки прекрасно справляются с более легкими транспортными средствами, которые не способны противостоять им из-за недостаточной огневой мощи или дальности стрельбы. Легкие транспортные средства, в свою очередь, могут эффективно противостоять тяжелым видам оружия, легко уклоняясь от сравнительно медленно летящих ракет.

• Во многих многопользовательских сетевых и настольных ролевых играх не­которые классы персонажей особенно хороши в поединке один на один с неко­торыми другими классами персонажей и плохо справляются с рядом других классов.

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

• Иногда отношения между игровыми объектами неочевидны. Примером может служить игра, в которой юнитов с большой дальностью атаки (например, снайперов) могут уничтожать юниты с небольшой дальностью атаки, способные становиться невидимыми (киллеры), которых могут уничтожать юниты со средней дальностью атаки, способные видеть невидимых юнитов (тяжеловооруженные солдаты), а их, в свою очередь, могут уничтожать снайперы с дальней дистанции.

• Временами отношения между игровыми объектами носят чисто математический характер. Так, в игре Magic: the Gathering каждое существо обладает определенным уровнем силы (количеством наносимого урона) и прочности (количеством урона, необходимым для их уничтожения). Когда два существа сходятся друг с другом в поединке, они одновременно наносят друг другу то количество урона, на которое способны, пока не исчерпают прочность противника, если только одно из них не обладает способностью «первый удар», в случае чего оно атакует первым и получает урон от другого существа лишь в том случае, если после атаки еще живо. При этом существо 1/3 (с 1 единицей силы и 3 единицами прочности) убивает существо 2/1 со способностью «первый удар», выжив после первого удара. Существо 2/1 со способностью «первый удар» убивает существо 3/2, а существо 3/2 — существо 1/3. Хотя эти три вида существ могли изначально создаваться без намерения получить нетранзитивные отношения, в итоге они оказались связанными такими отношениями.

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

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

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

Поиск решения для нетранзитивных механизмов

Для начала давайте выясним, что представляет собой решение в случае применения нетранзитивных механизмов. В данном случае им не может быть кривая стоимости, поскольку ни один из возможных вариантов выбора здесь не будет однозначно лучше или хуже других. Решением будет соотношение, показывающее, как часто игрок должен выбирать каждый доступный вариант, а в случае асимметричной игры — как часто предположительно будет выбирать свои варианты противник. Например, при наличии нетранзитивной взаимосвязи между лучниками, пехотой и летающими юнитами решением может быть рекомендация при создании армии включить в нее 30 % лучников, 50 % пехоты и 20 % летающих юнитов, то есть использовать их в соотношении 3:5:2.

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

Как, по-вашему, должно выглядеть решение для игры «Камень, ножницы, бумага»? Поскольку каждый из выбрасываемых вариантов теоретически не лучше и не хуже остальных, можно предположить, что оптимальным здесь будет соотношение 1:1:1, то есть выбор каждого из вариантов с примерно одинаковой частотой. Если вы решите использовать иную стратегию, например с сочетанием 1:2:1, где чаще других вариантов выбирается бумага, то ваш противник может избрать доминирующую контрстратегию 0:0:1, где всегда выбираются ножницы, что позволит ему выигрывать чаще, чем проигрывать. Однако не существует стратегии, способной доминировать над стратегией 1:1:1. Именно это нам подсказывает интуиция, и верность данного предположения подтверждается расчетами. Однако важно понимать, какие математические выкладки позволяют прийти к этому решению, чтобы мы могли решать более сложные и запутанные проблемы, где все не столь очевидно.

Поиск решения для базового варианта игры «Камень, ножницы, бумага»

Прежде всего рассмотрим все возможные исходы этой игры. Обозначим выбрасываемые нами варианты прописными буквами R, P и S, а варианты противника — строчными r, p и s (по первым буквам английских слов rock — «камень», paper — «бумага» и scissors — «ножницы»). Поскольку считается, что выигрыш и проигрыш равны по величине и противоположны друг другу (то есть один выигрыш и один проигрыш уравновешивают друг друга), а ничья находится ровно посередине между ними, условимся, что победа, поражение и ничья дают +1, –1 и 0 очков соответственно.

Исходя из этого, можно составить следующую таблицу результатов.

Вариант	r	p	s
R	0	–1	+1
P	+1	0	–1
S	–1	+1	0

Она показывает, как выглядят результаты с нашей точки зрения. Если, например, мы выбросим камень (R), а противник — ножницы (s), то мы одержим победу и наше количество очков будет +1. То есть для противника эта таблица содержала бы противоположные значения.

Что в действительности представляют собой переменные r, p и s? Поскольку выбор нашего противника не известен заранее и мы его не контролируем, можно считать, что это вероятности того, что соперник выберет тот или иной вариант. То есть мы можем смоделировать его поведение с помощью взвешенных случайных переменных!

Можно также считать, что переменные R, P и S (варианты нашего выбора) представляют собой ожидаемое значение результата при выборе нами того или иного варианта выбрасывания, что в теории игр принято называть выплатой или выигрышем.

Теперь, умножив каждый результат на соответствующую вероятность, можем получить размер выплаты для каждого варианта выбрасывания:

.

Допустим, нам известно, что противник использует не слишком разумную стратегию, где r = 0,5 и p = s = 0,25. Как при этом будет выглядеть наилучшая контрстратегия? Подставив эти значения переменных в приведенные ранее уравнения, мы получим следующие размеры выплат: R = 0, P = 0,25, S = –0,25. Поскольку переменная P, которая соответствует варианту «бумага», имеет наибольшее значение, то при условии, что противник не будет варьировать свою стратегию, наилучшей контрстратегией будет постоянное выбрасывание варианта «бумага». При таком подходе мы предположительно будем получать 0,25 очка за каждое выбрасывание (то есть за каждые четыре выбрасывания будем выигрывать на одну игру больше, чем проигрывать). Как оказалось, для того чтобы размер выплаты для бумаги был положительным и превышал остальные, делая наилучшей стратегией ее постоянное выбрасывание, достаточно, чтобы противник выбрасывал камень хотя бы немного чаще, чем остальные варианты, например используя стратегию, где r = 0,3334, p = s = 0,3333. Это очень важное открытие — оно показывает, насколько хрупкими могут быть нетранзитивные механизмы: реализация лишь чуть-чуть неоптимальной стратегии игры часто делает для противника возможным применение полностью доминирующей контрстратегии.

Приближение к установившемуся состоянию

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

Прежде чем ответить на этот вопрос, нужно изложить несколько основополагающих принципов.

Теорема 1. Если механизмы игры симметричны, то решение одинаково для обоих игроков.

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

Теорема 2. Каждая из стратегий, применение которых имеет смысл, обеспечивает одинаковую выплату.

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

Теорема 3. В симметричных играх с нулевой суммой выплата каждой из жизнеспособных стратегий равна нулю.

Это характерно исключительно для тех игр, которые одновременно обладают и свойствами игры с нулевой суммой, и свойством симметричности. Согласно теореме 1, в симметричной игре решение должно быть одинаковым для обоих игроков и, соответственно, выплаты тоже должны быть одинаковыми. А в игре с нулевой суммой, по определению, сумма выплат должна быть равна нулю. Сумма двух равных чисел может равняться нулю лишь в том случае, если оба эти числа — нули.

Поскольку игра «Камень, ножницы, бумага» — это симметричная игра с нулевой суммой, мы можем воспользоваться этими тремя теоремами. А если точнее, то теперь мы знаем, что выплаты R, P и S должны быть одинаковыми и равняться нулю. Исходя из этого, можем переписать приведенные ранее уравнения, заменив в них выплаты нулями:

.

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

.

Можно решить эту систему из четырех уравнений с тремя неизвестными, используя простейшие алгебраические выкладки. Переписав первые три уравнения, можно определить, что s = p, r = s и p = r, то есть все три переменные равны друг другу. Подставив в последнем уравнении переменную r вместо переменных p и s, получим:

.

Поскольку переменные s и p равны переменной r, решение выглядит следующим образом: r = p = s = 1/3. То есть здесь нужно использовать соотношение 1/3:1/3:1/3 (или, если вам так больше нравится, 1:1:1), как, собственно, мы и предполагали.

Значит ли это, что оптимальная стратегия в игре «Камень, ножницы, бумага» сводится к тому, чтобы каждый раз выбирать вариант выбрасывания случайным образом, например, каждый раз определять выбираемый вариант, бросая кубик? Вовсе нет. Существует разница между тем, чтобы выбирать каждый вариант выбрасывания с примерно одинаковой частотой, и тем, чтобы вести игру совершенно случайным образом, не обращая внимания на то, как действует противник. На реальном турнире по игре «Камень, ножницы, бумага» стратегия с абсолютно случайным выбором позволит выиграть треть матчей, проиграть треть матчей и треть матчей закончить вничью — итоговый счет нулевой. Для того чтобы победить в турнире, необходимо обеспечить более высокий результат!

Как отмечалось в главе 20, большинство людей очень плохо справляются с задачей сознательного получения случайных результатов. В реальной игре против противника-человека наилучшая стратегия будет состоять в том, чтобы выявлять и обращать в свою пользу паттерны в его поведении, стараясь замаскировать любые явные паттерны в собственном поведении. То, что решением здесь является соотношение 1:1:1, вовсе не значит, что игрок должен выбирать тот или иной вариант в тот или иной момент времени, — здесь свою роль должно сыграть умение предугадывать будущие действия противника. Это означает лишь то, что с течением времени соотношение вариантов выбрасывания в наилучших стратегиях будет приближаться к соотношению 1:1:1, потому что любое отклонение от этого дает противнику явную возможность применения контрстратегии, позволяющей выигрывать чаще, чем проигрывать… По крайней мере до тех пор, пока игрок не скорректирует свою стратегию, вернувшись к соотношению 1:1:1.

Поиск решения для игры «Камень, ножницы, бумага» со стоимостью

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

Внесем в игру «Камень, ножницы, бумага» простое изменение: пусть теперь за каждую победу при выборе камня игрок получает в два раза больше очков, чем в иных вариантах. (Хотя это выглядит скорее как преимущество, чем как стоимость (или затраты, издержки), в случае симметричной игры с нулевой суммой затраты игрока равны по величине преимуществу, которое получает противник, поэтому здесь эти два термина фактически синонимы.) Как это изменение правил скажется на оптимальной стратегии? Подумайте о том, что вам подсказывает интуиция, и запишите ответ, прежде чем продолжить чтение.

Как и раньше, сначала составляем таблицу выплат.

Вариант	r	p	s
R	0	–1	+2
P	+1	0	–1
S	–2	+1	0

На ее основе можно составить формулы для каждой из трех выплат:

Новая версия игры — это по-прежнему симметричная игра с нулевой суммой, где оба игрока должны выбирать ровно один вариант выбрасывания, поэтому мы по-прежнему имеем два дополнительных условия: r + p + s = 1 и R = P = S = 0. В результате получим следующие уравнения:

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

Подставив r = 1/4 в предыдущие уравнения, получим: s = 1/4, p = 1/2. То есть оптимальным соотношением r:p:s в данном случае будет 1/4:1/2:1/4 (или 1:2:1). Соответствует ли это вашим предположениям? Вероятно, нет, потому что на первый взгляд данный ответ кажется совершенно нелогичным! Хотя мы увеличиваем размер выигрыша для камня, это в итоге приводит к более частому выбору бумаги. Однако если хорошо подумать, то такой результат вполне логичен: поскольку выбор ножниц несет повышенный риск, вероятность выбора этого варианта уменьшается и, зная, что противник вряд ли выберет ножницы, игроки начинают чаще выбирать бумагу, поскольку этот вариант редко ведет к поражению, обеспечивая либо выигрыш, либо ничью. В результате игроки на самом деле начинают чаще использовать не камень, а бумагу.

Таким образом, если в игре жанра «файтинг» успешный бросок будет наносить в два раза больший урон, чем успешная атака или блок, можно рассчитывать на то, что игроки будут в два раза чаще применять атаки, а не броски или блоки!

Поиск решения для игры «Камень, ножницы, бумага» с неполными победами и поражениями

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

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

Наконец, допустим, что производство рыцаря стоит 50 золотых монет, лучника — 75 монет и дракона — 100 монет. Как будет выглядеть решение в таком случае?

Как и раньше, начнем с составления таблицы выплат, обозначив буквами K (knight — «рыцарь»), A (archer — «лучник») и D (dragon — «дракон») размер выплат при выборе юнита того или иного типа, а буквами k, a и d — вероятности того, юнит какого типа выберет противник.

Юнит	k	a	d
K	0	+65	–50
A	–65	0	+70
D	+50	–70	0

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

В схватке между рыцарем и лучником рыцарь убивает лучника, получая преимущество в 75 золотых монет, но теряет при этом 20 % здоровья, и, поскольку рыцарь стоит 50 монет, потеря 20 % рыцаря стоит 10 монет. Таким образом, на самом деле в результате этой схватки рыцарь получает преимущество в 65 монет. Сходным образом в схватке между лучником и драконом лучник убивает дракона, что дает преимущество в 100 золотых монет, но теряет при этом 40 % здоровья, а потеря 40 % от 75 монет составляет –30 монет. Таким образом, здесь мы имеем чистую прибыль 70 золотых монет. В схватке между драконом и рыцарем дракон убивает рыцаря, что дает преимущество в 50 золотых монет, не испытывая при этом никакого урона. Таким образом, здесь чистая прибыль 50 монет. Тот факт, что дракон стоит 100 золотых монет, не играет здесь никакой роли: несмотря на то что владелец дракона заплатил за него довольно крупную сумму, он ничего не теряет… по крайней мере пока! Поскольку данная игра симметрична, в тех случаях, когда игрок, наоборот, теряет юнит в схватке с противником, мы просто подставляем числа с противоположным знаком.

Таким образом, в играх с разной стоимостью юнитов и неполными победами самый сложный момент — корректировка значений в таблице выплат. Дальше все делается абсолютно так же, как и раньше. Поскольку, как и прежде, мы имеем здесь дело с симметричной игрой с нулевой суммой, можем записать K = A = D = 0 и k + a + d = 1. Это дает нам следующую систему уравнений:

Выразив из второго и третьего уравнений переменные a и d через переменную k и подставив полученные выражения в последнее уравнение, получим:

Таким образом, в данном случае решение выглядит так: k:a:d = 14:10:13. То есть различные типы юнитов здесь будут использоваться с почти одинаковой частотой — с чуть более частым применением рыцарей и чуть более редким — лучников. Если вместо этого вам нужно, чтобы реже задействовались драконы, можете изменить стоимость драконов либо относительный уровень стоимости или наносимого урона других юнитов. Как мы уже видели, даже очень простое изменение одного игрового объекта может непредсказуемым образом сказаться на других объектах, потому самый простой способ получения правильных цифр сводится к тому, чтобы занести их в электронную таблицу и либо поиграть с ними вручную, либо привести их в порядок с помощью надстройки «Поиск решения».

Поиск решения для асимметричного варианта игры «Камень, ножницы, бумага»

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

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

Рис. 25.1

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

Это может существенно усложнить ситуацию. Мы знаем, что в симметричной игре вероятности и выплаты у обоих игроков совершенно одинаковы. При наличии же асимметрии эти значения могут не совпадать, что удваивает количество переменных в наших уравнениях и, соответственно, требует в два раза большей работы, хотя во всех прочих отношениях процесс расчета остается таким же, как и раньше. Допустим, в данном случае играют геймеры A и B и первый из них получает удвоенный выигрыш в случае победы с использованием камня. Как будет выглядеть оптимальная стратегия игрока A? Игрока B? Дает ли игроку А преимущество эта карта, и если да, то какое?

В данном случае мы имеем не одну, а две таблицы выплат.

Игрок A	rb	pb	sb
RA	0	–1	+2
PA	+1	0	–1
SA	–1	+1	0

Игрок B	ra	pa	sa
RB	0	–1	+1
PB	+1	0	–1
SB	–2	+1	0

Мы не можем воспользоваться старым трюком с приравниванием всех выплат к нулю, потому что нам неизвестно, равны ли выплаты игрока A выплатам игрока B (интуиция подсказывает, что это не так, поскольку один из игроков обладает асимметричным преимуществом). Однако нам по крайней мере известно, что все выплаты игрока А равны друг другу, то же самое справедливо для выплат игрока В и, поскольку данная версия игры по-прежнему остается игрой с нулевой суммой, выплата игрока А равна по величине и противоположна соответствующей выплате игрока B. Кроме того, поскольку каждый игрок по-прежнему должен выбирать ровно один вариант выбрасывания, вероятности выбора того или иного варианта должны давать в сумме 1. Таким образом, получаем слегка пугающую систему уравнений:

Конечно, здесь можно пойти трудным путем с выражением одних переменных через другие, но гораздо проще переписать таблицы выплат в виде матриц. Вот как будет выглядеть матрица выплат для игрока А:

.

Это сокращенный способ записи трех нижних уравнений из приведенной выше системы уравнений. Крайний справа столбец представляет правую часть уравнения, крайний слева — переменную rB, второй столбец — переменную pB и третий — переменную sB. Таким образом, верхняя строка данной матрицы эквивалентна уравнению 0rB – 1pB + 2sB = X, но опускает имена переменных и знак равенства. Мы могли бы оставить эти данные в исходном виде, то есть в виде уравнения, но, как вы увидите далее, такими цифрами проще манипулировать, когда можно сосредоточиться только на числах, на время забыв про буквы.

Как мы знаем, согласно правилам алгебры можно умножить обе части уравнения на одно и то же число и оно по-прежнему останется верным (если a = b, то na = nb для любого числа n). Вы также получите верное уравнение, если сложите вместе левые и правые части двух уравнений и приравняете друг к другу полученные суммы (если a = b и c = d, то a + c = b + d). Наконец, поскольку каждая строка в матрице представляет отдельное независимое уравнение, можете изменить порядок строк по своему усмотрению, поскольку он не имеет значения. Наша задача состоит в том, чтобы привести полученную матрицу к треугольному виду:

.

В треугольной матрице все элементы, расположенные под диагональю, которая обозначена звездочками, равны нулю. Все элементы, расположенные на самой диагонали, должны быть ненулевыми. Остальные элементы, расположенные выше диагонали (помечены вопросительными знаками), могут представлять собой любое значение, как нулевое, так и ненулевое.

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

.

Обратите внимание: это позволяет поместить ноль ниже первого диагонального элемента, а это как раз то, что нам нужно. Чтобы убрать –1 из левого нижнего угла, можно сложить друг с другом верхнюю и нижнюю строки, что даст нам строку , которой заменить нижнюю строку:

.

Теперь нам остается убрать лишь еще один ненулевой элемент, +1 в нижней строке. Чтобы сделать это, можно сложить друг с другом две нижние строки, что даст строку , которой заменить нижнюю строку:

.

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

Теперь мы можем решить эту систему уравнений, двигаясь снизу вверх и используя подстановку sB = 3X:

В этой точке мы еще не определили выплаты игрока А, но нам уже известно, что для игрока B решение выглядит следующим образом: rB:pB:sB = 4:5:3. Поскольку rB + pB + sB = 1, мы даже можем определить точный размер выплат: rB = 4/12, pB = 5/12, sB = 3/12. Это позволяет нам также определить значение переменной X: если rB = 4X = 4/12, то X = 1/12, что подтверждается расчетами на основе переменных pB и sB.

Чтобы определить оптимальную стратегию для игрока A, можно использовать описанный подход и для формул выплат игрока B. Исходные таблицы выплат здесь выглядят следующим образом.

Игрок A	rb	pb	sb
RA	0	–1	+2
PA	+1	0	–1
SA	–1	+1	0

Игрок B	ra	pa	sa
RB	0	–1	+1
PB	+1	0	–1
SB	–2	+1	0

Они дают матрицу выплат для игрока B:

.

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

.

Хотя нельзя убрать +1 из средней строки, просто сложив друг с другом две верхние строки, мы можем добиться этого, если сначала умножим среднюю строку на 2, а потом сложим ее с верхней строкой. (Еще один вариант — умножить верхнюю строку на 1/2, однако большинству людей проще умножать на целые числа, а не на дроби.) Умножив среднюю строку на 2, получим строку . Сложив ее с верхней строкой, получим строку , которой и заменим среднюю строку:

.

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

.

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

Таким образом, решение выглядит следующим образом: rA:pA:sA = 3:5:4, или 3/12:5/12:4/12, если мы учтем, что rA + pA + sA = 1. Это немного отличается от оптимальной стратегии для игрока B с соотношением 4/12:5/12:3/12 — значения для камня и ножниц меняются местами.

Так какое преимущество над игроком B получает игрок А, если вообще получает? Оказывается, мы уже знаем его размер, поскольку он равен размеру выплаты. Составляя исходную систему уравнений, мы предполагали, что для игроков А и B размер выплаты равен X и –X соответственно. Ранее мы установили, что X = 1/12. Это означает, что, когда оба игрока придерживаются оптимальной стратегии, рассматриваемая карта дает игроку A удивительно малое преимущество над игроком B, позволяя ему дополнительно выигрывать лишь одну из 12 игр.

Поиск решения для игры «Камень, ножницы, бумага, ящерица, Спок»

Все нетранзитивные механизмы, которые мы анализировали до сих пор, имели только три варианта выбора. А можно ли этот подход применить к большему количеству вариантов выбора? Да, вы можете это делать, и сейчас мы рассмотрим несколько таких случаев.

В игре «Камень, ножницы, бумага, ящерица, Спок», помимо трех обычных, задействуются два дополнительных варианта выбрасывания. Камень ломает ножницы и давит ящерицу, бумага оборачивает камень и подставляет Спока, ножницы разрезают бумагу и ящерицу, ящерица отравляет Спока и съедает бумагу, а Спок испаряет ножницы и камень. Таблица выплат выглядит, как показано далее (во избежание путаницы ящерица и Спок обозначены буквами z и k соответственно).

Вариант	r	p	s	z	k
R	0	–1	+1	+1	–1
P	+1	0	–1	–1	+1
S	–1	+1	0	+1	–1
Z	–1	+1	–1	0	+1
K	+1	–1	+1	–1	0

Поскольку это симметричная игра с нулевой суммой, мы знаем, что r + p + s + + z + k = 1 и R = P = S = Z = K = 0. Выполнив ручные расчеты описанным ранее способом, мы придем к вполне ожидаемому решению 1:1:1:1:1 (а точнее, каждая из вероятностей, r, p, s, z, k, равна 1/5).

Поиск решения для игры «Камень, ножницы, бумага, динамит»

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

Допустим, мы добавили в игру «Камень, ножницы, бумага» четвертый вариант выбрасывания, динамит, при выборе которого нужно показать кулак с поднятым вверх большим пальцем. Динамит побеждает камень, взрывая его, а ножницы побеждают динамит, отрезая фитиль. Относительно того, побеждает динамит бумагу или, наоборот, бумага побеждает динамит, мнения могут расходиться, однако пока допустим, что динамит побеждает бумагу. Теоретически это делает динамит и ножницы одинаково хорошим выбором, потому что оба эти варианта выбрасывания побеждают два из трех других вариантов. Это также делает камень и бумагу более слабыми вариантами, поскольку оба они проигрывают двум из трех других вариантов. Но к какому выводу мы придем, если проведем математический анализ этого случая?

Таблица выплат выглядит здесь следующим образом.

Вариант	r	p	s	d
R	0	–1	+1	–1
P	+1	0	–1	–1
S	–1	+1	0	+1
D	+1	+1	–1	0

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

Если бы мы попытались просто преобразовать представленную ранее таблицу в матрицу выплат размером 4 × 5 и найти решение, как делали раньше, то довольно быстро увидели бы, что эта матрица ведет себя странно и найти для нее решение таким образом невозможно (или по крайней мере можно найти только не имеющее смысла решение, где вероятности r, p, s и d меньше 0 или больше 1). Это объясняется тем, что мы исходили бы из предположения, что все выплаты равны (R = P = S = D), однако в данном случае это не так. Поскольку выбор бумаги здесь не имеет смысла, выплата этого варианта, вполне очевидно, должна быть меньше выплаты динамита.

Что же делать в такой ситуации? Мы должны последовательно убирать варианты выбора, над которыми доминируют другие варианты. В данном случае это значит, что из матрицы выплат нужно удалить строку переменной P и столбец переменной p.

Вариант	r	s	d
R	0	+1	–1
S	–1	0	+1
D	+1	–1	0

Теперь следует провести еще одну проверку и посмотреть, не осталось ли у нас еще каких-либо вариантов, над которыми доминируют другие варианты. В данном случае их больше нет, и мы получаем точно такую же таблицу выплат, как и в исходной версии игры «Камень, ножницы, бумага», в которой место бумаги занимает динамит.

Поиск решения для игры «Камень, ножницы, бумага, отбойный молоток»

А что, если мы добавим в игру «Камень, ножницы, бумага» новый вариант выбрасывания таким образом, чтобы над ним не доминировали другие варианты, причем он работал бы немного не так, как они? Допустим, мы добавили в игру вариант «отбойный молоток», при выборе которого нужно показать кулак, отведя его в сторону так, как будто вы держите рукоятку отбойного молотка. Отбойный молоток разбивает камень, получает от бумаги штраф за чрезмерный шум и достигает ничьей с ножницами, поскольку не может с ними как-либо взаимодействовать. То есть это инверсия варианта «ножницы», побеждающая тот вариант, которому проигрывают ножницы, и проигрывающая тому, который ножницы побеждают. Таблица выплат при этом выглядит следующим образом.

Вариант	r	p	s	j
R	0	–1	+1	–1
P	+1	0	–1	+1
S	–1	+1	0	0
J	+1	–1	0	0

Здесь ни один из вариантов не имеет явного преимущества над каким-либо другим — доминирующие стратегии отсутствуют. Поскольку это симметричная игра с нулевой суммой и оба игрока должны выбирать только один вариант выбрасывания, мы знаем, что r + p + s + j = 1 и R = P = S = J = 0. Таким образом, получаем следующую матрицу выплат:

.

Обратите внимание на то, что крайний справа столбец содержит нули, а не переменные X, поскольку нам известно, что выплата каждого варианта здесь равна нулю. Теперь приведем эту матрицу к треугольному виду. Сначала поменяем строки местами так, чтобы на диагонали находились только ненулевые значения:

.

Теперь, когда первый диагональный элемент в левом верхнем углу уже не равен нулю, можно спуститься ниже. Мы можем убрать –1 во второй строке, сложив ее с первой строкой и получив в результате строку . Мы также можем убрать +1 с левого края в третьей строке, вычтя эту строку из первой и получив в результате . Заменив таким образом вторую и третью строки, получим:

.

Любопытным моментом здесь является то, что вторая строка содержит только нули. Это не дает нам никакой полезной информации (в виде уравнения это будет выглядеть как 0 = 0, а мы и так знаем, что ноль равняется самому себе). Кроме того, две нижние строки абсолютно идентичны друг другу, в результате чего последняя становится избыточной, опять же не сообщая нам ничего нового. Поскольку вторая строка содержит исключительно нули, а диагональные элементы должны быть ненулевыми, данная матрица не может быть приведена к треугольному виду и, соответственно, не имеет однозначно определяемого решения. Если мы попробуем снова представить ее в виде уравнений, то, имея лишь две строки полезной информации, получим только два уравнения:

Подставив эти выражения в уравнение r + p + s + j = 1, можем выразить все переменные через переменную s:

после подстановки в уравнение r = p:

r = 1 – 2s;

после подстановки в уравнение j = s – p:

j = 3s – 1.

Соответственно мы можем присвоить переменной s любое значение и затем использовать ее для расчета остальных переменных. Но можно ли присвоить переменной s абсолютно любое значение? Нет. Как вы помните, все эти значения представляют собой вероятности, а значит, они должны находиться в диапазоне от 0 (что соответствует случаю, когда вариант никогда не выбирается) до 1 (что соответствует случаю, когда вариант выбирается постоянно). Это позволяет ограничить и диапазон значений переменной s. Из уравнения j = 3s – 1 можно сделать вывод о том, что переменная s должна быть не меньше 1/3 (чтобы переменная j не была отрицательной) и не больше 2/3 (чтобы j не была больше 100 %). Из двух других уравнений, p = r = 1 – 2s, можно сделать вывод о том, что переменная s должна находиться в диапазоне от 0 до 1/2. Если мы объединим эти два ограничения, то получится, что переменная s должна находиться в диапазоне от 1/3 до 1/2. Это весьма значимый вывод, который говорит о том, что ножницы являются неотъемлемой частью любой идеальной стратегии.

На нижней границе диапазона (s = 1/3) мы получим следующие значения: p = 1/3, r = 1/3 и j = 0. То есть одна из действенных стратегий здесь выглядит так же, как оптимальная стратегия обычной версии игры «Камень, ножницы, бумага». На верхней границе диапазона (s = 1/2) получим следующие значения: p = 0, r = 0 и j = 1/2. Можно выбрать и любую промежуточную стратегию, например, при s = 2/5 получим следующие значения: p = 1/5, r = 1/5 и j = 1/5. Мы имеем здесь бесконечно большое количество действенных стратегий, поскольку таково и количество значений в промежутке между 1/3 и 1/2.

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

Поиск решения для «игры Малкава»

Мы рассмотрели много вариаций игры «Камень, ножницы, бумага», но еще не рассматривали случай, когда игрокам доступны разные наборы вариантов, то есть когда асимметричны не только выплаты, но и сама игра. Что, если, например, одному игроку доступны шесть вариантов выбрасывания, а его противнику — только пять? На первый взгляд может показаться, что эта проблема не имеет однозначного решения, поскольку при шести неизвестных имеем только пять уравнений, но, как оказывается, при определенных условиях в таком случае все же можно найти однозначное решение, реализуя некоторые продвинутые методы. В одном из первых наборов карт коллекционной карточной игры Jyhad (позже она получила новое название Vampire: the Eternal Struggle) была карта с названием «игра Малкава» (Game of Malkav). При использовании этой карты ее обладатель втайне от других игроков выбирает число от 1 до 6, а остальные игроки — от 1 до 5. Затем все одновременно сообщают, какое число они выбрали, и каждый игрок получает количество очков здоровья, равное выбранному числу, если только другой игрок не выбрал на единицу меньшее число, в случае чего игрок, наоборот, теряет это количество здоровья. Например, если один игрок выберет число 4, а любой другой — 3, то первый потеряет 4 очка здоровья, а второй получит 3 очка, если же никто из других игроков не выберет число 3, то первый получит 4 очка здоровья. Поскольку при нескольких игроках динамика игры может сильно усложниться, рассмотрим случай, когда в нее играют только двое. Также для простоты будем считать, что это игра с нулевой суммой, то есть получение игроком 1 очка здоровья равно по стоимости потере 1 очка здоровья его противником. Мы можем попытаться узнать, какую ожидаемую выплату дает применение этой карты. Обеспечивает ли ее обладателю какое-либо преимущество то, что, помимо чисел от 1 до 5, он может выбирать также число 6? Какова наилучшая стратегия и ожидаемая выплата для обоих игроков? В общем, стоит ли включать эту карту в колоду и если да, то какое число следует выбирать игрокам при ее использовании?

Давайте, как обычно, начнем с составления таблицы выплат, обозначив варианты выбора игрока P1 — P6, а варианты выбора противника — o1 — o5.

Вариант	o1	o2	o3	o4	o5
P1	0	+3	–2	–3	–4
P2	–3	0	+5	–2	–3
P3	+2	–5	0	+7	–2
P4	+3	+2	–7	0	+9
P5	+4	+3	+2	–9	0
P6	+5	+4	+3	+2	–11

Например, если мы выберем число 3 (P3), а противник — число 5 (o5), то мы получим 3 очка здоровья, а противник — 5, таким образом, наш относительный уровень здоровья уменьшится на 2 очка, что указано в таблице как –2.

Если мы попробуем для начала выявить какие-либо доминирующие строки или столбцы, то увидим, что здесь таковых нет. Если попытаемся решить данную задачу с помощью описанных ранее методов (если хотите, попробуйте их применить!), то очень быстро поймем, что расчеты становятся слишком сложными, фактически невыполнимыми. Хотя здесь имеется шесть уравнений и пять неизвестных, что говорит о некоторой избыточности, мы не можем сократить какую-либо строку до нулей или найти две эквивалентные строки. Это означает, что в итоге как минимум два уравнения будут противоречить друг другу. А это, в свою очередь, говорит о том, что на самом деле здесь имеются доминирующие стратегии, которые просто трудно заметить сразу. Однако мы все же можем их обнаружить.

Чтобы найти вариант, наилучшим образом подходящий для обоих игроков, предположим, что они будут точно знать заранее, какой вариант выберет противник. Например, если он будет знать, что мы выберем вариант P1, то наилучшим выбором для него в этой строке будет вариант o5, при котором мы потеряем 4 очка здоровья. Теперь мы можем отреагировать на реакцию противника: зная, что он выберет вариант o5, можно установить, что наилучшим выбором для нас в этом столбце будет вариант P4. При выборе нами варианта P4 наилучшим выбором для противника в этой строке будет вариант o3. При выборе противником варианта o3 наилучшим выбором для нас в этом столбце будет вариант P2. Если мы изобразим это в виде ряда стрелок, ведущих к оптимальным ответам, это будет выглядеть так, как на рис. 25.2.

Рис. 25.2

При выборе нами варианта P2 противник может выбрать в этой строке два одинаково хороших варианта — o1 и o5. Рассмотрим обе эти возможности.

Если противник выберет вариант o5, то наилучшим выбором для нас в этом столбце будет вариант P4, и мы начнем ходить по кругу в нетранзитивной последовательности: o5 → P4 → o3 → P2 → o5… и так до бесконечности. Если же противник выберет вариант o1, то наилучшим выбором в этом столбце будет вариант P6. При выборе нами варианта P6 наилучшим выбором для противника будет вариант o5, лучшим ответом на который опять же будет вариант P4, и таким образом мы получим нетранзитивную последовательность o5 → P4 → o3 → P2 → o1 → P6 → o5… которая станет повторяться бесконечно. В графическом виде эти циклы будут выглядеть следующим образом (рис. 25.3).

Рис. 25.3

Однако все это лишь цепочка событий, происходящих после выбора нами варианта P1. Что, если мы начнем с другой отправной точки, например с варианта P3? Наилучшим ответом противника в этом случае будет вариант o2, наилучшим ответом на который — вариант P6… что снова ведет нас к циклу o5 → P4 → o3 → P2 → o1 → P6 → o5.

А если начнем с варианта P5? Наилучшим ответом противника будет вариант o4, наилучшим ответом на который — вариант P3, а что происходит при выборе в качестве отправной точки варианта P3, мы только что сказали. Таким образом, мы уже рассмотрели, что будет при выборе в качестве отправной точки вариантов P2, P4 и P6.

А что случится при выборе в качестве отправной точки вариантов o1 — o5? Все они уже встречались в описанных ранее последовательностях. Таким образом, нам нечего больше анализировать. Вот как выглядит наша диаграмма в итоге (рис. 25.4).

Как видите, вне зависимости от того, из какой точки начинается движение, в конечном итоге после ряда наших ходов и ответных ходов противника нетранзитивные особенности данной игры будут определяться небольшим подмножеством ходов (эти циклически выполняемые ходы выделены на диаграмме жирным). То есть здесь важны только варианты o1, o3, o5, P2, P4 и P6. Любой другой выбор оказывается в итоге менее эффективным: например, в любой из точек, где выгодно выбрать вариант P6 (где он дает положительную ожидаемую выплату), нет никакого смысла выбирать вместо этого вариант P5.

Рис. 25.4

Используя такой метод выявления нетранзитивных циклов в большом наборе вариантов, часто можно сократить пространство возможностей до меньшего набора эффективных вариантов или в худшем случае доказать, что все элементы большого набора представляют собой эффективные варианты. В случае с «игрой Малкава» мы можем сократить таблицу выплат до подмножества значимых вариантов.

Вариант	o1	o3	o5
P2	–3	+5	–3
P4	+3	–7	+9
P6	+5	+3	–11

Теперь эти данные можно поместить в матрицу выплат. Поскольку здесь мы имеем дело с несимметричной игрой, размер выплаты является неизвестной величиной, для обозначения которой снова воспользуемся переменной X:

.

Как и раньше, пройдемся по элементам первого столбца сверху вниз, чтобы привести матрицу к треугольному виду. Сложение двух первых строк дает нам строку . Чтобы избавиться от значения +5 в третьей строке, можно умножить третью строку на 3, первую строку — на 5, а затем сложить их, получив в результате строку :

.

Чтобы обнулить значение +34 в третьей строке, можно умножить вторую строку на 17, а затем сложить ее с третьей, что даст строку . Поскольку любую строку можно умножить на константу, мы также можем уменьшить числа в этой строке, умножив ее на 1/6. Тем самым приведем ее к виду . Заменив третью строку этим результатом, мы наконец приведем матрицу к треугольному виду:

.

Решая эту систему уравнений снизу вверх и используя подстановку, получим: o5 = 7X/9, o3 = 4X/3 и o1 = 0X/9. Зная, что o1 + o3 + o5 = 1, можно определить, что X = 9/29, o1 = 10/29, o3 = 12/29 и o5 = 7/29. Поскольку переменная X представляет собой размер выплаты, получаемой обладателем рассматриваемой карты, данный результат означает, что ее средняя стоимость составляет меньше 1/3 очка здоровья. Это не слишком много, но на практике в силу случайных колебаний эффект этой карты иногда может оказаться и более мощным. Мы также теперь знаем, как будет выглядеть оптимальная стратегия противника при ее наличии.

Однако мы еще не знаем, как будет выглядеть наилучшая стратегия обладателя карты. Чтобы узнать это, мы должны преобразовать матрицу так, чтобы она показывала выплаты противника (O1, O3, O5) и соответствующие вероятности выбора нами того или иного варианта (p2, p4, p6). Поскольку выплата противника имеет противоположный знак, можем обозначить ее –X. Сходным образом следует инвертировать и все остальные элементы матрицы (то, что дает нам преимущество в 3 очка, несет противнику потерю 3 очков). Это позволит получить следующую транспонированную матрицу:

.

После приведения к треугольному виду она будет выглядеть следующим образом:

.

Решив эту систему уравнений, получим следующий результат: p6 = 4X/9, p4 = 32X/27, p2 = 43X/27. Подставив уже известное нам значение X = 9/29, получим: p6 = 12/87, p4 = 32/87, p2 = 43/87, что подтверждается подстановкой в равенство p2 + p4 + p6 = 1.

Поиск решения для игры «Камень, ножницы, бумага» с тремя игроками

Если игроков несколько, найти решение для «игры Малкава» будет чрезвычайно сложно, поэтому мы не станем пытаться это сделать. В то же время будет полезно рассмотреть более простой случай игры «Камень, ножницы, бумага» с тремя игроками, чтобы посмотреть, как этот метод анализа можно задействовать в многопользовательской игре. Ведь, в конце концов, далеко не все игры с нетранзитивными механизмами представляют собой противостояние двух игроков в режиме «один на один». Некоторые из них позволяют вести борьбу в командном режиме или в режиме «каждый сам за себя».

Случай с командной игрой не представляет больших трудностей. Если в ней участвуют только две команды, можно провести анализ, рассматривая каждую команду как одного игрока. Найти решение для режима «каждый сам за себя» гораздо сложнее, потому что здесь любой игрок должен учесть все возможные комбинации ходов своих противников. Как мы увидим далее, сложность этой задачи существенно возрастает с появлением каждого нового участника. При трех игроках ее, хотя и с большим трудом, еще можно решить вручную. В крайнем случае вы можете попытаться найти решение для игры с четырьмя игроками. Но если захотите отыскать решение для нетранзитивной игры в режиме «каждый сам за себя» и шестью игроками, где каждый обладает своим набором возможных вариантов и асимметричной матрицей выплат, отражающей все возможные комбинации выбрасываний, то, хотя в принципе это и можно сделать вручную, в силу большой трудоемкости этого процесса все же лучше автоматизировать расчеты и позвать на помощь специалиста по теории игр.

Для начала уточним, как выглядит механика игры «Камень, ножницы, бумага» с тремя игроками. Допустим, здесь используются следующие правила. Если все игроки выбирают один и тот же вариант выбрасывания или три разных варианта (один камень, одну бумагу и одни ножницы в любой комбинации), засчитывается ничья, поскольку в таком случае нет никакой возможности выбрать победителя. Если два игрока выбирают один и тот же вариант, а третий игрок — какой-то иной (и, таким образом, в целом три игрока применяют только два варианта), один из вариантов выбрасывания побеждает другой. В таком случае каждый игрок получает по одному очку за каждого другого игрока, выбравшего более слабый вариант, и теряет по одному очку за каждого другого игрока, выбравшего более сильный вариант. Например, если Альберт и Бетти выберут бумагу, а Чарльз — ножницы, то Чарльз получит два очка, а Альберт и Бетти потеряют по одному очку. Если же вместо ножниц Чарльз выберет камень, то Альберт и Бетти получат по одному очку, а Чарльз потеряет два очка. (Такой способ начисления очков позволит получить игру с нулевой суммой и тем самым упростить расчеты. При желании можете использовать любой другой способ начисления очков.)

Конечно, мы знаем, что в силу симметрии решение игры «Камень, ножницы, бумага» для трех игроков будет выглядеть так же, как и для двух, а именно r:p:s = 1:1:1. Поэтому давайте введем в игру то же дополнительное правило, которое мы использовали раньше: пусть каждая победа, полученная с помощью камня, засчитывается как две (и поскольку это игра с нулевой суммой, это также значит, что игроки должны терять в два раза больше очков в том случае, когда они терпят поражение, выбрав ножницы). Как мы помним, для двух игроков решение видоизмененной версии игры выглядело как r:p:s = 1/4:1/2:1/4. Давайте посмотрим, не будет ли оно выглядеть иначе при трех игроках, когда у вас не один, а сразу два противника, что делает еще более опасным выбрасывание ножниц и еще более выгодным выбрасывание камня.

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

Вариант	rr	rp	rs	pp	ps	ss
R	0	–1	+2	–2	0	+4
P	+2	+1	0	0	–1	–2
S	–4	0	–2	+2	+1	0

Поскольку здесь представлены три уравнения и шесть неизвестных, эта система уравнений, по идее, не должна иметь однозначно определяемого решения. Однако мы все же можем найти ее решение, потому что, как известно, в симметричной игре противник должен иметь такие же вероятности. Хотя здесь возможны шесть исходов, каждый из них представляет собой произведение двух отдельных вероятностей, и вероятности r, p и s одинаковы у обоих противников.

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

Вариант	rr	rp	pr	rs	sr	pp	ps	sp	ss
R	0	–1	–1	+2	+2	–2	0	0	4
P	+2	+1	+1	0	0	0	–1	–1	–2
S	–4	0	0	–2	–2	+2	+1	+1	0

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

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

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

С чего следует начинать решение такой системы уравнений? Полезно сначала использовать уравнение r + s + p = 1 для исключения одной из переменных, выразив ее через другие и подставив это выражение в три других уравнения. Если мы решим выразить таким образом и подставить переменную для камня (r = 1 – s – p), то после выполнения всех операций умножения и объединения подобных членов получим:

Количество уравнений сократилось до трех, а количество неизвестных — до двух, что уже можно считать существенным прогрессом. Мы могли бы найти значение переменной p или s в первом или третьем уравнении, используя формулу для корней квадратного уравнения, которая дает два возможных результата (при этом один из них можно было бы исключить, если бы он выходил за рамки приемлемого для вероятностей диапазона от 0 до 1). Однако, поскольку второе уравнение намного проще, чем первое и третье, давайте сначала найдем его решение — p = 1 – 2s. Подставив это выражение в первое и третье уравнения, полу­чим одинаковый результат. Таким образом, теперь мы по крайней мере знаем, что в системе нет противоречий. После выполнения всех операций умножения и объединения подобных членов получим: 20ss – 26s + 6 = 0.

Теперь все-таки придется использовать так пугающую нас формулу для корней квадратного уравнения. Если вы уже толком не помните, как это делается, напомним, что ее можно применять для любого уравнения вида ax2 + bx + c = 0, где x — переменная, а a, b и c — числа:

.

В нашем случае a = 20, b = –26 и c = 6. Это дает два решения, в числителе одного из которых стоит плюс, а другого — минус. Подставив найденные значения, получим s = (26 + 14) / 40 и s = (26 – 14) / 40, то есть вероятность s может составлять 100 или 30 %. Допустимы ли в данном случае оба решения? Чтобы выяснить это, снова воспользуемся выражениями для подстановки и определим соответствующие значения двух других переменных. С помощью выражения p = 1 – 2s можно найти значение переменной p, а затем с помощью выражения r = 1 – s – p — значение переменной r. Это дает нам два решения: r = 100 %, p = –100 %, s = 100 % и r = 30 %, p = 40 %, s = 30 %. Очевидно, что первое решение недопустимо (значение переменной p отрицательное, что неприемлемо для вероятностей). Следовательно, остается только одно допустимое решение — r:p:s = 3:4:3.

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

Резюме

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

• Сначала следует составить таблицу выплат.

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

• Выявите все нетранзитивные циклы, определив, каким будет наилучший ответ на тот или иной исходный выбор игрока. Удалите строки или столбцы, элементы которых не входят ни в один из этих циклов.

• После выполнения всех этапов удаления в таблице должны остаться только жизнеспособные варианты выбора. Используя только эти данные, составьте матрицы выплат для каждого игрока, учитывая следующее:

• все выплаты каждого отдельного игрока равны друг другу;

• в игре с нулевой суммой выплаты всех игроков в сумме дают ноль (например, если в игре с двумя игроками выплата одного игрока X, то выплата его противника –X);

• в симметричной игре с нулевой суммой все выплаты равны нулю.

• Добавьте еще одно уравнение: если каждый игрок должен выбирать ровно один вариант, то вероятности всех вариантов в сумме дают 1. В асимметричной игре это будет справедливо для вариантов выбора каждого отдельного игрока, поэтому здесь вы можете получить несколько таких уравнений.

• Используя алгебраическую подстановку, треугольные матрицы, электронные таблицы и любые другие доступные средства, решите полученную систему уравнений, вычислив значение как можно большего количества неизвестных. Если удастся определить значение переменной X (размер выплаты для отдельного игрока), то вы узнаете, каким будет размер ожидаемого выигрыша или потери соответствующего игрока. Сложив вместе значения X всех игроков, вы узнаете, является ли ваша игра игрой с нулевой суммой (когда эти значения в сумме дают ноль), игрой с положительной суммой (когда они в сумме дают положительное число) или игрой с отрицательной суммой (когда их сумма — отрицательное число)… если, конечно, не знали этого изначально.

• Если вам удастся найти однозначно определяемое значение каждой вероятности, находящееся в диапазоне от 0 до 1, то это будут оптимальные вероятности выбора того или иного варианта выбрасывания. В асимметричной игре у каждого отдельного игрока может быть свое оптимальное решение. Это оптимальное соотношение и является искомым решением.

• В игре с более чем двумя участниками выберите выплаты одного из них в качестве ориентира, рассматривая всех остальных как одного совокупного противника. Появление каждого нового игрока будет значительно усложнять расчеты: три игрока дадут вам систему квадратных уравнений, четыре — кубических уравнений, пять — уравнений четвертой степени и т.д.

Теория игр — это огромная область знаний, которая охватывает множество и других разновидностей игр, о которых мы не упоминали в этой главе. Например, она позволяет проанализировать игры, в которых играющие делают выбор по очереди, а не одновременно, а также те, в которых они могут договариваться о чем-то заранее, просить или угрожать чем-то друг другу, координировать свои действия и т.д., что, например, часто встречается в играх с положительной суммой, где два игрока могут объединить свои усилия, чтобы опередить своих противников.

Вопросы для обсуждения

1. Начиная играть в обычную версию игры «Камень, ножницы, бумага» с новым противником, какой вариант вы, как правило, используете в первом выбрасывании и почему?

2. Какую роль в обычной версии игры «Камень, ножницы, бумага» играет удача, а какую — навыки? Не изменилось ли ваше мнение об этом после прочтения данной главы?

3. В чем состоит разница между транзитивными и нетранзитивными механизмами?

4. Приведите пример игры, в которой одновременно присутствуют и транзитивные, и нетранзитивные элементы. Как они взаимодействуют друг с другом?

5. Придумайте для игры «Камень, ножницы, бумага» один или два новых варианта выбрасывания в дополнение к упомянутым в этой главе. Как будут работать новые варианты (какие другие варианты они будут побеждать, а каким, наоборот, уступать)?

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

7. Придумайте новую систему начисления очков для игры «Камень, ножницы, бумага» (так, чтобы победа с помощью камня давала x очков, с помощью бумаги — y очков и с помощью ножниц — z очков, где x, y и z — конкретные значения). Попробуйте угадать, какой будет оптимальная стратегия при использовании этой новой системы начисления очков, опираясь на свою интуицию. Затем проведите анализ и найдите реальный ответ. Насколько близким к истине оказалось ваше предположение?

8. Когда двум игрокам нужно быстро решить, кто из них должен ходить первым, им стоит сыграть в «Чет-нечет», а не в «Камень, ножницы, бумага», поскольку игра «Чет-нечет» никогда не заканчивается ничьей. (В ней один из игроков выбирает «чет», а другой — «нечет», после чего оба выбирают либо 1, либо 2 и складывают эти числа вместе. В случае четного результата побеждает игрок, выбравший «чет», а в случае нечетного — выбравший «нечет».) А какой способ будет наиболее эффективным, когда нужно определить, кто должен ходить первым в игре с тремя игроками? Можете ли вы расширить свое решение так, чтобы оно подходило для игры с произвольным количеством игроков?

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

10. Помимо игры «Камень, ножницы, бумага, ящерица, Спок», существуют и другие версии, имеющие еще больше вариантов выбрасывания, включая RPS 25 и RPS 101, в которых 25 и 101 вариант выбрасывания соответственно (при желании вы легко найдете их описание в Интернете). Как вы считаете, версии с бóльшим разнообразием вариантов выбрасывания лучше или, наоборот, хуже, чем исходная версия игры? Почему?

Побочные квесты

Побочный квест 25.1. Игра «Камень, ножницы, бумага» для трех игроков с меньшим количеством ничьих

Рассматривая приведенный в этой главе пример с игрой «Камень, ножницы, бумага», рассчитанной на трех игроков, вы могли заметить, что ее правила можно было сделать еще более простыми. Так, игроки могли бы просто получать по одному очку за каждого более слабого противника и терять по одному очку за каждого более сильного.

Так, наверное, было бы проще? Причем это полностью совпадает с тем, что предписывают более сложные правила нашей исходной версии игры для трех игроков.

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

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

Побочный квест 25.2. Игра в жанре «файтинг»

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

• Игроки: два.

• Цель: снизить уровень здоровья противника до нуля быстрее, чем он снизит до нуля ваш.

• Подготовка: оба игрока изначально имеют по 10 очков здоровья.

• Игровой процесс представляет собой серию раундов. В каждом из них оба игрока выбирают одно из четырех действий: быструю атаку, интенсивную атаку, особую атаку и бросок. Исход раунда определяется следующим образом.

• Быстрая атака наносит 1 очко урона и парирует особую атаку и бросок (а при использовании противником интенсивной атаки против быстрой атаки он получает 1 очко урона, не нанося ответного урона).

• Интенсивная атака наносит 2 очка урона и парирует быструю атаку.

• Особая атака наносит 3 очка урона и парирует бросок.

• Бросок наносит 4 очка урона.

• Завершение игры: игра заканчивается, когда один из игроков теряет последнее очко здоровья (его уровень здоровья становится нулевым или отрицательным). Если оба игрока теряют последнее очко здоровья в одном раунде, игра заканчивается ничьей. В противном случае игрок, сохранивший положительный уровень здоровья, становится победителем.

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

При этом можно заметить, что стратегия игры начинает меняться после того, как уровень здоровья игроков становится неодинаковым, особенно при очень сильном снижении у одного из них. (Например, когда у игрока остается только 2 очка здоровья, бросок становится не более полезным приемом, чем интенсивная атака, поскольку завершить игру позволяют оба.)

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

Более объемная задача. Найдите решение этой игры для обоих игроков, предполагая, что один из них имеет 3 очка здоровья, а другой — 10 очков. В данном случае игрок, имеющий 10 очков здоровья, будет получать одинаковую выплату в случае успешного проведения как броска, так и особой атаки. Эту выплату можно считать и равной 3 очкам (потому что оба приема наносят по 3 очка урона), и равной бесконечности (так как оба приема обеспечивают немедленную победу в игре). Заметьте, что теперь игра будет иметь асимметричные выплаты, потому что игрок с 3 очками здоровья по-прежнему будет иметь основания для выбора каждого из четырех приемов. Как будет выглядеть оптимальная стратегия для первого и второго игроков?

Задача-максимум. Найдите решение игры для всех случаев, где оптимальная стратегия зависит от того, сколько здоровья остается у обоих игроков. Создайте в редакторе электронных таблиц «искусственный интеллект», выбирающий тот или иной прием случайным образом в зависимости от используемой вами стратегии и текущего количества очков. Если вы читаете эту книгу вместе с другими людьми, например, в учебной аудитории, проведите турнир по ИИ для игры жанра «файтинг». Пусть каждый участник представит свою формулу и попробует применить ее для борьбы с другими участниками в нескольких тысячах игр. Затем сравните и обсудите представленные участниками формулы. Чем объясняется эффективность победившей стратегии? Чем объясняется неэффективность других стратегий?

Побочный квест 25.3. Битва с использованием пяти карт

Вот еще одна игра.

• Игроки: два.

• Цель: быстрее соперника получить наибольшее количество очков или набрать больше очков, чем соперник, по итогам пяти раундов.

• Подготовка: оба игрока получают по набору из пяти карт с номерами от 1 до 5. Третья колода, тоже содержащая дающие очки карты с номерами от 1 до 5, тасуется и кладется лицевой стороной вниз.

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

• Завершение игры: после пяти раундов побеждает игрок, который набрал больше очков. Если оба набирают одинаковое количество, засчитывается ничья. Если один из игроков набирает 8 очков или больше еще до завершения пяти раундов, он сразу становится победителем, потому что уже получил бóльшую часть очков.

Легко заметить, что здесь нет единственной доминирующей стратегии. Если противник играет абсолютно случайным образом (с 20%-ной вероятностью выбора каждой карты в первом раунде), то игрок может сильно вырваться вперед, если станет выбирать из своей руки карту с номером, совпадающим со стоимостью каждого раунда (то есть выбирая карту с номером 3 в трехочковом раунде, карту с номером 5 в пятиочковом и т.д.). В борьбе со стратегией случайного выбора такая стратегия с совпадением позволяет выигрывать гораздо чаще, чем проигрывать.

Однако стратегия с совпадением тоже не доминирующая: этот подход можно легко победить, выбирая карту с номером, на единицу превышающим номер карты, дающей очки (и выбирая карту с номером 1, если это — карта с номером 5). В борьбе со стратегией с совпадением такая стратегия с превышением на 1 ведет к потере пятиочковой карты, но позволяет выиграть остальные четыре карты, что обеспечивает гарантированную победу с 10 очками против 5.

Но является ли доминирующей стратегия с превышением на 1? Нет, ее может победить стратегия с превышением на 2, которую, в свою очередь, может победить стратегия с превышением на 3, которую может победить стратегия с превышением на 4, которую снова может победить стратегия с совпадением. Таким образом, все эти стратегии нетранзитивные.

Цель игры фактически состоит в том, чтобы угадать, какую карту будет использовать противник, и выбрать карту с номером, превышающим номер этой карты на единицу (или выбрать карту с номером 1 при выборе противником карты с номером 5).

Поскольку ни одна из стратегий — с совпадением и превышением на 1, 2, 3 и 4 — не дает однозначного преимущества, можно подумать: не лучше ли просто выбирать одну из них случайным образом? Однако, как мы уже выяснили, стратегия с совпадением побеждает стратегию случайного выбора! Это означает, что, по-видимому, оптимально в данном случае не соотношение 1:1:1:1:1, а какое-то другое. Определите, как будет выглядеть оптимальная стратегия в первом раунде этой игры.

Подсказка: к решению задачи нужно подходить следующим образом. В любом заданном раунде можно использовать только пять стратегий: с совпадением и превышением на 1, 2, 3 или 4. Игрок может менять стратегию в каждом следующем раунде (как в игре «Камень, ножницы, бумага»), но в отсутствие какой-либо иной информации в первом раунде он может выбрать только одну из пяти стратегий, каждая из которых может оказаться успешной или неудачной в зависимости от того, что будет делать соперник. Если предположить, что изначально оба игрока могут использовать любую из пяти стратегий, то таблица выплат будет выглядеть, как показано далее. Вы можете найти соответствующее решение, преобразовав эти данные в матрицу выплат.

Стратегия	С совпадением	С превышением
		На 1	На 2	На 3	На 4
С совпадением	0	–5	+3	9	+13
С превышением на 1	+5	0	–7	–1	+3
С превышением на 2	–3	+7	0	–9	–10
С превышением на 3	–9	+1	+9	0	–11
С превышением на 4	–13	–3	+10	+11	0

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

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

---