Решаем КНБ для трех игроков




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

Если команды всего две, решить задачу просто: всего-то и нужно, что посчитать каждую команду как отдельного игрока. В случае соревнований со свободным входом все немного сложнее, поскольку нужно будет принимать во внимание тот факт, что противников несколько; позже мы убедимся в том, что сложность возрастает с каждым последующим игроком. Решить КНБ для трех игроков сложно и неприятно, но все-таки возможно. Четыре игрока – вероятно, максимальное количество участников, с которыми я бы рискнул решать задачи одним из тех методов, которые мы сегодня рассмотрели. Если у вас интранзитивная игра с шестью участниками, где у каждого – свои варианты фигур, и огромная матрица выигрышей для каждого игрока с его комбинациями… ну, скажем так, решение все-таки возможно, но не без помощи компьютера и профессионального игрового теоретика, но сейчас не забивайте себе этим голову. Теоретики усвоили одно: чем сложнее игра, тем сложнее игрокам сойтись на оптимальных стратегиях… что означает, что при невероятно сложных условиях игры тестирование даст вам представление о том, как игра работает, что называется, «в поле», и это намного лучше, чем проводить бесконечные математические расчеты в надежде найти оптимальные решения, потому что игроки, скорее всего, не придут к единому мнению по поводу этих самых решений. Таким образом, для подобной сложной системы вам лучше использовать тестирование в игровом процессе… или, что более вероятно, вам придется упростить игровую механику!

Давайте рассмотрим простой случай: КНБ с тремя игроками. Определим правила следующим образом: если все игроки выбрасывают одну и ту же фигуру или три разных – это ничья. Если фигура одинакова у двух игроков, а третий – «третий лишний» — то тот, кто выбросил фигуру, которая принесла победу, получает по 1 очку от каждого проигравшего.Например, если у двоих –Камень, а у третьего – Ножницы, каждый игрок с Камнем получает +1 очка, а неудачник с ножницами теряет 2 очка. Или наоборот: у одного игрока Камень, а у двух других – Бумага, игрок с Камнем получает +2 очка, а двое других по одному теряют (вся идея в том, чтобы для простоты сохранить нулевую сумму игры, но можете использовать этот метод для решения других задач с механизмом счета).

Конечно, благодаря симметрии мы знаем, что ответ – 1:1:1, как и в версии с двумя игроками. Так что давайте воспользуемся той же схемой, что и раньше: победа при помощи Камня засчитывается как двойная (и из-за нулевой суммы это также значит, что проигрыш с Ножницами – двойной). В случае с двумя игроками мы обнаружили, что решение Камень=Ножницы=1/4, Бумага=1/2. Изменит ли положение ситуация с тремя игроками, ведь сейчас у нас два противника, из-за которых выбрасывать Ножницы – еще опаснее (и, возможно, еще выгоднее выбрасывать Камень)?

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

  кк кб кн бб бн нн
К   -1 +2 -2   +4
Б +2 +1     -1 -2
Н -4   -2 +2 +1  

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

  кк кб бк кн нк бб бн нб нн
К   -1 -1 +2 +2 -2     +4
Н +2 +1 +1       -1 -1 -2
Б -4     -2 -2 +2 +1 +1  

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

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

>> Выигрыш для К= -2кб+4кн-2бб+4нн = 0

>>Выигрыш для Б= 2кк+2кб-2нб-2нн = 0

>>Выигрыш для Н= -4кк-4кн+2бб+2бн = 0

>> к+н+б=1 (как обычно)

В конце «=0», поскольку мы знаем, что это симметричная игра с нулевой суммой.

С чего начинать, имея на руках подобные расчеты? Обычно полезно начать с к+н+б=1, чтобы убрать одну из переменных, совместив ее с другими слагаемыми, и затем подставить результат в три вышеприведенных уравнения выигрыша. Избавившись от Камня (к=1-н-б) и подставляя результат, после умножения и сложения, мы получим:

>> -4бб+2бн-2б+4н = 0

>> -2б-4н+2 = 0

>> 2бб-6бн+8б+4н-4 = 0

Мы могли изолировать либо б, либо н в первом или последнем уравнении, используя квадратичную формулу (ну, знаете, «минус б плюс или минус квадратный корень из 4ас и разделить все на 2а»). Это дало бы нам два возможных решения, хотя в большинстве случаев вы обнаружите, что можете одно исключить, так как оно выбивается за границы от 0 до 1 (в которых должны оставаться к, б и н, поскольку они все – вероятности).

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

>> б=1-2н

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

>> 20нн-26н+6 = 0

Здесь нам все-таки придется использовать ту квадратичную формулу, которой мы так боялись. Умножив все, мы получим: н=(26+/-14)/40… таким образом, н=100% или н=30%.
Оба ли эти решения верны? Чтобы убедиться в этом, нам нужно найти численное значение б=1-2н и любого другого уравнения с к.

Если н=30%, мы высчитываем, что б=40%, а к=30%, так что решение верно.

Если н=100%, мы высчитываем, что б= -100%, а к=100%, и это неверно (значение б не может быть ниже нуля), так что у нас остается всего один правильный ответ: к:б:н = 3:4:3.

Оказывается, случай с несколькими игроками влияет на задачу «победы с Камнем засчитываются как двойные», но мы, может быть, ожидали не такого результата; с тремя игроками ответ ближе к 1:1:1, чем с двумя! Возможно, это из-за того, что вероятность исхода с ничьей повышается, если один игрок выберет Камень, другой – Ножницы, а третий – Бумагу. И выбирать Бумагу здесь не так рискованно, как в варианте с двумя игроками, ведь, даже если один противник выберет Камень, другой может тоже выбрать Бумагу, и это превратит двойной проигрыш в ничью.

