mikä on optimaalinen algoritmi peliin 2048?
Johdanto
2048 on jännittävä laatta-siirtymässä peli, jossa meidän on siirtää laatat ympärillä, yhdistää ne, tavoitteena yhä suurempi laatta-arvot.
tässä opetusohjelmassa, aiomme tutkia algoritmi pelata 2048, joka auttaa päättämään paras liikkuu voit tehdä jokaisessa vaiheessa saada parhaat pisteet.
Kuinka Pelata 2048
peli 2048 pelataan 4×4 aluksella., Jokainen asema aluksella voi olla tyhjä tai voi sisältää laatta, ja jokainen laatta on numero sitä.
Kun aloitamme, hallituksen on kahden laatat satunnaisessa paikoissa, joista jokainen joko on ”2” tai ”4”, se on – jokainen on itsenäinen 10%: n mahdollisuus ”4”, tai muuten on ”2”.
liikkeet suoritetaan siirtämällä kaikki laatat yhteen reunaan – ylös, alas, vasemmalle tai oikealle., Kun teet tämän, kaikki laatat, joissa sama arvo, jotka ovat lähellä toisiaan ja etenevät yhdessä, yhdistää ja päätyä uusi laatta summa aiemmin kaksi:
sen Jälkeen, kun olemme tehneet liikkua, uusi laatta asetetaan pöydälle. Tämä sijoitetaan satunnaiseen paikkaan, ja on ”2” tai ”4” samalla tavalla kuin alkuperäinen laatat – ”2” 90% ajasta ja ”4” 10% ajasta.
peli jatkuu, kunnes siirtoja ei enää ole.
yleensä, pelin tavoitteena on päästä yksi laatta, jonka arvo on ”2048”., Peli ei kuitenkaan lopu tähän, ja voimme jatkaa pelaamista niin pitkälle kuin on mahdollista, tavoitteena suurin mahdollinen laatta. Teoriassa kyseessä on laatta, jonka arvo on ”131 072”.
Ongelma Selitys
Ratkaista tämä peli on mielenkiintoinen ongelma, koska se on satunnainen komponentti. On mahdotonta oikein ennustaa paitsi missä jokainen uusi laatta sijoitetaan, mutta onko se on ”2”tai ” 4″.
sellaisenaan on mahdotonta saada algoritmia, joka ratkaisisi palapelin oikein joka kerta., Parasta mitä voimme tehdä on määrittää, mikä on todennäköisesti paras liikkua kussakin vaiheessa ja pelata todennäköisyyspeli.
missään vaiheessa mahdollisia liikkeitä on vain neljä. Joskus joitakin näistä liikkuu ei ole vaikutus hallituksen ja ovat näin ollen ole syytä tehdä – esimerkiksi edellä aluksella liikkua ”Alas” ei ole vaikutusta, koska kaikki laatat ovat jo alareunassa.
haasteena on sitten selvittää, kumpi näistä neljästä siirrosta on se, jolla on paras pitkän aikavälin tulos.,
– Meidän algoritmi perustuu Expectimax algoritmi, joka on itse vaihtelu Minimax-algoritmi, mutta jossa mahdolliset reitit läpi meidän puu on painotettu todennäköisyys, että ne tapahtuu.
Pohjimmiltaan, me kohtelemme pelin kahden pelaajan peli:
- Pelaaja Yhden ihmisen pelaaja voi siirtää hallituksen neljästä suunnasta
- Pelaaja Kaksi – tietokoneen pelaaja – voi sijoittaa laatta tyhjään paikkaan aluksella
tämän Perusteella voimme luoda puu tuloksia kunkin liikkua, painotettu todennäköisyys jokainen siirto tapahtuu., Tämä voi sitten antaa meille tarvittavat yksityiskohdat sen määrittämiseksi, mikä ihmisen liike todennäköisesti antaa parhaan tuloksen.
3.1. Vuokaavio Pelattavaa
yleistä kulkua, miten pelattavuus toimii:
– Voimme heti nähdä, satunnainen osa peliä ”Lisää Satunnainen Laatta” prosessi – sekä siitä, että olemme löytää satunnainen neliö lisätä laatta, ja olemme valitsemalla satunnainen arvo laatta.
haasteemme on sitten päättää, mitä tehdä ”Determine Next Move” – vaiheessa. Tämä on algoritmimme pelata peliä.,
yleiset-ylivuoto tämä näyttää petollisen yksinkertainen:
Kaikki meidän täytyy tehdä, on simuloida kunkin mahdollisia liikkeitä, mitkä yksi antaa paras tulos, ja sitten käyttää sitä.
joten olemme nyt vähentäneet algoritmiamme simuloimaan mitä tahansa liikettä ja tuottamaan jonkin verran pisteitä lopputulokselle.
Tämä on kaksiosainen prosessi. Ensimmäinen syöttö on nähdä, onko siirto edes mahdollista, ja jos ei, niin keskeytä aikaisin pisteellä ”0”., Jos siirto on mahdollista, sitten siirrymme todellinen algoritmi, jossa voimme selvittää, miten hyvä liikkua tämä on:
3.2. Määritetään Seuraavaksi
keskeinen osa meidän algoritmi toistaiseksi on simuloidaan liikkua, ja keskeinen osa tätä on, kuinka voimme tuottaa pisteet jokaiselle mahdollista liikkua. Tässä tulee Expectimax-algoritmimme.
simuloimme jokaisen mahdollisen siirron molemmilta pelaajilta useiden vaiheiden ajan ja katsomme, mikä niistä antaa parhaan lopputuloksen. Ihmispelaajalle tämä tarkoittaa jokaista ”ylös”, ”alas”, ”vasemmalle” ja ”oikealle” liikettä.,
tietokoneen pelaaja, tämä tarkoittaa asettamalla molemmat ”2” tai ”4” laatta osaksi jokainen mahdollinen tyhjä paikka:
Tämä algoritmi on rekursiivinen, jossa jokainen rekursiivinen askel pysäyttää vain, jos se on tietty syvyys todellisen liikkuvat todellinen peli.,ulating pisteet tällä hetkellä simuloitu board layout
- Simuloida kaikki mahdolliset ihmisen liikkua
- kunkin
- Recurse takaisin algoritmi
- Paluu pisteet lasketaan tämän ihmisen liikkua
- Lisätä pisteet lasketaan tämän tietokoneen liikkua, painotettuna todennäköisyydellä tämä siirto tapahtuu
– Kun saimme tämän valmiiksi, sitten lisätä jopa kaikki lasketut tulokset, ja tämä on lopullinen pisteet siirtää haluamme tehdä nykyisestä pelilaudan., Koska teemme tämän neljä kertaa – yksi kutakin mahdollista siirtää nykyisestä peli board – päädymme neljä tulokset, ja korkein niistä on siirtyä tehdä.
3.3. Pisteytys Hallituksen Kanta
tässä vaiheessa, ainoa asia jäljellä, voit tehdä, on laskea pisteet aluksella. Tämä ei ole sama pisteytys kuin peli käyttää, mutta se on otettava huomioon, kuinka hyvä asema tässä on jatkaa pelaamista alkaen.
On olemassa useita tapoja, joilla tämä voidaan saavuttaa lisäämällä useita tekijöitä yhdessä asianmukaiset korjauskertoimet., Esimerkiksi:
- Määrä tyhjiä paikkoja
- Useita mahdollisia yhdistämisiä – eli monta kertaa sama numero on kaksi vierekkäistä paikkakunnalla
- suurin arvo joka paikkaan
- Summa kaikki paikat
- Monotonicity hallituksen – tämä on, miten hyvin hallitus on jäsennelty siten, että paikka arvot lisätä yhteen suuntaan.
Pseudokoodina
Nyt kun tiedämme, miten algoritmi toimii, miltä tämä näyttää? Tutkitaan tarkemmin algoritmia kuvaavaa pseudokoodia.,
– Emme ole kiinnostuneita todellinen peli, vain algoritmi määrittämiseksi liikkuu, joten voit aloittaa sieltä:
Kuten ennen, tämä saa meidät siihen pisteeseen, jossa olemme simuloimalla kunkin mahdollisia liikkuu alkaen hallituksen ja palauttamalla että tulokset parhaat. Tämä jättää meille tarvetta tuottaa pisteitä juuri simuloitu levyt.
olemme lisänneet syvyysrajan, jotta voimme lopettaa käsittelyn jonkin ajan kuluttua., Koska teemme yhteistyötä rekursiivinen algoritmi, tarvitsemme tapa estää se, muuten se on mahdollisesti ajaa ikuisesti:
Tämä antaa meille rekursio, simuloida kaikki mahdolliset ihmisen ja tietokoneen siirtää tiettyjä vaiheita ja päättää, mitkä ihmisen liikkeitä antaa parhaan mahdollisen tuloksen.
ainoa jäljellä oleva asia on selvittää lopullinen pistemäärä mille tahansa hallituspaikalle. Ei ole olemassa täydellistä algoritmia, ja eri tekijät antavat erilaisia tuloksia.,
Suorituskyvyn Optimointi
toistaiseksi meillä on algoritmi, joka yrittää ratkaista peli, mutta se ei ole niin tehokas kuin se voisi olla. Koska satunnainen luonne pelin, se on mahdotonta saada täysin optimoitu ratkaisija – siellä on aina olemaan jonkin verran toistoa yksinkertaisesti, koska prosessin luonne.
voimme ainakin tehdä parhaamme vähentääksemme työtä, jota meidän ei kuitenkaan tarvitse tehdä.,
– Olemme jo tekemässä vähän optimointi edellä algoritmi ei käsittele mitään liikkuu, että ei ole mitään vaikutusta peliin. On muitakin tapoja, joilla voimme vähentää työtä, vaikka, kuten seuranta kumulatiivinen todennäköisyys liikkuu ja pysähtyy, kun se saa liian alhainen. Tämä ei ole riskin poistamiseksi täydellinen ratkaisu, mutta jos todennäköisyys on alhainen, sitten se lähes varmasti ei tapahdu muutenkin.
Voimme myös dynaamisesti määrittää syvyys rajoittaa työskennellä., Meidän edellä pseudokoodina on hard-koodattu raja 3, mutta voimme dynaamisesti laskea tämän perusteella muodon hallituksen alussa meidän laskelmat – esimerkiksi asettamalla sen määrä tyhjiä neliöitä tai useita eri laatat taululle. Tämä tarkoittaisi sitä, että kuljemme vähemmän siirtoja lautoilta, joilla on vähemmän mahdollisuuksia laajentua.
Lisäksi, koska on mahdollista palata samaan hallituksen kantoja useita kertoja, voimme muistaa nämä ja välimuisti pisteet niille kantoja sen sijaan, että uudelleen computing niitä joka kerta., Mahdollisesti voimme tuottaa kaikki mahdolliset hallituksen kannan etuajassa, mutta on olemassa valtava määrä näitä – 281,474,976,710,656 eri mahdollista hallituksen kantoja käyttämällä laatat jopa 2048 – joten tämä ei luultavasti ole mahdollista.
tärkein optimointi, jonka voimme tehdä, on kuitenkin algoritmin säätäminen lautapisteiden tuottamiseksi. Tämä toimii, päättää, kuinka hyvä hallitus on edelleen pelata ja tekijät ja painotukset, joita käytämme tämän ovat suoraan sidoksissa siihen, miten hyvin meidän algoritmi toistaa.,
Johtopäätös
2048 on erittäin mielenkiintoinen peli, yrittää ratkaista. Ei ole täydellistä tapaa ratkaista sitä, mutta voimme kirjoittaa heuristiikkaa, joka etsii parhaat mahdolliset reitit läpi pelin.
samat yleiset periaatteet työtä tahansa kahden pelaajan peli – esimerkiksi, shakkia, jossa et voi ennustaa, mitä toinen pelaaja tekee varmuudella.
miksi et yrittäisi kirjoittaa tämän toteutusta ja nähdä, kuinka hyvin se toimii?