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

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

Обычно проблема усугубляется необходимостью не только 6-гранного штампа D6, но и всего остального зоопарка платоновых тел D4, D8 , D12, D20. D10 иногда также добавляется в смесь. Я видел много решений этой проблемы, от написания чисел на листках бумаги и рисования их из коробки до того, как мастер подземелий составляет числа. У первого есть проблема в том, что ему нужны дополнительные материалы, которых может не быть, а у второго проблема в том, что GM может быть предвзятым.

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

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

Но действительно ли это хорошее решение, и как мы узнаем, так ли это? Войдите в теорию генераторов псевдослучайных чисел (PRNG).

Генераторы псевдослучайных чисел

Проблема генерации случайности старая. В 1946 году Джону фон Нейману понадобилось множество случайных чисел для моделирования методом Монте-Карло во время работы над атомной бомбой. В методах Монте-Карло для вычислений используется случайность. Самый простой пример — нарисовать четверть круга внутри квадрата. Бросьте песчинки на рисунок наугад. Подсчитайте количество зерен внутри круга, разделите его на общее количество, умножьте на 4 и вуаля, вы вычислили число Пи методом Монте-Карло.

seq = [random.randint(0,100) for x in range(200)]
rand_coords = list(zip(seq[::2], seq[1::2]))
sum(1 if math.sqrt(x**2+y**2)<=100 else 0 for x,y in rand_coords)*4/len(rand_coords)

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

8524 -> 72658576 -> 6585 -> 43362225 -> 3622

Это выглядит случайным, но так ли это? Является ли последовательность 777777 случайной? Вероятность его появления составляет 1 из 10⁶, но, с другой стороны, то же самое верно и для 758336.

Проверка на случайность — нетривиальная задача, и для этой цели разработан ряд методов. Мы рассмотрим некоторые из них.

Визуальный анализ

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

def plot_rand(seq):
    dim = int((seq.size)**(1/2))
    seq = seq[:(dim**2)].reshape(dim, dim)
    plt.imshow(seq)

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

Давайте попробуем другой:

plot_rand([(x**2-3*x)%10 for x in range(300)])

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

Позже были изобретены лучшие методы, чем средний квадрат, но в этой области возникли проблемы. Одним из примеров является алгоритм IBM RANDU. На первый взгляд кажется, что он выдает хорошие случайные числа, но это оказывается иллюзией. На самом деле это настолько плохо, что Дональд Кнут назвал его «поистине ужасным», и в результате широкого использования RANDU в начале 1970-х годов многие результаты того времени рассматриваются как подозрительные.

Другой пример — PHP rand().

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

Но насколько эффективен описанный выше метод, когда два человека произносят числа одновременно?

Мне кажется довольно случайным, первый тест пройден.

Колмогоров

Другой способ рассматривать случайность состоит в том, что ее трудно описать, в то время как порядок описать легко.

Таким образом, 10001101011100101110 выглядит более случайным, чем 11111111110000000000, поскольку последнее можно описать как [1]*10 + [0]*10, но первое труднее найти сжатую форму.

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

Попробуем сжать наши последовательности описанным выше способом.

def compress(string):
    return ''.join((char + str(sum(1 for _ in group)).replace('1','')) for char, group in groupby(string))

*В приведенном выше коде мы обрабатываем простейший случай с одним граммом, поэтому, например, 10101010 не будет сжиматься этим алгоритмом. Улучшенный алгоритм сжатия оставлен читателю в качестве упражнения.

400 radom.randint() сжимается до 395, а числа из двух человек получают 390. Достаточно близко, второй тест пройден.

хи-квадрат

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

Давайте поместим наши последовательности в тест хи-квадрат.

chisquare([v/len(seq) for k,v in Counter(seq).items()], [.1]*10)

random.randint() дает хи-квадрат 0,03. Случайная последовательность, которую я сгенерировал, нажимая кнопки, имеет значение 0,12, поэтому не совсем случайно. Последовательность из двух последовательностей нажатия кнопок получила 0,04 балла, что, на мой взгляд, неплохо. Случайная последовательность с «1» на каждом 5-м месте получает 0,38.

