Wie kann ich einen "zufälligen" Generator erstellen, der durch frühere Ereignisse beeinflusst wird?

37

Ich versuche, ein zufallsbasiertes System zu implementieren, das durch vorherige Ereignisse verzerrt ist.

Hintergrund: Vor einigen Jahren erinnere ich mich an ein Update für World of Warcraft, in dem angekündigt wurde, einen neuen Chancenrechner zu implementieren, der stacheligen Ereignisketten entgegenwirkt. (zB kritische Treffer erzielen oder mehrmals hintereinander ausweichen). Die Idee war, dass für den Fall, dass Sie einem Treffer ausweichen würden, die Wahrscheinlichkeit, dass Sie dem nächsten Treffer ausweichen würden, geringer wäre, aber es würde in beide Richtungen funktionieren. Wenn Sie einem Treffer nicht ausweichen, steigt auch die Wahrscheinlichkeit, dem nächsten Treffer auszuweichen. Der Haupttrick dabei war, dass die Ausweichchance bei mehreren Versuchen immer noch dem Prozentsatz entspricht, den der Spieler in seiner Statistik angegeben hat.

Diese Art von System hat mich damals sehr fasziniert, und jetzt bin ich in der Situation, eine solche Lösung zu brauchen.

Hier sind meine Probleme:

  • Ich vermute, dass ich Online-Ressourcen zur Implementierung eines solchen Systems finden könnte, aber mir fehlen möglicherweise nur die relevanten Schlagworte, um es zu finden.
  • Auch ich brauche diesen Ansatz, um ein System anzupassen, das nicht binomial ist (dh zwei Ergebnisse), sondern stattdessen 4 sich gegenseitig ausschließende Ereignisse enthält.

Mein derzeitiger Ansatz ähnelt dem eines Gewinnspiel-Ticketsystems. Wenn ein Ereignis eintritt, ändere ich die Gewichte zugunsten aller anderen Ereignisse. Dies könnte funktionieren, wenn die vier Ereignisse gleich wahrscheinlich wären, aber in meinem Fall müssen sie viel häufiger auftreten. Da das vorherrschende Ereignis jedoch häufiger auftritt, werden die Gewichte des anderen um ein vielfaches höher als beabsichtigt verschoben, und ich kann die Zahlen für die Gewichtsverschiebungen nicht finden, die erforderlich sind, um die durchschnittliche Ticketanzahl um die Anfangswerte des Ereignisses zu halten gegeben.

Ein paar Richtungsweiser oder ein anschauliches Beispiel wären sehr willkommen.

Sonaten
quelle
4
Wenn Sie eine differenzierte oder differenzierte Antwort wünschen, haben Sie möglicherweise mehr Glück, wenn Sie bei Mathematics.SE nachfragen. Die dortigen Mathematiker beantworten gerne komplizierte Fragen zur Wahrscheinlichkeit. math.stackexchange.com
Kevin - Reinstate Monica
1
PRNG
Jon
6
Eine Alternative zur Mathematik-Website, auf der Sie die Antworten mit größerer Wahrscheinlichkeit verstehen, ist Programmers.SE . Das Algorithmus-Design ist in Mathematik nicht besonders thematisch und Sie müssten wahrscheinlich ein erstes Design erstellen, um nützliche Eingaben zu erhalten.
Lilienthal
1
Ich stimme Kevin und Lilienthal zu, dass Sie dort möglicherweise eine bessere Antwort erhalten, aber als ich die Antwort von mklingen las, wurde mir klar, dass das, was hier beschrieben wird, als Markov-Kette modelliert werden kann und dass dies ein nützliches Werkzeug für Spieleentwickler sein könnte. Ich werde versuchen, das später genauer zu beschreiben.
nwellcome
1
Da ich einige der Antworten hier durchgesehen habe, stelle ich fest, dass es eine Reihe verschiedener Einschränkungen gibt und dass eine Lösung, die alle löst, komplexer sein kann als das, was Sie benötigen. Einige weitere Details zu Ihrem Anwendungsfall helfen möglicherweise dabei, die besten Optionen einzugrenzen. Sind zum Beispiel die Wahrscheinlichkeiten Ihrer Ereignisse ziemlich ähnlich (z. B. 5 unterschiedliche Ergebnisse mit jeweils 20% Chance) oder sehr unterschiedlich (z. B. 10% verfehlen 80% treffen 10% kritisch)? Möchten Sie Läufe minimieren (z. B. 3 Fehlversuche hintereinander) oder Klumpen / Wartezeiten (z. B. 3 Fehlversuche von 8 Versuchen oder 20 Versuchen, bevor ich einen kritischen Treffer erhalte)?
DMGregory

Antworten:

19

Grundsätzlich benötigen Sie einen "semi-zufälligen" Ereignisgenerator, der Ereignisse mit den folgenden Eigenschaften generiert:

  1. Die durchschnittliche Häufigkeit, mit der jedes Ereignis eintritt, ist im Voraus festgelegt.

  2. Es ist weniger wahrscheinlich, dass dasselbe Ereignis zweimal hintereinander auftritt als zufällig.

  3. Die Ereignisse sind nicht vollständig vorhersehbar.

Eine Möglichkeit, dies zu tun, besteht darin, zuerst einen nicht zufälligen Ereignisgenerator zu implementieren , der die Ziele 1 und 2 erfüllt, und dann eine gewisse Zufälligkeit hinzuzufügen, um Ziel 3 zu erfüllen.


Für den nicht zufälligen Ereignisgenerator können wir einen einfachen Dithering- Algorithmus verwenden. Insbesondere sei p 1 , p 2 , ..., p n die relative Wahrscheinlichkeit der Ereignisse 1 bis n , und sei s = p 1 + p 2 + ... + p n die Summe der Gewichte. Mit dem folgenden Algorithmus können wir dann eine nicht zufällige, maximal gleich verteilte Folge von Ereignissen erzeugen:

  1. Zunächst sei e 1 = e 2 = ... = e n = 0.

  2. Um ein Ereignis zu erzeugen, inkrementieren Sie jedes e i um p i und geben Sie das Ereignis k aus, für das e k am größten ist (brechen Sie die Bindungen nach Belieben).

  3. Dekrementieren Sie e k um s und wiederholen Sie den Vorgang ab Schritt 2.

