Simuler avec précision les lots de dés sans boucles?

OK, donc si votre jeu lance beaucoup de dés, vous pouvez simplement appeler un générateur de nombres aléatoires en boucle. Mais pour tout ensemble de dés lancé assez souvent, vous obtiendrez une courbe / histogramme de distribution. Donc ma question est-il un bon calcul simple que je peux exécuter qui me donnera un nombre qui correspond à cette distribution?

Par exemple 2D6 - Score -% de probabilité

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%

Donc, sachant ce qui précède, vous pouvez rouler un seul d100 et calculer une valeur 2D6 précise. Mais une fois que nous commençons avec 10D6, 50D6, 100D6, 1000D6, cela pourrait économiser beaucoup de temps de traitement. Il doit donc y avoir un didacticiel / une méthode / un algorithme qui peut le faire rapidement? C'est probablement pratique pour les marchés boursiers, les casinos, les jeux de stratégie, la forteresse naine, etc. Et si vous pouviez simuler les résultats d'une bataille stratégique complète qui prendrait des heures à jouer avec quelques appels à cette fonction et quelques mathématiques de base?

Comme je l'ai mentionné dans mon commentaire ci-dessus, je vous recommande de profiler cela avant de trop compliquer votre code. Une forboucle rapide sommant les dés est beaucoup plus facile à comprendre et à modifier que les formules mathématiques compliquées et la construction / recherche de tables. Faites toujours le profil en premier pour vous assurer de résoudre les problèmes importants. ;)

Cela dit, il existe deux façons principales d'échantillonner des distributions de probabilité sophistiquées d'un seul coup:

1. Distributions de probabilités cumulatives

Il existe une astuce intéressante pour échantillonner à partir de distributions de probabilités continues en utilisant uniquement une seule entrée aléatoire uniforme . Cela a à voir avec la distribution cumulative , la fonction qui répond "Quelle est la probabilité d'obtenir une valeur non supérieure à x?"

Cette fonction est non décroissante, commençant à 0 et augmentant à 1 sur son domaine. Un exemple pour la somme de deux dés à six faces est illustré ci-dessous:

Si votre fonction de distribution cumulative a une inverse pratique à calculer (ou si vous pouvez l'approximer avec des fonctions par morceaux comme les courbes de Bézier), vous pouvez l'utiliser pour échantillonner à partir de la fonction de probabilité d'origine.

La fonction inverse gère le morcellement du domaine entre 0 et 1 en intervalles mappés à chaque sortie du processus aléatoire d'origine, la zone de chalandise correspondant à sa probabilité d'origine. (Ceci est vrai à l'infini pour les distributions continues. Pour les distributions discrètes comme les lancers de dés, nous devons appliquer un arrondi prudent)

Voici un exemple d'utilisation de ceci pour émuler 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);
}

Comparez cela à:

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

Vous voyez ce que je veux dire sur la différence de clarté et de flexibilité du code? La manière naïve peut être naïve avec ses boucles, mais elle est courte et simple, immédiatement évidente sur ce qu'elle fait et facile à mettre à l'échelle pour différentes tailles et nombres de matrices. Apporter des modifications au code de distribution cumulative nécessite des calculs non triviaux, et il serait facile de casser et de provoquer des résultats inattendus sans erreurs évidentes. (Ce que j'espère que je n'ai pas fait ci-dessus)

Donc, avant de vous débarrasser d'une boucle claire, assurez-vous absolument que c'est vraiment un problème de performances qui vaut ce genre de sacrifice.

2. La méthode des alias

La méthode de distribution cumulative fonctionne bien lorsque vous pouvez exprimer l'inverse de la fonction de distribution cumulative comme une simple expression mathématique, mais ce n'est pas toujours facile ni même possible. Une alternative fiable pour les distributions discrètes est ce qu'on appelle la méthode des alias .

Cela vous permet d'échantillonner à partir de n'importe quelle distribution de probabilité discrète arbitraire en utilisant seulement deux entrées aléatoires indépendantes et uniformément réparties.

Cela fonctionne en prenant une distribution comme celle ci-dessous à gauche (ne vous inquiétez pas que les zones / poids ne totalisent pas 1, pour la méthode Alias, nous nous soucions du poids relatif ) et en le convertissant en un tableau comme celui sur le droit où:

• Il y a une colonne pour chaque résultat.
• Chaque colonne est divisée en au plus deux parties, chacune associée à l'un des résultats originaux.
• L'aire / poids relatif de chaque résultat est conservé.

(Diagramme basé sur les images de cet excellent article sur les méthodes d'échantillonnage )

Dans le code, nous représentons cela avec deux tables (ou une table d'objets avec deux propriétés) représentant la probabilité de choisir le résultat alternatif de chaque colonne, et l'identité (ou "alias") de ce résultat alternatif. Ensuite, nous pouvons échantillonner de la distribution comme suit:

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

Cela implique un peu de configuration:

1. Calculez les probabilités relatives de chaque résultat possible (donc si vous roulez 1000d6, nous devons calculer le nombre de façons d'obtenir chaque somme de 1000 à 6000)

2. Créez une paire de tableaux avec une entrée pour chaque résultat. La méthode complète va au-delà de la portée de cette réponse, donc je recommande fortement de se référer à cette explication de l'algorithme de la méthode d'alias .

3. Stockez ces tableaux et faites-y référence chaque fois que vous avez besoin d'un nouveau jet de dé aléatoire de cette distribution.

Il s'agit d'un compromis espace-temps . L'étape de précalcul est quelque peu exhaustive, et nous devons mettre de côté la mémoire proportionnelle au nombre de résultats que nous avons (bien que même pour 1000d6, nous parlons de kilo-octets à un chiffre, donc rien pour perdre le sommeil), mais en échange de notre échantillonnage est à temps constant, quelle que soit la complexité de notre distribution.

J'espère que l'une ou l'autre de ces méthodes peut être utile (ou que je vous ai convaincu que la simplicité de la méthode naïve vaut le temps qu'il faut pour boucler);)

La réponse est malheureusement que cette méthode n'entraînerait pas une augmentation des performances.

Je pense qu'il peut y avoir un malentendu dans la question de savoir comment un nombre aléatoire est généré. Prenons l'exemple ci-dessous [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);
}

Ce code bouclera 20 fois en imprimant des nombres aléatoires entre 1 et 6 (inclus). Lorsque nous parlons des performances de ce code, il y a un certain temps pour créer l'objet aléatoire (ce qui implique la création d'un tableau d'entiers pseudo-aléatoires basé sur l'horloge interne de l'ordinateur au moment de sa création), puis 20 temps constant recherches à chaque appel nextInt (). Étant donné que chaque «rouleau» est une opération à temps constant, cela rend le roulement très bon marché dans le temps. Notez également que la plage de min à max n'a pas d'importance (en d'autres termes, il est tout aussi facile pour un ordinateur de rouler un d6 que pour rouler un d10000). En termes de complexité temporelle, les performances de la solution sont simplement O (n) où n est le nombre de dés.

