Что если мы создадим новую фигуру, над которой не будут сильно доминировать другие фигуры, но роль которой будет немного иной? Например, фигуру — эквивалент ножниц, но с обратным действием: она будет побеждает камень, но проигрывать бумаге? Ну-ка… Строительная машина (С), которая разбивает (побеждает) камень и проигрывает бумаге; при выпадении с ножницами — ничья, потому что обе фигуры особо невзаимодействуют. Теперь наша матрица выигрышей выглядит следующим образом:
| к | б | н | с | |
| К | -1 | +1 | -1 | |
| Б | +1 | -1 | +1 | |
| Н | -1 | +1 | ||
| С | +1 | -1 |
В данном примерени у одной фигуры нет какого-то особого преимущества перед другой, так что давайте перейдём к решению. Мы знаем, что к+б+н+с=1, а выигрыши К=Б=Н=С=0.
Итак, наша матрица будет выглядеть следующим образом:
0 -1 +1 -1 0
+1 0 -1 +1 0
[ -1 +1 0 0 0 ]
+1 -1 0 0 0
Меняем последовательность строк, чтобы показатели, неравные нулю, находились по диагонали, для этого меняем порядок строк:
+1 -1 0 0 0
-1 +1 0 0 0
[ +1 0 -1 +1 0 ]
0 -1 +1 -1 0
Суммируем две первые строки и получаем в первой строке показатели, равные 0, вычитаем третью строку из первой и получаем следующие результаты:
+1 -1 0 0 0
0 0 0 0 0
[ 0 -1 +1 -1 0 ]
0 -1 +1 -1 0
Интересно, что все показатели во второй сроке равны 0 (в этом нет никакой полезной информации, это всего лишь означает, что 0 равен 0), и две последние строки совершенно одинаковые (что значит, что последняя строка лишняя и не сообщает нам никакой дополнительной информации).Таким образом, у нас остаётся только две строки полезной информации. Иначе говоря, у нас есть два уравнения (три, если посчитать к+б+н+с=1) и четыре неизвестные величины.
Это значит, что на самом деле решений для данного примера несколько, возможно, их бесконечно много.
Запишем решения:
- к-б=0, поэтому к=б
- -б+н-с=0, поэтому с=н-б
Заменяем величины в уравнении к+б+н+с=1 и получаем:
- б+б+н+(н-б)=1, поэтому б+2н=1, поэтому б=1-2н (и поэтому к=1-2н).
Заменяем величины в с=н-б и получаем с=н-1+2н, поэтому с=3н-1.
Таким образом, при помощи н мы можем вывести три другие переменные:
- б=1-2н
- к=1-2н
- с=3н-1
На первый взгляд может показаться, что для данного примера существует бесконечное количество решений: выберите любую величину для н и сможете посчитать соответствующие значения для б, к и с. Но можно сузить диапазон.
Каким образом? Давайте вспомним, что все эти переменные — это вероятности, то есть диапазон их значений должен быть от 0 (если событие никогда не происходит) до 1 (если событие происходит всегда).Вероятности никогда не могут быть меньше нуля или больше 1. С помощью этого правила мы можем ограничить диапазон для н. Начнем с того, что диапазон значения должен быть от 0 до 1.
Из уравнения с=3н-1 мы знаем, что н должно равняться минимум 1/3 (иначе с будет отрицательным) и максимально значение н может быть 2/3 (иначе с будет больше 100%). Если же мы посмотрим на б и к, мы узнаем, что диапазон значения н от 0 до 1/2. При совмещении двух величин диапазон н должен быть от 1/3 до 1/2. Это интересно: мы видим, что Ножницы в любом случае остаются незаменимым элементом любой стратегии, и их используют постоянно – от трети всего времени до доброй половины.
При условии, что нижняя граница (н=1/3), мы обнаруживаем следующее: б=1/3, к=1/3, с=0, и это тоже верная стратегия. При нижней границе (н=1/2) мы находим это: б=0, к=0, с=1/2. Мы также можем выбрать любую стратегию между этими значениями, скажем, н=2/5, б=1/5, к=1/5, с=1/5.
Есть ли среди этих стратегий какая-нибудь одна, которая лучше прочих, та, которая приносила бы победу чаще, чем остальные? К сожалению, для ответа на этот вопрос нужно поговорить о теории игр чуть больше, чем я сегодня рассчитывал, но, если вкратце, «это зависит от разных обстоятельств», и этот ответ основан на определенных предположениях о том, насколько рациональны ваши противники; могут ли игроки иногда ошибаться в своей стратегии; что игрокам известно о методах противников, и от многого другого. Давайте просто скажем, что все причины хороши, хотя, я уверен, профессионалы в области теории игр могут поспорить о том, что важнее чего.
Также мы можем сказать, что Строительная машина, вероятно, не самое лучшее дополнение к КНБ, поскольку ее присутствие допускает одну стратегию победы, где эту фигуру можно вообще игнорировать, и еще одну – где можно пренебречь и Б, и К. Это заставит задуматься, а зачем вообще тратить ресурсы разработки на ввод двух из трех фигур, которые могут вообще не использоваться, когда игроки набьют руку!
Решаем «GameofMalkav»
До настоящего момента мы постепенно разбирались с каждым нашим предположением: что в игре симметричен выигрыш, что это игра с нулевой суммой, что есть всего три фигуры. Но есть один момент, который мы не прояснили в варианте игры с двумя игроками – что случится, если у игроков будут разные варианты фигур. Будет уже не просто несимметричный выигрыш, а несимметричная игра. Если мы будем опираться на предположение, что у одного игрока столько же фигур, сколько и у другого, что случится, если, скажем, у одного игрока шесть фигур, а у его противника – всего лишь пять? Казалось бы, такого рода задача нерешаема для уникального уравнения (ведь неизвестных шесть, а уравнений всего пять, верно?), но, по сути, получается, что мы в некоторых случаях можем использовать более мощную технику для решения этой задачи в уникальном порядке.
Давайте рассмотрим карту под названием «GameofMalkav» из странной ККИ, о которой большинство из вас, наверное, и не слышало. Она применяется следующим образом: все игроки втайне друг от друга одновременно загадывают число. Игрок, у которого эта карта, выбирает число в диапазоне от 1 до 6, а все остальные – от 1 до 5. Каждый игрок получает количество очков жизни, равное выбранному номеру… если только другой игрок не выбрал число, меньшее на 1 – в этом случае игрок теряет столько очков жизни. Например, если вы выбрали 5, вы получаете 5 очков жизни, если только кто-то другой не выбрал 4. В таком случае вы теряете 5 очков жизни, а противник получает 4, если только кто-то не выбрал 3… и так далее. Чем больше игроков, тем сложнее, так что давайте рассмотрим вариант, где их только двое. Давайте также сделаем упрощающее допущение, что игра – с нулевой суммой, и, если вы получаете 1 очко жизни, противник его теряет (я понимаю, что это не всегда верно, и это будет варьироваться в зависимости от относительных итогов, но так мы, по крайней мере, начнем понимать, что это вообще за карта).
Мы можем задуматься, а какой вообще ожидаемый выигрыш от этой карты? Помогает ли то, что у вас 6 ходов, а у вашего противника – всего 5? Какова лучшая стратегия, и к какому результату мы ожидаем прийти? Короче говоря, имеет ли смысл использовать эту карту… и, если да, как вы решите, используя ее, какое число загадать?
Как обычно, начнем с таблицы выигрышей. Давайте назовем столбцы И1-И6 (игрок), а строки – П1-П5 (противник):
| П1 | П2 | П3 | П4 | П5 | |
| И1 | +3 | -2 | -3 | -4 | |
| И2 | -3 | +5 | -2 | -3 | |
| И3 | +2 | -5 | +7 | -2 | |
| И4 | +3 | +2 | -7 | +9 | |
| И5 | +4 | +3 | +2 | -9 | |
| И6 | +5 | +4 | +3 | +2 | -11 |
Мы могли бы попытаться решить ее, и, кажется, ни для одного, ни для второго игрока нет вариантов, над которыми доминируют другие, но мы бы быстро обнаружили, что в цифрах куча знаков после запятой… а еще то, что решения, оказывается, нет – и причину вы бы обнаружили, как только принялись за решение. По сути, 6 уравнений и 5 переменных создают избыточность… только вот в этом случае мы не можем откинуть строки, и в конце концов вы получите как минимум два противоречащих друг другу уравнения. Так что здесь не может не быть стратегий, над которыми доминируют другие стратегии… дело просто в том, что они очевидны не сразу, потому что у нас здесь несколько строк или столбцов, над всеми которыми сразу доминируют другие несколько строк, и это нельзя заметить невооруженным взглядом. Как же нам тогда их найти?
Мы начнем с того, что найдем лучшие варианты для каждого игрока, как если бы игрок знал, что сделает его противник, заранее. К примеру, если противник знает, что мы выбросим И1, их лучшим вариантом стал бы П5 (тогда у него было бы чистые +4, а у нас – чистые -4). Но затем мы бы продолжили реагировать на их реакцию: если игрок знает, что противник выберет П5, лучшим ходом станет И4. Но лучший ход против И4 – П3. Лучший ход против П3 – И2. Лучших ходом против И2 два – П1 и П5, так что рассмотрим оба варианта:
>>Лучший ответ на П5 – это И4, как и ранее (и мы можем продолжать непереходную последовательность П5->И4->П3->И2->П5 бесконечно).
>> Лучший ответ на П1 – И6. Лучший ход против И6 – П5, что снова приводит нас к непереходной последовательности П5->И4->П3->И2->П1->И6->П5.
А что, если мы начнем не оттуда, скажем, первым нашим ходом станет И3? Тогда противнику следует будет выбрать П2, мы ответим на это И6, что в итоге приведет нас к петле П5->И4->П3->И2->П1->И6->П5. Если мы начнем с П5, противник выберет П4, на что получит И3 в ответ, а мы только что рассмотрели этот случай. Почему бы нам не начать с П1, П2, П3, П4, П5, P2, И4 или И6? Мы уже обсуждали эти варианты, анализировать больше нечего.
Таким образом, неважно, откуда мы начинаем, в конце концов, после того, как мы совсем немного поиграем, поймем, что только небольшая фиксированная последовательность ходов на самом деле является частью непереходной натуры этой игры, потому что эти ходы создают две непереходные петли: П5/И4/П3/И2 и П5/И4/П3/И2/П1/И6. Если мы посмотрим на эти последовательности, то увидим, что игроки всегда выбирают либо П1, П3, П5, либо И2, И4, И6. Любой другой вариант невыгоден: например, в любом моменте, где кажется, что использовать И6 – выгодно (то есть вы ожидаете, что выиграете), на самом деле нет никакой причины использовать И5 (даже если вы ожидаете, что ваш противник сделает ход П5, вам лучше использовать не И5, а И4).
Если вы используете эту технику для того, чтобы находить непереходные петли, часто можно уменьшить более широкий спектр вариантов до маленького, в котором будут только подходящие варианты… или, на худой конец, вы докажете, что все эти варианты имеют право на существование. Время от времени вам будут встречаться игры (Prisoner’s Dilemma – довольно-таки известный пример, если вы о нем слышали), где для обоих игроков существуют одинаково дающие преимущество зоны в игровом пространстве, так что при последующих раундах можно ожидать, что все игроки будут оказываться в этих зонах; специалисты в теории игр называют такие случаи равновесием Нэша в честь математика, который первым их описал (можете на этом не заморачиваться).
В данном случае мы можем сократить таблицу до нескольких переменных, которые нам интересны:
| П1 | П3 | П5 | |
| И2 | -3 | +5 | -3 |
| И4 | +3 | -7 | +9 |
| И6 | +5 | +3 | -11 |
Запомните, что эти переменные несимметричны. Таким образом, мы знаем, что П1=П3=П5 и И2=И4=И6, но мы не знаем, равны ли они все нулю, или одна отрицательна по отношению к другой (предполагается, что И1 – положительна, а П1 – отрицательна, раз уж мы ожидаем, что у игрока с этой картой есть преимущество, но… посмотрим).
Мы составляем матрицу, используя Х, который обозначает выигрыш для И2, И4 и И6:
-3 +5 -3 X
[ +3 -7 +9 X ]
+5 +3 -11 X
Ее можно сократить до треугольной формы и решить так же, как мы делали раньше. Попробуйте сделать это самостоятельно! Ответ я приведу ниже.
Итак, решив эту матрицу, вы получите вероятности П1, П3 и П5, но, чтобы узнать вероятности выбора И2, И4 и И6, вам нужно повернуть матрицу по диагонали, так, чтобы все П оказались слева, а И – наверху (иными словами, вы ее транспонируете). В данном случае нам также потребуется сделать все числа отрицательными, потому что это матрица с точки зрения противника, и, следовательно, выигрыши противоположны:
+3 -3 -5 Y
[ -5 +7 -3 Y ]
+3 -9 +11 Y
Ее тоже можно решить, как обычно. Если вам интересно, ответы будут приблизительно такими:
И2:И4:И6 = 49%: 37%: 14%
П1:П3:П5 = 35%: 41%: 24%
Ожидаемый выигрыш для игрока И (выше он обозначен как Х) — 0.31; выигрыш для игрока П (Y) отрицателен по отношению к Х — -0.31.
Иными словами, если в эту игру играют двое и играют оптимально, игрок с этой картой в среднем получает преимуществов одну треть очка жизни – так что, пока мы доказывали, что использование этой карты и возможность выбора числа 6 – это преимущество, оказалось, что это не совсем так. С другой стороны, вероятность внезапных крупных изменений может сделать эту карту стоящей в настоящей игре (или нет) – все зависит от вашей колоды. И, разумеется, игра заметно усложняется, если игроков трое или больше – эти случаи мы здесь не рассматриваем.