🤖 AI

Strongly Solving 2048 4x3

Dieser Artikel stellt die starke Lösung der 4x3-Variante des stochastischen Spiels 2048 vor und ermittelt durch die Anwendung einer altersbasierten Partitionierungstechnik zur Bewältigung seines riesigen Zustandsraums von über 1,15 Billionen erreichbaren Zuständen eine optimale erwartete Punktzahl von etwa 50.724,26.

Ursprüngliche Autoren: Tomoyuki Kaneko, Shuhei Yamashita

Veröffentlicht 2026-05-26

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Tomoyuki Kaneko, Shuhei Yamashita

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich das beliebte Puzzle-Spiel 2048 als eine riesige, chaotische Küche vor, in der Sie versuchen, Zutaten (Kacheln) zu kombinieren, um immer größere Gerichte zuzubereiten. In der Standardversion haben Sie ein 4x4-Raster (16 Plätze). In diesem Papier entschieden sich die Autoren, die Küche auf ein 4x3-Raster (12 Plätze) zu verkleinern, was es zu einer engeren, überfüllteren Herausforderung macht.

Hier ist die einfache Aufschlüsselung dessen, was sie taten, wie sie es taten und was sie herausfanden, unter Verwendung alltäglicher Analogien.

1. Die große Herausforderung: Eine Bibliothek, die zu groß zum Lesen ist

Die Autoren wollten diese kleinere Version des Spiels „stark lösen". In Spielesprache bedeutet dies, dass sie nicht nur den besten Zug für den Start wissen wollten; sie wollten den perfekten Zug für jede einzelne mögliche Situation wissen, die das Spiel jemals erreichen könnte.

Stellen Sie sich die möglichen Situationen des Spiels als eine Bibliothek vor.

Die ursprüngliche 3x3-Version (Mini2048) war wie ein kleines Bücherregal mit etwa 48.000 Büchern. Leicht zu lesen.
Diese neue 4x3-Version ist eine riesige Bibliothek mit über 1,15 Billionen Büchern (Zuständen) und fast 740 Milliarden „Zwischen"-Büchern (Nachzuständen).

Versuchen Sie, jedes Buch in dieser Bibliothek einzeln zu lesen, würde ewig dauern und einen Computer mit mehr Speicher erfordern, als auf der Welt existiert. Die Autoren brauchten einen Zaubertrick, um diese Bibliothek so zu organisieren, dass sie sie in nur wenigen Tagen auf einem normalen persönlichen Computer lösen konnten.

2. Der Zaubertrick: Das „Alter" des Spiels

Der Schlüssel zu ihrem Erfolg war ein Konzept, das sie „Alter" nennen.

Stellen Sie sich vor, jedes Mal, wenn Sie das Spiel spielen, fügen Sie einer Waage Gewicht hinzu.

Wenn Sie beginnen, haben Sie zwei Kacheln (sagen wir, zwei 2er). Das „Alter" ist die Summe aller Zahlen auf dem Brett (2 + 2 = 4).
Wenn Sie Kacheln schieben und zusammenführen, verdoppeln sich die Zahlen, aber das Alter bleibt genau gleich. (Das Zusammenführen zweier 2er zu einer 4 ändert die Gesamtsumme nicht).
Das einzige Mal, dass sich das Alter ändert, ist, wenn der Computer zufällig eine neue Kachel (eine 2 oder eine 4) fallen lässt. Dies addiert 2 oder 4 zum Alter.

Die Analogie:
Stellen Sie sich das Spiel nicht als Labyrinth vor, sondern als ein mehrstöckiges Gebäude.

Jeder „Stock" des Gebäudes repräsentiert ein bestimmtes Alter (z. B. Stock 4, Stock 6, Stock 8...).
Sie können sich auf demselben Stock frei bewegen (Kacheln schieben und zusammenführen), ohne hoch- oder runterzugehen.
Sie wechseln nur in den nächsten Stock, wenn der Computer eine neue Kachel fallen lässt.