Alternativement, nous pourrions approximer n'importe quel nombre de rouleaux d6 avec un seul rouleau d100 (ou d10000 d'ailleurs). En utilisant cette méthode, nous devons d'abord calculer s [nombre de faces des dés] * n [nombre de dés] pourcentages avant de lancer (techniquement, c'est s * n - n + 1 pourcentages, et nous devrions être en mesure de le diviser approximativement en deux car il est symétrique; notez que dans votre exemple de simulation d'un rouleau 2d6, vous avez calculé 11 pourcentages et 6 étaient uniques). Après le roulement, nous pouvons utiliser une recherche binaire pour déterminer dans quelle plage notre rouleau est tombé. En termes de complexité temporelle, cette solution s'évalue en une solution O (s * n), où s est le nombre de côtés et n est le nombre de dés. Comme nous pouvons le voir, c'est plus lent que la solution O (n) proposée dans le paragraphe précédent.

En extrapolant à partir de là, disons que vous avez créé ces deux programmes pour simuler un rouleau de 1000d20. Le premier roulerait simplement 1000 fois. Le deuxième programme devrait d'abord déterminer 19 001 pourcentages (pour la plage potentielle de 1 000 à 20 000) avant de faire quoi que ce soit d'autre. Donc, à moins que vous ne soyez sur un système étrange où les recherches de mémoire sont considérablement plus chères que les opérations en virgule flottante, l'utilisation d'un appel nextInt () pour chaque rouleau semble être la voie à suivre.

Si vous souhaitez stocker les combinaisons de dés, la bonne nouvelle est qu'il existe une solution, le mauvais est que nos ordinateurs sont en quelque sorte limités en ce qui concerne ce type de problèmes.

La bonne nouvelle:

Il existe une approche déterministe de ce problème:

1 / Calculez toutes les combinaisons de votre groupe de dés

2 / Déterminer la probabilité de chaque combinaison

3 / Cherchez dans cette liste un résultat au lieu de lancer les dés

Les mauvaises nouvelles:

Le nombre de combinaison avec répétition est donné par les formules suivantes

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

(à partir de wikipedia français ):

Cela signifie que, par exemple, avec 150 dés, vous avez 698'526'906 combinaisons. Supposons que vous stockiez la probabilité sous forme de flottant 32 bits, vous aurez besoin de 2,6 Go de mémoire et vous devrez encore ajouter de la mémoire pour les index ...

En termes de calcul, le nombre de combinaisons peut être calculé par convolutions, ce qui est pratique mais ne résout pas les contraintes de mémoire.

En conclusion, pour un nombre élevé de dés, je conseillerais de lancer les dés et d'observer le résultat plutôt que de précalculer les probabilités associées à chaque combinaison.

Éditer

Cependant, comme vous n'êtes intéressé que par la somme des dés, vous pouvez stocker les probabilités avec beaucoup moins de ressources.

Vous pouvez calculer des probabilités précises pour chaque somme de dés en utilisant la convolution.

$F_i(m) = \sum_n F_1(n) F_{i-1}(m - n)$

Puis à partir de 1/6 de chaque résultat avec 1 dé, vous pouvez construire toutes les probabilités correctes pour n'importe quel nombre de dés.

Voici un code java grossier que j'ai écrit pour illustration (pas vraiment optimisé):

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

}

}

Appelez calcProb () avec les paramètres que vous voulez puis accédez à la table proba pour les résultats (premier index: 0 pour 1 dé, 1 pour deux dés ...).

Je l'ai vérifié avec 1'000D6 sur mon portable, il m'a fallu 10 secondes pour calculer toutes les probabilités de 1 à 1'000 dés et toutes les sommes de dés possibles.

Grâce au précalcul et au stockage efficace, vous pourriez avoir des réponses rapides pour un grand nombre de dés.

J'espère que cela aide.