Hvad er den optimale algoritme til spillet 2048?
Indledning
2048 er en spændende flise-shifting spil, hvor vi flytte fliser rundt for at kombinere dem, sigter mod stadig større flise-værdier.
i denne tutorial skal vi undersøge en algoritme til at spille 2048, en der vil hjælpe med at bestemme de bedste træk at gøre ved hvert trin for at få den bedste score.
Sådan spiller du 2048
et spil på 2048 spilles på et 4 4 4 bord., Hver position på brættet kan være tom eller kan indeholde en flise, og hver flise vil have et nummer på den.
Når vi starter, vil bestyrelsen have to fliser i tilfældige steder, hver enten har en “2” eller “4” på det, der hver har en uafhængig 10% chance for at være en “4”, eller på anden måde en er en “2”.
bevægelser udføres ved at flytte alle fliser mod en kant – op, ned, venstre eller højre., Når du gør dette, vil alle fliser med den samme værdi, der støder op til hinanden og bevæger sig sammen, fusionere og ende med en ny flise svarende til summen af de tidligere to:
Når vi har foretaget et træk, placeres en ny flise på brættet. Dette er placeret i en tilfældig placering, og vil være en “2” eller en “4” på samme måde som de oprindelige fliser – “2” 90% af tiden og “4” 10% af tiden.
spillet fortsætter derefter, indtil der ikke er flere træk mulige.
generelt er målet med spillet at nå en enkelt flise med en værdi på “2048”., Spillet stopper dog ikke her, og vi kan fortsætte med at spille så langt som muligt, med henblik på den størst mulige flise. I teorien er dette en flise med værdien”131.072″.
Problemforklaring
løsning af dette spil er et interessant problem, fordi det har en tilfældig komponent. Det er umuligt at forudsige ikke kun, hvor hver ny flise vil blive placeret, men om det vil være en “2” eller en “4”.
som sådan er det umuligt at have en algoritme, der korrekt løser puslespillet hver gang., Det bedste, vi kan gøre, er at bestemme, hvad der sandsynligvis vil være det bedste træk på hvert trin og spille sandsynlighedsspillet.
på ethvert tidspunkt er der kun fire mulige træk, som vi kan gøre. Nogle gange har nogle af disse bevægelser ingen indflydelse på brættet og er derfor ikke værd at gøre – for eksempel i ovenstående bord vil et skridt på “ned” ikke have nogen indflydelse, da alle fliserne allerede er på bundkanten.
udfordringen er derefter at bestemme, hvilke af disse fire træk der vil være den, der har det bedste langsigtede resultat.,
Vores algoritme er baseret på den Expectimax algoritme, der er i sig selv en variation af Minimax-algoritmen, men hvor de mulige ruter gennem vores træ er vægtet med sandsynligheden for, at de vil ske.
vi er grundlæggende at behandle spillet som en to-player spil:
- Spiller En – den menneskelige spiller – kan flytte bord i en af de fire retninger
- Spiller To – computeren spilleren kan placere en brik i en tom placering på bord
Baseret på dette, kan vi generere et træ af resultater fra hver flytte, vægtet med sandsynligheden for, at hver bevægelse sker., Dette kan så give os de detaljer, der er nødvendige for at bestemme, hvilken menneskelig bevægelse der sandsynligvis vil give det bedste resultat.
3.1. Flowchart af Gameplay
Det generelle forløb af, hvordan gameplayet fungerer det:
Vi umiddelbart kan se det tilfældige aspekt af spillet i “Tilføj Tilfældige Flise” proces – både i det faktum, at vi finder en tilfældig pladsen for at tilføje fliser til, og vi er valg af en tilfældig værdi for fliser.
vores udfordring er derefter at beslutte, hvad de skal gøre i trinnet “Bestem næste træk”. Dette er vores algoritme til at spille spillet.,
det generelle overløb af dette virker bedragerisk simpelt:
alt, hvad vi skal gøre, er at simulere hvert af de mulige træk, bestemme, hvilken der giver det bedste resultat, og brug det derefter.
så vi har nu reduceret vores algoritme til at simulere et givet træk og generere en vis score for resultatet.
Dette er en todelt proces. Det første pass er at se, om flytningen endda er mulig, og hvis ikke, så aborter tidligt med en score på “0”., Hvis flytningen er mulig, går vi videre til den rigtige algoritme, hvor vi bestemmer, hvor godt et træk dette er:
3.2. Bestemmelse af det næste træk
den vigtigste del af vores algoritme hidtil er at simulere et træk, og den vigtigste del af det er, hvordan vi genererer en score for hvert muligt træk. Det er her vores e .pectima.algoritme kommer ind.
vi simulerer alle mulige træk fra begge spillere i flere trin, og se, hvilken af dem der giver det bedste resultat. For den menneskelige spiller betyder dette, at hver af” op”,” ned”,” venstre “og” højre ” bevæger sig.,
For computer-spiller, det betyder, at placere både et “2” eller “4” fliser i alle mulige tom placering:
Denne algoritmen er rekursiv, med hvert rekursive skridt stopper kun, hvis det er en bestemt dybde fra det faktiske træk i det rigtige spil.,ulating en score for øjeblikket simuleret bord layout
- Simulere alle mulige menneskelige træk
- For hver af disse
- Recurse tilbage i den algoritme
- Returnere score beregnes ud fra denne menneskelige træk
- Tilføj score beregnes ud fra denne computer flytte, vægtet med en sandsynlighed for, at denne bevægelse sker
Når vi er færdige med dette, vil vi tilføje op alle de beregnede scores, og dette er det endelige resultat for vi ønsker at gøre fra den aktuelle spil bord., Fordi vi gør dette fire gange – en for hver mulig bevægelse fra det nuværende spilbræt-ender vi med fire scoringer, og den højeste af dem er flytningen at gøre.
3.3. Scoring af en Bestyrelsesposition
På dette tidspunkt er det eneste, der er tilbage at gøre, at beregne en score for et bræt. Dette er ikke den samme score som spillet bruger, men det skal tage højde for, hvor god en position Dette er at fortsætte med at spille fra.
Der er mange måder, hvorpå dette kan opnås ved at tilføje flere faktorer sammen med passende vægtninger., For eksempel:
- Antallet af tomme steder
- Antallet af mulige smelter sammen – dvs, antal gange samme nummer i to tilstødende steder
- Den største værdi i enhver placering
- Sum af alle steder
- Monotonicity af bestyrelsen – dette er, hvor godt bord er struktureret, sådan at placeringen værdier stigning i en enkelt retning.
pseudokode
nu hvor vi ved, hvordan algoritmen skal fungere, hvordan ser det ud? Lad os undersøge nogle pseudokoder, der beskriver algoritmen mere detaljeret.,
Vi er ikke interesseret i den faktiske afspilning af spil, bare i en algoritme til at afgøre bevæger sig, så lad os starte der:
Som før, dette får os til det punkt, hvor vi simulerer hver af de mulige træk fra start bestyrelsen og returnere den ene, der scorer bedst. Dette efterlader os med at skulle generere scoringer for de nyligt simulerede brædder.
Vi har tilføjet en dybdegrænse, så vi kan stoppe behandlingen efter et stykke tid., Fordi vi arbejder med en rekursiv algoritme, vi har brug for en måde at stoppe det, da det ellers vil kunne køre for evigt:
Dette giver os vores rekursion, der simulerer ud alle mulige menneskelige og computer flytte til en række trin, og beslutter, hvilke menneskelige træk give det bedst mulige resultat.
det eneste, der er tilbage, er at udarbejde en endelig score for en given bestyrelsesposition. Der er ingen perfekt algoritme til dette, og forskellige faktorer vil give forskellige resultater.,
Performance optimi .ation
indtil videre har vi en algoritme, der vil forsøge at løse spillet, men det er ikke så effektivt som det kunne være. På grund af den tilfældige karakter af spillet, er det umuligt at have en perfekt optimeret solver – der vil altid være en vis grad af gentagelse simpelthen på grund af arten af processen.
Vi kan i det mindste gøre vores bedste for at reducere arbejde, som vi ikke behøver at gøre selv.,
Vi laver allerede en smule optimering i ovenstående algoritme ved ikke at behandle bevægelser, der ikke har nogen indflydelse på spillet. Der er dog andre måder, hvorpå vi kan reducere arbejdet, såsom at spore den kumulative sandsynlighed for bevægelser og stoppe, når det bliver for lavt. Dette har risikoen for at fjerne den perfekte løsning, men hvis sandsynligheden er så lav, så vil det næsten helt sikkert ikke ske alligevel.
Vi kan også dynamisk bestemme dybdegrænsen for at arbejde med., Vores ovennævnte pseudokode har en hårdkodet grænse på 3, men vi kunne dynamisk beregne dette baseret på formen på brættet i starten af vores beregninger – for eksempel indstille det til antallet af tomme firkanter eller antallet af forskellige fliser på brættet. Dette ville betyde, at vi krydser færre bevægelser fra tavler, der har mindre plads til ekspansion.fordi det er muligt at revidere de samme bestyrelsespositioner flere gange, kan vi huske disse og cache scoren for disse positioner i stedet for at beregne dem hver gang., Potentielt kan vi generere alle mulige bord position forud for tid, men der er et stort antal af disse – 281,474,976,710,656 forskellige mulige bestyrelsesposter ved hjælp af fliser op til 2048 – så det er nok ikke muligt.
den vigtigste optimering, vi kan gøre, er imidlertid at justere algoritmen til generering af board score. Dette fungerer til at beslutte, hvor godt bord er for at fortsætte med at spille, og de faktorer og vægtninger, vi bruger til dette, er direkte knyttet til, hvor godt vores algoritme spiller ud.,
konklusion
2048 er et enormt interessant spil at forsøge at løse. Der er ingen perfekt måde at løse det på, men vi kan skrive heuristik, der vil søge efter de bedst mulige ruter gennem spillet.
de samme generelle principper fungerer for ethvert to-spiller spil – for eksempel skak – hvor du ikke kan forudsige, hvad den anden spiller vil gøre med nogen grad af sikkerhed.
hvorfor ikke prøve at skrive en implementering af dette og se, hvor godt det fungerer?