Genaue Simulation der vielen Würfelwürfe ohne Schleifen?

OK, wenn Ihr Spiel viele Würfel wirft, können Sie einfach einen Zufallsgenerator in einer Schleife aufrufen. Für jeden Würfelsatz, der oft genug gewürfelt wird, erhalten Sie eine Verteilungskurve / ein Histogramm. Also meine Frage gibt es eine nette einfache Berechnung, die ich ausführen kann, die mir eine Zahl gibt, die zu dieser Verteilung passt?

ZB 2D6 - Score -% Wahrscheinlichkeit

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%

Wenn Sie also das Obige wissen, können Sie einen einzelnen d100 würfeln und einen genauen 2D6-Wert ermitteln. Sobald wir jedoch mit 10D6, 50D6, 100D6, 1000D6 beginnen, kann dies viel Verarbeitungszeit sparen. Also muss es ein Tutorial / eine Methode / einen Algorithmus geben, die / der dies schnell kann? Es ist wahrscheinlich praktisch für Aktienmärkte, Casinos, Strategiespiele, Zwergenfestungen usw. Was wäre, wenn Sie die Ergebnisse eines vollständigen strategischen Kampfes simulieren könnten, der Stunden in Anspruch nehmen würde, wenn Sie ein paar Aufrufe dieser Funktion und einige grundlegende mathematische Methoden benötigen?

Wie ich oben in meinem Kommentar erwähnt habe, empfehle ich Ihnen, dieses Profil zu erstellen, bevor Sie Ihren Code überkomplizieren. Eine schnelle forSummierung von Würfeln ist viel einfacher zu verstehen und zu ändern als komplizierte mathematische Formeln und das Erstellen / Suchen von Tabellen. Profilieren Sie immer zuerst, um sicherzustellen, dass Sie die wichtigen Probleme lösen. ;)

Es gibt jedoch zwei Möglichkeiten, ausgefeilte Wahrscheinlichkeitsverteilungen auf einen Schlag abzutasten:

1. Kumulative Wahrscheinlichkeitsverteilungen

Es gibt einen tollen Trick, um aus kontinuierlichen Wahrscheinlichkeitsverteilungen mit nur einer einheitlichen Zufallseingabe eine Stichprobe zu erstellen . Es hat mit der kumulativen Verteilung zu tun , der Funktion, die antwortet: "Wie groß ist die Wahrscheinlichkeit, dass ein Wert nicht größer als x wird?"

Diese Funktion nimmt nicht ab und beginnt bei 0 und steigt über ihre Domäne auf 1 an. Ein Beispiel für die Summe von zwei sechsseitigen Würfeln ist unten gezeigt:

Wenn Ihre kumulative Verteilungsfunktion eine bequem zu berechnende Inverse aufweist (oder Sie können sie mit stückweisen Funktionen wie Bézier-Kurven approximieren), können Sie diese verwenden, um eine Stichprobe aus der ursprünglichen Wahrscheinlichkeitsfunktion zu erstellen.

Die Umkehrfunktion verarbeitet das Parzellieren der Domäne zwischen 0 und 1 in Intervalle, die auf jede Ausgabe des ursprünglichen Zufallsprozesses abgebildet werden, wobei der Einzugsbereich jedes Bereichs mit seiner ursprünglichen Wahrscheinlichkeit übereinstimmt. (Dies gilt infiniteszimal für kontinuierliche Verteilungen. Für diskrete Verteilungen wie Würfelwürfe müssen wir vorsichtig runden.)

Hier ist ein Beispiel für die Emulation von 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);
}

Vergleichen Sie dies mit:

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

Sehen Sie, was ich über den Unterschied in der Code-Klarheit und Flexibilität meine? Der naive Weg mag mit seinen Schleifen naiv sein, aber er ist kurz und einfach, sofort offensichtlich, was er tut, und leicht auf verschiedene Würfelgrößen und -zahlen zu skalieren. Das Vornehmen von Änderungen am kumulativen Verteilungscode erfordert einige nicht triviale Berechnungen, und es wäre leicht, ohne offensichtliche Fehler zu brechen und unerwartete Ergebnisse zu erzielen. (Was ich hoffe, dass ich oben nicht gemacht habe)

Bevor Sie also eine klare Schleife beseitigen, stellen Sie unbedingt sicher, dass es sich wirklich um ein Leistungsproblem handelt, das diese Art von Opfer wert ist.

2. Die Alias-Methode