Da das Spiel sich im Alter immer vorwärts bewegt (Sie kehren nie zu einer niedrigeren Summe zurück), konnten die Autoren die Bibliothek stockweise behandeln. Sie mussten nicht die ganze Bibliothek auf einmal im Kopf behalten. Sie mussten nur den aktuellen Stock, den nächsten Stock und den danach in ihrem Speicher halten. Sobald sie die besten Züge für Stock 100 berechnet hatten, konnten sie die Daten für Stock 98 wegwerfen, um Platz für Stock 102 zu schaffen.

3. Die Kompression: Einen Wal in einen Rucksack zu packen

Selbst mit diesem Stock-für-Stock-Trick waren die Daten immer noch riesig. Wenn sie jeden einzelnen Spielzustand auf Papier aufschreiben wollten, würde dies etwa 4,4 Terabyte Festplattenspeicher beanspruchen (ungefähr die Größe eines riesigen Rechenzentrums).

Um dies zu beheben, verwendeten sie eine clevere Datenkomprimierungstechnik namens Elias-Fano-Codierung.

Die Analogie: Stellen Sie sich vor, Sie haben eine Liste von 1 Milliarde Menschen, aber alle tragen rote Hemden. Anstatt neben jeden einzelnen Namen „Rotes Hemd" zu schreiben (was Platz verschwendet), schreiben Sie einen speziellen Code, der sagt: „Jeder in dieser Liste trägt ein rotes Hemd."
Sie fanden einen Weg, die „Ausweise" jedes möglichen Spielzustands auf etwa 1,4 Terabyte zu komprimieren. Wenn sie sich nur für die besten Züge interessierten (und die Rohdaten ignorierten), konnten sie es noch weiter auf etwa 300 Gigabyte verkleinern (die Größe der Festplatte eines High-End-Laptops).

4. Die Ergebnisse: Was haben sie gelernt?

Indem sie das Spiel lösten, berechneten sie die perfekte erwartete Punktzahl für einen Spieler, der nie einen Fehler macht.

Die Punktzahl: Wenn Sie mit dem häufigsten Setup beginnen (zwei 2er) und perfekt spielen, können Sie mit etwa 50.724 Punkten rechnen.
Der „Pech"-Faktor: Sie stellten fest, dass der Start mit einer 4er-Kachel anstelle von zwei 2er-Kacheln Sie tatsächlich einen leichten Nachteil bringt (etwa 4 Punkte weniger). Es ist wie ein Rennen mit einem schweren Rucksack zu beginnen; Sie müssen härter arbeiten, um aufzuholen.
Der „2048"-Hügel: Die Grafik ihrer Ergebnisse zeigte „Täler" (Einbrüche in der Leistung), immer wenn das Alter Vielfache von 2048 erreichte. Dies bestätigt ein Gefühl, das viele Spieler haben: Es wird unglaublich schwer, die 2048er-Kachel zu machen, weil Ihnen auf Ihrem kleinen 12-Quadrat-Brett der Platz ausgeht. Sie benötigen eine perfekte Anordnung, um alle kleineren Zahlen (2, 4, 8... bis 1024) unterzubringen, bevor Sie sie kombinieren können.

Zusammenfassung

Die Autoren nahmen ein Spiel, das aufgrund seiner enormen Anzahl an Möglichkeiten zu komplex erschien, um es vollständig zu lösen. Sie erkannten, dass sich das Spiel natürlich durch die „Summe der Zahlen" (Alter) organisiert. Indem sie das Spiel als eine Reihe von Etagen behandelten und nicht als ein riesiges, verworrenes Netz, und indem sie ein super-effizientes Ablagesystem (Kompression) verwendeten, kartierten sie die perfekte Strategie für jeden möglichen Zug.

Sie bewiesen, dass man mit einem Standardcomputer und ein paar Tagen Arbeit ein Spiel mathematisch meistern kann, das normalerweise auf Glück und Intuition beruht.

Technische Zusammenfassung: Starkes Lösen von 2048 auf einem 4×3-Brett

Problemdefinition

