🤖 AI

Strongly Solving 2048 4x3

Dit artikel presenteert de sterke oplossing van de 4x3-variant van het stochastische spel 2048, waarbij een optimale verwachte score van ongeveer 50.724,26 wordt vastgesteld door gebruik te maken van een op leeftijd gebaseerde partitioneringstechniek om de enorme toestandsruimte van meer dan 1,15 biljoen bereikbare toestanden te beheersen.

Oorspronkelijke auteurs: Tomoyuki Kaneko, Shuhei Yamashita

Gepubliceerd 2026-05-26

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tomoyuki Kaneko, Shuhei Yamashita

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je het populaire puzzelspel 2048 voor als een gigantische, chaotische keuken waar je ingrediënten (tegels) probeert te combineren om steeds grotere gerechten te maken. In de standaardversie heb je een 4x4-rooster (16 plekken). In dit artikel hebben de auteurs besloten om de keuken te verkleinen tot een 4x3-rooster (12 plekken), waardoor het een strakkere, meer overvolle uitdaging wordt.

Hier is de eenvoudige uitleg van wat ze deden, hoe ze het deden en wat ze ontdekten, met behulp van alledaagse analogieën.

1. De Grote Uitdaging: Een Bibliotheek Te Groot Om Te Lezen

De auteurs wilden deze kleinere versie van het spel "sterk oplossen". In gametermen betekent dit dat ze niet alleen de beste zet voor het begin wilden weten; ze wilden de perfecte zet voor elke mogelijke situatie weten die het spel ooit kan bereiken.

Stel je de mogelijke situaties van het spel voor als een bibliotheek.

De originele 3x3-versie (Mini2048) was als een klein boekenrek met ongeveer 48.000 boeken. Makkelijk te lezen.
Deze nieuwe 4x3-versie is een enorme bibliotheek met meer dan 1,15 biljoen boeken (staten) en bijna 740 miljard "tussenliggende" boeken (afterstates).

Elk boek in deze bibliotheek één voor één proberen te lezen zou eeuwen duren en vereist een computer met meer geheugen dan er ter wereld bestaat. De auteurs hadden een magische truc nodig om deze bibliotheek zo te organiseren dat ze het binnen een paar dagen konden oplossen op een gewone persoonlijke computer.

2. De Magische Truc: De "Leeftijd" van het Spel

De sleutel tot hun succes was een concept dat ze "Leeftijd" noemen.

Stel je voor dat elke keer dat je het spel speelt, je gewicht toevoegt aan een weegschaal.

Wanneer je begint, heb je twee tegels (bijvoorbeeld twee 2-en). De "Leeftijd" is de som van alle getallen op het bord (2 + 2 = 4).
Wanneer je tegels schuift en samenvoegt, verdubbelen de getallen, maar blijft de Leeftijd exact hetzelfde. (Het samenvoegen van twee 2-en tot een 4 verandert de totale som niet).
De enige keer dat de Leeftijd verandert, is wanneer de computer willekeurig een nieuwe tegel laat vallen (een 2 of een 4). Dit voegt 2 of 4 toe aan de Leeftijd.

De Analogie:
Stel je het spel niet voor als een doolhof, maar als een meerdere verdiepingen tellend gebouw.

Elke "verdieping" van het gebouw vertegenwoordigt een specifieke Leeftijd (bijvoorbeeld Verdieping 4, Verdieping 6, Verdieping 8...).
Je kunt vrij bewegen op dezelfde verdieping (tegels schuiven en samenvoegen) zonder omhoog of omlaag te gaan.
Je verplaatst je pas naar de volgende verdieping wanneer de computer een nieuwe tegel laat vallen.

Omdat het spel altijd vooruitgaat in Leeftijd (je gaat nooit terug naar een lagere som), konden de auteurs de bibliotheek verdieping voor verdieping behandelen. Ze hoefden niet de hele bibliotheek in hun hoofd te houden. Ze hoefden alleen de huidige verdieping, de volgende verdieping en die daarna in hun geheugen te houden. Zodra ze de beste zetten voor Verdieping 100 hadden berekend, konden ze de data voor Verdieping 98 weggooien om ruimte te maken voor Verdieping 102.

3. De Compressie: Een Walvis in een Rugzak Proppen

Zelfs met deze verdieping-voor-verdieping truc was de data nog steeds enorm. Als ze elke enkele speltoestand op papier hadden willen schrijven, zou dit ongeveer 4,4 Terabyte aan harde schijfruimte in beslag nemen (ongeveer de grootte van een enorm datacentrum).

Om dit op te lossen, gebruikten ze een slimme datacompressietechniek genaamd Elias-Fano-codering.

De Analogie: Stel je hebt een lijst met 1 miljard mensen, maar ze dragen allemaal rode shirts. In plaats van "Rood Shirt" naast elke enkele naam te schrijven (wat ruimte verspilt), schrijf je een speciale code die zegt: "Iedereen in deze lijst draagt rood."
Ze vonden een manier om de "ID-kaarten" van elke mogelijke speltoestand te comprimeren tot ongeveer 1,4 Terabyte. Als ze alleen om de beste zetten gaven (de ruwe data negerend), konden ze het zelfs nog verder verkleinen tot ongeveer 300 Gigabyte (de grootte van de harde schijf van een high-end laptop).

