Tehisintellekti kasutamine 2048 mängu lahendamiseks (JAVA kood)

• Aprill 7, 2014
• Vasilis Vryniotis
• . 6 kommentaari

Praeguseks on enamik teist seda kuulnud/mänginud 2048 mängu autor Gabriele Cirulli. See on lihtne, kuid väga sõltuvust tekitav lauamäng, mis nõuab lahtrite arvude kombineerimist, et jõuda numbrini 2048. Ootuspäraselt suureneb mängu keerukus, kui rohkem lahtreid täidetakse kõrgete väärtustega. Kuigi ma isiklikult veetsin mängu mängides üsna palju aega, ei jõudnud ma kunagi 2048-ni. Seega on loomulik, et proovime JAVA-s arendada tehisintellekti lahendajat, et võita 2048. aasta mäng. 🙂

Selles artiklis käsitlen lühidalt oma lähenemist Game 2048 tehisintellekti lahendaja loomisele, kirjeldan kasutatud heuristikat ja annan täieliku koodi, mis on kirjutatud JAVA-s. Kood on avatud lähtekoodiga GPL v3 litsentsi alusel ja saate selle alla laadida aadressilt Github.

2048 mängu arendamine JAVA-s

Algne mäng on kirjutatud JavaScriptis, seega pidin selle nullist JAVA-s ümber kirjutama. Mängu põhiidee seisneb selles, et teil on 4 × 4 ruudustik täisarvuliste väärtustega, mis kõik on 2 astmed. Nullväärtusega lahtrid loetakse tühjaks. Mängu igas punktis saate väärtusi liigutada 4 suunas üles, alla, paremale või vasakule. Kui sooritate liigutuse, liiguvad kõik ruudustiku väärtused sellesse suunda ja need peatuvad, kui jõuavad ruudustiku piiridesse või kui jõuavad teise nullist erineva väärtusega lahtrisse. Kui eelmisel lahtril on sama väärtus, liidetakse need kaks lahtrit kahekordse väärtusega lahtrisse. Iga käigu lõpus lisatakse lauale ühte tühja lahtrisse juhuslik väärtus ja selle väärtus on kas 2 tõenäosusega 0.9 või 4 tõenäosusega 0.1. Mäng lõppeb siis, kui mängijal õnnestub luua lahter väärtusega 2048 (võit) või kui pole muud käiku teha (kaotus).

Mängu algses teostuses on liigutamise-liitmise algoritm pisut keeruline, kuna võtab arvesse kõiki suundi. Algoritmi mõnusa lihtsustuse saab teha, kui fikseerime suuna, mille poole saame nuppe kombineerida ja käigu sooritamiseks vastavalt tahvlit pöörata. Maurits van der Schee kirjutas hiljuti selle kohta artikli, mida minu arvates tasub vaadata.

Kõik klassid on dokumenteeritud Javadoci kommentaaridega. Allpool pakume juurutamise arhitektuuri kõrgetasemelist kirjeldust:

1. Lauaklass

Lauaklass sisaldab mängu põhikoodi, mis vastutab nuppude liigutamise, skoori arvutamise, mängu katkestamise jm eest.

2. ActionStatus ja Direction Enum

ActionStatus ja Direction on kaks olulist loendit, mis salvestavad vastavalt liikumise tulemuse ja selle suuna.

3. ConsoleGame klass

ConsoleGame on põhiklass, mis võimaldab meil mängu mängida ja AI Solveri täpsust testida.

4. AIsolveri klass

AIsolver on tehisintellekti mooduli põhiklass, mis vastutab konkreetse juhatuse järgmise parima käigu hindamise eest.

Tehisintellekti tehnikad: Minimax vs alfa-beeta pügamine

Selle mängu automaatseks lahendamiseks on avaldatud mitu lähenemisviisi. Kõige tähelepanuväärsem on see, mille on välja töötanud Matt Overlan. Probleemi lahendamiseks proovisin kahte erinevat lähenemisviisi, kasutades Minimaxi algoritmi ja alfa-beeta pügamist.

Minimax algoritm

