Algorithmus wirft effizient gezinkte Würfel

Würfel: Virtuelles Zinken macht durchaus Sinn.

Bild: Jose-Luis Olivares/mit.edu

Forscher am Massachusetts Institute of Technology (MIT) haben einen neuen Algorithmus entwickelt, der virtuelle gezinkte Würfel wirft. Der "Fast Loaded Dice Roller" (FLDR) bietet dem Team nach die derzeit beste Kombination aus Geschwindigkeit, Genauigkeit und geringer Speichernutzung. Das soll die Simulation komplexer Systeme, in denen Dinge zwar zufällig, aber nicht mit gleicher Wahrscheinlichkeit passieren, erleichtern - von der Klimaforschung über die Epidemiologie bis hin zu Finanzmärkten.

Gewichteter Zufall

Das schnelle, effiziente Generieren von Zufallszahlen ist eine der grundlegendsten Herausforderungen in der Informatik und für Computersimulationen. Oft wäre dabei eine Gewichtung sinnvoll, dass also verschiedene Zahlen mit unterschiedlicher Wahrscheinlichkeit auftreten. Wenn zum Beispiel zwei Sportteams aufeinandertreffen, gibt es nur drei mögliche Ergebnisse - aber dass das stärkere Team gewinnt, ist wahrscheinlicher als ein Überraschungssieg oder Unentschieden. Hier könnte also ein passend gezinkter Würfel am schnellsten geeignete Zufallszahlen liefern - und genau das ist die Aufgabe des FLDR.

Der Algorithmus, der kommende Woche bei der 23rd International Conference on Artificial Intelligence and Statistics näher vorgestellt wird, verspricht nämlich exakt gewichtete Ergebnisse. Das heißt: Jede einer Reihe von Zufallszahlen tritt mit genau der gewünschten Wahrscheinlichkeit auf. Das allerdings ist gar nicht das Entscheidende am neuen Algorithmus; der eigentliche Durchbruch liegt darin, wie wenig Speicherbedarf dieser hat. Eben das sollte ihn den MIT-Forschern zufolge für Simulationsanwendungen sehr interessant machen.

Kompakt und schnell

Die Informatiker Donald Knuth und Andrew Yao haben bereits 1976 einen Algorithmus vorgestellt, der gezinkte Würfel mit der größtmöglichen zeitlichen Effizienz wirft. Allerdings ist ihr Ansatz ein unglaublicher Speicherfrssser. "Wir sind fast so zeiteffizient, aber wesentlich speicherffizienter", betont MIT-Doktorand Feras Saad; einer der Entwickler des FLDR. Dieser erfordert bis zu 10.000 Mal weniger Speicher, braucht aber höchstens 1,5 Mal so lange für eine Operation. Im Vergleich zum derzeit für gewichtete Zufallszahlen gängigen Ansatz "Alias" sei FLDR etwas effizienter und bisweilen auch schneller.

Das macht den neuen Algorithmus für immer größere, komplexere Computersimulationen interessant. Denn hier gibt es oft nur eine begrenzte Zahl möglicher Ergebnisse, die nicht gleich wahrscheinlich sind. Als Beispiel verweist das MIT besonders auf Inferenz-Verfahren, wo mehrere Simulationen reale Daten erklären sollen. Das ist klarerweise rechenaufwendiger als eine einfache Simulation, kommt aber beispielsweise bei den UN zum Einsatz, um seismische Daten zu interpretieren. Zu anderen Feldern, die profitieren könnten, zählt die dank COVID-19 ins Rampenlicht geratene Epidemiologie.

Quelle: www.pressetext.com/Thomas Pichler