Die kumulative Verteilungsmethode eignet sich gut, wenn Sie die Umkehrung der kumulativen Verteilungsfunktion als einfachen mathematischen Ausdruck ausdrücken können. Dies ist jedoch nicht immer einfach oder sogar möglich. Eine zuverlässige Alternative für diskrete Verteilungen ist die sogenannte Alias-Methode .

Auf diese Weise können Sie eine beliebige diskrete Wahrscheinlichkeitsverteilung mit nur zwei unabhängigen, gleichmäßig verteilten Zufallseingaben abtasten.

Es funktioniert, indem Sie eine Verteilung wie die unten auf der linken Seite nehmen (keine Sorge, dass die Flächen / Gewichte nicht 1 ergeben, für die Alias-Methode ist das relative Gewicht wichtig) und sie in eine Tabelle wie die folgende umwandeln das richtige wo:

• Für jedes Ergebnis gibt es eine Spalte.
• Jede Spalte ist in höchstens zwei Teile unterteilt, die jeweils einem der ursprünglichen Ergebnisse zugeordnet sind.
• Die relative Fläche / das relative Gewicht jedes Ergebnisses bleibt erhalten.

(Diagramm basierend auf Bildern aus diesem ausgezeichneten Artikel über Stichprobenverfahren )

Im Code stellen wir dies mit zwei Tabellen (oder einer Tabelle von Objekten mit zwei Eigenschaften) dar, die die Wahrscheinlichkeit der Auswahl des alternativen Ergebnisses aus jeder Spalte und die Identität (oder den "Alias") dieses alternativen Ergebnisses darstellen. Dann können wir wie folgt aus der Distribution probieren:

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

Dies erfordert einige Einstellungen:

1. Berechnen Sie die relativen Wahrscheinlichkeiten jedes möglichen Ergebnisses (wenn Sie also 1000d6 würfeln, müssen wir die Anzahl der Möglichkeiten berechnen, um jede Summe von 1000 auf 6000 zu bekommen).

2. Erstellen Sie ein Tabellenpaar mit einem Eintrag für jedes Ergebnis. Die vollständige Methode geht über den Rahmen dieser Antwort hinaus. Ich empfehle daher dringend, auf diese Erklärung des Algorithmus der Alias-Methode zu verweisen .

3. Speichern Sie diese Tabellen und greifen Sie jedes Mal darauf zurück, wenn Sie einen neuen zufälligen Würfelwurf aus dieser Verteilung benötigen.

Dies ist ein Kompromiss zwischen Raum und Zeit . Der Vorberechnungsschritt ist einigermaßen erschöpfend und wir müssen den Speicher entsprechend der Anzahl der erzielten Ergebnisse freigeben (obwohl wir auch bei 1000d6 von einstelligen Kilobyte sprechen, um den Schlaf nicht zu verlieren), sondern unsere Stichprobe austauschen ist konstante Zeit, egal wie komplex unsere Verteilung sein mag.

Ich hoffe, dass die eine oder andere dieser Methoden von Nutzen sein kann (oder dass ich Sie davon überzeugt habe, dass die Einfachheit der naiven Methode die Zeit wert ist, die für eine Schleife benötigt wird);)

Die Antwort ist leider, dass diese Methode nicht zu einer Leistungssteigerung führen würde.

Ich glaube, dass es bei der Frage, wie eine Zufallszahl erzeugt wird, Missverständnisse geben kann. Nehmen Sie das folgende Beispiel [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);
}

Dieser Code wiederholt die Ausgabe von Zufallszahlen zwischen 1 und 6 (einschließlich) 20 Mal. Wenn wir über die Leistung dieses Codes sprechen, wird etwas Zeit benötigt, um das Zufallsobjekt zu erstellen (wobei ein Array von Pseudozufallszahlen basierend auf der internen Uhr des Computers zum Zeitpunkt der Erstellung erstellt wird), und dann 20 konstante Zeit Nachschlagen bei jedem nextInt () -Aufruf. Da jede "Rolle" eine konstante Zeitoperation ist, ist das Rollen zeitlich sehr billig. Beachten Sie auch, dass der Bereich von min bis max keine Rolle spielt (mit anderen Worten, es ist für einen Computer genauso einfach, einen W6 zu würfeln, wie für einen W10000). In Bezug auf die Zeitkomplexität ist die Leistung der Lösung einfach O (n), wobei n die Anzahl der Würfel ist.