. Minimax on rekursiivne algoritm, mida saab kasutada kahe mängijaga nullsumma mängude lahendamiseks. Igas mängu olekus seostame väärtuse. Algoritm Minimax otsib läbi võimalike mänguseisundite ruumi, luues puu, mida laiendatakse, kuni see jõuab teatud etteantud sügavusele. Kui need lehtede olekud on saavutatud, kasutatakse nende väärtusi vahesõlmede olekute hindamiseks.

Selle algoritmi huvitav idee seisneb selles, et iga tase tähistab ühe mängija järjekorda. Võitmiseks peab iga mängija valima käigu, mis minimeerib vastase maksimaalse väljamakse. Siin on minimaxi algoritmi kena videoesitlus:

[Varjatud sisu]

Allpool näete Minimaxi algoritmi pseudokoodi:

funktsioon minimax (sõlm, sügavus, maksimeeriv mängija)
    if sügavus = 0 or sõlm on terminalisõlm
        tagasipöördumine sõlme heuristiline väärtus
    if maximizingPlayer bestValue := -∞
        igaühele sõlme laps val := minimax(laps, sügavus - 1, FALSE)) parimVäärtus := max(parimVäärtus, val);
        tagasipöördumine parim hind
    teine
        bestValue := +∞
        igaühele sõlme laps val := minimax(laps, sügavus - 1, TRUE)) parimVäärtus := min(parimVäärtus, val);
        tagasipöördumine parim hind
(* Esialgne kõne mängija maksimeerimiseks *)
minimax (päritolu, sügavus, TRUE)

Alfa-beeta pügamine

. Alfa-beeta pügamisalgoritm on minimaxi laiendus, mis vähendab (kärpib) oluliselt sõlmede arvu, mida peame hindama/laiendama. Selle saavutamiseks hindab algoritm kahte väärtust alfa ja beeta. Kui antud sõlmes on beeta väiksem kui alfa, saab ülejäänud alampuid kärpida. Siin on kena alfabeeta algoritmi videoesitlus:

[Varjatud sisu]

Allpool näete alfa-beeta pügamisalgoritmi pseudokoodi:

funktsioon tähestik (sõlm, sügavus, α, β, mängija maksimeerimine)
    if sügavus = 0 or sõlm on terminalisõlm
        tagasipöördumine sõlme heuristiline väärtus
    if maksimizingPlayer
        igaühele sõlme α laps := max(α, tähestik(laps, sügavus - 1, α, β, VÄÄR))
            if β ≤ α
                murdma (* β piirväärtus *)
        tagasipöördumine α
    teine
        igaühele sõlme β laps := min(β, tähestik(laps, sügavus - 1, α, β, TÕENE))
            if β ≤ α
                murdma (* α piirväärtus *)
        tagasipöördumine β
(* Esmane kõne *)
tähestik (päritolu, sügavus, -∞, +∞, TÕENE)

Kuidas kasutatakse tehisintellekti mängu 2048 lahendamiseks?

Ülaltoodud algoritmide kasutamiseks peame esmalt tuvastama kaks mängijat. Esimene mängija on isik, kes mängu mängib. Teine mängija on arvuti, mis sisestab juhuslikult väärtused laua lahtritesse. Ilmselgelt püüab esimene mängija oma skoori maksimeerida ja saavutada 2048. aasta ühinemise. Teisest küljest ei ole algses mängus arvuti spetsiaalselt programmeeritud kasutajat blokeerima, valides tema jaoks halvima võimaliku käigu, vaid sisestab väärtused juhuslikult tühjadesse lahtritesse.

Miks me siis kasutame tehisintellekti tehnikaid, mis lahendavad nullsummamänge ja eeldavad, et mõlemad mängijad valivad nende jaoks parima võimaliku käigu? Vastus on lihtne; Vaatamata sellele, et alles esimene mängija püüab oma skoori maksimeerida, võivad arvuti valikud edenemist blokeerida ja kasutajal mängu lõpetada. Arvuti kui ortoloogilise mittejuhusliku mängija käitumist modelleerides tagame, et meie valik on kindel, sõltumata sellest, mida arvuti mängib.