Diese Arbeit behandelt die „starke Lösung" einer stochastischen, Einzelspieler-Spielvariante: 2048 auf einem 4×3-Brett (bezeichnet als 2048 $^{4\times3}$ ). Im Gegensatz zur Standardversion 4×4 nutzt diese Variante ein Gitter mit 12 Zellen. Das Spiel wird als Markov-Entscheidungsprozess (MDP) modelliert, bei dem ein Agent Aktionen (hoch, runter, links, rechts) auswählt, um benachbarte Kacheln gleichen Werts zu verschmelzen. Nach einer gültigen Aktion geht der Brettzustand deterministisch in einen „Nachzustand" über (Verschieben und Verschmelzen der Kacheln). Anschließend generiert die Umgebung stochastisch eine neue Kachel (2 mit 90 % Wahrscheinlichkeit, 4 mit 10 %) in einer zufälligen leeren Zelle und geht in den nächsten Zustand über.

Das Ziel ist die Berechnung der optimalen Strategie $\pi^*$ und der optimalen Wertefunktion $v^*(s)$ , die die erwartete kumulierte Belohnung von jedem erreichbaren Zustand $s$ darstellt. Die Hauptherausforderung liegt in der Größe des Zustandsraums: Die 4×3-Variante enthält etwa $1,15 \times 10^9$ erreichbare Zustände und $7,4 \times 10^8$ Nachzustände. Dieser Umfang ist ungefähr $10^4$ -mal größer als bei der zuvor gelösten 3×3-Variante (Mini2048), was eine direkte Enumeration und Speicherung auf Standardhardware unmöglich macht.

Methodik

Die Autoren schlagen eine Lösung vor, die auf Zustandsraum-Partitionierung nach „Alter" und kompakter Datenrepräsentation basiert.

1. Alterbasierte Partitionierung

Die Kerninnovation besteht darin, das Alter eines Zustands als Summe aller Kachelwerte auf dem Brett zu definieren ( $age(s) = \sum c_i$ ).

Invarianz: Das Alter bleibt zwischen einem Zustand und seinem unmittelbaren Nachzustand nach einer gültigen Aktion konstant (da das Verschmelzen von Kacheln die Summe der Werte erhält und das Verschieben die Werte nicht verändert).
Progression: Das Alter erhöht sich um 2 oder 4 während des stochastischen Übergangs (Generieren einer neuen Kachel).
Algorithmische Implikation: Diese Eigenschaft ermöglicht die Aufteilung des Zustandsraums in disjunkte Teilmengen basierend auf dem Alter.
- Vorwärtspass (Enumeration): Gültige Zustände des Alters $n$ können ausschließlich aus Nachzuständen der Alter $n-2$ und $n-4$ generiert werden. Der Algorithmus iteriert durch steigende Alter und hält nur drei Mengen im Speicher (aktuelles Alter, Alter+2, Alter+4), um alle erreichbaren Zustände und Nachzustände zu enumerieren.
- Rückwärtspass (Wertberechnung): Optimale Werte werden durch Iteration rückwärts vom maximalen Alter zum Anfangsalter berechnet. Der Wert eines Zustands ist der maximale Wert seiner erreichbaren Nachzustände; der Wert eines Nachzustands ist der erwartete Wert seiner erreichbaren nächsten Zustände (gewichtet mit den Spawn-Wahrscheinlichkeiten).

2. Kompakte Repräsentation

Um die Speicheranforderungen (geschätzt auf ~4,4 TiB für rohe 48-Bit-IDs) zu bewältigen, verwenden die Autoren Elias-Fano-Codes zur Speicherung von Mengen eindeutiger Zustands-IDs.

Struktur: Sortierte eindeutige IDs werden in höherwertige Bits ( $h_i$ ) und niederwertige Bits ( $l_i$ ) aufgeteilt. Die niederwertigen Bits werden in einem zusammenhängenden Bitvektor gespeichert, während die höherwertigen Bits in einem dünn besetzten Bitvektor $H$ unter Verwendung von Rang-Operationen kodiert werden.
Optimierungen:
- Symmetriereduktion: IDs werden auf den minimalen Wert unter horizontalen, vertikalen und 180-Grad-Rotationssymmetrien normalisiert.
- Basisanpassung: Die Kodierungsbasis wird basierend auf dem maximalen Kachelwert für ein spezifisches Alter angepasst.
- Zellen-Entfernung: Informationen einer Zelle werden während der Kodierung weggelassen, da die Summe (Alter) das Gesamtergebnis einschränkt und eine vollständige Rekonstruktion später ermöglicht.
Effizienz: Dies reduziert den Speicherbedarf für alle Nachzustands-IDs von ~4,4 TiB auf ungefähr 1,4 TiB, während effiziente Nachschlagefähigkeiten erhalten bleiben. Für optimales Spiel speziell reduziert eine spezialisierte Repräsentation (unter Verwendung des BuRR-Algorithmus) die Anforderung auf unter 300 GiB.

