Twee samenvoegspellen, één vraag: kan een van beide foutloos gespeeld worden? Het antwoord loopt via de hoek van een bord, een tegenstander die nooit komt opdagen en een getal van zeventien exponenten hoog.
In het Engels geschreven en geredigeerd. Deze Nederlandse versie is met machinevertaling gemaakt; waar precisie ertoe doet, is het Engelse origineel leidend. Lees het origineel in het Engels →
Begin bij het spel dat iedereen kent. 2048, vier richtingen, een 4×4-rooster, tegels die verdubbelen wanneer ze elkaar raken, is strikt genomen onopgelost. Niemand heeft een algoritme geschreven dat het perfect speelt. Wat we hebben, zijn zeer sterke benaderingen. Een expectimax-zoekalgoritme, dat een zet of acht vooruitkijkt en elk bord beoordeelt aan de hand van een handvol met de hand afgestelde heuristieken (open vakjes, grote tegels vastgepind aan een rand, gladheid), haalt de 32768-tegel in ruim een derde van zijn partijen, 1 en de sterkste openbare engine bereikt de 65536-tegel in een paar procent van de gevallen. 2 Veralgemeend naar een m×n-bord is alleen al beslissen of een doeltegel bereikbaar is NP-moeilijk. 3 Sterk is niet hetzelfde als opgelost.
Hoe hoog kan één tegel klimmen? Op zestien vakjes is het antwoord een klein, elegant stukje telwerk. Leg het bord uit als een aflopende trap: 65536, 32768, 16384, en zo verder omlaag tot één eenzame 2. Elke tegel ligt precies één macht van twee onder zijn buur, dus de zestien verschillende machten 21 tot en met 216 vullen het bord precies, en 65536 = 216 staat op de top: één exponent per vakje. Dat is het plafond als het spel je alleen maar 2’s geeft. Maar 2048 laat één keer op de tien een 4 verschijnen, en één goed getimede 4 smokkelt een zeventiende exponent naar binnen, waardoor het werkelijke maximum stijgt naar 131072 = 217: zeventien tegels aan machten, gepropt in zestien vakjes. 4 Geen mens heeft hem gebouwd; een paar AI’s zijn er rakelings langs gekomen.
Waarom belonen deze borden het wegstoppen van je grootste tegel in een hoek? Een tegel in het midden kan in vier richtingen worden geduwd, en raakt steeds weer gescheiden van de tegels waarmee hij wil trouwen. Een hoektegel raakt twee wanden; duwen in de richting van de wanden die hij al raakt kan hem niet verplaatsen, en zolang je niet van die wanden af duwt, blijft hij stilliggen terwijl al het andere zich om hem heen ordent. Rijg de rest aaneen tot een monotone slang, de hoogste in de hoek, heen en weer slingerend in aflopende volgorde, en één veeg kan een cascade van samenvoegingen in gang zetten. 1 Dit is de heuristiek die het spel van gewone menselijke spelers domineert, en het is vrijwel precies wat de AI’s herontdekken wanneer je ze hun eigen gewichten laat afstellen.
Een samenvoegspel met willekeurige nieuwe tegels heeft geen tegenstander, alleen weer. Het “oplossen” betekent de dobbelstenen gemiddeld verslaan, niet een geest verslaan.
Kantel het bord nu in drie dimensies. 3927 is de kubische neef van 2048: een 3×3×3-rooster van 27 vakjes, zes schuifrichtingen in plaats van vier, en tegels die per drie samensmelten, 3 tot 9 tot 27 tot 81, grondtal drie waar 2048 grondtal twee gebruikt. 5 Overleeft het stapelen in de hoek de extra dimensie? Een kubus heeft acht hoeken, en een hoekvakje raakt nu drie vlakken in plaats van twee; het zou dus nog stabieler moeten zijn, vastgepind door drie wanden tegelijk, al geven de zes richtingen het bord meer manieren om je structuur los te schudden. De slang wordt een gevouwen pad dat door alle drie de lagen loopt. Voor zover ik kan vinden, heeft niemand uitgezocht of de analogie werkelijk opgaat: redenering, geen meting.
En het plafond? De regel van één exponent per vakje zou 327 ≈ 7,6 biljoen als ruime bovengrens suggereren. Maar de analogie rafelt flink. De extra exponent van 2048 kwam van een gelukkige 4; 3927 laat alleen ooit de kleinste tegel verschijnen, een kale 3, dus er is geen bonus. Erger nog: een drievoudige samenvoeging vereist drie tegels op één lijn, en elke rij, kolom en pilaar in een 3×3×3-kubus is precies drie vakjes lang, dus elke samenvoeging verbruikt een hele lijn. Die beperking bijt veel harder dan wat dan ook in het platte spel en drukt het werkelijke maximum vrijwel zeker ver onder 327. Wat dat ware getal is, heb ik nergens berekend gevonden. (Duidelijk als zodanig aangeduide redenering; de mechanica hierboven is gemeten aan de ontwerpdocumenten van het spel.)
Hier zit de subtiliteit die “perfect spel” glibberig maakt. Een samenvoegspel met willekeurige nieuwe tegels is een stochastisch spel voor één speler, een patience tegen een dobbelsteen, geen duel. Niets kiest de slechtste nieuwe tegel uit om je te ruïneren; er is alleen de toevalsgenerator, onverschillig. Het juiste begrip van optimaal spel is dus expectimax: maximaliseer de verwachte uitkomst over de verdeling van nieuwe tegels. Het is nadrukkelijk niet minimax: minimax veronderstelt een tegenstander, en als je er daadwerkelijk een elke tegel laat plaatsen (“evil 2048”, kwaadaardige 2048), wordt het spel iets wreders dat je gedwongen kunt worden te verliezen. Omdat de dobbelstenen in principe elke reeks kunnen geven, bestaat een strategie die een bepaalde tegel garandeert misschien simpelweg niet. Het eerlijke antwoord op “bestaat er een perfecte strategie?” is dus dat je voor een stochastisch spel hooguit een strategie kunt definiëren die gemiddeld de beste is, en die exact berekenen is buiten bereik voor 2048 6 en een volledig open vraag voor 3927.