Beispielsweise erzeugt dieser Algorithmus bei drei Ereignissen A, B und C mit p A = 5, p B = 4 und p C = 1 so etwas wie die folgende Folge von Ausgaben:

A B A B C A B A B A A B A B C A B A B A A B A B C A B A B A

Beachten Sie, dass diese Folge von 30 Ereignissen genau 15 As, 12 Bs und 3 Cs enthält. Es ist nicht ganz optimal verteilt - es gibt ein paar Vorkommen von zwei As in einer Reihe, die hätte vermieden werden können - aber es kommt näher.


Um dieser Sequenz eine Zufälligkeit hinzuzufügen, haben Sie mehrere (sich nicht unbedingt gegenseitig ausschließende) Optionen:

  • Sie können Philipps Rat befolgen und ein "Deck" mit N anstehenden Ereignissen für eine entsprechend große Anzahl von N verwalten . Jedes Mal, wenn Sie ein Ereignis erzeugen müssen, wählen Sie ein zufälliges Ereignis aus dem Deck aus und ersetzen es durch das nächste Ereignis, das vom obigen Dithering-Algorithmus ausgegeben wird.

    Wendet man dies auf das obige Beispiel mit N = 3 an, so erhält man zB:

    A B A B C A B B A B A B C A A A A B B A B A C A B A B A B A

    Während N = 10 das eher zufällig aussehende ergibt:

    A A B A C A A B B B A A A A A A C B A B A A B A C A C B B B

    Beachten Sie, dass die häufigen Ereignisse A und B aufgrund des Mischens viel häufiger auftreten, während die seltenen C-Ereignisse immer noch relativ weit auseinander liegen.

  • Sie können dem Dithering-Algorithmus Zufälligkeiten hinzufügen. Anstatt in Schritt 2 e i um p i zu inkrementieren, könnten Sie es beispielsweise um p i × random (0, 2) inkrementieren , wobei random ( a , b ) eine gleichmäßig verteilte Zufallszahl zwischen a und b ist ; Dies würde eine Ausgabe wie die folgende ergeben:

    A B B C A B A A B A A B A B A A B A A A B C A B A B A C A B

    oder Sie könnten e i um p i + zufällig erhöhen (- c , c ), was ergeben würde (für c = 0,1 × s ):

    B A A B C A B A B A B A B A C A B A B A B A A B C A B A B A

    oder für c = 0,5 × s :

    B A B A B A C A B A B A A C B C A A B C B A B B A B A B C A

    Beachten Sie, dass das additive Schema für die seltenen Ereignisse C einen viel stärkeren Randomisierungseffekt hat als für die häufigen Ereignisse A und B, verglichen mit dem multiplikativen. Dies könnte oder könnte nicht wünschenswert sein. Natürlich können Sie auch eine Kombination dieser Schemata oder eine andere Anpassung der Inkremente verwenden, sofern dabei die Eigenschaft erhalten bleibt, dass das durchschnittliche Inkrement von e i gleich p i ist .

  • Alternativ können Sie die Ausgabe des Dithering-Algorithmus stören, indem Sie manchmal das ausgewählte Ereignis k durch ein zufälliges Ereignis ersetzen (das gemäß den Rohgewichten p i ausgewählt wird ). Solange Sie in Schritt 3 dasselbe k wie in Schritt 2 verwenden, gleicht der Dithering-Vorgang zufällige Schwankungen aus.

    Hier ein Beispiel für eine Ausgabe mit einer Wahrscheinlichkeit von 10%, dass jedes Ereignis nach dem Zufallsprinzip ausgewählt wird:

    B A C A B A B A C B A A B B A B A B A B C B A B A B C A B A

    und hier ist ein Beispiel mit einer 50% igen Chance, dass jede Ausgabe zufällig ist:

    C B A B A C A B B B A A B A A A A A B B A C C A B B A B B C

    Sie können auch erwägen, eine Mischung aus rein zufälligen und geditherten Ereignissen in einen Deck / Mixing-Pool einzuspeisen, wie oben beschrieben, oder den Dithering-Algorithmus durch zufällige Auswahl von k zu randomisieren, wie durch die e i gewichtet (wobei negative Gewichte als Null behandelt werden).

Ps. Hier sind einige völlig zufällige Ereignissequenzen mit den gleichen Durchschnittsraten zum Vergleich:

A C A A C A B B A A A A B B C B A B B A B A B A A A A A A A
B C B A B C B A A B C A B A B C B A B A A A A B B B B B B B
C A A B A A B B C B B B A B A B A A B A A B A B A C A A B A

Tangens: Da in den Kommentaren einige Debatten darüber geführt wurden, ob es für deckbasierte Lösungen erforderlich ist, das Deck vor dem Nachfüllen entleeren zu lassen, habe ich mich für einen grafischen Vergleich mehrerer Strategien zum Befüllen von Decks entschieden:

Handlung
Darstellung mehrerer Strategien zur Erzeugung von halbzufälligen Münzwürfen (mit einem durchschnittlichen Verhältnis von Kopf zu Zahl von 50:50). Die horizontale Achse ist die Anzahl der Kippbewegungen, die vertikale Achse ist der kumulative Abstand vom erwarteten Verhältnis, gemessen als (Kopf - Zahl) / 2 = Kopf - Kippbewegungen / 2.

