Simular com precisão os lotes de dados sem loops?

OK, então se o seu jogo rolar muitos dados, você pode simplesmente chamar um gerador de números aleatórios em um loop. Mas, para qualquer conjunto de dados que seja lançado com freqüência suficiente, você receberá uma curva de distribuição / histograma. Então, minha pergunta: existe um bom cálculo simples que eu possa executar que me dê um número que se encaixe nessa distribuição?

Por exemplo, 2D6 - Pontuação -% de probabilidade

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%

Portanto, sabendo o que foi dito acima, você pode rolar um único d100 e calcular um valor 2D6 preciso. Mas uma vez que começamos com 10D6, 50D6, 100D6, 1000D6, isso pode economizar muito tempo de processamento. Portanto, deve haver um tutorial / método / algoritmo que possa fazer isso rápido? Provavelmente é útil para mercados de ações, cassinos, jogos de estratégia, fortalezas anãs etc.

Como mencionei no meu comentário acima, recomendo que você crie um perfil antes de complicar demais o seu código. Um fordado de soma rápida de loop é muito mais fácil de entender e modificar do que fórmulas matemáticas complicadas e criação / pesquisa de tabelas. Sempre perfil primeiro para garantir que você está resolvendo os problemas importantes. ;)

Dito isto, existem duas maneiras principais de amostrar distribuições sofisticadas de probabilidade de uma só vez:

1. Distribuições de Probabilidades Cumulativas

Há um truque interessante para amostrar distribuições de probabilidade contínuas usando apenas uma única entrada aleatória uniforme . Tem a ver com a distribuição cumulativa , a função que responde "Qual é a probabilidade de obter um valor não superior a x?"

Essa função não diminui, iniciando em 0 e subindo para 1 sobre seu domínio. Um exemplo para a soma de dois dados de seis lados é mostrado abaixo:

Se sua função de distribuição cumulativa tiver uma inversa conveniente de calcular (ou você pode aproximar-se dela com funções fragmentadas, como curvas de Bézier), você pode usá-la para obter amostras da função de probabilidade original.

A função inversa manipula o parcelamento do domínio entre 0 e 1 em intervalos mapeados para cada saída do processo aleatório original, com a área de captação de cada uma correspondendo à sua probabilidade original. (Isso é verdade infinitamente em distribuições contínuas. Para distribuições discretas, como lançamentos de dados, precisamos aplicar um arredondamento cuidadoso)

Aqui está um exemplo de como usar isso 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 isso com:

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

Entendeu o que quero dizer sobre a diferença de clareza e flexibilidade de código? A maneira ingênua pode ser ingênua com seus loops, mas é curta e simples, imediatamente óbvia sobre o que faz e fácil de ser dimensionada para diferentes tamanhos e números de matrizes. Fazer alterações no código de distribuição cumulativo requer alguma matemática não trivial e seria fácil interromper e causar resultados inesperados sem erros óbvios. (Que espero não ter feito acima)

Portanto, antes de acabar com um loop claro, tenha certeza absoluta de que é realmente um problema de desempenho que vale esse tipo de sacrifício.

2. O método de alias

O método de distribuição cumulativa funciona bem quando você pode expressar o inverso da função de distribuição cumulativa como uma expressão matemática simples, mas isso nem sempre é fácil ou até possível. Uma alternativa confiável para distribuições discretas é algo chamado Método Alias .

Isso permite que você faça uma amostra de qualquer distribuição de probabilidade discreta arbitrária usando apenas duas entradas aleatórias independentes e uniformemente distribuídas.

Ele funciona pegando uma distribuição como a abaixo, à esquerda (não se preocupe, pois as áreas / pesos não somam 1, para o método Alias, nos preocupamos com o peso relativo ) e convertendo-a em uma tabela como a da o certo onde:

• Há uma coluna para cada resultado.
• Cada coluna é dividida em no máximo duas partes, cada uma associada a um dos resultados originais.
• A área / peso relativo de cada resultado é preservada.

(Diagrama baseado nas imagens deste excelente artigo sobre métodos de amostragem )

No código, representamos isso com duas tabelas (ou uma tabela de objetos com duas propriedades) representando a probabilidade de escolher o resultado alternativo de cada coluna e a identidade (ou "alias") desse resultado alternativo. Em seguida, podemos amostrar da distribuição da seguinte forma:

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

Isso envolve um pouco de configuração:

1. Calcule as probabilidades relativas de todos os resultados possíveis (por isso, se você estiver lançando 1000d6, precisamos calcular o número de maneiras de obter cada soma de 1000 a 6000)

2. Crie um par de tabelas com uma entrada para cada resultado. O método completo vai além do escopo desta resposta, por isso recomendo que se refira a esta explicação do algoritmo do método Alias .

3. Armazene essas tabelas e consulte-as sempre que precisar de um novo rolo aleatório desta distribuição.

