Wat is het optimale algoritme voor het spel 2048?
Inleiding
2048 is een spannend spel waarbij we tegels verplaatsen om ze te combineren, met als doel steeds grotere tegelwaarden.
in deze tutorial gaan we een algoritme onderzoeken om 2048 te spelen, een algoritme dat zal helpen bij het bepalen van de beste zetten om bij elke stap de beste score te krijgen.
hoe te spelen 2048
een spel van 2048 wordt gespeeld op een 4×4 bord., Elke positie op het bord kan leeg zijn of kan een tegel bevatten, en elke tegel zal een nummer op hebben.
wanneer we beginnen, zal het bord twee tiles hebben op willekeurige locaties, die elk een ” 2 “of een” 4 “hebben – elk heeft een onafhankelijke 10% kans om een” 4 “te zijn, of anders is a een”2”.
bewegingen worden uitgevoerd door alle tiles naar één kant te verschuiven – omhoog, omlaag, links of rechts., Als u dit doet, zullen alle tiles met dezelfde waarde die naast elkaar liggen en samen bewegen, samenvoegen en eindigen met een nieuwe tile gelijk aan de som van de vorige twee:
nadat we een zet hebben gedaan, zal een nieuwe tile op het bord worden geplaatst. Dit wordt geplaatst in een willekeurige locatie, en zal een ” 2 “of een” 4 “op dezelfde manier als de eerste tegels –” 2 “90% van de tijd en” 4 ” 10% van de tijd.
het spel gaat dan verder totdat er geen zetten meer mogelijk zijn.
in het algemeen is het doel van het spel om een enkele tegel te bereiken met een waarde van “2048”., Echter, het spel stopt hier niet, en we kunnen blijven spelen zo ver als het mogelijk is om te gaan, gericht op de grootst mogelijke tegel. In theorie is dit een tegel met de waarde “131,072”.
probleem uitleg
het oplossen van dit spel is een interessant probleem omdat het een willekeurige component heeft. Het is onmogelijk om niet alleen correct te voorspellen waar elke nieuwe tegel zal worden geplaatst, maar of het een “2” of een “4”zal zijn.
als zodanig is het onmogelijk om een algoritme te hebben dat de puzzel elke keer correct oplost., Het beste dat we kunnen doen is bepalen wat waarschijnlijk de beste zet is in elke fase en speel het waarschijnlijkheidsspel.
op elk moment zijn er maar vier mogelijke zetten die we kunnen maken. Soms, sommige van deze bewegingen hebben geen invloed op het bord en zijn dus niet de moeite waard om te maken – bijvoorbeeld, in het bovenstaande bord een beweging van “omlaag” zal geen invloed hebben, omdat alle tegels zijn al op de onderste rand.
de uitdaging is dan om te bepalen welke van deze vier zetten het beste resultaat op lange termijn zal hebben.,
ons algoritme is gebaseerd op het Expectimax algoritme, dat zelf een variatie is op het Minimax algoritme, maar waarbij de mogelijke routes door onze boom worden gewogen door de waarschijnlijkheid dat ze zullen gebeuren.
in wezen behandelen we het spel als een spel met twee spelers:
- speler één-de menselijke speler – kan het bord in een van de vier richtingen verschuiven
- speler twee – de computerspeler-kan een tegel op een lege locatie op het bord plaatsen
Op basis hiervan kunnen we een tree van resultaten genereren van elke zet, gewogen naar de waarschijnlijkheid dat elke zet plaatsvindt., Dit kan ons dan de details geven die nodig zijn om te bepalen welke menselijke beweging waarschijnlijk het beste resultaat zal geven.
3.1. Stroomschema van de Gameplay
de algemene stroom van hoe de gameplay werkt:
We kunnen direct het random aspect van het spel zien in het “add Random Tile” proces – zowel in het feit dat we een willekeurig vierkant vinden om de tile aan toe te voegen, en we selecteren een willekeurige waarde voor de tile.
onze uitdaging is dan om te beslissen wat te doen in de” Bepaal de volgende zet ” stap. Dit is ons algoritme om het spel te spelen.,
de Algemene overloop hiervan lijkt bedrieglijk eenvoudig:
het enige wat we hoeven te doen is elk van de mogelijke zetten te simuleren, te bepalen welke het beste resultaat geeft, en dat dan te gebruiken.
dus we hebben ons algoritme nu gereduceerd tot het simuleren van een bepaalde beweging en het genereren van een score voor de uitkomst.
Dit is een tweedelig proces. De eerste pas is om te zien of de zet zelfs mogelijk is, en zo niet, dan afbreken vroeg met een score van “0”., Als de zet mogelijk is, dan gaan we verder met het echte algoritme waar we bepalen hoe goed een zet is:
3.2. Bepalen van de volgende zet
het belangrijkste deel van ons algoritme tot nu toe is het simuleren van een zet, en het belangrijkste deel daarvan is hoe we een score genereren voor elke mogelijke zet. Dit is waar ons Expectimax algoritme van pas komt.
we simuleren elke mogelijke zet van beide spelers voor meerdere stappen, en zien welke van deze geeft de beste uitkomst. Voor de menselijke speler betekent dit elk van de bewegingen” omhoog”, “omlaag”, “links” en “rechts”.,
voor de computerspeler betekent dit het plaatsen van zowel een “2” als een “4” tile op elke mogelijke lege locatie:
dit algoritme is recursief, waarbij elke recursieve stap alleen stopt als het een bepaalde diepte is van de werkelijke zet in het echte spel.,ulating een score voor de huidige gesimuleerde board layout
- het Simuleren van alle mogelijke menselijke verplaatsen
- Voor elk van deze
- Recurse terug in het algoritme
- de Terugkeer van de score berekend op basis van deze menselijke verplaatsen
- Voeg de score berekend op basis van deze computer verplaatsen, gewogen met een waarschijnlijkheid van dit verplaatsen gebeurt
Wanneer we klaar zijn met deze, die we vervolgens optellen van alle scores berekend, en dit is de uiteindelijke score voor de actie die we willen maken van het huidige spel van bestuur., Omdat we dit vier keer doen-één voor elke mogelijke zet van het huidige spelbord – eindigen we met vier scores, en de hoogste daarvan is de zet die je moet maken.
3.3. Het scoren van een Board positie
Op dit punt is het enige wat nog te doen is het berekenen van een score voor een board. Dit is niet dezelfde score als het spel gebruikt, maar het moet rekening houden met hoe goed een positie is om te blijven spelen vanaf.
dit kan op een groot aantal manieren worden bereikt door verschillende factoren en passende wegingen toe te voegen., Bijvoorbeeld:
- aantal lege locaties
- aantal mogelijke samenvoegingen-d.w.z. Het Aantal keer dat hetzelfde aantal op twee aangrenzende locaties is
- de grootste waarde op elke locatie
- som van alle locaties
- monotoniciteit van het bord – dit is hoe goed het bord gestructureerd is, zodat de locatiewaarden in één richting toenemen.
Pseudocode
nu we weten hoe het algoritme zal werken, hoe ziet dit eruit? Laten we een pseudocode onderzoeken die het algoritme in meer detail beschrijft.,
we zijn niet geïnteresseerd in het eigenlijke spelen van het spel, alleen in het algoritme voor het bepalen van zetten, dus laten we daar beginnen:
zoals eerder, dit brengt ons op het punt waar we elk van de mogelijke zetten van het startbord simuleren en degene teruggeven die het beste scoort. Dit laat ons met de noodzaak om scores te genereren voor de nieuw gesimuleerde boards.
we hebben een dieptelimiet toegevoegd zodat we de verwerking Na een tijdje kunnen stoppen., Omdat we met een recursief algoritme werken, hebben we een manier nodig om het te stoppen, anders zal het mogelijk voor altijd draaien:
Dit geeft ons onze recursie, het simuleren van elke mogelijke menselijke en computer beweging voor een bepaald aantal stappen en beslissen welke menselijke bewegingen het best mogelijke resultaat geven.
het enige wat overblijft is om een eindscore uit te werken voor een bepaalde board positie. Er is geen perfect algoritme hiervoor, en verschillende factoren zullen verschillende resultaten geven.,
Performance Optimization
tot nu toe hebben we een algoritme dat zal proberen om het spel op te lossen, maar het is niet zo efficiënt als het zou kunnen zijn. Vanwege de willekeurige aard van het spel, het is onmogelijk om een perfect geoptimaliseerde oplosser – er is altijd gaat om een niveau van herhaling gewoon vanwege de aard van het proces.
we kunnen op zijn minst ons best doen om werk te verminderen dat we niet hoeven te doen.,
We zijn al bezig met een beetje optimalisatie in het bovenstaande algoritme door geen bewegingen te verwerken die geen impact hebben op het spel. Er zijn echter andere manieren waarop we het werk kunnen verminderen, zoals het bijhouden van de cumulatieve waarschijnlijkheid van bewegingen, en stoppen wanneer dat te laag wordt. Dit heeft wel het risico van het verwijderen van de perfecte oplossing, maar als de kans is dat laag, dan zal het bijna zeker niet gebeuren hoe dan ook.
We kunnen ook dynamisch de dieptelimiet bepalen om mee te werken., Onze bovenstaande pseudocode heeft een hardgecodeerde limiet van 3, maar we kunnen dit dynamisch berekenen op basis van de vorm van het bord aan het begin van onze berekeningen – Bijvoorbeeld door het aantal lege vierkanten of het aantal verschillende tegels op het bord te zetten. Dit zou betekenen dat we minder zetten doorlopen van planken die minder ruimte hebben voor uitbreiding.
bovendien, omdat het mogelijk is om dezelfde boardposities meerdere keren opnieuw te bezoeken, kunnen we deze onthouden en de score voor die posities cachen in plaats van ze elke keer opnieuw te berekenen., Mogelijk kunnen we elke mogelijke positie van het bord van tevoren genereren, maar er zijn een groot aantal van deze – 281.474.976.710.656 verschillende mogelijke posities van het bord met behulp van tegels tot 2048-dus dit is waarschijnlijk niet haalbaar.
echter, de belangrijkste optimalisatie die we kunnen doen is het aanpassen van het algoritme voor het genereren van board scores. Dit werkt om te beslissen hoe goed board is om te blijven Spelen en de factoren en wegingen die we gebruiken voor dit zijn direct gekoppeld aan hoe goed ons algoritme speelt.,
conclusie
2048 is een enorm interessant spel om op te lossen. Er is geen perfecte manier om het op te lossen, maar we kunnen heuristiek schrijven die zal zoeken naar de best mogelijke routes door het spel.
dezelfde algemene principes werken voor elk twee-speler spel – bijvoorbeeld, Schaken-waar je niet kunt voorspellen wat de andere speler zal doen met enige mate van zekerheid.
waarom niet proberen een implementatie van dit te schrijven en zien hoe goed het werkt?