Simulando con precisión los lotes de tiradas de dados sin bucles

OK, así que si tu juego tira muchos dados, puedes llamar a un generador de números aleatorios en un bucle. Pero para cualquier conjunto de dados que se lance con la frecuencia suficiente, obtendrá una curva de distribución / histograma. Entonces, mi pregunta, ¿puedo hacer un cálculo simple y agradable que me dé un número que se ajuste a esa distribución?

Ej. 2D6 - Puntuación -% de probabilidad

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%

Entonces, sabiendo lo anterior, podría lanzar un solo d100 y calcular un valor 2D6 preciso. Pero una vez que comenzamos con 10D6, 50D6, 100D6, 1000D6, esto podría ahorrar mucho tiempo de procesamiento. ¿Entonces debe haber un tutorial / método / algoritmo que pueda hacer esto rápidamente? Probablemente sea útil para los mercados de valores, casinos, juegos de estrategia, fortaleza enana, etc. ¿Qué pasaría si pudiera simular los resultados de una batalla estratégica completa que llevaría horas jugar con algunas llamadas a esta función y algunas matemáticas básicas?

Como mencioné en mi comentario anterior, le recomiendo que haga un perfil de esto antes de complicar demasiado su código. Un fordado de suma de bucle rápido es mucho más fácil de entender y modificar que las fórmulas matemáticas complicadas y la creación / búsqueda de tablas. Siempre perfile primero para asegurarse de que está resolviendo los problemas importantes. ;)

Dicho esto, hay dos formas principales de muestrear distribuciones de probabilidad sofisticadas de una sola vez:

1. Distribuciones de probabilidad acumulativa

Hay un buen truco para muestrear a partir de distribuciones de probabilidad continuas utilizando solo una entrada aleatoria uniforme . Tiene que ver con la distribución acumulativa , la función que responde "¿Cuál es la probabilidad de obtener un valor no mayor que x?"

Esta función no disminuye, comienza en 0 y sube a 1 sobre su dominio. A continuación se muestra un ejemplo de la suma de dos dados de seis lados:

Si su función de distribución acumulativa tiene un inverso conveniente para calcular (o puede aproximarlo con funciones por partes como las curvas de Bézier), puede usar esto para tomar muestras de la función de probabilidad original.

La función inversa maneja la parcelación del dominio entre 0 y 1 en intervalos asignados a cada salida del proceso aleatorio original, con el área de captación de cada uno coincidiendo con su probabilidad original. (Esto es cierto infinitamente para distribuciones continuas. Para distribuciones discretas como tiradas de dados, debemos aplicar un redondeo cuidadoso)

Aquí hay un ejemplo de cómo usar esto para emular 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);
}

Compare esto con:

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;
}

¿Ves lo que quiero decir sobre la diferencia en la claridad y flexibilidad del código? La forma ingenua puede ser ingenua con sus bucles, pero es corta y simple, inmediatamente obvia sobre lo que hace y fácil de escalar a diferentes tamaños y números de dados. Realizar cambios en el código de distribución acumulativo requiere algunas matemáticas no triviales, y sería fácil de romper y causar resultados inesperados sin errores obvios. (Que espero no haber hecho arriba)

Por lo tanto, antes de deshacerse de un ciclo claro, asegúrese absolutamente de que realmente sea un problema de rendimiento que valga este tipo de sacrificio.

2. El método alias

El método de distribución acumulativa funciona bien cuando puede expresar el inverso de la función de distribución acumulativa como una simple expresión matemática, pero eso no siempre es fácil o incluso posible. Una alternativa confiable para distribuciones discretas es algo llamado Método Alias .

Esto le permite tomar muestras de cualquier distribución de probabilidad discreta arbitraria utilizando solo dos entradas aleatorias independientes, distribuidas uniformemente.

Funciona tomando una distribución como la de abajo a la izquierda (no se preocupe que las áreas / pesos no sumen 1, para el Método Alias ​​nos importa el peso relativo ) y conviértalo en una tabla como la de el derecho donde:

• Hay una columna para cada resultado.
• Cada columna se divide en a lo sumo dos partes, cada una asociada con uno de los resultados originales.
• Se preserva el área / peso relativo de cada resultado.

(Diagrama basado en imágenes de este excelente artículo sobre métodos de muestreo )

En el código, representamos esto con dos tablas (o una tabla de objetos con dos propiedades) que representan la probabilidad de elegir el resultado alternativo de cada columna y la identidad (o "alias") de ese resultado alternativo. Entonces podemos muestrear de la distribución así:

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];
    }
}

Esto implica un poco de configuración:

1. Calcule las probabilidades relativas de cada resultado posible (por lo tanto, si está obteniendo 1000d6, necesitamos calcular la cantidad de formas de obtener cada suma de 1000 a 6000)

2. Construya un par de tablas con una entrada para cada resultado. El método completo va más allá del alcance de esta respuesta, por lo que recomiendo consultar esta explicación del algoritmo del Método Alias .

3. Almacene esas tablas y refiérase a ellas cada vez que necesite una nueva tirada aleatoria de esta distribución.