Teine oluline osa on väärtuste määramine mängu olekutele. See probleem on suhteliselt lihtne, sest mäng ise annab meile hinde. Kahjuks ei ole üksi skoori maksimeerimine hea lähenemine. Selle üheks põhjuseks on see, et väärtuste asukoht ja tühjade väärtustega lahtrite arv on mängu võitmiseks väga olulised. Näiteks kui hajutame suured väärtused kauglahtritesse, oleks meil neid väga raske kombineerida. Lisaks, kui meil pole ühtegi tühja lahtrit, on oht, et kaotame mängu igal minutil.

Kõigil ülaltoodud põhjustel on mitu heuristikat on soovitatud nagu plaadi monootilisus, sujuvus ja vabad plaadid. Põhiidee on mitte kasutada iga mänguseisundi hindamiseks ainult skoori, vaid selle asemel koostada heuristiline koondskoor, mis sisaldab ülalnimetatud punkte.

Lõpetuseks peaksime märkima, et kuigi olen välja töötanud Minimaxi algoritmi teostuse, muudab võimalike olekute suur arv algoritmi väga aeglaseks ja seega on vaja kärpida. Selle tulemusena kasutan JAVA juurutamisel Alpha-beta pügamisalgoritmi laiendust. Lisaks, erinevalt teistest rakendustest, ei kärbi ma agressiivselt arvuti valikuid suvaliste reeglite abil, vaid võtan neid kõiki arvesse, et leida mängija parim võimalik käik.

Heuristilise skoori funktsiooni väljatöötamine

Mängu ületamiseks proovisin mitmeid erinevaid heuristlikke funktsioone. Minu arvates oli kõige kasulikum järgmine:

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));
}

Ülaltoodud funktsioon ühendab tahvli tegeliku skoori, tühjade lahtrite/plaatide arvu ja mõõdiku, mida nimetatakse klastriskooriks, mida käsitleme hiljem. Vaatame iga komponenti üksikasjalikumalt:

1. Tegelik skoor: Arusaadavatel põhjustel peame tahvli väärtuse arvutamisel arvestama selle skoori. Üldjuhul eelistatakse kõrgema punktisummaga tahvleid võrreldes madalama punktisummaga tahvlitega.
2. Tühjade lahtrite arv: Nagu varem mainisime, on väheste tühjade lahtrite hoidmine oluline tagamaks, et me ei kaotaks mängu järgmistel käikudel. Tavaliselt eelistatakse rohkem tühje lahtreid sisaldavaid tahvelolekuid võrreldes teiste vähemate lahtritega. Tekib küsimus, kuidas me neid tühje rakke väärtustaksime? Oma lahenduses kaalun neid tegeliku skoori logaritmi järgi. Sellel on järgmine mõju: mida madalam on skoor, seda vähem oluline on palju tühje lahtreid (seda seetõttu, et mängu alguses on lahtrite kombineerimine üsna lihtne). Mida kõrgem on skoor, seda olulisem on tagada, et meie mängus oleks tühjad lahtrid (seda seetõttu, et mängu lõpus on tühjade lahtrite puudumise tõttu tõenäolisem kaotada.
3. Klastrite skoor: Kasutame klastrite skoori, mis mõõdab, kui hajutatud on meie tahvli väärtused. Kui sarnaste väärtustega lahtrid on lähedased, on neid lihtsam kombineerida, mis tähendab, et mängu on raskem kaotada. Sel juhul on klastri skoor madal väärtus. Kui tahvli väärtused on hajutatud, saab see skoor väga suure väärtuse. See skoor lahutatakse kahest eelmisest tulemusest ja see toimib karistusena, mis tagab, et eelistatakse rühmitatud tahvleid.

Funktsiooni viimasel real tagame, et skoor ei oleks negatiivne. Hinne peaks olema rangelt positiivne, kui laua skoor on positiivne, ja null ainult siis, kui skoor on null. Funktsioonid max ja min on konstrueeritud nii, et saame selle efekti.

Lõpetuseks peaksime tähele panema, et kui mängija jõuab mänguterminali olekusse ja enam käike pole lubatud, ei kasuta me ülaltoodud skoori oleku väärtuse hindamiseks. Mängu võidu korral omistame suurima võimaliku täisarvu väärtuse, mängu kaotamisel aga madalaima mittenegatiivse väärtuse (0 või 1 sarnase loogikaga nagu eelmises lõigus).

Lisateavet klastri skoori kohta

Nagu me varem ütlesime, mõõdab klastrite skoor, kui palju on laua väärtused hajutatud, ja toimib karistusena. Koostasin selle skoori nii, et see sisaldaks näpunäiteid/reegleid kasutajatelt, kes mängu "meisterdasid". Esimene soovitatud reegel on see, et proovite hoida sarnaste väärtustega lahtrid lähedal, et neid oleks lihtsam kombineerida. Teine reegel on, et kõrge väärtusega lahtrid peaksid asuma üksteise lähedal ja mitte jääma tahvli keskele, vaid pigem külgedele või nurkadele.

Vaatame, kuidas klastri skoori hinnatakse. Tahvli iga lahtri jaoks hindame naabrite absoluutsete erinevuste summat (välja arvatud tühjad lahtrid) ja võtame keskmise erinevuse. Põhjus, miks me võtame keskmised, on vältida kahe naaberlahtri mõju rohkem kui ühekordset arvestamist. Klastrite koguskoor on kõigi nende keskmiste summa.

Klasterdamisskooril on järgmised atribuudid.

1. See saab kõrge väärtuse, kui tahvli väärtused on hajutatud, ja madala väärtuse, kui sarnaste väärtustega lahtrid on üksteise lähedal.
2. See ei kaalu üle kahe naaberraku mõju.
3. Veeristes või nurkades olevatel lahtritel on vähem naabreid ja seega madalamad punktisummad. Selle tulemusena, kui kõrged väärtused asetatakse veeriste või nurkade lähedusse, on neil väiksemad punktisummad ja seega on karistus väiksem.

Algoritmi täpsus

Nagu oodatud, sõltub algoritmi täpsus (teise nimega võidetud mängude protsent) suuresti kasutatavast otsingusügavusest. Mida suurem on otsingu sügavus, seda suurem on täpsus ja seda rohkem kulub selle käivitamiseks aega. Minu testides kestab sügavusega 3 otsing vähem kui 0.05 sekundit, kuid annab 20% võiduvõimaluse, sügavus 5 kestab umbes 1 sekundi, kuid annab 40% võiduvõimaluse ja lõpuks sügavus 7 kestab 27-28 sekundit ja annab umbes 70-80% võiduvõimaluse.

Tulevased laiendused

Neile, kes on huvitatud koodi täiustamisest, on siin mõned asjad, mida saate uurida.

1. Parandage kiirust: Algoritmi kiiruse parandamine võimaldab teil kasutada suuremat sügavust ja seeläbi saada paremat täpsust.
2. Loo graafika: Sellel, miks Gabriele Cirulli teostus nii kuulsaks sai, on hea põhjus. See on kena välimus! Ma ei viitsinud GUI-d arendada, vaid pigem prindin tulemused konsoolile, mis teeb mängu jälgimise ja mängimise raskemaks. Kena GUI loomine on kohustuslik.
3. Helistamise heuristika: Nagu ma varem mainisin, on mitmed kasutajad soovitanud erinevaid heuristikaid. Võib katsetada skooride arvutamise viisi, raskusi ja laua omadusi, mida arvesse võetakse. Minu lähenemisviis klastri skoori mõõtmisel peaks ühendama muid soovitusi, nagu monotoonsus ja sujuvus, kuid arenguruumi on veel.
4. Sügavuse häälestamine: Sõltuvalt mängu olekust võib proovida ka otsingu sügavust häälestada/reguleerida. Samuti saate kasutada Iteratiivne süvenev sügavus-esimene otsing algoritm, mis teadaolevalt parandab alfa-beeta pügamisalgoritmi.

Ärge unustage alla laadida JAVA koodi aadressilt Github ja katsetada. Loodan, et teile meeldis see postitus! Kui jagasite, võtke hetk, et jagada artiklit Facebookis ja Twitteris. 🙂