Hva er den Optimale Algoritmen for Spillet 2048?
Innledning
2048 er en spennende flis-skiftende spill, hvor vi flytte fliser rundt for å kombinere dem, mål for stadig større fliser verdier.
I denne opplæringen, vi kommer til å undersøke en algoritme for å spille 2048, en som vil hjelpe deg med å bestemme det beste trekk å gjøre på hvert trinn for å få den beste poengsummen.
Hvordan Spille 2048
Et spill på 2048 spilles på en 4×4 brett., Hver posisjon på brettet kan være tom eller inneholde en flis, og hver brikke har et tall på det.
Når vi begynner, vil styret har to fliser på tilfeldige steder, som hver har enten en «2» eller «4» på den – hver har en selvstendig 10% sjanse for å være en «4», eller på annen måte en er en «2».
Beveger seg utføres ved å flytte alle brikkene mot en kant – opp, ned, til venstre eller høyre., Når du gjør dette, vil eventuelle fliser med samme verdi som er ved siden av hverandre og går sammen vil slå sammen og ender opp med en ny rute som er lik summen av de tidligere to:
Etter at vi har gjort et trekk, en ny rute vil bli plassert på brettet. Denne er plassert i et tilfeldig sted, og vil være en «2» eller «4» på samme måte som den første fliser – «2» 90% av tiden, og «4» 10% av tiden.
spillet fortsetter til det ikke er flere trekk som mulig.
I den generelle målet med spillet er å nå en enkelt flis med en verdi på «2048»., Men spillet stopper ikke her, og vi kan fortsette å spille i så langt som det er mulig å gå, mål for den største mulige flis. I teorien, dette er en flis med verdien «131,072».
Problemet Forklaring
Løse dette spillet er et interessant problem fordi den har en tilfeldig komponent. Det er umulig å tippe ikke bare hvor hver nye fliser vil bli plassert, men om det vil være en «2» eller «4».
Som sådan, det er umulig å ha en algoritme som vil riktig løse puslespill hver gang., Det beste vi kan gjøre er å bestemme hva som er sannsynlig å være den beste flytte på hvert trinn og spille sannsynlighet spillet.
Når som helst, det er bare fire mulige trekk som vi kan gjøre. Noen ganger, noen av disse trekkene, har ingen innvirkning på styret, og er dermed ikke verdt å gjøre, for eksempel i over bord en flytting av «Ned» vil ikke ha noen betydning, siden alle brikkene er allerede på den nederste kanten.
utfordringen er da å finne ut hvilke av disse fire trekkene kommer til å være den som har best langsiktig resultat.,
Vår algoritmen er basert på Expectimax algoritmen, som i seg selv er en variant av Minimax algoritmen, men hvor mulige ruter gjennom våre treet er vektet med sannsynligheten for at de vil skje.
Egentlig, vi behandler spillet som en to-spiller spill:
- En Spiller – human-spiller – kan skifte bord i en av fire retninger
- Spiller To – datamaskinen spiller – kan plassere en brikke i et tomt sted på tavlen
Basert på dette, kan vi generere et tre av resultatene fra hvert trekk, vektet med sannsynligheten for hvert trekk skjer., Dette kan så gi oss den informasjon som trengs for å finne ut hvilke menneskelige trekk er sannsynlig å gi det beste resultatet.
3.1. Flytskjema av Gameplay
Den generelle flyten av hvordan spillingen fungerer:
Vi kan umiddelbart se tilfeldig aspekter av spillet i «Legge til Tilfeldige Flis» prosess – både i det faktum at vi finner en tilfeldig plass for å legge flis til, og vi er å velge en tilfeldig verdi for flis.
Vår utfordring blir da å avgjøre hva du skal gjøre i «Bestemme Neste trekk» trinn. Dette er vår algoritme for å spille spillet.,
Den generelle overløp av dette virker utrolig enkel:
Alt vi trenger å gjøre er å simulere hver av de mulige trekk, finne ut hvilken som gir det beste utfallet, og deretter bruke det.
Så nå har vi redusert våre algoritme til å simulere en gitt flytte og generere noen score for utfallet.
Dette er en todelt prosess. I første omgang er å se om flyttingen er også mulig, og hvis ikke, så abort tidlig med en score på «0»., Hvis farten er mulig, så vi vil gå videre til den virkelige algoritme hvor vi finne ut hvor god en flytte dette er:
3.2. Fastsettelse av Neste Move
viktig del av vår algoritme så langt i å simulere en bevegelse, og viktig del av det er hvordan vi genererer en score for hvert mulig trekk. Dette er hvor våre Expectimax algoritme kommer inn.
Vi vil simulere alle mulige trekk fra begge spillere for flere trinn, og se hvilke av dem som gir det beste resultatet. For human-spiller, betyr dette at hver av «opp», «ned», «venstre» og «høyre» beveger seg.,
For datamaskinen spiller, dette betyr å plassere både en «2» eller «4» flis i alle mulige tomt sted:
Denne algoritmen er rekursiv, med hver rekursiv trinn stopper bare hvis det er en viss dybde fra den faktiske flytte i det virkelige spillet.,ulating en score for tiden simulert bord layout
- Simulere alle mulige menneskelige move
- For hver av disse
- Recurse tilbake til algoritmen
- gå Tilbake scoren beregnet fra denne menneskelige move
- Legge til poengsummen beregnes fra denne datamaskinen flytte, vektet med en sannsynlighet på dette trekket skjer
Når vi er ferdig med dette, så vi legger sammen alle de beregnet score, og dette er det endelige resultat for move-vi ønsker å gjøre fra det aktuelle spillet styret., Fordi dette gjør vi fire ganger – en for hver mulig å gå fra nåværende spillet styret – vi ender opp med fire poeng, og den høyeste av dem er flytt til å gjøre.
3.3. En Scoring Styret Posisjon
På dette punktet, er det eneste igjen å gjøre er å beregne en score for et styre. Dette er ikke det samme score som bruker spillet, men det er behov for å ta hensyn til hvor bra en posisjon dette er for å fortsette å spille fra.
Det er et stort antall måter at dette kan oppnås ved å legge til flere faktorer sammen med riktig vekt., For eksempel:
- Antall tomme steder
- Antall mulige fusjonerer – det vil si, mange ganger den samme tall i to tilstøtende steder
- Den største verdien i en hvilken som helst plassering
- Summen av alle steder
- Monotonicity av styret – dette er hvor godt styret er strukturert, slik at plassering verdier øker i samme retning.
Pseudocode
Nå som vi vet hvordan algoritmen kommer til å fungere, hva ser dette ut som? La oss utforske noen pseudocode beskrive algoritmen i mer detalj.,
Vi er ikke interessert i selve spillingen av spillet, bare i algoritme for å bestemme trekk, så kan du starte det:
Som før, dette får oss til det punktet hvor vi er simulere hver av de mulige trekk fra start-styret og returnerer en som scorer best. Dette etterlater oss med å måtte genererer score for den nylig simulert styrene.
Vi har lagt til i en dybde grense, slik at vi kan stoppe behandlingen etter en stund., Fordi vi jobber med en rekursiv algoritme, trenger vi en måte å stoppe det, ellers vil det potensielt kjøre for alltid:
Dette gir oss vår recursion, simulere ut alle mulige menneskelige og flytte datamaskinen til et visst antall skritt og bestemmer hvilke menneskelige trekk gi best mulig resultat.
Det eneste som gjenstår er å utarbeide et endelig resultat for en gitt styret posisjon. Det er ingen perfekt algoritme for dette, og ulike faktorer vil gi forskjellige resultater.,
Ytelse Optimalisering
Så langt at vi har fått en algoritme som vil forsøke å løse spillet, men det er ikke så effektiv som den kunne være. På grunn av tilfeldig natur spillet, er det umulig å ha en perfekt optimalisert solver – det er alltid kommer til å være en viss grad av repetisjon, bare på grunn av arten av prosessen.
Vi kan i alle fall gjøre vårt beste for å redusere arbeidet som vi ikke trenger å gjøre selv.,
Vi allerede gjør en bit av optimalisering i over algoritmen ved ikke å behandle noen trekk som ikke har noen innvirkning på spillet. Det er andre måter vi kan redusere arbeidet med å gjøre, selv om, for eksempel sporing av den kumulative sannsynligheten for beveger seg, og stopp når det blir for lave. Dette har risikoen for å fjerne den perfekte løsningen, men hvis sannsynligheten er at lave, så er det nesten helt sikkert ikke til å skje uansett.
Vi kan også dynamisk bestemme dybden grensen for å arbeide med., Våre over pseudocode har en hard-kodet grense på 3, men vi kunne dynamisk beregne dette basert på formen av styret ved start av våre beregninger, for eksempel sette den til antall tomme firkanter eller antall forskjellige brikkene på brettet. Dette ville bety at vi traverse færre flytter fra styrene som har mindre rom for ekspansjon.
i Tillegg, fordi det er mulig å komme tilbake til samme bordet flere ganger, kan vi huske disse og buffer score for de stillinger i stedet for re-computing dem hver gang., Potensielt kan vi generere alle mulige styret posisjon forut for sin tid, men det er et stort antall av disse – 281,474,976,710,656 forskjellige styreverv bruke fliser opp til 2048 – så dette er nok ikke mulig.
Imidlertid det viktigste, optimalisering vi kan gjøre er å justere algoritme for å generere styret score. Dette fungerer for å avgjøre hvor god styret er for å fortsette å spille, og hvilke faktorer og vekter som vi bruker for dette er direkte knyttet til hvor godt vår algoritme som spiller seg ut.,
Konklusjon
2048 er et veldig interessant spill for å prøve å løse. Det er ingen perfekt måte å løse det på, men vi kan skrive heuristikk som søker etter den beste mulige ruter gjennom spillet.
De samme generelle prinsipper for arbeid for alle to-spiller spill – for eksempel sjakk – der du kan ikke forutsi hva den andre spilleren vil gjøre med noen grad av sikkerhet.
Hvorfor ikke prøve å skrive en implementering av dette og se hvor godt det fungerer?