Точно имитировать множество бросков кубиков без петель?

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

Например, 2D6 - оценка -% вероятности

2 - 2,77%

3 - 5,55%

4 - 8,33%

5 - 11,11%

6 - 13,88%

7 - 16,66%

8 - 13,88%

9 - 11,11%

10 - 8,33%

11 - 5,55%

12 - 2,77%

Таким образом, зная выше, вы могли бы бросить один d100 и получить точное значение 2D6. Но как только мы начнем с 10D6, 50D6, 100D6, 1000D6, это может сэкономить много времени на обработку. Таким образом, должен быть учебник / метод / алгоритм, который может сделать это быстро? Это, вероятно, удобно для фондовых рынков, казино, стратегических игр, крепости дварфов и т. Д. Что если вы могли бы смоделировать результаты полного стратегического сражения, которое потребовало бы нескольких часов, чтобы выполнить несколько вызовов этой функции и некоторые базовые математические операции?

Как я уже упоминал в своем комментарии выше, я рекомендую вам профилировать его перед тем, как усложнять свой код. Кости с быстрым forциклом суммирования намного легче понять и изменить, чем сложные математические формулы и построение / поиск таблиц. Всегда делайте профиль первым, чтобы убедиться, что вы решаете важные проблемы. ;)

Тем не менее, есть два основных способа выборки сложных распределений вероятностей одним махом:

1. Совокупное распределение вероятностей

Есть хитрый трюк для выборки из непрерывных распределений вероятности, используя только один равномерный случайный вход . Это связано с кумулятивным распределением , функцией, которая отвечает: «Какова вероятность получения значения, не превышающего x?»

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

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

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

Вот пример использования этого для эмуляции 2d6:

int SimRoll2d6()
{
    // Get a random input in the half-open interval [0, 1).
    float t = Random.Range(0f, 1f);
    float v;

    // Piecewise inverse calculated by hand. ;)
    if(t <= 0.5f)
    {
         v = (1f + sqrt(1f + 288f * t)) * 0.5f;
    }
    else
    {
         v = (25f - sqrt(289f - 288f * t)) * 0.5f;
    }

    return floor(v + 1);
}

Сравните это с:

int NaiveRollNd6(int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
       sum += Random.Range(1, 7); // I'm used to Range never returning its max
    return sum;
}

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

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

2. Метод псевдонимов

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

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

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

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

(Схема основана на изображениях из этой превосходной статьи о методах отбора проб )

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

int SampleFromTables(float[] probabiltyTable, int[] aliasTable)
{
    int column = Random.Range(0, probabilityTable.Length);
    float p = Random.Range(0f, 1f);
    if(p < probabilityTable[column])
    {
        return column;
    }
    else
    {
        return aliasTable[column];
    }
}

Это включает в себя немного настройки:

1. Вычислить относительные вероятности каждого возможного результата (поэтому, если вы бросаете 1000d6, нам нужно вычислить количество способов получить каждую сумму от 1000 до 6000)

2. Создайте пару таблиц с записью для каждого результата. Полный метод выходит за рамки этого ответа, поэтому я настоятельно рекомендую обратиться к этому объяснению алгоритма метода псевдонима .

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

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

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

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

Я считаю, что в вопросе о том, как генерируется случайное число, может возникнуть некоторое недопонимание. Возьмите пример ниже [Java]:

Random r = new Random();
int n = 20;
int min = 1; //arbitrary
int max = 6; //arbitrary
for(int i = 0; i < n; i++){
    int randomNumber = (r.nextInt(max - min + 1) + min)); //silly maths
    System.out.println("Here's a random number: " + randomNumber);
}

Этот код будет зацикливаться 20 раз, распечатывая случайные числа от 1 до 6 (включительно). Когда мы говорим о производительности этого кода, у нас есть время, затрачиваемое на создание объекта Random (который включает создание массива псевдослучайных целых чисел на основе внутренних часов компьютера на момент его создания), а затем 20 постоянных времени. поиск по каждому вызову nextInt (). Поскольку каждый «крен» является операцией с постоянным временем, это делает прокатку очень дешевой по времени. Также обратите внимание, что диапазон от минимального до максимального значения не имеет значения (другими словами, для компьютера так же легко бросить d6, как и для d10000). Говоря с точки зрения сложности времени, производительность решения просто O (n), где n - количество кубиков.

