Wie produziere ich "unterhaltsamen" Zufall im Gegensatz zu Pseudo-Zufall?

26

Ich mache ein Spiel, das nacheinander verschiedene Arten von Rätseln präsentiert. Ich wähle jedes Puzzle mit einer Pseudozufallszahl aus. Für jedes Puzzle gibt es eine Reihe von Variationen. Ich wähle die Variante mit einer anderen Pseudozufallszahl. Und so weiter.

Die Sache ist, dass dies zwar eine nahezu wahre Zufälligkeit erzeugt, der Spieler dies jedoch nicht wirklich wünscht. Der Spieler möchte normalerweise, was er wahrnimmt und als zufällig identifiziert, aber nur, wenn er nicht dazu neigt, Rätsel zu wiederholen. Also nicht wirklich zufällig. Einfach unvorhersehbar.

Wenn ich darüber nachdenke, kann ich mir hackige Wege vorstellen, es zu tun. Entfernen Sie beispielsweise vorübergehend die letzten N Auswahlmöglichkeiten aus dem Satz von Möglichkeiten, wenn Sie eine neue Auswahl treffen. Oder weisen Sie jeder Auswahl die gleiche Wahrscheinlichkeit zu, reduzieren Sie die Wahrscheinlichkeit einer Auswahl bei der Auswahl auf Null und erhöhen Sie dann alle Wahrscheinlichkeiten bei jeder Auswahl langsam.

Ich gehe davon aus, dass es einen etablierten Weg gibt, aber ich kenne die Terminologie einfach nicht und kann sie daher nicht finden. Weiß jemand? Oder hat jemand dies auf eine erfreuliche Weise gelöst?

Hilton Campbell
quelle
4
Das Buch "AI Game Programming Wisdom 2" enthält ein Kapitel über gefilterte Zufälligkeiten, das, wie ich mich erinnere, genau das ist, wonach Sie suchen. Ich habe es im Moment jedoch nicht, daher kann ich Ihnen keine vollständige Antwort geben.
Anton
Um es zu klären: Wenn Sie sagen, dass Sie Rätsel nicht wiederholen, wollen Sie dann nicht, dass zwei Rätsel des gleichen Typs nebeneinander stehen? Mit anderen Worten, wenn Sie gerade ein Sudoku ausgewählt haben, bieten Sie kein weiteres Sudoku-Puzzle an, aber wenn es Sudoku Nr. 19 war, ist es in Ordnung, Picross Nr. 19 als Nächstes anzubieten (mit anderen Worten, die Variationsnummer spielt keine Rolle). ?
Steven Stadnicki
2
Sehr verwandte Frage: stackoverflow.com/questions/910215/…
Chris Burt-Brown
1
OK, meine Kopie von AI Game Programming Wisdom 2 ist gerade eingetroffen. Ich las das Kapitel über gefilterte Zufälligkeiten und überprüfte den Quellcode. Dies ist wahrscheinlich der beste Ansatz. Es erlaubt mir, nur Zufallszahlen zu verwenden, aber dann die Zahlen so zu filtern, dass keine unerwarteten Muster auftreten. Es scheint kugelsicherer als der Shuffle Bag.
Hilton Campbell
1
Noch ein Update ... für meine spezielle Anwendung hat es die gefilterte Zufälligkeit nicht ganz geschafft. Ich möchte wirklich, dass der Player alle Typen und Untertypen durchspielt, bevor er sie wiederholt. Deshalb habe ich mich für eine Shuffle-Bag entschieden.
Hilton Campbell

Antworten:

25

Wenn Sie eine begrenzte Anzahl von Rätseln haben, können Sie:

  • Erstellen Sie eine Liste mit Puzzles, entweder alle oder zufällig ausgewählte Puzzles.
  • Mische diese Liste (siehe zum Beispiel Knuth Shuffle );
  • Lassen Sie Ihren Spieler diese Liste durchspielen.
  • Wenn die Liste leer ist, beginnen Sie mit einer neuen.

BEARBEITEN

Ich wusste das nicht, aber beim Durchstöbern von SE wurde mir klar, dass dies eigentlich als "Shuffle Bag" bekannt ist. Noch ein paar Infos hier , hier oder da .

BEARBEITEN 2

Der klassische Knuth Shuffle geht so:

To shuffle an array a of n elements (indices 0..n-1):
    for i from n  1 down to 1 do
        j  random integer with 0  j  i
        exchange a[j] and a[i]

Steven Stadnicki wies in seiner Bemerkung zu Recht darauf hin, dass dies die Wiederholung einer Umbildung nicht verhindert. Eine Möglichkeit, dies zu berücksichtigen, besteht darin, einen Sonderfall für das letzte Element hinzuzufügen:

To reshuffle an array a of n elements and prevent repetitions (indices 0..n-1):
    return if n <= 2

    // Classic Knuth Shuffle for all items *except* the last one
    for i from n  2 down to 1 do
        j  random integer with 0  j  i
        exchange a[j] and a[i]

    // Special case for the last item
    // Exchange it with an item which is *not* the first one
    r  random integer with 1  r  n - 1
    exchange a[r] and a[n - 1]
Laurent Couvidou
quelle
1
Dies kann funktionieren, aber Sie müssen ein wenig vorsichtig sein, wenn Sie nach jedem Durchspielen neu mischen, um nicht mit demselben Element zu beginnen, mit dem Sie geendet haben.
Steven Stadnicki
@Steven In der Tat. Dieser Artikel könnte aus der neuen Liste ausgeschlossen werden. Tatsächlich könnte es eine Idee sein, eine Liste mit nur wenigen zufälligen Elementen zu erstellen und die nächste Liste nur mit den verbleibenden Elementen zu erstellen. Wenn Sie also 100 Elemente haben, erstellen Sie z. B. eine gemischte Liste von 10. Wenn Sie mit dieser Liste fertig sind, erstellen Sie die nächste Liste mit 10 Elementen in den 90, die zuvor nicht ausgewählt wurden.
Laurent Couvidou
+1. Zusätzliche Unterstützung für diese Technik, die "mehr Spaß" macht: So produziert beispielsweise Tetris "zufällige" Teile. Von jedem Stück wird ein Satz gemischt und durchlaufen, wodurch die langen Sequenzen von Duplikaten vermieden werden, die durch echte Zufälligkeit zwangsläufig erzeugt würden.
KutuluMike
1
@Hilton Ich neige dazu, diese Art von "while-Schleife bis zufällig gibt mir, was ich will" -Ansatz nicht zu mögen ... Nicht sehr wahrscheinlich, dass dies irgendwelche Probleme verursachen wird. Trotzdem habe ich immer das Gefühl, dass dies ein Aufruf für zufällige Endlosschleifen oder Leistungseinbußen ist - die schrecklich zu debuggen sind. Wenn Sie das letzte Element der vorherigen Liste von der neuen Liste ausschließen, können Sie nur einmal mischen, um dasselbe Ergebnis zu erzielen.
Laurent Couvidou
1
Du hast recht und ich hatte die gleichen Vorbehalte. Anstatt das vorherige letzte Element auszuschließen, muss es jetzt nur noch einmal gemischt werden. Wenn das vorherige letzte Element jetzt das erste ist, tausche ich es nach dem Zufallsprinzip mit einem anderen Element aus.
Hilton Campbell
2

Eine Variante des Ansatzes von Lorancou: Halten Sie für jeden Rätseltyp eine Reihe von (gemischten) Rätselnummern bereit; Jedes Mal, wenn Sie ein Puzzle dieses Typs schlagen, wird die nächste Zahl von der Liste gestrichen. Nehmen wir zum Beispiel an, Sie haben Sudoku-, Picross- und Kenken-Rätsel, jedes mit Rätseln # 1..6. Sie erstellen drei gemischte Arrays mit den Nummern 1..6, eines für jeden Puzzletyp:

  • Sudoku: [5, 6, 1, 3, 4, 2]
  • Picross: [6, 2, 4, 1, 3, 5]
  • KenKen: [3, 2, 5, 6, 4, 1]

Nun mischen Sie die Puzzletypen, so wie es Lorancu vorschlägt. Nehmen wir an, es kommt auf [Picross, Sudoku, Kenken]. Verwenden Sie dann jedes Mal, wenn Sie ein Puzzle eines bestimmten Typs treffen, die nächste Zahl in der 'Zufallsliste'. Insgesamt wäre Ihre Puzzle-Präsentation [Sudoku # 5, Picross # 6, Kenken # 3, Sudoku # 6, Picross # 2, Kenken # 2, ...]

Wenn Sie die Rätsel nicht jedes Mal in der gleichen Gesamtreihenfolge halten möchten, ist es meiner Meinung nach am besten, wenn Sie die Auswahl nach dem Zufallsprinzip treffen und die letzten Picks ignorieren. Es gibt auch Möglichkeiten, wie Sie dies ein wenig effizienter gestalten können. Nehmen wir zum Beispiel an, Sie haben 20 Dinge und möchten die letzten 5 Dinge ignorieren. Anstatt nach dem Zufallsprinzip eine Zahl 1..20 auszuwählen und erneut zu spielen, bis Sie eine außerhalb der letzten 5 erhalten, wählen Sie stattdessen einfach eine Zahl 1..15 und gehen Sie die Puzzletypen in so vielen Schritten durch, dass Sie alle Puzzletypen überspringen, die vorhanden sind ausgewählt worden (Sie können dies einfach tun, indem Sie ein Bit-Array mit den letzten 5 ausgewählten Rätseln beibehalten).

Steven Stadnicki
quelle