4. De Resultaten: Wat Leerden Ze?

Door het spel op te lossen, berekenden ze de perfecte verwachte score voor een speler die nooit een fout maakt.

De Score: Als je begint met de meest gebruikelijke opstelling (twee 2-en) en perfect speelt, kun je verwachten ongeveer 50.724 punten te scoren.
De "Slecht Geluk" Factor: Ze ontdekten dat beginnen met een 4-tegel in plaats van twee 2-en je eigenlijk een klein nadeel oplevert (ongeveer 4 punten lager). Het is alsof je een race begint met een zware rugzak; je moet harder werken om bij te komen.
De "2048" Bult: De grafiek van hun resultaten toonde "dalen" (dips in prestaties) telkens wanneer de Leeftijd een veelvoud van 2048 bereikte. Dit bevestigt een gevoel dat veel spelers hebben: het wordt ongelooflijk moeilijk om de 2048-tegel te maken omdat je ruimte tekort komt op je kleine 12-vakken bord. Je hebt een perfecte opstelling nodig om alle kleinere getallen (2, 4, 8... tot 1024) te passen voordat je ze kunt combineren.

Samenvatting

De auteurs namen een spel dat te complex leek om volledig op te lossen vanwege het enorme aantal mogelijkheden. Ze realiseerden zich dat het spel zich van nature organiseert op basis van de "som van getallen" (Leeftijd). Door het spel te behandelen als een reeks verdiepingen in plaats van een gigantisch verward web, en door een super-efficiënt archiefsysteem (compressie) te gebruiken, hebben ze de perfecte strategie voor elke mogelijke zet in kaart gebracht.

Ze bewezen dat je met een standaardcomputer en een paar dagen werk een spel wiskundig kunt beheersen dat meestal afhankelijk is van geluk en intuïtie.

Technische Samenvatting: Sterk Oplossen van 2048 op een 4×3 Bord

Probleemdefinitie

Dit artikel behandelt de "sterke oplossing" van een stochastische variant van een single-player spel: 2048 op een 4×3 bord (aangeduid als 2048 $^{4\times3}$ ). In tegenstelling tot de standaard 4×4-versie, maakt deze variant gebruik van een raster van 12 cellen. Het spel wordt gemodelleerd als een Markov-beslissingsproces (MDP) waarbij een agent acties (omhoog, omlaag, links, rechts) selecteert om aangrenzende tegels met gelijke waarde te samenvoegen. Na een geldige actie gaat de bordtoestand deterministisch over naar een "afterstate" (het verschuiven en samenvoegen van tegels). Vervolgens spawnt de omgeving stochastisch een nieuwe tegel (2 met 90% waarschijnlijkheid, 4 met 10%) in een willekeurige lege cel, waardoor de overgang naar de volgende toestand plaatsvindt.

Het doel is het berekenen van het optimale beleid $\pi^*$ en de optimale waardenfunctie $v^*(s)$ , die de verwachte cumulatieve beloning vertegenwoordigt vanuit elke bereikbare toestand $s$ . De primaire uitdaging ligt in de grootte van de toestandsruimte: de 4×3-variant bevat ongeveer $1,15 \times 10^9$ bereikbare toestanden en $7,4 \times 10^8$ afterstates. Deze schaal is ongeveer $10^4$ keer groter dan de eerder opgeloste 3×3-variant (Mini2048), waardoor rechtstreekse enumeratie en opslag op standaardhardware onuitvoerbaar is.

Methodologie

De auteurs stellen een oplossing voor gebaseerd op partitie van de toestandsruimte op basis van "leeftijd" en compacte datavoorstelling.

1. Leeftijdsgedreven Partitie

De kerninnovatie is het definiëren van de leeftijd van een toestand als de som van alle tegelnummers op het bord ( $age(s) = \sum c_i$ ).

Invariantie: De leeftijd blijft constant tussen een toestand en zijn directe afterstate na een geldige actie (aangezien het samenvoegen van tegels de som van waarden behoudt en het verschuiven de waarden niet verandert).
Progressie: De leeftijd neemt toe met 2 of 4 tijdens de stochastische overgang (het spawnen van een nieuwe tegel).
Algoritmische Implicatie: Deze eigenschap maakt het mogelijk de toestandsruimte te partitioneren in disjuncte subsets op basis van leeftijd.
- Forward Pass (Enumeratie): Geldige toestanden van leeftijd $n$ kunnen uitsluitend worden gegenereerd vanuit afterstates van leeftijden $n-2$ en $n-4$ . Het algoritme iteratieert door toenemende leeftijden, waarbij slechts drie sets in het geheugen worden bijgehouden (huidige leeftijd, leeftijd+2, leeftijd+4) om alle bereikbare toestanden en afterstates te enumereren.
- Backward Pass (Waardeberekening): Optimale waarden worden berekend door achterwaarts te itereren van de maximale leeftijd naar de initiële leeftijd. De waarde van een toestand is de maximale waarde van zijn bereikbare afterstates; de waarde van een afterstate is de verwachte waarde van zijn bereikbare volgende toestanden (gewogen naar spawn-waarschijnlijkheden).