Die roten und grünen Linien in der Grafik zeigen zum Vergleich zwei nicht deckbasierte Algorithmen:

  • Rote Linie, deterministisches Dithering : Gerade Ergebnisse sind immer Köpfe, ungerade Ergebnisse sind immer Schwänze.
  • Grüne Linie, unabhängige Zufallswechsel : Jedes Ergebnis wird unabhängig nach dem Zufallsprinzip ausgewählt, mit einer 50% igen Chance für Kopf und einer 50% igen Chance für Zahl.

Die anderen drei Linien (blau, lila und cyan) zeigen die Ergebnisse von drei deckbasierten Strategien, die jeweils mit einem Deck von 40 Karten implementiert wurden, das anfänglich mit 20 "Kopf" -Karten und 20 "Schwanz" -Karten gefüllt ist:

  • Blaue Linie, leer ausfüllen : Die Karten werden nach dem Zufallsprinzip gezogen, bis das Deck leer ist. Anschließend wird das Deck mit 20 "Kopf" -Karten und 20 "Schwanz" -Karten aufgefüllt.
  • Lila Linie, füllen, wenn die Hälfte leer ist : Die Karten werden nach dem Zufallsprinzip gezogen, bis noch 20 Karten übrig sind. Dann wird das Deck mit 10 "Kopf" -Karten und 10 "Schwanz" -Karten aufgefüllt.
  • Cyan-Linie, kontinuierlich füllen : Die Karten werden nach dem Zufallsprinzip gezogen. Unentschieden mit geraden Zahlen werden sofort durch eine "Kopf" -Karte und Unentschieden mit ungeraden Zahlen durch eine "Schwanz" -Karte ersetzt.

Natürlich ist die obige Handlung nur eine einzelne Realisierung eines zufälligen Prozesses, aber sie ist einigermaßen repräsentativ. Insbesondere können Sie sehen, dass alle deckbasierten Prozesse eine begrenzte Verzerrung aufweisen und ziemlich nahe an der roten (deterministischen) Linie bleiben, während die rein zufällige grüne Linie schließlich abweicht.

(Tatsächlich ist die Abweichung der blauen, violetten und cyanfarbenen Linien von Null streng durch die Deckgröße begrenzt: Die blaue Linie kann niemals mehr als 10 Schritte von Null entfernt sein, die violette Linie kann nur 15 Schritte von Null entfernt sein In der Praxis ist es natürlich äußerst unwahrscheinlich, dass eine der Linien tatsächlich ihre Grenze erreicht, da die Tendenz besteht, dass sie näher an Null zurückkehren, wenn sie zu weit wandern aus.)

Auf einen Blick gibt es keinen offensichtlichen Unterschied zwischen den verschiedenen deckbasierten Strategien (obwohl die blaue Linie im Durchschnitt etwas näher an der roten Linie und die Cyan-Linie etwas weiter entfernt bleibt), aber eine genauere Betrachtung der blauen Linie zeigt ein deutliches deterministisches Muster: Alle 40 Ziehungen (markiert durch die gepunkteten grauen vertikalen Linien) trifft die blaue Linie genau auf die rote Linie bei Null. Die violetten und cyanfarbenen Linien sind nicht so stark eingeschränkt und können an jedem Punkt von Null abweichen.

Bei allen deckbasierten Strategien ist das wichtige Merkmal, das die Variation begrenzt, die Tatsache, dass das Deck deterministisch aufgefüllt wird , während die Karten zufällig aus dem Deck gezogen werden . Wenn die Karten, die zum Nachfüllen des Decks verwendet wurden, selbst zufällig ausgewählt würden, würden alle deckbasierten Strategien nicht mehr von der reinen Zufallsauswahl (grüne Linie) zu unterscheiden sein.

Ilmari Karonen
quelle
Sehr durchdachte Antwort. Das Hinzufügen von Zufallsfaktoren zum Dithering-Algorithmus scheint einfach zu sein. :)
Sonaten
Beschlossen, mit Ihrer Antwort zu gehen. :) Aber ich würde empfehlen, dass Sie die Ergänzungen der Methodenübersicht ganz oben setzen. Was ich tun werde, basierend auf Ihrer Antwort, ist, sowohl die "rote" als auch die "lila" Lösung auszuprobieren.
Sonaten,
53

Nicht würfeln, Karten austeilen.

Nehmen Sie alle möglichen Ergebnisse Ihres RNG, fügen Sie sie in eine Liste ein, mischen Sie sie nach dem Zufallsprinzip und geben Sie die Ergebnisse in der zufälligen Reihenfolge zurück. Wenn Sie am Ende der Liste angekommen sind, wiederholen Sie den Vorgang.

Die Ergebnisse werden immer noch gleichmäßig verteilt, aber die einzelnen Ergebnisse wiederholen sich erst, wenn das Letzte der Liste auch das Erste des nächsten ist.

Wenn dies für Ihren Geschmack etwas zu vorhersehbar ist, können Sie eine Liste verwenden, die ndie Anzahl der möglichen Ergebnisse multipliziert und jedes mögliche Ergebnis nvor dem Mischen einfügt. Sie können die Liste auch neu mischen, bevor sie vollständig iteriert wird.

