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

14

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?


quelle
5
Selbst bei 1000 d6 ist die Schleife auf einem modernen PC schnell genug, so dass Sie es kaum bemerken werden. Dies kann eine vorzeitige Optimierung sein. Versuchen Sie immer, ein Profil zu erstellen, bevor Sie eine klare Schleife durch eine undurchsichtige Formel ersetzen. Das heißt, es gibt algorithmische Optionen. Interessieren Sie sich für diskrete Wahrscheinlichkeiten wie Würfel in Ihren Beispielen oder ist es akzeptabel, sie als kontinuierliche Wahrscheinlichkeitsverteilung zu modellieren (sodass ein Bruchergebnis wie 2,5 möglich sein könnte)?
DMGregory
DMGregory richtig, die Berechnung von 1000d6 wird kein allzu großes Problem für den Prozessor sein. Es gibt jedoch eine Sache namens Binomial Distribution, die (mit etwas gescheiter Arbeit) das Ergebnis liefert, an dem Sie interessiert sind. Wenn Sie jemals die Wahrscheinlichkeiten für einen beliebigen Roll-Regelsatz finden möchten, versuchen Sie es mit TRoll, das eine bescheidene Sprache hat Mit set wird festgelegt, wie ein Würfelsatz gewürfelt werden soll, und es werden alle Wahrscheinlichkeiten für jedes mögliche Ergebnis berechnet.
Draco18s
Verwenden Sie eine Poisson-Verteilung: p.
Luis Masuelli
1
Für jeden Würfelsatz, der oft genug gewürfelt wird, erhalten Sie wahrscheinlich eine Verteilungskurve / ein Histogramm. Das ist ein wichtiger Unterschied. Ein Würfel kann eine Million 6s hintereinander werfen, es ist unwahrscheinlich, aber es kann
Richard Tingle
@RichardTingle Kannst du das näher erläutern? Eine Verteilungskurve / ein Histogramm enthält auch den Fall "Million 6s in einer Reihe".
amitp

Antworten:

16

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:

Diagramme der Wahrscheinlichkeit, der kumulativen Verteilung und der Inversen für 2d6

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.

Beispiel einer Alias-Methode zum Konvertieren einer Distribution in eine Nachschlagetabelle

(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);)

DMGregory
quelle
1
Geniale Antwort. Ich mag die naive Herangehensweise. Viel weniger Platz für Fehler und einfach zu verstehen.
Bummzack
FYI diese Frage ist ein Kopieren-Einfügen von einer zufälligen Frage auf Reddit.
Vaillancourt
Der Vollständigkeit halber denke ich, dass dies der reddit Thread ist, über den @AlexandreVaillancourt spricht. Die Antworten dort deuten hauptsächlich darauf hin, dass die Loop-Version (mit einigen Hinweisen darauf, dass der Zeitaufwand wahrscheinlich vernünftig ist) beibehalten oder eine große Anzahl von Würfeln mit einer normalen / Gaußschen Verteilung approximiert wird.
DMGregory
+1 für die Alias-Methode scheinen so wenige Leute darüber Bescheid zu wissen, und es ist wirklich die ideale Lösung für viele dieser Arten von Wahrscheinlichkeitswahlsituationen und +1 für die Erwähnung der Gaußschen Lösung, die wahrscheinlich die "bessere" ist. Antworten Sie, wenn es uns nur um Leistung und Platzersparnis geht.
am
0

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.

ZackDeRose
quelle
2
Die obige Analyse ist nicht ganz richtig. Wenn wir im Voraus etwas Zeit einplanen, um Wahrscheinlichkeits- und Alias-Tabellen gemäß der Alias-Methode zu generieren , können wir eine Stichprobe aus einer beliebigen diskreten Wahrscheinlichkeitsverteilung in konstanter Zeit (2 Zufallszahlen und eine Tabellensuche) erstellen. Das Simulieren eines Würfels mit 5 Würfeln oder eines Würfels mit 500 Würfeln erfordert also den gleichen Arbeitsaufwand, sobald die Tische vorbereitet sind. Dies ist asymptotisch schneller als das Durchlaufen einer großen Anzahl von Würfeln für jede Probe, obwohl dies nicht unbedingt eine bessere Lösung für das Problem darstellt. ;)
DMGregory
0

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

Γnk=(n+k-1k)=(n+k-1)!k! (n-1)!

( aus französisch wikipedia ):

Kombination mit Wiederholungen

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.

Fich(m)=nF1(n)Fich-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.

elenfoiro78
quelle
3
Da OP nur nach dem Wert der Würfelsumme sucht , gilt diese kombinatorische Mathematik nicht, und die Anzahl der Einträge in der Wahrscheinlichkeitstabelle wächst linear mit der Größe der Würfel und mit der Anzahl der Würfel.
DMGregory
Sie haben Recht ! Ich habe meine Antwort bearbeitet. Wir sind immer schlau, wenn viele;)
elenfoiro78
Ich denke, Sie können die Effizienz ein wenig verbessern, indem Sie einen Divide & Conquer-Ansatz verwenden. Wir können die Wahrscheinlichkeitstabelle für 20d6 berechnen, indem wir die Tabelle für 10d6 mit sich selbst falten. 10d6 finden wir, indem wir die 5d6-Tabelle mit sich selbst falten. 5d6 finden wir, indem wir die 2d6- und 3d6-Tabellen zusammenfalten. Wenn Sie auf diese Weise in zwei Hälften vorgehen, können Sie die meisten Tabellengrößen von 1 bis 20 überspringen und uns auf die interessanten konzentrieren.
DMGregory
1
Und Symmetrie verwenden!
elenfoiro78