2. Compacte Representatie

Om te voldoen aan de opslagvereisten (geschat op ~4,4 TiB voor ruwe 48-bits ID's), maken de auteurs gebruik van Elias-Fano-codes voor het opslaan van sets unieke toestands-ID's.

Structuur: Gesorteerde unieke ID's worden opgesplitst in hogere bits ( $h_i$ ) en lagere bits ( $l_i$ ). De lagere bits worden opgeslagen in een aaneengesloten bit-vector, terwijl de hogere bits worden gecodeerd in een spaarzaam bit-vector $H$ met behulp van rank-operaties.
Optimalisaties:
- Symmetrie-reductie: ID's worden genormaliseerd naar de minimale waarde onder horizontale, verticale en 180-graden rotatiesymmetrie.
- Basisaanpassing: De coderingsbasis wordt aangepast op basis van de maximale tegelwaarde voor een specifieke leeftijd.
- Celverwijdering: Informatie van één cel wordt weggelaten tijdens het coderen omdat de som (leeftijd) de totale waarde beperkt, wat volledige reconstructie later mogelijk maakt.
Efficiëntie: Dit vermindert de opslag voor alle afterstate-ID's van ~4,4 TiB tot ongeveer 1,4 TiB terwijl efficiënte opzoekmogelijkheden behouden blijven. Voor specifiek optimaal spel reduceert een gespecialiseerde representatie (met gebruik van het BuRR-algoritme) de vereiste opslag tot onder de 300 GiB.

Belangrijkste Resultaten

Statistieken van de Toestandsruimte: Het totale aantal bereikbare toestanden is 1.152.817.492.752 en het aantal afterstates is 739.648.886.170.
Optimale Verwachte Score: Voor de meest voorkomende initiële toestanden (twee tegels met waarde 2) is de verwachte score onder een optimale strategie ongeveer 50.724,26.
- Initiële toestanden met een 4-tegel (leeftijd 6) leveren een iets lagere verwachte score op (~50.720,62).
- Initiële toestanden met twee 4-tegels (leeftijd 8) leveren de laagste op (~50.708,99), wat wijst op een klein nadeel van starten met hogere-waarde tegels.
Toestandsverdeling: Het aantal toestanden per leeftijd is over het algemeen beheersbaar (minder dan $3 \times 10^6$ per leeftijd), waardoor het algoritme meerdere leeftijdslagen in het geheugen kan houden.
Terminale Toestanden: "Dalen" in de verdeling van het aantal toestanden treden op bij leeftijden die veelvouden zijn van 2048, wat de moeilijkheid weerspiegelt om grote tegels te vormen met beperkte bordruimte. Bepaalde leeftijden (bijvoorbeeld 8190, 12286) hebben geen geldige afterstates omdat het vormen van die sommen meer tegels zou vereisen dan de beschikbare 12 cellen toelaten.
Actiegevoeligheid: Het verschil in waarde tussen optimale en suboptimale acties piekt rond leeftijden 2048 en 4096, wat suggereert dat vroege beslissingen direct na het vormen van grote tegels cruciaal zijn.

Betekenis en Claims

Het artikel claimt de 2048 $^{4\times3}$ -variant sterk opgelost te hebben, een taak die eerder als onuitvoerbaar werd beschouwd vanwege de grootte van de toestandsruimte. De betekenis van dit werk ligt in:

Schaalbaarheid: Aantonen dat een spel met meer dan $10^9$ toestanden op een persoonlijke computer binnen enkele dagen kan worden opgelost door gebruik te maken van spel-specifieke structurele eigenschappen (leeftijd) in plaats van brute-force methoden.
Methodologische Bijdrage: De introductie van de "leeftijd"-partitietechniek maakt enumeratie en waardeberekening mogelijk voor stochastische MDP's waarbij toestandswaarden afhankelijk zijn van verwachtingen, waardoor de noodzaak van $\alpha\beta$ -pruning (wat inefficiënt is in stochastische omgevingen) effectief wordt omzeild.
Beschikbaarheid van Data: De auteurs bieden de optimale waardenfunctie en een compacte representatie van de toestandsruimte, die dienen als baseline voor toekomstig onderzoek naar reinforcement learning en spelanalyse.
Opslag-efficiëntie: De succesvolle toepassing van Elias-Fano-codes om een enorme set speltoestanden te comprimeren tot ~1,4 TiB maakt de dataset toegankelijk voor onderzoekers met gemiddelde rekenmiddelen (bijvoorbeeld 4 TiB SSD's).

De auteurs merken op dat hoewel het primaire doel het oplossen van het spel was, het resulterende dataset en het concept van "leeftijd" kunnen dienen als fundament voor verdere studies in stochastische spellen en evaluatie van reinforcement learning.