Philipp
quelle
1
Lookup "Shuffle Bag" (auch auf dieser Seite)
jhocking
3
So vermeiden viele Tetris-Spiele, dass der Spieler zu lange hungrig nach Schlüsselstücken ist. Es ist wichtig, den Beutel / das Deck zu leeren, wie es Philipp vorschlägt, bevor Sie neue Karten einlegen, wenn Sie die Vorkommnisse in einem festgelegten Intervall kontrollieren möchten. Durch erneutes Einlegen von Karten (oder erneutes Anpassen von Gewichten) können Sie die Wahrscheinlichkeitsverteilung auf eine Weise verzerren, die schwierig zu berechnen und leicht falsch zu verstehen ist.
DMGregory
2
@DMGregory: Tatsächlich ist es vollkommen in Ordnung, neue Karten zu mischen, bevor das Deck geleert wird (und ich würde dies empfehlen, um die Ergebnisse natürlicher und schwerer vorhersehbar zu machen). Das Wichtigste ist , um sicherzustellen , dass der (mittlere) Anteil an neuen Karten gemischt in das Deck gleich die gewünschte Fraktion , dass Sie zeichnen möchten heraus es.
Ilmari Karonen
4
Illmari Karonen: Wenn Sie Gegenstände ersetzen, können Sie die Vorteile des Shuffle-Beutels in Bezug auf die Begrenzung von Läufen mit identischen Ergebnissen oder langen Lücken zwischen bestimmten Ergebnissen verlieren. Wenn Ihre Ersatzrate der Zielwahrscheinlichkeitsverteilung entspricht, sind Sie nachweislich in der gleichen Position, wie Sie jedes Ergebnis unabhängig und zufällig generieren. Wenn es nicht der Zielwahrscheinlichkeitsverteilung entspricht, können Sie die effektiven Wahrscheinlichkeiten auf schwer vorhersagbare Weise verzerren und entsprechend ausgleichen - der Fragesteller beschreibt, wie er mit genau diesem Problem zu kämpfen hat.
DMGregory
2
Einverstanden mit @DMGregory. Indem Sie neue Karten mischen, machen Sie das System selbst ungültig. Das Kartenhandelssystem ist speziell und perfekt für das gewünschte Ergebnis geeignet. Wenn Sie beispielsweise eine Dame aus dem Stapel nehmen (um beispielsweise herkömmliche Karten zu verwenden), verringert sich die Wahrscheinlichkeit, eine Dame zu ziehen, und die Wahrscheinlichkeit, eine andere Karte als eine Dame zu ziehen, erhöht sich. Es ist ein sich selbst anpassendes System, wenn Sie so wollen.
Volte
17

Sie könnten einen Markov-Zufallsgraphen ausprobieren . Betrachten Sie jedes Ereignis, das auftreten kann, als Knoten in einem Diagramm. Stellen Sie von jedem Ereignis aus einen Link zu jedem anderen Ereignis her, das möglicherweise danach kommen könnte. Jeder dieser Links wird mit der sogenannten Übergangswahrscheinlichkeit gewichtet . Anschließend führen Sie eine zufällige Wanderung des Diagramms gemäß dem Übergangsmodell durch.

Sie können beispielsweise eine Grafik erstellen, die das Ergebnis eines Angriffs darstellt (kritischer Treffer, Ausweichen usw.). Initialisiere den Startknoten so, dass er zufällig ausgewählt wird, abhängig von den Statistiken des Spielers. Überlegen Sie sich dann beim nächsten Angriff, was angesichts des Übergangsmodells als Nächstes passiert.

Es muss sorgfältig entschieden werden, wie die Übergänge gewichtet werden sollen. Zum einen müssen sich alle Übergänge, die von einem Knoten ausgehen, zu einer Wahrscheinlichkeit von 1 summieren. Eine einfache Sache, die Sie tun können, ist, einen Übergang von jedem Knoten zu jedem anderen Knoten mit einer Gewichtung durchzuführen, die der Wahrscheinlichkeit entspricht, dass diese Ereignisse auftreten a priori , da das aktuelle Ereignis nicht erneut eintreten kann.

Wenn Sie beispielsweise drei Ereignisse haben:

  Critical, P = 0.1
  Hit,      P = 0.3
  Miss,     P = 0.6

Sie können das Übergangsmodell so einrichten, dass ein kritischer Treffer nicht erneut auftritt, indem Sie einfach seine Wahrscheinlichkeitsmasse gleichmäßig auf die anderen Ereignisse verteilen:

  Critical -> Critical,   P = 0.0
  Critical -> Hit,        P = 0.35
  Critical -> Miss,       P = 0.65

BEARBEITEN: Wie die Kommentare unten sagen, ist dieses Modell nicht kompliziert genug, um das gewünschte Verhalten zu erzielen. Stattdessen müssen Sie möglicherweise mehrere zusätzliche Status hinzufügen!

