Vad är den optimala algoritmen för spelet 2048?
introduktion
2048 är ett spännande kakel-skiftande spel, där vi flyttar plattor runt för att kombinera dem, som syftar till allt större kakel värden.
i den här handledningen kommer vi att undersöka en algoritm för att spela 2048, en som hjälper till att bestämma de bästa rörelserna för att göra vid varje steg för att få den bästa poängen.
hur man spelar 2048
ett spel på 2048 spelas på ett 4×4-bräde., Varje position på brädet kan vara tom eller kan innehålla en kakel, och varje kakel kommer att ha ett nummer på den.
När vi börjar kommer brädet att ha två plattor på slumpmässiga platser, som var och en antingen har en ”2” eller en ”4” på den – var och en har en oberoende 10% chans att vara en ”4”, eller annars är en ”2”.
rörelser utförs genom att flytta alla brickor mot en kant – upp, ner, vänster eller höger., När du gör detta kommer alla brickor med samma värde som ligger intill varandra och rör sig tillsammans att sammanfoga och sluta med en ny kakel som motsvarar summan av de tidigare två:
När vi har gjort ett drag kommer en ny kakel att placeras på brädet. Detta placeras i en slumpmässig plats, och kommer att vara en ”2” eller en ”4” på samma sätt som de ursprungliga plattorna – ”2” 90% av tiden och ”4” 10% av tiden.
spelet fortsätter sedan tills det inte finns några fler drag möjliga.
i allmänhet är målet med spelet att nå en enda kakel med ett värde av ”2048”., Spelet slutar dock inte här, och vi kan fortsätta spela så långt det är möjligt att gå och sikta på största möjliga kakel. I teorin är detta en kakel med värdet ”131,072”.
Problemförklaring
att lösa detta spel är ett intressant problem eftersom det har en slumpmässig komponent. Det är omöjligt att korrekt förutsäga inte bara var varje ny kakel kommer att placeras, men om det kommer att bli en ”2”eller en ”4”.
som sådan är det omöjligt att ha en algoritm som korrekt löser pusslet varje gång., Det bästa vi kan göra är att bestämma vad som sannolikt kommer att vara det bästa draget i varje steg och spela sannolikhetsspelet.
när som helst finns det bara fyra möjliga drag som vi kan göra. Ibland har några av dessa rörelser ingen inverkan på brädet och är därför inte värt att göra – till exempel i ovanstående styrelse ett drag av ”ner” kommer inte att ha någon inverkan eftersom alla brickor är redan på den nedre kanten.
utmaningen är då att bestämma vilken av dessa fyra drag som kommer att vara den som har det bästa långsiktiga resultatet.,
vår algoritm är baserad på Expectimax-algoritmen, som i sig är en variant av Minimax-algoritmen, men där de möjliga vägarna genom vårt träd viktas av sannolikheten att de kommer att hända.
i huvudsak behandlar vi spelet som ett tvåspelarspel:
- spelare ett-den mänskliga spelaren – kan flytta brädet i en av fyra riktningar
- spelare två – datorspelaren – kan placera en kakel på en tom plats på brädet
baserat på detta kan vi generera ett träd av resultat från varje drag, viktat av sannolikheten för att varje rörelse händer., Detta kan sedan ge oss de uppgifter som behövs för att avgöra vilken mänsklig rörelse som sannolikt kommer att ge det bästa resultatet.
3.1. Flowchart av Gameplay
det allmänna flödet av hur spelet fungerar:
Vi kan omedelbart se den slumpmässiga aspekten av spelet i ”Lägg till slump kakel” – processen-både i det faktum att vi hittar en slumpmässig ruta för att lägga till kakel till, och vi väljer ett slumpmässigt värde för plattan.
vår utmaning är då att bestämma vad du ska göra i ”Bestäm nästa steg” – steget. Detta är vår algoritm för att spela spelet.,
det allmänna överflödet av detta verkar bedrägligt enkelt:
allt vi behöver göra är att simulera var och en av de möjliga rörelserna, bestämma vilken som ger det bästa resultatet och använd sedan det.
Så vi har nu minskat vår algoritm för att simulera ett visst drag och generera några poäng för resultatet.
detta är en tvådelad process. Det första passet är att se om flytten är ens möjlig, och om inte, Avbryt sedan tidigt med en poäng på ”0”., Om flytten är möjlig går vi vidare till den verkliga algoritmen där vi bestämmer hur bra ett drag är:
3.2. Att bestämma nästa drag
den viktigaste delen av vår algoritm hittills är att simulera ett drag, och den viktigaste delen av det är hur vi genererar en poäng för varje möjligt drag. Det är här vår Expectimax algoritm kommer in.
vi simulerar alla möjliga drag från båda spelarna för flera steg och ser vilka av dem som ger det bästa resultatet. För den mänskliga spelaren betyder detta var och en av” upp”,” ner”,” vänster ”och” höger ” rör sig.,
för datorspelaren betyder det att du placerar både en” 2 ”eller en” 4 ” – bricka på alla möjliga tomma platser:
den här algoritmen är rekursiv, med varje rekursivt steg som bara stannar om det är ett visst djup från det faktiska draget i det verkliga spelet.,för var och en av dessa
- simulera alla möjliga mänskliga drag
- för var och en av dessa
- simulera alla möjliga mänskliga drag
- för var och en av dessa
- Recurse tillbaka till algoritmen
- returnera poängen beräknas från detta mänskliga drag
- Lägg till poängen beräknas från den här datorn flytta, viktad av en sannolikhet för detta drag händer
>
När vi har avslutat detta lägger vi sedan upp alla beräknade poäng, och det här är slutresultatet för det drag vi vill göra från det aktuella spelbrädet., Eftersom vi gör detta fyra gånger-en för varje möjligt drag från den nuvarande spelplanen – slutar vi med fyra poäng, och den högsta av dem är flytten att göra.
3.3. Poäng en styrelseposition
vid denna tidpunkt är det enda som återstår att göra att beräkna en poäng för ett bräde. Detta är inte samma poäng som spelet använder, men det måste ta hänsyn till hur bra en position Detta är att fortsätta spela från.
det finns ett stort antal sätt att detta kan uppnås genom att lägga till flera faktorer tillsammans med lämpliga viktningar., Till exempel:
- antal tomma platser
- antal möjliga sammanslagningar – dvs antal gånger samma nummer är i två intilliggande platser
- det största värdet på vilken plats som helst
- summan av alla platser
- monotonicitet i styrelsen-det här är hur bra styrelsen är strukturerad, så att platsvärdena ökar i en enda riktning.
Pseudocode
Nu när vi vet hur algoritmen kommer att fungera, hur ser det ut? Låt oss utforska lite pseudokod som beskriver algoritmen mer detaljerat.,
Vi är inte intresserade av den faktiska spelningen av spelet, bara i algoritmen för att bestämma drag, så kan vi börja där:
som tidigare får det oss till den punkt där vi simulerar var och en av de möjliga rörelserna från startkortet och returnerar den som gör bäst. Detta lämnar oss med att behöva generera poäng för de nyligen simulerade styrelser.
Vi har lagt till en djupgräns så att vi kan stoppa bearbetningen efter ett tag., Eftersom vi arbetar med en rekursiv algoritm behöver vi ett sätt att stoppa det annars kommer det potentiellt att köras för alltid:
detta ger oss vår rekursion, simulerar alla möjliga mänskliga och datorrörelser för ett visst antal steg och bestämmer vilka mänskliga rörelser som ger bästa möjliga resultat.
det enda som återstår är att utarbeta en slutpoäng för en given styrelseposition. Det finns ingen perfekt algoritm för detta, och olika faktorer kommer att ge olika resultat.,
prestandaoptimering
hittills har vi en algoritm som kommer att försöka lösa spelet, men det är inte så effektivt som det kan vara. På grund av spelets slumpmässiga karaktär är det omöjligt att ha en perfekt optimerad lösare – det kommer alltid att bli någon repetitionsnivå helt enkelt på grund av processens natur.
Vi kan åtminstone göra vårt bästa för att minska det arbete som vi inte behöver göra.,
vi gör redan lite optimering i ovanstående algoritm genom att inte bearbeta några rörelser som inte har någon inverkan på spelet. Det finns andra sätt att vi kan minska arbetet att göra, men som att spåra den kumulativa sannolikheten för rörelser och stoppa när det blir för lågt. Detta har risken att ta bort den perfekta lösningen, men om sannolikheten är så låg, så kommer det nästan säkert inte att hända ändå.
Vi kan också dynamiskt bestämma djupgränsen att arbeta med., Vår ovanstående pseudokod har en hårdkodad gräns på 3, men vi kan dynamiskt beräkna detta baserat på styrelsens form i början av våra beräkningar – till exempel ställa in det på antalet tomma rutor eller antalet distinkta plattor på brädet. Detta skulle innebära att vi korsar färre drag från brädor som har mindre utrymme för expansion.
Dessutom, eftersom det är möjligt att återkomma till samma styrelsepositioner flera gånger, kan vi komma ihåg dessa och cache poängen för dessa positioner istället för att omberäkna dem varje gång., Potentiellt kan vi generera alla möjliga styrelseposition i förväg, men det finns ett stort antal av dessa-281,474,976,710,656 olika möjliga styrelsepositioner med kakel upp till 2048 – så det här är förmodligen inte möjligt.
den viktigaste optimeringen vi kan göra är dock att justera algoritmen för att generera styrelsepoäng. Detta fungerar för att bestämma hur bra styrelsen är för att fortsätta att spela och de faktorer och viktningar som vi använder för detta är direkt kopplade till hur väl vår algoritm spelar ut.,
slutsats
2048 är ett enormt intressant spel att försöka lösa. Det finns inget perfekt sätt att lösa det, men vi kan skriva heuristik som kommer att söka efter bästa möjliga vägar genom spelet.
samma allmänna principer fungerar för alla tvåspelarspel-till exempel schack – där du inte kan förutsäga vad den andra spelaren kommer att göra med någon grad av säkerhet.
varför inte försöka skriva en implementering av detta och se hur bra det fungerar?