Подведем итоги

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

— Составьте таблицу выигрышей.

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

— Найдите все непереходные «петли», найдя лучший ответный ход на первый ход каждого игрока.

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

— Добавьте еще одно уравнение, которое сведет сумму вероятностей всех выборов к 1.

— Используя алгебраическую замену, треугольные матрицы, Excel или любые другие имеющиеся в вашем распоряжении средства, решите так много переменных, сколько сможете. Если вам удастся найти значение Х, вы найдете ожидаемый выигрыш (или проигрыш) игрока. Сложив значения Х всех игроков, вы поймете, какая у вас игра: с нулевой суммой (X1+X2+…=0), с положительной (>0) или отрицательной (<0), и насколько она такова.

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

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

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

Если вы сейчас работаете над игрой…

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

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

Домашнее задание

Не стесняйтесь выполнять расчеты вручную, если вы хотите подтвердить решения всех приведенных мной задач, — практика никогда не помешает. Когда почувствуете себя уверенно, вот вам небольшая задачка, основанная на мини-игре, которую я однажды видел в серии РПГ Suikoden (не помню, в какой именно игре). В настоящей игре было 13 карт, но я упрощу задачу: здесь будет колода из 5 карт. Вот правила:

  • Игроков двое.
  • Начало игры: каждый игрок берет 5 карт, пронумерованных от 1 до 5. Третья такая колода тасуется и кладется рубашкой вверх на стол.
  • Игровой процесс: в начале каждого раунда карта из колоды переворачивается рисунком вверх; очки по итогам раунда присуждаются в зависимости от цифры на карте. Оба игрока одновременно выбирают одну из своих карт. Побеждает тот, у кого цифра больше; если карты одинаковы – ничья. Оба игрока откладывают эти карты в сторону, их больше использовать нельзя.
  • Итог: игра оканчивается либо после 5 раундов, либо тогда, когда кто-то набирает 8 очков и побеждает.

Как видите, здесь нет определенной доминирующей стратегии. Если противник играет совершенно случайным образом (20% — шанс вытаскивания любой карты), вы можете просто брать ту карту, цифра на которой совпадает с количеством очков, присуждаемых в этом раунде (ходите картой с 3, если выпадает карта с 3, бейте 4 карту с 4 и так далее). Это можно продемонстрировать в Excel, смешав карты противника так, чтобы они выпадали в случайном порядке и, сравнив эту стратегию с описанной выше стратегией «совпадающих цифр», и вы быстро обнаружите, что совпадение цифр приносит победу в большинстве случаев (также, если хотите, можете вычислить все возможные шансы, поскольку существует всего 120 способов перестроить 5 карт).

Означает ли это, что стратегия с совпадением очков – доминантна? Конечно, нет. Если я знаю, что мой противник использует эту стратегию, я смогу победить, играя картой, на которой цифра на 1 больше, чем очков в этом раунде, а в раунде с 5 очками я просто использую карту с 1. Я потеряю 5 очков, но получу другие 10 для победы. Доминирует ли стратегия «больше на 1»? Нет, она проигрывает стратегии «больше на 2»… и так далее, а «больше на 4» проигрывает стратегии «совпадающих цифр» — это непереходные взаимоотношения. Суть этой игры в том, чтобы угадать, какой картой пойдет ваш противник и пойти той, на которой цифра больше на 1 (если у противника 5 – берите 1).

Поскольку все эти стратегии одинаково хороши, вы можете подумать, что можно выбирать любую… но, как мы только что увидели, «совпадающие очки» побьют вашу стратегию! Так что, возможно, оптимальное соотношение не 1:1:1:1:1, а какое-то другое. Можете попробовать его найти.

Если вы не уверены, с чего начать, посмотрите на ситуацию так: в любом случае, стратегий всего 5: совпадающие цифры, больше на одну, больше на две, больше на три и больше на 4. Рассчитайте таблицу выигрышей для каждой, учитывая все пять карт. Можете менять стратегии каждый раунд, как в КНБ, но, как бы то ни было, в первом раунде у вас всего пять вариантов, и каждый может как помочь вам выиграть, так и привести к поражению – в зависимости от стратегии противника. Таким образом, хотя бы для первой игры вам нужна будет эта таблица выигрышей (в конце концов, у вас всего пять карт и пять стратегий в первом раунде):

  сопадающие больше на 1 на 2 на 3 на 4
С   -5 +3 +9 +13
+1 +5   -7 -1 +3
+2 -3 +7   -9 -10
+3 -9 +1 +9   -11
+4 -13 -3 +10 +11  

 

Ссылки

Вот несколько ссылок, которые показались мне полезными, когда я писал эту статью:

“Game Architecture and Design” (Rollings& Morris), главы 3 и 5.

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

“Game Theory: a Critical Text” (Heap &Varoufakis). Книга показалась мне удобным и в меру доступным введением в теорию игр. Должен предупредить, что в целях краткости авторы часто используют собственные акронимы. То есть просто пролистать некоторые места не получится, ведь из-за этого можно пропустить ключевые понятия, а еще иногда там встречаются предложения, в которых больше нераспознаваемых акронимов, чем нормальных слов!



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-06-11 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: