Решаем кнб с неравным соотношением

До настоящего момента мы по умолчанию считали, что игра симметрична: и у игрока, и у противника одинаковое количество ходов, и мы оба выигрываем или теряем одинаковое количество очков или единиц чего-либо, и всё это подчиняется единому своду правил. Но не все интранзитивные игры одинаково симметричны. Например, давайте представим, что я создал вариант КНБ, в котором в каждом раунде я открываю новую карту, которая меняет выигрыши. В этом раунде, согласно моей карте,мой противник получаетдва очка за победу, выкинув Камень, а я – нет (я бы набрал обычное количество очков). Как это все меняет? Вообще-то это здорово усложняет ситуацию, поскольку теперь оба игрока должны просчитывать вероятности фигур противника, а эти вероятности уже могут измениться! Скажем, игрок А получает бонус в виде двух очков за победу с Камнем, а игрок Б – нет. Какова оптимальная стратегия для обоих игроков? И какое преимущество у игрока А, и есть ли оно вообще? Давайте выясним это, составив две таблицы выигрышей.

Таблица игрока А будет выглядеть так:

	кБ	бБ	нБ
КА	0	-1	+2
БА	+1	0	-1
НА	-1	+1	0

Таблица игрока Б будет выглядеть так:

	кА	бА	нА
КБ	0	-1	+1
ББ	+1	0	-1
НБ	-2	+1	0

Здесь мы можем предположить, что КА=БА=НА и КБ=ББ=НБ, а также, что кА+БА+нА = кБ+бБ+нБ = 1. Тем не менее, мы не можем предположить, что КA=БA=НA=КБ=ББ=НБ=0, потому что мы на самом деле не знаем, равны ли выигрыши для игрока А и игрока Б. Более того, интуиция подсказывает нам, что они скорее всего неравны! И вот мы получили устрашающую систему уравнений:

КA = 2нБ – бБ

БA = кБ – нБ

НA = бБ – кБ

КБ = нA – бA

ББ = кA – нA

НБ = бA – 2кA

КA = БA = НA

КБ = ББ = НБ

кA + бA + нA = 1

кБ + бБ + нБ = 1

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

КА      0          -1         +2

[           БА       +1        0          -1         ]

НА       -1         +1        0

Столбец представляет левую сторону первых трех уравнений выше, строка – это кА, третий – бА, а четвертый – нА. Давайте для того, чтобы было более понятно, внесем два изменения: во-первых, сместим столбец вправо, что облегчить работу с ним; во-вторых, поскольку КА=БА=НА, давайте просто заменим их все одной переменной Х, которая будет представлять чистый выигрыш игрока А:

0          -1         +2        X

[           +1        0          -1         X         ]

-1         +1        0          X

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

0кБ      -1бБ    +2нБ    = X

1кБ      +0бБ   -1нБ     = X

-1кБ     +1бБ   +0нБ    = X

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

*          ?          ?          ?

[           0          *          ?          ?          ]

0          0          *          ?

Итак, сначала мы перестроим их, поменяв местами верхнюю и среднюю строки: -1         +1        0          X

[           0          -1         +2        X         ]

+1        0          -1         X

Чтобы избавиться от +1 в нижнем ряду, мы сложим верхнюю и среднюю строкии заменим результатом

-1         +1        0          X

+          +1        0          -1         X

0          +1        -1         2*X

Теперь наша матрица выглядит так: -1         +1        0          X

[           0          -1         +2        X         ]

0          +1        -1         2*X

Теперь нам нужно избавиться от +1 в нижнем ряду, так что мы складываем среднюю и нижнюю строки и заменяем нижнюю строку результатом: -1         +1        0          X

[           0          -1         +2        X         ]

0          0          +1        3*X

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

>>+1(нБ) = 3*X, таким образом, нБ = 3*X

>>-1(бБ) +2(нБ) = X, таким образом, -1(бБ)+2(3*X) = X, таким образом, бБ = 5*X

>>-1(кБ) + 1(бБ) = X, таким образом, кБ = 4*X

На данном этапе нам необязательно знать значение Х, но что мы знаем, так то, что соотношение для игрока Б таково: 3 Ножниц к 5 Бумаги к 4 Камням. Поскольку нБ+бБ+кБ = 1, это означает:

кБ = 4/12         бБ = 5/12        нБ = 3/12

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

	кА	бА	нА
КВ	0	-1	+1
БВ	+1	0	-1
НВ	-2	+1	0

Матрица будет выглядеть следующим образом: 0          -1         +1        КБ

[           +1        0          -1         ББ       ]

-2         +1        0          НБ

Мы снова перестраиваем все, и, поскольку КБ=ББ=НБ, давайте введем для них новую переменную Y (X не будем использовать, чтобы избежать путаницы с предыдущим случаем; помните, что в этом случае выигрыш для одного и другого игроков может различаться). Давайте на этот раз поменяем местами верхнюю и нижнюю строки, а также заменим выигрыши Y:

-2         +1        0          Y

[           +1        0          -1         Y         ]

0          -1         +1        Y

Чтобы избавиться от +1 в центральной строке, перед тем, как складывать центральную строку с верхней, мы должны умножить этустроку на 2 (или же умножить верхнююстроку на ½, но мне кажется, что умножать на целые числа легче, чем на дроби):

-2         +1        0          Y

+          +1*2    0*2      -1*2     Y*2

0          +1        -2         Y*3

Теперь наша матрица выглядит так:

-2         +1        0          Y

[           0          +1        -2         Y*3     ]

0          -1         +1        Y

Сложив вторую и третью строки, чтобы избавиться от -1 в нижней, мы получим:

-2         +1        0          Y

[           0          +1        -2         Y*3     ]

0          0          -1         Y*4

Опять пойдем снизу вверх и используем замену: >>нA = -Y*4

>>бA – 2нA = Y*3, таким образом, бA = -Y*5

>>-2кA + бA = Y, таким образом, -2кA = 6Y, таким образом, кA = -Y*3

Итак, может показаться немного странным, что у нас тут сплошные отрицательные числа вместо положительных в прошлом случае. Возможно, это всего лишь побочный эффект того факта, что средний выигрыш для игрока А скорее всего положителен, тогда как выигрыш игрока Б скорее всего отрицателен. Так или иначе, это все выносится за скобки, так как все, что нас интересует, это относительное соотношение Камня к Ножницам к Бумаге. Для игрока А это соотношение – 3 Камня к 4 Ножницам к 5 Бумаги.

кA = 3/12         бA = 5/12        нA = 4/12

Это слегка отличается от оптимального варианта для игрока Б: кБ = 4/12         бБ = 5/12        нБ = 3/12

Итак, мы можем использовать эти данные для того, чтобы вычислить конкретное преимущество для игрока А. Мы могли бы сделать это, нарисовав таблицу 12х12 и проверив все 144 комбинации, высчитав их все при помощи вероятности, или мы могли бы применить метод Монте-Карло, или просто вставить эти величины в существующие уравнения. Мне представляется наиболее легким последний метод, поскольку у нас уже есть пара уравнений из более ранних примеров, которые прямо относятся к этим: нA = -Y*4, таким образом, Y = -1/12

кБ = X*4, таким образом, X = +1/12

Мы знаем, что КA = БA = НA и что КБ = ББ = НБ, значит, выигрыш для игрока А равен +1/12, а для игрока Б — -1/12. Это весьма логично и действует как дополнительная проверка: поскольку это все еще игра с нулевой суммой, мы знаем, что выигрыш А должен быть равен отрицательному результату Б. В симметричной игре у них обоих бы получился 0, но эта игра несимметрична. Таким образом, если оба игрока играют оптимально, преимущество удивительно мало: всего лишь один лишний выигрыш из 12 раундов!

Решаем КНБ с дополнениями

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

Давайте проанализируем игру Камень-Ножницы-Бумага-Ящерица-Спок.  В этой игре ножницы режут бумагу. Бумага заворачивает камень. Камень давит ящерицу, а ящерица травит Спока, в то время как Спок ломает ножницы, которые, в свою очередь, отрезают голову ящерице, которая ест бумагу, на которой улики против Спока. Спок испаряет камень, а камень, разумеется, затупляет ножницы. Наша таблица выигрышей (С – Спок, Я – ящерица) будет выглядеть следующим образом:

	к	б	н	я	с
К	0	-1	+1	+1	-1
Б	+1	0	-1	-1	+1
Н	-1	+1	0	+1	-1
Я	-1	+1	-1	0	+1
С	+1	-1	+1	-1	0

Также нам известно, что к+б+н+я+с=1, и К=Б=Н=Я=С=0. Можно посчитать это вручную, как и в предыдущих примерах, но есть и другой способ – использовать Excel, который иногда здорово облегчает жизнь.

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

=MMULT(MINVERSE(A1:E5),F1:F5)

Для параметра MINVERSE используйте область ячеек от верхней левой до нижней правой (я, к примеру, использую область A1:E5, если моя таблица начинается в самом начале листа). Для итоговых значений (я в данном случае использую F1:F5) выделите отдельный столбец на пять строк. Наконец — и это важно — нажмите Ctrl+Shift+Enter, когда закончите вписывать формулу (а не просто Enter). Это скопирует формулу во все выделенные вами пять ячеек и будет работать с ними, как с единым массивом, что для нас важно.

Считаю необходимым предупредить, что этот метод срабатывает не всегда; в частности, если решений нет или они бесконечны, Excel в результате выдаст вам #NUM! вместо собственно числа. По сути, если вы введете вышеупомянутую таблицу выигрышей, он выдаст вам эту ошибку; лишь слегка подправив одну из ячеек (скажем, заменив одну +1s на +0.999999), вы создадите уникальное решение, которое отличается всего лишь на небольшую дробную часть, так что округлите несколько знаков после запятой под «настоящий» ответ. Еще одно предупреждение: любой, кто действительно разбирается в математике, содрогнется, когда вы поступите подобным образом, потому что это в некотором роде жульничество, и вообще-то так матрицу решать нельзя.

Excel дает нам решение для 0,2 каждой из пяти переменных, это означает, что в равной степени вероятно, что противник выберет любую из пяти вариантов. Мы можем убедиться, что да, в самом деле, К = Б = Н = Я = С = 0, так что не имеет значения, какую фигуру мы выбираем, в данном случае они все годятся, если противник играет случайно и шансы выбрасывания каждой фигуры равны.