mklingen
quelle
1
Das von Ihnen vorgeschlagene Neugewichtungsschema berücksichtigt nicht die gewünschten Wahrscheinlichkeiten für jeden Staat. Wenn Sie einen empirischen Test mit diesen Zahlen durchführen, treten in etwa 41% der Fälle Fehler auf, und in etwa 25% der Fälle Fehler, die von den Eingabewerten abweichen. Der Übergang in die verbleibenden Zustände ist proportional zu ihren Wahrscheinlichkeiten (z. B. Miss hat eine 25% ige Chance, zu Kritisch zu werden, und eine 75% ige Chance, zu Treffer zu werden), ist etwas besser, mit einer 44% igen Miss-Rate und 17% Kritisch, aber es ist immer noch so spiegelt nicht die gewünschten Wahrscheinlichkeiten in der Eingabe wider.
DMGregory
Ich habe die Bayes-Regel vergessen :( Wird später erneut berechnet. Es ist möglicherweise nicht möglich, die vorherige Wahrscheinlichkeitsverteilung beizubehalten, da das Übergangsmodell mögliche Sequenzen wie CCHM oder CHHM oder das sehr wahrscheinliche MMHM usw. ausschließt.
mklingen
Die Beschränkung "keine Wiederholungen" könnte Ihnen hier die Hände binden, was extreme hohe und niedrige Gewichte betrifft. Wenn Sie möchten, dass 1 von 10 Versuchen kritisch ist, können Sie mit dieser Methode nur 5 Fehler und 5 Treffer abwechseln, wodurch die Treffer- und Fehlerwahrscheinlichkeiten in Richtung ihres Durchschnitts verzerrt werden. Keine Sequenz ohne aufeinanderfolgende Fehlschläge kann hier die Anforderungen der Eingabe erfüllen.
DMGregory
4
@mklingen, da stimme ich DMGregory zu, das "strikt keine Wiederholungen" ist hier nicht wünschenswert. Sie möchten vielmehr, dass die Wahrscheinlichkeit, dass lange Ketten desselben Ergebnisses auftreten, geringer ist als bei einer einheitlichen Zufallswahrscheinlichkeit. Man könnte dies mit einer Markov - Kette tun (das gerichtet ist) , dass sieht aus wie diese . Dies verwendet mehrere Zustände, um wiederholte Ereignisse darzustellen, bei denen die Wahrscheinlichkeiten des Übergangs von "Treffer 1" zu "Treffer 2" und "Treffer 2" zu "Treffer 3+" sinken und die Wahrscheinlichkeiten des Übergangs zurück zu "Treffer 1" und "Kritisch" 1 "steigen.
Nwellcome
@nwellcome das ist eine tolle idee.
Mklingen
3

Hier ist eine Implementierung, die ich in C # erstellt habe:

  • Aktivieren Sie Ereignisse basierend auf Wahrscheinlichkeiten
  • Passen Sie diese Wahrscheinlichkeiten an, um die Wahrscheinlichkeit wiederkehrender Ereignisse zu verringern
  • Nicht zu weit von den ursprünglichen Wahrscheinlichkeiten entfernt

Ich habe ein paar Kommentare hinzugefügt, damit Sie sehen können, was ich tue.

    int percentageEvent1 = 15; //These are the starter values. So given a scenario, the
    int percentageEvent2 = 40; //player would have around a 15 percent chance of event
    int percentageEvent3 = 10; //one occuring, a 40 percent chance of event two occuring
    int percentageEvent4 = 35; //10 percent for event three, and 35 percent for event four.

    private void ResetValues()
    {
        percentageEvent1 = 15;
        percentageEvent2 = 40;
        percentageEvent3 = 10;
        percentageEvent4 = 35;
    }

    int resetCount = 0; //Reset the probabilities every so often so that they don't stray too far.

    int variability = 1; //This influences how much the chance of an event will increase or decrease
                           //based off of past events.

    Random RandomNumberGenerator = new Random();

    private void Activate() //When this is called, an "Event" will be activated based off of current probability.
    {
        int[] percent = new int[100];
        for (int i = 0; i < 100; i++) //Generate an array of 100 items, and select a random event from it.
        {
            if (i < percentageEvent1)
            {
                percent[i] = 1; //Event 1
            }
            else if (i < percentageEvent1 + percentageEvent2)
            {
                percent[i] = 2; //Event 2
            }
            else if (i < percentageEvent1 + percentageEvent2 + percentageEvent3)
            {
                percent[i] = 3; //Event 3
            }
            else
            {
                percent[i] = 4; //Event 4
            }
        }
        int SelectEvent = percent[RandomNumberGenerator.Next(0, 100)]; //Select a random event based on current probability.

        if (SelectEvent == 1)
        {
            if (!(percentageEvent1 - (3 * variability) < 1)) //Make sure that no matter what, probability for a certain event
            {                                                //does not go below one percent.
                percentageEvent1 -= 3 * variability;
                percentageEvent2 += variability;
                percentageEvent3 += variability;
                percentageEvent4 += variability;
            }
        }
        else if (SelectEvent == 2)
        {
            if (!(percentageEvent2 - (3 * variability) < 1))
            {
                percentageEvent2 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent3 += variability;
                percentageEvent4 += variability;
            }
        }
        else if (SelectEvent == 3)
        {
            if (!(percentageEvent3 - (3 * variability) < 1))
            {
                percentageEvent3 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent2 += variability;
                percentageEvent4 += variability;
            }
        }
        else
        {
            if (!(percentageEvent4 - (3 * variability) < 1))
            {
                percentageEvent4 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent2 += variability;
                percentageEvent3 += variability;
            }
        }

        resetCount++;
        if (resetCount == 10)
        {
            resetCount = 0;
            ResetValues();
        }

        RunEvent(SelectEvent); //Run the event that was selected.
    }

Hoffe, das hilft, bitte schlagen Sie Verbesserungen an diesem Code in den Kommentaren vor, danke!

Superdoggy
quelle
1
Diese Neugewichtung führt tendenziell dazu, dass die Ereignisse als gleich wahrscheinlich eingestuft werden. Ein regelmäßiges Zurücksetzen der Gewichte ist eigentlich nur ein Hilfsmittel, um das Ausmaß zu begrenzen, während sichergestellt wird, dass jeder zehnte Wurf überhaupt keinen Nutzen aus der Neugewichtung zieht. Ein weiterer Hinweis zum Algorithmus: Sie verschwenden viel Arbeit, wenn Sie eine Tabelle mit 100 Einträgen füllen, um eine zufällige Auswahl zu treffen. Stattdessen können Sie einen zufälligen Wurf generieren und dann über Ihre 4 Ergebnisse iterieren und dabei deren Wahrscheinlichkeiten aufsummieren. Sobald der Wurf kleiner als die Summe ist, haben Sie Ihr Ergebnis. Keine Tischfüllung erforderlich.
DMGregory
3

Lassen Sie mich die Antwort von mklingen etwas verallgemeinern . Grundsätzlich möchten Sie das Gambler's Fallacy implementieren , obwohl ich hier eine allgemeinere Methode bereitstellen werde:

Angenommen, es gibt nmögliche Ereignisse mit Wahrscheinlichkeiten p_1, p_2, ..., p_n. Wenn ein Ereignis ieingetreten ist, wird seine Wahrscheinlichkeit mit einem Faktor neu skaliert 0≤a_i≤1/p_i(letzterer ist wichtig, sonst haben Sie eine größere Wahrscheinlichkeit als eines und die anderen Ereignisse müssen negative Wahrscheinlichkeiten haben , was im Grunde genommen " Anti " -Ereignisse bedeutet. Oder so etwas) typisch a_i<1. Sie können beispielsweise wählen a_i=p_i, was bedeutet, dass die Wahrscheinlichkeit, dass ein Ereignis ein zweites Mal eintritt, die ursprüngliche Wahrscheinlichkeit ist, dass das Ereignis genau zweimal hintereinander eintritt. Beispielsweise hätte ein zweiter Münzwurf eine Wahrscheinlichkeit von 1/4 anstelle von 1/2. Auf der anderen Seite können Sie auch welche haben a_i>1, was bedeuten würde, einen "Glücksfall / Unglücksfall" auszulösen.

Alle anderen Ereignisse sollen gleich wahrscheinlich relativ zueinander bleiben, dh sie müssen alle um den gleichen Faktor neu skaliert werden, b_iso dass die Summe aller Wahrscheinlichkeiten gleich eins ist, dh

1 = a_i*p_i + b_i*(1-p_i)  # Σ_{j≠i) p_j  = 1 - p_i
 b_i = (1 - a_i*p_i) / (1 - p_i).   (1)

So weit, so einfach. Fügen wir nun eine weitere Anforderung hinzu: Unter Berücksichtigung aller möglichen Sequenzen von zwei Ereignissen müssen die daraus extrahierten Einzelereigniswahrscheinlichkeiten die ursprünglichen Wahrscheinlichkeiten sein.

Lassen

        / p_i * b_i * p_j  (ji)
p_ij = <
        \ a_i * (p_i     (j=i)

bezeichnen die Wahrscheinlichkeit des Eintretens eines Ereignisses jnach dem Ereignis iund beachten Sie, dass, p_ij≠p_jisofern b_i=b_j (2)(was (1)impliziert a_j = 1 - a_i*p_i + (1-a_i)*p_i/p_j). Dies erfordert auch der Satz von Bayes, und dies impliziert auch

Σ_j p_ij = p_i * b_i * (1 - p_i) + a_i * (p_i
         = b_i * p_i + (a_i - b_i) * (p_i
         = p_i  # using (1)

wie gewünscht. Beachten Sie nur, wie dies bedeutet, dass man a_ialle anderen repariert.


Nun wollen wir sehen, was passiert, wenn wir diese Prozedur mehrmals anwenden, dh für Sequenzen von drei und mehr Ereignissen. Grundsätzlich gibt es zwei Optionen für die Auswahl der manipulierten Wahrscheinlichkeiten des dritten Ereignisses:

a) Vergessen Sie das erste Ereignis und das Rig, als ob nur das zweite aufgetreten wäre, d. h

         / p_ij * a_j * p_j  (j=k)
p_ijk = <
         \ p_ij * b_j * p_l  (jk)

Beachten Sie, dass dies in der Regel gegen Bayes verstößt, da zB p_jik≠p_ikjin den meisten Fällen.

b) Verwenden Sie die Wahrscheinlichkeiten p_ij(für fest i) als neue Wahrscheinlichkeiten, pi_jaus denen Sie die neuen Wahrscheinlichkeiten pi_jkfür kdas nächste Ereignis erhalten . Ob Sie die ändern ai_joder nicht, liegt an Ihnen, aber beachten Sie, dass die neuen bi_jaufgrund der geänderten definitiv anders sind pi_j. Andererseits wird die Auswahl ai_jwahrscheinlich dadurch eingeschränkt, dass alle Permutationen ijkmit der gleichen Wahrscheinlichkeit auftreten müssen. Wir werden sehen...

         / p_ij * bi_j * pi_k  (jk)
p_ijk = <
         \ (p_ij * ai_j      (j=k)

         / b_i * bi_j * p_i * p_j * pi_k  (ijki)
         | b_i * ai_j * p_i * (p_j      (ij=k)
      = <  a_i * (p_i * bi_i * pi_k     (i=jk)
         | b_i * p_i * bi_j * p_k * pi_i  (i=kj)
         \ a_i * ai_i * (p_i * pi_i     (i=k=j)

und deren zyklische Permutationen, die für die jeweiligen Fälle gleich sein müssen.

Ich fürchte, meine Fortsetzung muss noch eine Weile warten ...

Tobias Kienzler
quelle
Wenn dies empirisch getestet wird, führt dies immer noch zu einer Verzerrung weg von den Eingabewahrscheinlichkeiten über viele Läufe. Wenn beispielsweise a_i / p_i = 0,5 ist (und Zahlen aus der Antwort von mklingen verwendet), wird eine Eingangsfehlrate von 60% zu einer beobachteten Rate von 50,1%, und eine Eingangskritikalitätsrate von 10% wird zu 13,8% beobachtet. Sie können dies überprüfen, indem Sie die resultierende Übergangsmatrix auf eine hohe Leistung bringen. Die Wahl von Verhältnissen von a_i: p_i näher an 1 führt zu einer geringeren Verzerrung, aber auch zu einer geringeren Wirksamkeit bei der Reduzierung der Läufe.
DMGregory
@DMGregory guter Punkt: Sie können nicht einfach Potenzen der Übergangsmatrix übernehmen. Ich werde später auf meine Antwort
eingehen
@DMGregory Ich habe angefangen, den gesamten Prozess zu beschreiben (Variante b)), aber es wird ziemlich langweilig und mir fehlt momentan die Zeit: /
Tobias Kienzler
1

Ich denke, die beste Option ist die zufällig gewichtete Artikelauswahl. Es gibt eine Implementierung für C # hier , aber sie können leicht gefunden oder auch für andere Sprachen erstellt werden.

Die Idee wäre, das Gewicht einer Option jedes Mal zu reduzieren, wenn sie ausgewählt wird, und es jedes Mal zu erhöhen, wenn sie nicht ausgewählt wird.

Wenn Sie beispielsweise das Gewicht der ausgewählten Option um verringern NumOptions-1und das Gewicht aller anderen Optionen um 1 erhöhen (wobei Sie darauf achten müssen, Elemente mit einem Gewicht von <0 zu entfernen und sie zu lesen, wenn sie über 0 steigen) , werden alle Optionen ungefähr ausgewählt über einen langen Zeitraum gleich oft, aber bei kürzlich ausgewählten Optionen ist die Wahrscheinlichkeit, dass sie ausgewählt werden, sehr viel geringer.


Das Problem bei der Verwendung einer zufälligen Reihenfolge besteht darin, dass Sie nach Auswahl jeder Option mit 100% iger Sicherheit vorhersagen können, welche Option als Nächstes ausgewählt wird. Das ist nicht sehr zufällig.

BlueRaja - Danny Pflughoeft
quelle
1

Meine Antwort ist falsch, mein Test war fehlerhaft.

Ich lasse diese Antwort hier für die Diskussion und Kommentare, die auf die Fehler in diesem Design hinweisen, aber der eigentliche Test war falsch.

Was Sie suchen, ist ein gewichtetes Gewicht: Die Gewichte für Ihre vier möglichen Ergebnisse müssen durch vorherige Ergebnisse weiter angepasst (gewichtet) werden, wobei die richtigen Gewichte insgesamt erhalten bleiben müssen.

Der einfachste Weg, dies zu erreichen, besteht darin , alle Gewichte für jede Rolle zu ändern, indem Sie das Gewicht für den spezifischen gewürfelten Wert verringern und die anderen Gewichte erhöhen .

Nehmen wir als Beispiel an, Sie haben 4 Gewichte: Fumble, Miss, Hit und Crit. Sagen wir auch, dass Ihre gewünschten Gesamtgewichte für sie Fumble = 10%, Miss = 50%, Hit = 30% und Crit = 10% sind.

Wenn Sie einen Zufallszahlengenerator (RNG) verwenden, um Werte zwischen 1 und 100 zu erzeugen, und diesen Wert dann mit dem Wert vergleichen, der in diesen Bereich fällt (1-10 Fumble, 11-60 Miss, 61-90 Hit, 91-100 Crit ), generieren Sie eine einzelne Rolle.

Wenn Sie bei diesem Wurf diese Bereiche sofort auf der Grundlage des gewürfelten Werts anpassen, werden Sie zukünftige Würfe gewichten, aber Sie müssen auch das gewürfelte Gewicht um denselben Gesamtbetrag reduzieren, um den Sie die anderen Gewichte erhöhen. In unserem obigen Beispiel würden Sie also das gerollte Gewicht um 3 reduzieren und die anderen Gewichte jeweils um 1 erhöhen.

Wenn Sie dies für jeden Wurf tun, haben Sie immer noch die Chance auf Streifen, aber diese werden stark reduziert, da Sie für jeden Wurf die Chance erhöhen, dass zukünftige Wurf etwas anderes sind als der aktuelle Wurf. Sie können diesen Effekt erhöhen und dadurch die Wahrscheinlichkeit von Streifen weiter verringern, indem Sie die Gewichte um einen größeren Faktor erhöhen / verringern (z. B. Strom um 6 verringern und andere um 2 erhöhen).

Ich habe eine schnelle App ausgeführt, um diesen Ansatz zu validieren, und nach 32000 Iterationen mit diesen Gewichten werden die folgenden Grafiken erstellt. Das obere Diagramm zeigt die 4 Gewichtungs-Sofortwerte bei jedem Wurf, und das untere Diagramm zeigt die Gesamtzahl der bis zu diesem Punkt gerollten Ergebnistypen.

Wie Sie sehen, schwanken die Gewichte geringfügig um ihre gewünschten Werte, aber die Gesamtgewichte bleiben innerhalb der gewünschten Bereiche, und nachdem sich die anfängliche Vielfalt der Startnummern eingestellt hat, passen die Ergebnisse fast perfekt zu unseren gewünschten Prozentsätzen.

Beachten Sie, dass dieses Beispiel mit der .NET System.Random-Klasse erstellt wurde, die nicht wirklich zu den besseren RNGs auf dem Markt gehört, sodass Sie wahrscheinlich genauere Ergebnisse erzielen können, wenn Sie ein besseres RNG verwenden. Beachten Sie auch, dass 32000 die maximalen Ergebnisse waren, die ich mit diesem Tool grafisch darstellen konnte, mein Test-Tool jedoch in der Lage war, über 500 Millionen Ergebnisse mit denselben Gesamtmustern zu generieren.

David C Ellis
quelle
Beachten Sie, dass dies nur funktioniert, wenn Ihre +1 / -3 relativ zu den ursprünglichen Gewichten und nicht zu den zuletzt verwendeten Gewichten angewendet werden. (Wenn Sie die Gewichte auf diese Weise kontinuierlich und gleichmäßig ändern, tendieren Sie dazu, gleich wahrscheinlich zu sein.) Auf diese Weise bleibt die Wahrscheinlichkeit auf lange Sicht auf dem Ziel, aber es wird nur sehr wenig zur Reduzierung der Läufe beigetragen. Angesichts der Tatsache, dass ich einmal verpasst habe, beträgt die Chance, dass ich zweimal hintereinander verpasse, bei diesem Schema 22%, bei unabhängigen Ziehungen 25%. Ein Erhöhen der Gewichtsverlagerung für einen größeren Effekt (sagen wir + 3 / -9) führt zu einer Verzerrung der langfristigen Wahrscheinlichkeit.
DMGregory
Bei den oben dargestellten Daten wird bei jeder Verarbeitung einer Rolle das letzte Gewicht mit + 1 / -3 angegeben. Wenn Sie also beim anfänglichen Gewicht von 50% einmal verfehlen, beträgt das nächste verfehlte Gewicht 47%, und wenn Sie erneut verfehlen, beträgt das folgende Gewicht 44% und so weiter. Es werden zwar Läufe reduziert (separate Metrik verfolgte Läufe, bis zu 24% weniger Läufe), diese sind jedoch unvermeidlich, da bei diesem Schema die Wahrscheinlichkeit groß ist, dass jedes der 4 Gewichtungen mit einer Wahrscheinlichkeit ungleich Null zurückbleibt ( ZB würden vier Crits in einer Reihe das Crit-Gewicht mit null Eintrittswahrscheinlichkeit verlassen.
David C Ellis
Wenn das Ihre Absicht war, dann hat Ihre Implementierung einen Fehler. Schauen Sie sich die Grafik an - Das Fummelgewicht springt immer nur zwischen 7 und 11, ohne dass Werte darüber hinausgehen. Ich habe eine Simulation mit der von Ihnen beschriebenen kontinuierlichen Modifikation durchgeführt und die Diagramme unterscheiden sich drastisch, wobei die Wahrscheinlichkeiten jedes Zustands in den ersten hundert Versuchen gegen jeweils 25% konvergieren.
DMGregory
Verdammt, es war in der Tat nervig, wie Sie betonten. Nun, schlagen Sie diese Antwort.
David C Ellis
@ DavidCEllis sagen Sie, Ihre Implementierung war fehlerhaft, oder die Idee selbst ist? Meine Intuition auf der Rückseite einer Serviette ergab ungefähr das Modell, das Sie beschrieben haben (reduzieren Sie die Wahrscheinlichkeit beim Zeichnen, stellen Sie nach und nach alle Wahrscheinlichkeiten mit der Zeit auf ihre ursprünglichen Werte wieder her), und es ist für mich immer noch sinnvoll.
dimo414
0

Sie könnten tun, was im Wesentlichen ein Filter ist. Verfolgen Sie die letzten n Ereignisse. Die Wahrscheinlichkeit ist ein Teil eines Filters, der auf diese Ereignisse angewendet wird. Der 0. Filter ist die Basiswahrscheinlichkeit. Wenn 0, sind Sie ausgewichen, wenn 1, haben Sie versagt. Angenommen, die Basis betrug 25%, und der Filter nimmt bei jeder Iteration um die Hälfte ab. Ihr Filter wäre dann:

[.25 .125 .0625 .03125] 

Fühlen Sie sich frei, um fortzufahren, wenn Sie es wünschen. Die Gesamtwahrscheinlichkeit dieses Schemas ist geringfügig höher als die Basiswahrscheinlichkeit von 0,25. Tatsächlich ist die Wahrscheinlichkeit bei dem gleichen Schema (ich nenne x die reale Wahrscheinlichkeit, p ist die Wahrscheinlichkeitseingabe):

x=p+(1-x)*(p/2+p/4+p/8)

Wenn man nach x auflöst, findet man die Antwort p(1+1/2+1/4+1/8)/(1+p(1/2+1/4+1/8)oder für unseren gegebenen Fall x=0.38461538461. Aber was Sie wirklich wollen, ist, p mit x zu finden. Das ist ein schwierigeres Problem. Wenn Sie einen unendlichen Filter angenommen haben, wird das Problem zu x+x*p=2*poder p=x/(2-x). Wenn Sie also Ihren Filter vergrößern, können Sie nach einer Zahl p suchen, die im Durchschnitt dieselben Ergebnisse liefert, jedoch in Abhängigkeit davon, wie erfolgreich Sie in letzter Zeit waren.

Grundsätzlich verwenden Sie die vorherigen Werte, um die Akzeptanzschwelle für diese Runde zu bestimmen, und nehmen einen zufälligen Wert. Produziere dann den nächsten Zufallswert unter Berücksichtigung des Filters.

PearsonArtPhoto
quelle
-1

Wie Sie sich selbst vorgeschlagen haben, besteht einer der Ansätze darin, einen gewichteten Zufall zu implementieren. Die Idee ist, einen Zufallszahlen- (oder Ergebnis-) Generator zu erstellen, in dem Gewichte und Ergebnisse geändert werden können.

Hier ist eine Implementierung davon in Java.

import java.util.Map;
import java.util.Random;

/**
 * A psuedorandom weighted outcome generator
 * @param <E> object type to return
 */
public class WeightedRandom<E> {

    private Random random;
    private Map<E, Double> weights;

    public WeightedRandom(Map<E, Double> weights) {
        this.random = new Random();
        this.weights = weights;
    }

    /**
     * Returns a random outcome based on the weight of the outcomes
     * @return
     */
    public E nextOutcome() {
        double totalweight = 0;

        // determine the total weigth
        for (double w : weights.values()) totalweight += w;

        // determine a value between 0.0 and the total weight
        double remaining = random.nextDouble() * totalweight;

        for (E entry : weights.keySet()) {
            // subtract the weight of this entry
            remaining -= weights.get(entry);

            // if the remaining is smaller than 0, return this entry
            if (remaining <= 0) return entry;
        }

        return null;
    }

    /**
     * Returns the weight of an outcome
     * @param outcome the outcome to query
     * @return the weight of the outcome, if it exists
     */
    public double getWeight(E outcome) {
        return weights.get(outcome);
    }

    /**
     * Sets the weight of an outcome
     * @param outcome the outcome to change
     * @param weight the new weigth
     */
    public void setWeight(E outcome, double weight) {
        weights.put(outcome, weight);
    }
}

BEARBEITEN Wenn Sie die Gewichte automatisch anpassen möchten, erhöhen Sie beispielsweise die Wahrscheinlichkeit von A, wenn das Ergebnis B war. Sie können entweder

  1. Ändern Sie das Verhalten der nextOutcome()Methode, sodass das Gewicht entsprechend dem Ergebnis geändert wird
  2. Verwenden Sie setWeight(), um das Gewicht entsprechend dem Ergebnis zu ändern.
erikgaal
quelle
Ich glaube, Sie haben die Frage falsch verstanden: Das OP fragt nicht, wie gewichtete zufällige Ergebnisse generiert werden sollen, sondern wie die Gewichte angepasst werden müssen, um die Wahrscheinlichkeit zu verringern, dass dasselbe Ergebnis mehrmals hintereinander auftritt.
Ilmari Karonen
Ich habe einige meiner Antworten geändert, um zu erklären, wie dies mit diesem System möglich wäre.
Erikgaal