Но не только распределение чисел здесь представляет интерес. Нас также интересуют биграммы, а именно: Два последовательных числа. Числа от 1 до 9 могут встречаться равномерно, но, возможно, два числа «29» встречаются чаще, чем «23», поскольку я использую две руки при составлении чисел и имею тенденцию чередовать их. Также было бы интересно попробовать триграммы и выше.

При тестировании с биграммами random.randint() получает 0,2, мое нажатие кнопки получает 1,28, наша добавленная последовательность получает 0,34, а случайное с «1» на каждом 5-м месте получает 4,45.

Не идеально, но достаточно близко, третье испытание пройдено.

Pi

Конечно, мы можем использовать метод Монте-Карло, описанный выше, но в обратном порядке. Поскольку мы знаем, каким должен быть Пи, чем ближе, тем лучше PRNG.

Получаем 2,96. Не совсем Пи, но одна из причин этого в том, что у нас есть только целые числа от 0 до 9. random.randint(0,9) в этом случае дает 2,9.

4-й тест пройден.

Несгибаемые тесты

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

Многорукие бандиты

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

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

Расширением этой концепции является проблема контекстного многорукого бандита (CMAB), где вы также смотрите на контекст, например, на время суток.

Давайте смоделируем нашу ситуацию как CMAB, используя contextualbandits lib. Контекст — это предыдущие числа, и всякий раз, когда нашему алгоритму удается выбрать число, которое приводит к числу выше среднего, он получает вознаграждение. Нашим конкретным алгоритмом будет Bootstrapd Thompson Sampling, алгоритм, который определяет вероятность того, что каждое действие будет правильным, используя бета-распределение.

def run_bandit(seq, nchoices, reward_func):
    base_algorithm = LogisticRegression(random_state=123, 
                                        solver='lbfgs')
    beta_prior = ((3, 7), 2)
    model = BootstrappedTS(deepcopy(base_algorithm), 
                           nchoices = nchoices, 
                           beta_prior=beta_prior)
    r_hist = []
    a_hist = []
    X_hist = []
    model.fit(X=np.array([[0]]), a=np.array([0]), 
              r=np.array([0]))
    for X,y in ngram(seq, 2):
        a = model.predict(np.array([[int(X)]]))[0]
        a_hist.append(a)
        X_hist.append([int(X)])
        r = reward_func(a,y)
        r_hist.append(r)
        model.fit(X=np.array(X_hist), a=np.array(a_hist), 
                  r=np.array(r_hist))
        
    return r_hist

np.mean(run_bandit([random.randint(0,9) for x in range(200)], 10, lambda a,y: 1 if (a+int(y))%10 >= 5 else 0))

Результаты:

Для random.randint() алгоритм получает в среднем 0,51 балла.

Для сгенерированной GM последовательности алгоритм получает в среднем 0,63 балла.

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

Бонус 1: Камень-ножницы-бумага

Кстати, этот же метод можно использовать и для победы в игре «камень-ножницы-бумага», просто используйте nchoices=3 и другую функцию вознаграждения. Пытаться:

np.mean(run_bandit(sequence, 3, lambda a,y: 1 if int(a) == (int(y)+1)%3 else 0))

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

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

Бонус 2: Представление числа

Одна не совсем не связанная с этим проблема связана с передачей чисел GM. Часто случается так, что после того, как GM бросил кубик, он/она хотел бы узнать, например, значение способности одного игрока, чтобы другие игроки не слышали. Это можно сделать, показав число с помощью пальцев, но обычный способ сделать это подходит только для чисел 0–10, в то время как показатели способности обычно составляют до 18.

Один из способов решить эту проблему — использовать основание 6, когда одна рука соответствует первому порядку, а другая — второму. Таким образом, можно пройти весь путь от 0 до 35. Если этого недостаточно, можно использовать двоичный код, чтобы добраться до 1023, хотя вам нужны довольно ловкие пальцы.

Если конкретный диапазон близок к 1–110, китайские числовые жесты кажутся подходящими. Тем более, что наша система счисления основана на 10, что облегчает понимание этих жестов.

Вывод

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