Esta é uma troca de espaço-tempo . A etapa de pré-computação é um pouco exaustiva e precisamos reservar memória proporcional ao número de resultados que temos (embora, mesmo para 1000d6, falemos kilobytes de um dígito, para que nada perca o sono), mas em troca de nossa amostragem é de tempo constante, por mais complexa que seja a nossa distribuição.

Espero que um ou outro desses métodos possa ter alguma utilidade (ou que eu o tenha convencido de que a simplicidade do método ingênuo vale o tempo que leva para fazer um loop);)

Infelizmente, a resposta é que esse método não resultaria em um aumento no desempenho.

Acredito que possa haver algum mal-entendido na questão de como um número aleatório é gerado. Veja o exemplo abaixo [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);
}

Esse código fará um loop 20 vezes, imprimindo números aleatórios entre 1 e 6 (inclusive). Quando falamos sobre o desempenho desse código, leva algum tempo para criar o objeto Random (que envolve a criação de uma matriz de números inteiros pseudo-aleatórios com base no relógio interno do computador no momento em que foi criado) e depois 20 em tempo constante pesquisas em cada chamada nextInt (). Como cada rolo é uma operação de tempo constante, isso torna o rolamento muito barato em termos de tempo. Observe também que o intervalo de min a max não importa (em outras palavras, é tão fácil para um computador rolar um d6 quanto rolar um d10000). Falando em termos de complexidade de tempo, o desempenho da solução é simplesmente O (n) onde n é o número de dados.

Como alternativa, poderíamos aproximar qualquer número de rolos d6 com um único rolo d100 (ou d10000). Usando esse método, precisamos primeiro calcular as porcentagens s [número de faces dos dados] * n [número de dados] antes de lançar (tecnicamente são porcentagens s * n - n + 1, e poderemos dividir isso aproximadamente ao meio, uma vez que é simétrico; observe que, no seu exemplo para simular um rolo 2d6, você calculou 11 porcentagens e 6 eram únicas). Após a rolagem, podemos usar uma pesquisa binária para descobrir em qual intervalo nosso rolagem se enquadra. Em termos de complexidade de tempo, esta solução é avaliada como uma solução O (s * n), em que s é o número de lados en é o número de dados. Como podemos ver, isso é mais lento que a solução O (n) proposta no parágrafo anterior.

Extrapolando a partir daí, digamos que você criou esses dois programas para simular um rolo de 1000d20. O primeiro simplesmente rolaria 1.000 vezes. O segundo programa precisaria primeiro determinar 19.001 porcentagens (para o intervalo potencial de 1.000 a 20.000) antes de fazer qualquer outra coisa. Portanto, a menos que você esteja em um sistema estranho, onde as pesquisas de memória são muito mais caras que as operações de ponto flutuante, usar uma chamada nextInt () para cada rolo parece ser o caminho a seguir.

Se você deseja armazenar as combinações de dados, a boa notícia é que existe uma solução, o ruim é que nossos computadores são de alguma forma limitados em relação a esse tipo de problema.

As boas notícias:

Há uma abordagem determinista desse problema:

1 / Calcule todas as combinações do seu grupo de dados

2 / Determine a probabilidade de cada combinação

3 / Procure nesta lista um resultado em vez de jogar os dados

As más notícias:

O número de combinação com repetição é dado pelas seguintes fórmulas

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

( da Wikipédia em francês ):

Isso significa que, por exemplo, com 150 dados, você tem 698'526'906 combinações. Vamos supor que você armazene a probabilidade como um flutuador de 32 bits, precisará de 2,6 GB de memória e ainda precisará adicionar requisitos de memória para os índices ...

Em termos de computação, o número da combinação pode ser calculado por convoluções, o que é útil, mas não resolve as restrições de memória.

Em conclusão, para um grande número de dados, eu recomendaria jogar os dados e observar o resultado, em vez de pré-computar as probabilidades associadas a cada combinação.

Editar

No entanto, como você está interessado apenas na soma dos dados, é possível armazenar as probabilidades com muito menos recursos.

Você pode calcular probabilidades precisas para cada soma de dados usando convolução.

A fórmula geral é $F_i(m) = \sum_n F_1(n) F_{i-1}(m - n)$

Em seguida, a partir de 1/6 do formulário de cada resultado com 1 dado, você pode construir todas as probabilidades corretas para qualquer número de dados.

Aqui está um código java bruto que escrevi para ilustração (não realmente otimizado):

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

}

}

Chame calcProb () com os parâmetros desejados e acesse a tabela proba para obter resultados (primeiro índice: 0 para 1 dado, 1 para dois dados ...).

Eu verifiquei com 1'000D6 no meu laptop, levou 10 segundos para calcular todas as probabilidades de 1 a 1 000 dados e todas as somas possíveis de dados.

Com pré-computação e armazenamento eficiente, você pode obter respostas rápidas para um alto número de dados.

Espero que ajude.