Zwei Merge-Spiele, eine Frage: Kann eines von ihnen fehlerfrei gespielt werden? Die Antwort führt durch die Ecke eines Bretts, einen Gegner, der nie eintrifft, und eine Zahl, die siebzehn Exponenten hoch ist.
Auf Englisch verfasst und redigiert. Diese deutsche Fassung wurde maschinell übersetzt; wo es auf Genauigkeit ankommt, ist das englische Original maßgeblich. Das englische Original lesen →
Beginnen wir mit dem Spiel, das jeder kennt. 2048, vier Richtungen, ein 4×4-Raster, Kacheln, die verdoppelt werden, wenn sie sich berühren, ist streng genommen ungelöst. Niemand hat einen Algorithmus geschrieben, der es perfekt spielt. Was wir haben, sind sehr starke Approximationen. Eine Expectimax-Suche, die etwa acht Züge voraus schaut und jedes Brett anhand einer Handvoll handgefeilter Heuristiken bewertet, freie Felder, große Kacheln, die an einer Kante festgepinnt sind, Glätte, erreicht die 32768-Kachel in besser als einem Drittel ihrer Spiele, 1 und die stärkste öffentliche Engine berührt die 65536-Kachel ein paar Prozent der Zeit. 2 Verallgemeinert auf ein m×n-Brett ist allein die Entscheidung, ob eine Zielkachel erreichbar ist, NP-schwer. 3 Stark ist nicht dasselbe wie gelöst.
Wie hoch kann eine einzelne Kachel klettern? Auf sechzehn Feldern ist die Antwort ein kleines, elegantes Stück Zählen. Legen Sie das Brett als eine absteigende Treppe aus, 65536, 32768, 16384, hinab bis zu einer einzelnen 2. Jede Kachel ist genau eine Zweierpotenz niedriger als ihre Nachbarin, sodass die sechzehn verschiedenen Potenzen von 21 bis 216 das Brett perfekt füllen und 65536 = 216 an der Spitze sitzt: ein Exponent pro Feld. Das ist die Obergrenze, wenn das Spiel Ihnen nur 2er austeilt. Aber 2048 spawnt ein 4er einmal in zehn, und ein gut getimtes 4er schmuggelt einen siebzehnten Exponenten ein und hebt das wahre Maximum auf 131072 = 217, siebzehn Kacheln voller Potenzen, gepackt in sechzehn Quadrate. 4 Kein Mensch hat es gebaut; ein paar KIs haben es gestreift.
Warum belohnen diese Bretter das Einstecken Ihrer größten Kachel in eine Ecke? Eine Kachel in der Mitte kann auf vier Arten geschoben werden, und sie wird immer wieder von den Kacheln getrennt, mit denen sie sich verbinden möchte. Eine Eckkachel berührt zwei Wände; sie bewegt sich nur, wenn Sie in Richtung der Wände schieben, an denen sie bereits anliegt, sodass sie stillhält, während sich alles um sie herum organisiert. Ketten Sie den Rest zu einer monotonen Schlange, am höchsten in der Ecke, in absteigender Reihenfolge hin und her gefaltet, und ein Wischen kann eine Kaskade von Merges auslösen. 1 Dies ist die Heuristik, die das gelegentliche menschliche Spiel dominiert, und es ist fast genau das, was die KIs wiederentdecken, wenn man ihnen erlaubt, ihre eigenen Gewichte zu justieren.
Ein Merge-Spiel mit zufälligen Spawns hat keinen Gegner, nur Wetter. Es zu „lösen" bedeutet, im Durchschnitt die Würfel zu schlagen, nicht einen Geist.
Neigen Sie nun das Brett in drei Dimensionen. 3927 ist der kubische Cousin von 2048: ein 3×3×3-Gitter aus 27 Feldern, sechs Schiebrichtungen statt vier, und Kacheln, die zu dritt verschmelzen, 3 zu 9 zu 27 zu 81, Basis drei, wo 2048 Basis zwei ist. 5 Überlebt das Ecken-Stapeln die zusätzliche Dimension? Ein Würfel hat acht Ecken, und ein Eckfeld berührt nun drei Flächen statt zwei, es sollte noch stabiler sein, von drei Wänden gleichzeitig festgepinnt, obwohl die sechs Richtungen dem Brett mehr Wege geben, Ihre Struktur zu lösen. Die Schlange wird zu einem gefalteten Pfad, der alle drei Ebenen durchdringt. Soweit ich finden kann, hat niemand herausgearbeitet, ob die Analogie tatsächlich hält, Schlussfolgerung, nicht Messung.
Und die Obergrenze? Die Regel eines Exponenten pro Feld würde 327 ≈ 7,6 Billionen als eine lockere Obergrenze vorschlagen. Aber die Analogie frisst sich stark. Der zusätzliche Exponent von 2048 kam von einem glücklichen 4er; 3927 spawnt nur die kleinste Kachel, ein nacktes 3, also gibt es keinen Bonus. Schlimmer noch, ein Dreier-Merge benötigt drei Kacheln, die in einer Reihe ausgerichtet sind, und jede Reihe, Spalte und Säule auf einem 3×3×3-Würfel ist genau drei Felder lang, sodass jeder Merge eine gesamte Reihe verbraucht. Diese Einschränkung beißt viel härter als alles im flachen Spiel und zieht das wahre Maximum mit ziemlicher Sicherheit weit unter 327. Was diese wahre Zahl ist, habe ich nirgendwo berechnet gefunden. (Klar beschriftete Schlussfolgerung; die Mechaniken oben sind aus den Design-Dokumenten des Spiels gemessen.)
Hier liegt die Feinheit, die „perfektes Spiel" so schwer greifbar macht. Ein Verschmelzungsspiel mit zufälligen Spawns ist ein einspielerisches stochastisches Spiel, ein Solitär gegen einen Würfel, kein Duell. Nichts wählt den schlechtesten Spawn, um Sie zu ruinieren; es gibt nur den RNG, der gleichgültig ist. Der richtige Begriff für optimales Spiel ist daher Expectimax: Maximieren Sie das erwartete Ergebnis über die Verteilung der Spawns. Es ist ausdrücklich kein Minimax, denn Minimax setzt einen Gegner voraus, und wenn Sie tatsächlich einen Gegner zulassen, der jede Kachel platziert („böses 2048"), wird das Spiel zu etwas Grausamerem, bei dem Sie gezwungen werden können, zu verlieren. Da die Würfel prinzipiell jede Sequenz austeilen können, mag eine Strategie, die eine gegebene Kachel garantiert, schlicht nicht existieren. Die ehrliche Antwort auf die Frage „Gibt es eine perfekte Strategie?" lautet also, dass für ein stochastisches Spiel das Beste, was man überhaupt definieren kann, eine im Durchschnitt beste ist, und deren exakte Berechnung für 2048 unerreichbar ist 6 und für 3927 weit offen steht.