Hauptergebnisse

Zustandsraum-Statistik: Die Gesamtzahl der erreichbaren Zustände beträgt 1.152.817.492.752, und die Anzahl der Nachzustände beträgt 739.648.886.170.
Optimale Erwartungspunktzahl: Für die häufigsten Anfangszustände (zwei Kacheln mit dem Wert 2) beträgt die erwartete Punktzahl unter einer optimalen Strategie ungefähr 50.724,26.
- Anfangszustände mit einer 4er-Kachel (Alter 6) ergeben eine leicht niedrigere erwartete Punktzahl (~50.720,62).
- Anfangszustände mit zwei 4er-Kacheln (Alter 8) ergeben die niedrigste (~50.708,99), was auf einen kleinen Nachteil beim Start mit höherwertigen Kacheln hindeutet.
Zustandsverteilung: Die Anzahl der Zustände pro Alter ist allgemein handhabbar (weniger als $3 \times 10^6$ pro Alter), was dem Algorithmus ermöglicht, mehrere Altersschichten im Speicher zu halten.
Terminale Zustände: „Täler" in der Verteilung der Zustandsanzahl treten bei Altersstufen auf, die Vielfache von 2048 sind, was die Schwierigkeit widerspiegelt, große Kacheln mit begrenztem Brettspielraum zu bilden. Bestimmte Altersstufen (z. B. 8190, 12286) haben keine gültigen Nachzustände, da die Bildung dieser Summen mehr Kacheln erfordern würde, als die verfügbaren 12 Zellen zulassen.
Aktions-Sensitivität: Der Unterschied im Wert zwischen optimalen und suboptimalen Aktionen erreicht in der Nähe der Alter 2048 und 4096 ihren Höhepunkt, was darauf hindeutet, dass frühe Entscheidungen unmittelbar nach der Bildung großer Kacheln kritisch sind.

Bedeutung und Behauptungen

Die Arbeit behauptet, die 2048 $^{4\times3}$ -Variante stark gelöst zu haben, eine Aufgabe, die zuvor aufgrund der Größe des Zustandsraums als unlösbar galt. Die Bedeutung dieser Arbeit liegt in:

Skalierbarkeit: Der Nachweis, dass ein Spiel mit über $10^9$ Zuständen auf einem Personalcomputer innerhalb weniger Tage gelöst werden kann, indem spiel-spezifische strukturelle Eigenschaften (Alter) genutzt werden, anstatt auf Brute-Force-Methoden zurückzugreifen.
Methodischer Beitrag: Die Einführung der „Alter"-Partitionierungstechnik ermöglicht die Enumeration und Wertberechnung stochastischer MDPs, bei denen Zustandswerte von Erwartungen abhängen, und umgeht effektiv die Notwendigkeit von $\alpha\beta$ -Abschneidung (die in stochastischen Umgebungen unwirksam ist).
Datenverfügbarkeit: Die Autoren stellen die optimale Wertefunktion und eine kompakte Repräsentation des Zustandsraums bereit, die als Basis für zukünftige Forschungsarbeiten im Bereich Reinforcement Learning und Spielanalyse dienen.
Speichereffizienz: Die erfolgreiche Anwendung von Elias-Fano-Codes zur Komprimierung einer riesigen Menge von Spielzuständen auf ~1,4 TiB macht den Datensatz für Forscher mit moderaten Rechenressourcen (z. B. 4-TiB-SSDs) zugänglich.

Die Autoren merken an, dass, obwohl das Hauptziel das Lösen des Spiels war, der resultierende Datensatz und das Konzept des „Alters" als Grundlage für weitere Studien zu stochastischen Spielen und der Evaluierung von Reinforcement Learning dienen können.