Keinotekoisen älykkyyden käyttäminen 2048-pelin ratkaisemiseen (JAVA-koodi)

• Huhtikuu 7, 2014
• Vasilis Vryniotis
• . 6 kommenttia

Tähän mennessä suurin osa teistä on kuullut / soittanut 2048 peli kirjoittanut Gabriele Cirulli. Se on yksinkertainen mutta erittäin koukuttava lautapeli, joka vaatii solujen lukumäärän yhdistämistä numeron 2048 saavuttamiseksi. Pelin vaikeus kasvaa odotetusti, kun enemmän soluja täytetään korkeilla arvoilla. Henkilökohtaisesti, vaikka vietin melko paljon aikaa pelin pelaamiseen, en koskaan pystynyt saavuttamaan 2048: ta. Joten luonnollinen asia on yrittää kehittää AA-ratkaisija JAVA: n voittamaan 2048-peli. 🙂

Tässä artikkelissa käsittelen lyhyesti lähestymistapaani pelin 2048 keinotekoisen älykkyyden ratkaisijan rakentamiseen, kuvaan käyttämäni heuristiikka ja annan täydellisen koodin, joka on kirjoitettu Java-kielellä. Koodi on avoimen lähteen GPL v3 -lisenssi ja voit ladata sen osoitteesta Github.

Vuoden 2048 pelin kehittäminen JAVAssa

Alkuperäinen peli on kirjoitettu JavaScriptiä, joten minun piti kirjoittaa se JAVA: han alusta alkaen. Pelin pääidea on, että sinulla on 4 × 4-ruudukko, jossa on kokonaislukuarvot, jotka kaikki ovat 2: n voimia. Nolla-arvoisia soluja pidetään tyhjinä. Pelin jokaisessa vaiheessa voit siirtää arvoja 4 suuntaan ylös, alas, oikealle tai vasemmalle. Kun suoritat siirron, kaikki ruudukon arvot liikkuvat kohti kyseistä suuntaa ja ne pysähtyvät joko saavuttaessaan ruudukon rajat tai kun ne saavuttavat toisen solun, jolla ei ole nolla-arvoa. Jos tällä edellisellä solulla on sama arvo, nämä kaksi solua yhdistetään yhdeksi soluksi, jolla on kaksinkertainen arvo. Jokaisen siirron lopussa taululle lisätään satunnaisarvo yhteen tyhjistä soluista ja sen arvo on joko 2 0.9 todennäköisyydellä tai 4 0.1 todennäköisyydellä. Peli päättyy, kun pelaaja onnistuu luomaan solun, jonka arvo on 2048 (voitto) tai kun ei ole muita tekemisiä (häviämistä).

Pelin alkuperäisessä toteutuksessa siirto-yhdistämisalgoritmi on vähän monimutkainen, koska se ottaa huomioon kaikki suunnat. Algoritmin mukava yksinkertaistaminen voidaan suorittaa, jos kiinnitämme suunta, johon kappaleita voidaan yhdistää, ja käännämme levyä vastaavasti liikkeen suorittamiseksi. Maurits van der Schee on äskettäin kirjoittanut siitä artikkelin, jonka mielestäni kannattaa tarkistaa.

Kaikki luokat on dokumentoitu Javadoc-kommentteilla. Alla tarjoamme korkean tason kuvauksen toteutuksen arkkitehtuurista:

1. Hallitusluokka

Lautakurssi sisältää pelin pääkoodin, joka vastaa kappaleiden siirtämisestä, pisteet laskemisesta, pelin lopettamisen tarkistamisesta jne.

2. ActionStatus ja Suunta Enum

ActionStatus ja suunta ovat 2 välttämätöntä enumia, jotka tallentavat siirron lopputuloksen ja sen suunnan vastaavasti.

3. ConsoleGame-luokka

ConsoleGame on pääluokka, jonka avulla voimme pelata peliä ja testata AI-ratkaisimen tarkkuutta.

4. AIsolver-luokka

AIsolver on keinotekoisen älykkyyden moduulin pääluokka, jonka tehtävänä on arvioida seuraavan parhaan siirron määräys tietylle hallitukselle.

Keinotekoinen älykkyystekniikat: Minimax vs. alfa-beeta-karsinta

Pelin automaattiseen ratkaisemiseen on julkaistu useita lähestymistapoja. Huomattavin on se, jonka on kehittänyt Matt Overlan. Yritin ratkaista ongelman kokeilemalla kahta erilaista lähestymistapaa, käyttämällä Minimax-algoritmia ja Alfa-beetaleikkausta.