Esta es una compensación espacio-tiempo . El paso de precomputación es algo exhaustivo, y necesitamos reservar memoria proporcional al número de resultados que tenemos (aunque incluso para 1000d6, estamos hablando de kilobytes de un solo dígito, por lo que no hay nada que perder el sueño), pero a cambio de nuestra muestra es de tiempo constante, no importa cuán compleja sea nuestra distribución.

Espero que uno u otro de esos métodos pueda ser de alguna utilidad (o que te haya convencido de que la simplicidad del método ingenuo vale la pena el tiempo que lleva en bucle);)

Desafortunadamente, la respuesta es que este método no daría lugar a un aumento en el rendimiento.

Creo que puede haber algunos malentendidos en la cuestión de cómo se genera un número aleatorio. Tome el siguiente ejemplo [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);
}

Este código se repetirá 20 veces imprimiendo números aleatorios entre 1 y 6 (inclusive). Cuando hablamos sobre el rendimiento de este código, se tarda un tiempo en crear el objeto Aleatorio (que implica crear una matriz de enteros pseudoaleatorios basados ​​en el reloj interno de la computadora en el momento en que se creó), y luego 20 veces constantes búsquedas en cada llamada nextInt (). Dado que cada 'rollo' es una operación de tiempo constante, esto hace que rodar sea muy barato en el tiempo. También tenga en cuenta que el rango de min a max no importa (en otras palabras, es tan fácil para una computadora lanzar un d6 como para rodar un d10000). Hablando en términos de complejidad temporal, el rendimiento de la solución es simplemente O (n) donde n es el número de dados.

Alternativamente, podríamos aproximar cualquier cantidad de rollos d6 con un solo rollo d100 (o d10000 para el caso). Usando este método, primero tenemos que calcular los porcentajes de s [número de caras al dado] * n [número de dados] antes de lanzar (técnicamente son porcentajes s * n - n + 1, y deberíamos poder dividir eso aproximadamente a la mitad ya que es simétrico; observe que en su ejemplo para simular un lanzamiento 2d6, calculó 11 porcentajes y 6 fueron únicos). Después de rodar, podemos usar una búsqueda binaria para averiguar en qué rango cayó nuestro rollo. En términos de complejidad temporal, esta solución se evalúa como una solución O (s * n), donde s es el número de lados yn es el número de dados. Como podemos ver, esto es más lento que la solución O (n) propuesta en el párrafo anterior.

Extrapolando desde allí, supongamos que creó ambos programas para simular un rollo 1000d20. El primero simplemente rodaría 1,000 veces. El segundo programa primero necesitaría determinar 19,001 porcentajes (para el rango potencial de 1,000 a 20,000) antes de hacer cualquier otra cosa. Entonces, a menos que esté en un sistema extraño donde las búsquedas de memoria son mucho más caras que las operaciones de punto flotante, usar una llamada nextInt () para cada rollo parece ser el camino a seguir.

Si desea almacenar las combinaciones de dados, la buena noticia es que hay una solución, lo malo es que nuestras computadoras están de alguna manera limitadas con respecto a este tipo de problemas.

Las buenas noticias:

Hay un enfoque determinista de este problema:

1 / Calcula todas las combinaciones de tu grupo de dados

2 / Determinar la probabilidad para cada combinación

3 / Busca en esta lista un resultado en lugar de tirar los dados

Las malas noticias:

El número de combinaciones con la repetición viene dado por las siguientes fórmulas.

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

( de la wikipedia francesa ):

Eso significa que, por ejemplo, con 150 dados, tienes 698'526'906 combinaciones. Supongamos que almacena la probabilidad como un flotante de 32 bits, necesitará 2,6 GB de memoria y aún debe agregar el requisito de memoria para los índices ...

En términos de computación, el número de combinación se puede calcular por convoluciones, lo cual es útil pero no resuelve las restricciones de memoria.

En conclusión, para una gran cantidad de dados, recomendaría tirar los dados y observar el resultado en lugar de calcular previamente las probabilidades asociadas con cada combinación.

Editar

Sin embargo, como solo le interesa la suma de los dados, puede almacenar las probabilidades con muchos menos recursos.

Puede calcular probabilidades precisas para cada suma de dados usando convolución.

La fórmula general es $F_i(m) = \sum_n F_1(n) F_{i-1}(m - n)$

Luego, a partir de 1/6 de cada resultado con 1 dado, puede construir todas las probabilidades correctas para cualquier número de dados.

Aquí hay un código Java aproximado que escribí para ilustración (no realmente optimizado):

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];

}

}

Llame a calcProb () con los parámetros que desee y luego acceda a la tabla de probabilidades para obtener resultados (primer índice: 0 para 1 dado, 1 para dos dados ...).

Lo revisé con 1'000D6 en mi computadora portátil, me tomó 10 segundos calcular todas las probabilidades de 1 a 1'000 dados y todas las posibles sumas de dados.

Con la precomputación y el almacenamiento eficiente, puede tener respuestas rápidas para una gran cantidad de dados.

Espero eso ayude.