В качестве альтернативы, мы можем приблизить любое количество бросков d6 одним броском d100 (или d10000 в этом отношении). Используя этот метод, нам нужно сначала вычислить s [количество граней к кости] * n [количество костей], прежде чем мы бросим (технически это s * n - n + 1 процент, и мы должны быть в состоянии разделить это примерно пополам, поскольку это симметрично; обратите внимание, что в вашем примере для симуляции броска 2d6 вы вычислили 11 процентов и 6 были уникальными). После броска мы можем использовать двоичный поиск, чтобы выяснить, в какой диапазон попал наш бросок. С точки зрения сложности времени это решение оценивается как решение O (s * n), где s - количество сторон, а n - количество кубиков. Как мы видим, это медленнее, чем решение O (n), предложенное в предыдущем абзаце.

После экстраполяции, скажем, вы создали обе эти программы для имитации броска 1000d20. Первый просто бросил бы 1000 раз. Вторая программа должна сначала определить 19 001 процент (для потенциального диапазона от 1000 до 20 000), прежде чем делать что-либо еще. Так что, если вы не находитесь в странной системе, где поиск в памяти несколько дороже, чем операции с плавающей запятой, использование вызова nextInt () для каждого броска кажется подходящим вариантом.

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

Хорошие новости:

Существует детерминистский подход к этой проблеме:

1 / Вычислите все комбинации вашей группы игральных костей

2 / Определить вероятность для каждой комбинации

3 / Поиск в этом списке для результата, а не бросать кубики

Плохие новости:

Количество комбинаций с повторениями дается по следующим формулам

$\Gamma_n^k={n+k-1 \choose k}=\frac{(n+k-1)!}{k!~(n-1)!}$

( из французской википедии ):

Это означает, что, например, с 150 кубиками у вас есть 698'526'906 комбинаций. Предположим, вы храните вероятность как 32-разрядное число с плавающей запятой, вам потребуется 2,6 ГБ памяти, и вам все равно нужно добавить требования к памяти для индексов ...

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

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

редактировать

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

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

Общая формула $F_i(m) = \sum_n F_1(n) F_{i-1}(m - n)$

Затем, начиная с 1/6 формы каждого результата с 1 кубиком, вы можете построить все правильные вероятности для любого количества кубиков.

Вот примерный код Java, который я написал для иллюстрации (не очень оптимизированный):

public class DiceProba {

private float[][] probas;
private int currentCalc;

public int getCurrentCalc() {
    return currentCalc;
}

public float[][] getProbas() {
    return probas;
}

public void calcProb(int faces, int diceNr) {

    if (diceNr < 0) {
        currentCalc = 0;
        return;
    }

    // Initialize
    float baseProba = 1.0f / ((float) faces);
    probas = new float[diceNr][];
    probas[0] = new float[faces + 1];
    probas[0][0] = 0.0f;
    for (int i = 1; i <= faces; ++i)
        probas[0][i] = baseProba;

    for (int i = 1; i < diceNr; ++i) {

        int maxValue = (i + 1) * faces + 1;
        probas[i] = new float[maxValue];

        for (int j = 0; j < maxValue; ++j) {

            probas[i][j] = 0;
            for (int k = 0; k <= j; ++k) {
                probas[i][j] += probability(faces, k, 0) * probability(faces, j - k, i - 1);
            }

        }

    }

    currentCalc = diceNr;

}

private float probability(int faces, int number, int diceNr) {

    if (number < 0 || number > ((diceNr + 1) * faces))
        return 0.0f;

    return probas[diceNr][number];

}

}

Вызовите calcProb () с нужными параметрами, а затем получите доступ к таблице вероятностей для результатов (первый индекс: 0 для 1 кубика, 1 для двух кубиков ...).

Я проверил это с 1'000D6 на моем ноутбуке, потребовалось 10 секунд, чтобы вычислить все вероятности от 1 до 1000 кубиков и все возможные суммы кубиков.

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

Надеюсь, это поможет.