Minimax-algoritmi

- Minimax on rekursiivinen algoritmi, jota voidaan käyttää ratkaisemaan kahden pelaajan nollasummapelejä. Jokaisessa pelitilassa yhdistämme arvon. Minimax-algoritmi etsii mahdollisten pelitilojen tilaa luomalla puun, jota laajennetaan, kunnes se saavuttaa tietyn ennalta määritetyn syvyyden. Kun nämä lehtitilat on saavutettu, niiden arvoja käytetään arvioimaan välisolmujen arvot.

Tämän algoritmin mielenkiintoinen idea on, että kukin taso edustaa toisen pelaajan vuoroa. Voittaaksesi jokaisen pelaajan on valittava siirto, joka minimoi vastustajan suurimman voiton. Tässä on hieno videoesitys minimax-algoritmista:

[Upotetun sisällön]

Alla näet Minimax-algoritmin pseudokoodin:

toiminto minimax (solmu, syvyys, maximizingPlayer)
    if syvyys = 0 or solmu on päätesolmu
        palata solmun heuristinen arvo
    if maximizingPlayer bestValue: = -∞
        jokaiselle solmun val lapsi: = minimax (lapsi, syvyys - 1, EPÄTOSI)) bestValue: = max (bestValue, val);
        palata paras arvo
    muu
        bestValue: = + ∞
        jokaiselle solmun lapsi lapsi: = minimax (lapsi, syvyys - 1, TOSI)) bestValue: = min (bestValue, val);
        palata paras arvo
(* Alkupuhelu pelaajan maksimoimiseksi *)
minimax (alkuperä, syvyys, TOSI)

Alfa-beeta-karsinta

- Alfa-beetaleikkausalgoritmi on minimix-laajennus, joka vähentää voimakkaasti (karsimaan) niiden solmujen lukumäärää, jotka meidän on arvioitava / laajennettava. Tämän saavuttamiseksi algoritmi estimoi kaksi arvoa alfa ja beeta. Jos tietyssä solmussa beeta on vähemmän kuin alfa, niin loput alapuut voidaan karsia. Tässä on hieno videoesitys aakkosalgoritmista:

[Upotetun sisällön]

Alla näet alfa-beeta-karsimisalgoritmin pseudokoodin:

toiminto aakkoset (solmu, syvyys, α, β, maximizingPlayer)
    if syvyys = 0 or solmu on päätesolmu
        palata solmun heuristinen arvo
    if maximizingPlayer
        jokaiselle solmun α lapsi: = max (α, aakkoset (lapsi, syvyys - 1, α, β, EPÄTOSI))
            if p <α
                rikkoa (* β-raja *)
        palata α
    muu
        jokaiselle solmun β lapsi: = min (β, aakkoset (lapsi, syvyys - 1, α, β, TOSI))
            if p <α
                rikkoa (* α-raja *)
        palata β
(* Alkuperäinen puhelu *)
aakkoset (alkuperä, syvyys, -∞, + ∞, tosi)

Kuinka AI: ta käytetään ratkaisemaan peli 2048?

Edellä olevien algoritmien käyttämiseksi meidän on ensin tunnistettava kaksi pelaajaa. Ensimmäinen pelaaja on henkilö, joka pelaa peliä. Toinen pelaaja on tietokone, joka satunnaisesti lisää arvoja taulukon soluihin. On selvää, että ensimmäinen pelaaja yrittää maksimoida pisteet ja saavuttaa vuoden 2048 yhdistymisen. Toisaalta alkuperäisen pelin tietokonetta ei ole erityisesti ohjelmoitu estämään käyttäjää valitsemalla pahin mahdollinen siirto hänelle, vaan pikemminkin satunnaisesti lisää arvot tyhjiin soluihin.

Joten miksi käytämme AI-tekniikoita, jotka ratkaisevat nollasummien pelit ja joissa erityisesti oletetaan, että molemmat pelaajat valitsevat heille parhaan mahdollisen siirron? Vastaus on yksinkertainen; Huolimatta siitä, että vasta ensimmäinen pelaaja yrittää maksimoida pisteet, tietokoneen valinnat voivat estää etenemisen ja estää käyttäjää suorittamasta peliä. Mallinnamalla tietokoneen käyttäytymistä ortologisena, satunnaisena pelaajana, varmistamme, että valintamme on vankka valinta riippumatta siitä, mitä tietokone pelaa.