Alternativ könnten wir eine beliebige Anzahl von d6-Rollen mit einer einzelnen d100-Rolle (oder d10000 für diese Angelegenheit) approximieren. Bei dieser Methode müssen wir zuerst s [Anzahl der Gesichter zu den Würfeln] * n [Anzahl der Würfel] Prozentzahlen berechnen, bevor wir würfeln (technisch sind es s * n - n + 1 Prozentzahlen, und wir sollten in der Lage sein, diese grob zu teilen in der Hälfte, da es symmetrisch ist; beachten Sie, dass Sie in Ihrem Beispiel für die Simulation eines 2-W6-Wurfs 11 Prozent berechnet haben und 6 eindeutig waren). Nach dem Würfeln können wir mit einer binären Suche herausfinden, in welchen Bereich unser Würfeln fiel. In Bezug auf die Zeitkomplexität ergibt diese Lösung eine O (s * n) -Lösung, wobei s die Anzahl der Seiten und n die Anzahl der Würfel ist. Wie wir sehen können, ist dies langsamer als die im vorherigen Absatz vorgeschlagene O (n) -Lösung.

Wenn Sie von dort aus extrapolieren, haben Sie diese beiden Programme erstellt, um eine 1000d20-Rolle zu simulieren. Der erste würde einfach 1000-mal rollen. Das zweite Programm müsste zunächst 19.001 Prozent (für den potenziellen Bereich von 1.000 bis 20.000) ermitteln, bevor Sie etwas anderes tun können. Wenn Sie sich also nicht in einem seltsamen System befinden, in dem die Speichersuche erheblich teurer ist als Gleitkommaoperationen, ist die Verwendung eines nextInt () -Aufrufs für jede Rolle der richtige Weg.

Wenn Sie die Würfelkombinationen speichern möchten, ist die gute Nachricht, dass es eine Lösung gibt, die schlechte ist, dass unsere Computer in Bezug auf diese Art von Problemen irgendwie eingeschränkt sind.

Die guten Nachrichten:

Es gibt einen deterministischen Ansatz für dieses Problem:

1 / Berechne alle Kombinationen deiner Würfelgruppe

2 / Bestimmen Sie die Wahrscheinlichkeit für jede Kombination

3 / Suche in dieser Liste nach einem Ergebnis, anstatt die Würfel zu werfen

Die schlechten Nachrichten:

Die Anzahl der Kombinationen mit Wiederholungen ergibt sich aus den folgenden Formeln

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

( aus französisch wikipedia ):

Das bedeutet, dass Sie zum Beispiel mit 150 Würfeln 698'526'906 Kombinationen haben. Nehmen wir an, Sie speichern die Wahrscheinlichkeit als 32-Bit-Float, benötigen 2,6 GB Speicher und müssen den Speicherbedarf für die Indizes noch erhöhen ...

In Bezug auf die Berechnung kann die Kombinationszahl durch Faltungen berechnet werden, was praktisch ist, aber die Speicherbeschränkungen nicht löst.

Abschließend würde ich für eine große Anzahl von Würfeln raten, die Würfel zu werfen und das Ergebnis zu beobachten, anstatt die mit jeder Kombination verbundenen Wahrscheinlichkeiten vorab zu berechnen.

Bearbeiten

Da Sie jedoch nur an der Summe der Würfel interessiert sind, können Sie die Wahrscheinlichkeiten mit viel weniger Ressourcen speichern.

Mit Hilfe der Faltung können Sie genaue Wahrscheinlichkeiten für jede Würfelsumme berechnen.

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

Dann beginnend mit 1/6 von jedem Ergebnis mit 1 Würfel können Sie alle richtigen Wahrscheinlichkeiten für eine beliebige Anzahl von Würfeln konstruieren.

Hier ist ein grober Java-Code, den ich zur Veranschaulichung geschrieben habe (nicht wirklich optimiert):

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

}

}

Rufen Sie calcProb () mit den gewünschten Parametern auf und greifen Sie dann auf die Probentabelle für Ergebnisse zu (erster Index: 0 für 1 Würfel, 1 für zwei Würfel ...).

Ich habe es mit 1'000D6 auf meinem Laptop überprüft. Es dauerte 10 Sekunden, um alle Wahrscheinlichkeiten von 1 bis 1'000 Würfeln und alle möglichen Würfelsummen zu berechnen.

Mit Precomputing und effizientem Speicher können Sie schnell Antworten auf eine große Anzahl von Würfeln erhalten.

Ich hoffe es hilft.