Toinen tärkeä osa on osoittaa arvoja pelin tiloille. Tämä ongelma on suhteellisen yksinkertainen, koska peli itse antaa meille pisteet. Valitettavasti yrittäminen maksimoida pisteet yksinään ei ole hyvä lähestymistapa. Yksi syy tähän on, että arvojen sijainti ja tyhjien arvostettujen solujen lukumäärä ovat erittäin tärkeitä pelin voittamiseksi. Esimerkiksi, jos hajotamme suuret arvot etäsoluihin, meidän olisi todella vaikea yhdistää niitä. Lisäksi, jos meillä ei ole tyhjiä soluja käytettävissä, vaarana on menettää peli milloin tahansa.

Kaikista edellä mainituista syistä useita heuristiikka on ehdotettu kuten levyn monoottisuus, sileys ja vapaat laatat. Pääideana ei ole käyttää pisteet pelkästään kunkin pelitilan arvioimiseksi, vaan sen sijaan rakentaa heuristinen yhdistelmäpiste, joka sisältää edellä mainitut pisteet.

Lopuksi meidän on huomattava, että vaikka olenkin kehittänyt Minimax-algoritmin toteutuksen, suuri määrä mahdollisia tiloja tekee algoritmista erittäin hitaita ja siten karsinta on välttämätöntä. JAVA-toteutuksen tuloksena käytän Alfa-beeta-karsimisalgoritmin laajennusta. Lisäksi toisin kuin muut toteutukset, en karsitse aggressiivisesti tietokoneen valintoja mielivaltaisten sääntöjen avulla, vaan sen sijaan otan ne kaikki huomioon löytääkseni pelaajan parhaan mahdollisen liikkeen.

Heuristisen pisteytysfunktion kehittäminen

Pelin voittamiseksi kokeilin useita erilaisia ​​heuristisia toimintoja. Pidän hyödyllisimmäksi seuraavaa:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

Yllä oleva toiminto yhdistää levyn todellisen pisteet, tyhjien solujen / laattojen määrän ja metrisen nimityksen klusterointituloksen, josta keskustellaan myöhemmin. Katsotaan jokainen komponentti yksityiskohtaisemmin:

1. Todellinen pistemäärä: Ilmeisistä syistä laskettaessa pöydän arvoa on otettava huomioon sen pisteet. Taulut, joilla on korkeammat pisteet, ovat yleensä parempia verrattuna taulukoihin, joiden pisteet ovat alhaisemmat.
2. Tyhjien solujen lukumäärä: Kuten aiemmin mainitsimme, muutaman tyhjän solun pitäminen on tärkeää, jotta voimme hävittää pelin seuraavissa liikkeissä. Lautatilat, joissa on enemmän tyhjiä soluja, ovat yleensä parempia verrattuna muihin, joissa on vähemmän tyhjiä soluja. Esiin nousee kysymys siitä, kuinka arvokkaamme näitä tyhjiä soluja? Painotan niitä ratkaisessani todellisen pistemäärän logaritmilla. Tällä on seuraava vaikutus: Mitä pienempi pistemäärä, sitä vähemmän tärkeätä on, että on paljon tyhjiä soluja (Tämä johtuu siitä, että pelin alussa solujen yhdistäminen on melko helppoa). Mitä korkeampi pistemäärä, sitä tärkeämpää on varmistaa, että pelissämme on tyhjiä soluja (Tämä johtuu siitä, että pelin lopussa se todennäköisemmin häviää tyhjien solujen puutteen vuoksi.
3. Klusterointitulos: Käytämme klusterointitulosta, joka mittaa, kuinka hajotetut hallituksen arvot ovat. Kun solut, joilla on samanlaiset arvot, ovat lähellä, niitä on helpompi yhdistää, on vaikeampaa menettää peli. Tässä tapauksessa ryhmittelypisteellä on alhainen arvo. Jos taulun arvot ovat hajallaan, niin tämä pistemäärä saa erittäin suuren arvon. Tämä pistemäärä vähennetään kahdesta edellisestä pistemäärästä ja toimii kuin rangaistus, joka varmistaa, että ryhmitetyt levyt ovat parempia.

Toiminnon viimeisellä rivillä varmistetaan, että pistemäärä ei ole negatiivinen. Pistemäärän tulee olla ehdottomasti positiivinen, jos pöydän pisteet ovat positiiviset ja nolla vain, kun pisteet ovat nollat. Max- ja min-toiminnot on rakennettu siten, että saamme tämän vaikutuksen.

Lopuksi meidän on huomattava, että kun pelaaja saavuttaa päätepelin tilan ja enää liikkeitä ei sallita, emme käytä yllä olevaa pistemäärää tilan arvon arvioimiseen. Jos peli voitetaan, määritämme korkeimman mahdollisen kokonaisluvun, kun taas peli häviää, annamme pienimmän ei-negatiivisen arvon (0 tai 1 samanlaisella logiikalla kuin edellisessä kappaleessa).

Lisätietoja klusterointituloksesta

Kuten aiemmin totesimme, klusterointitulos mittaa, kuinka paljon sironnut ovat hallituksen arvot ja toimii kuin rangaistus. Olen rakentanut tämän pisteet siten, että se sisältää vinkkejä / sääntöjä käyttäjiltä, ​​jotka “hallitsivat” pelin. Ensimmäinen ehdotettu sääntö on, että yrität pitää solut, joilla on samanlaiset arvot lähellä, jotta ne olisi helpompi yhdistää. Toinen sääntö on, että arvokkaiden kennojen tulee olla lähellä toisiaan eivätkä ne saa olla taulun keskellä vaan pikemminkin sivuilla tai kulmissa.

Katsotaan kuinka klusterointitulos arvioidaan. Jokaiselle taulun solulle arvioimme absoluuttisten erojen summan naapureistaan ​​(pois lukien tyhjät solut) ja otamme keskimääräisen eron. Syy, miksi otamme keskiarvot, on välttää kahden naapurisolun vaikutuksen laskemista useammin kuin kerran. Kokonainen klusterointitulos on kaikkien näiden keskiarvojen summa.

Rypytyspisteellä on seuraavat määritteet:

1. Se saa suuren arvon, kun levyn arvot ovat hajallaan, ja alhaisen arvon, kun solut, joilla on samanlaiset arvot ovat lähellä toisiaan.
2. Se ei ylitä kahden naapurisolun vaikutusta.
3. Reunojen tai kulmien soluissa on vähemmän naapureita ja siten pienemmät pisteet. Seurauksena, kun korkeat arvot sijoitetaan marginaalien tai kulmien läheisyyteen, niiden pisteet ovat pienempiä, joten rangaistus on pienempi.

Algoritmin tarkkuus

Odotetusti algoritmin tarkkuus (eli voitettujen pelien prosenttiosuus) riippuu suuresti käyttämästämme hakusyvyydestä. Mitä suurempi haun syvyys, sitä suurempi tarkkuus ja sitä enemmän aikaa se vaatii suorittamiseen. Kokeissani haku, jonka syvyys on 3, kestää alle 0.05 sekuntia, mutta antaa 20% mahdollisuuden voittaa, 5 syvyys kestää noin yhden sekunnin, mutta antaa 1% mahdollisuuden voittaa ja lopulta syvyys 40 kestää 7-27 sekuntia ja antaa noin 28-70% mahdollisuuden voittaa.

Tulevat laajennukset

Niille teistä, jotka ovat kiinnostuneita koodin parantamisesta, on muutamia asioita, joita voit tutkia:

1. Paranna nopeutta: Algoritmin nopeuden parantaminen antaa sinun käyttää suurempaa syvyyttä ja saada siten paremman tarkkuuden.
2. Luo grafiikka: On hyvä syy, miksi Gabriele Cirullin toteutus tuli niin kuuluisaksi. Se on hieno näköinen! En vaivaudu kehittämään käyttöliittymää, vaan tulostan tulokset pikemminkin konsoliin, mikä vaikeuttaa pelin seuraamista ja pelaamista. Mukavan käyttöliittymän luominen on välttämätöntä.
3. Viritä heuristiikka: Kuten aiemmin mainitsin, useat käyttäjät ovat ehdottaneet erilaista heuristiikkaa. Voidaan kokeilla pisteiden laskentatapaa, painoja ja huomioitujen levyominaisuuksien ominaisuuksia. Klusteripisteiden mittaamisen lähestymistapana on tarkoitus yhdistää muita ehdotuksia, kuten monotonisuus ja sileys, mutta parantamisen varaa on vielä.
4. Syvyyden virittäminen: Voit myös yrittää virittää / säätää haun syvyyttä pelin tilasta riippuen. Voit myös käyttää Iteratiivinen syventävä syvä-ensimmäinen haku algoritmi, jonka tiedetään parantavan alfa-beeta-karsimisalgoritmia.

Muista ladata JAVA-koodi osoitteesta Github ja kokeilla. Toivottavasti nautit tästä viestistä! Jos et, ota hetki jakaaksesi artikkeli Facebookissa ja Twitterissä. 🙂