Strategiapelien pelaaminen Minimax-algoritmilla

Tässä oppitunnissa tutkitaan suosittua minimx- algoritmia . Opimme myös joitain sen ystävällisiä naapuruston lisäominaisuuksia, kuten heuristiset pisteet , iteratiivinen syventäminen ja alfa-beeta-karsinta . Näitä tekniikoita käyttämällä voimme luoda joustavamman ja tehokkaamman peliagentin. Se pystyy kilpailemaan monissa haasteissa, mukaan lukien strategiapeli Isolation.

Edellisessä viestissä How to Win Sudoku opimme kuinka opettaa tietokoneita ratkaisemaan Sudoku-palapeli. Jos et ole lukenut sitä, jatka ja lue se nopeasti. Mutta se oli oikeastaan ​​vain tapa kastaa jalkamme, ennen kuin sukellat kehittyneempiin peliagenttien menetelmiin. Varsinkin ne menetelmät, jotka voivat tehdä strategisia liikkeitä vastustajaa vastaan!

Älä jää hukkaan

Isolation (tai Isola) on vuoropohjainen strateginen lautapeli, jossa kaksi pelaajaa yrittää rajoittaa vastustajansa 7x7-ruutuun. Lopulta he eivät voi enää tehdä liikettä (eristää heidät).

Jokaisella pelaajalla on yksi pala, jonka he voivat liikkua kuin kuningatar shakissa - ylös-alas, vasemmalta-oikealta ja lävistäjä. Kappaleita voidaan siirtää kolmella tavalla -

  1. He eivät voi sijoittaa kappalettaan jo vieraillulle aukiolle.
  2. He eivät voi ylittää jo käyneitä neliöitä (niiden lävistäminen diagonaalisesti on OK).
  3. He eivät voi ylittää toistensa kappaletta.

Yllä olevasta kuvasta näet mustista neliöistä, että molemmat pelaajat ovat asettaneet nappulansa laudan eri osiin. Mutta pelin edetessä se osoittaa, että keltaisella pelaajalla on vielä kolme mahdollista siirtoa. Ylhäällä ja oikealla, oikealla yksi neliö ja oikealla kaksi neliötä. Mutta sininen soitin on poissa vaihtoehdoista. Siksi keltainen pelaaja on voittaja tässä.

Nyt tämä saattaa tuntua yksinkertaiselta peliltä - ja ollakseni rehellinen, se on. Ei ole kuin pelaisimme pokeria tai Starcraftia. Silti on vielä valtava määrä mahdollisia liikkeitä, joita kukin pelaaja voi tehdä milloin tahansa pelin aikana.

Sudoku-kaltaisissa pulmissa on "vastaus", jonka haluamme ratkaista. Strategiapeleihin ei kuitenkaan ole vastausta.

Pelaamme toista vastustajaa vastaan ​​- kuten henkilöä, tietokonetta tai kissan etsivää. Tämä vaatii strategiaa ja jonkin verran ajatusta siitä, miten peli voi kehittyä, kun se liikkuu.

Tällaiset pelit voivat kehittyä ja tuottaa absurdin määrän mahdollisia tuloksia. Joten meidän on mietittävä, kuinka voimme valita parhaan mahdollisen liikkeen kuluttamatta aikaa, joka kissaa kesti maan asuttamiseen.

Okei, ei enää kissoja!

Mahtava Minimax ja ystävät

Nyt kun tiedät kuinka pelata eristämistä, katsotaanpa kuinka voimme käyttää minimx- algoritmia; katkottua tekoälyyhteisössä. Tarkastelemme myös heuristisia pisteitä , iteratiivista syventämistä ja alfa-beeta-karsimista . Yhdessä näiden kanssa voimme rakentaa kilpailukykyisen tekoälyn.

Minimax

Minimix-algoritmi on erittäin suosittu tekoälyjen agenttien opettamiseen vuoropohjaisten strategiapelien pelaamisessa. Syynä on se, että siinä otetaan huomioon kaikki mahdolliset liikkeet, joita pelaajat voivat tehdä milloin tahansa pelin aikana. Näiden tietojen avulla se yrittää minimoida vastustajan pelaajan edun ja maksimoida agentin jokaisessa käännöksessä, jonka tekoälyagentti saa pelata.

Kuinka tämä näyttää?

No, samalla tavalla kuin tekoälyn agentti pelaisi Sudokun kaltaista peliä, voimme mallintaa seuraavat mahdolliset liikkeet, jotka kukin pelaaja voi tehdä hakupuun kautta . Meidän on kuitenkin käytettävä hakupuuta, jonka leveys vaihtelee - tai toisin sanoen puutason leveys. Syynä on se, että jokainen pelaaja voi tehdä vaihtelevan määrän liikkeitä milloin tahansa pelin aikana.

Yllä esitetty puu edustaa seuraavia siirtoja, jotka ovat käytettävissä eristyspelin aikana. Siinä on 2x3 ruudukko, jolloin oikean alakulman neliö on saavuttamaton. Kuten näette, kaksi pelaajaa ovat sininen ympyrä ja punainen risti.

Puun yläosa (juurisolmu) kuvaa punaisen pelaajan tekemää liikettä. Keskitaso kuvaa sinisen pelaajan seuraavia mahdollisia liikkeitä. Ja kolmas taso kuvaa punaisen pelaajan mahdollisia liikkeitä, kun otetaan huomioon sinisen pelaajan edellinen liike.

Jokaisella puun pelitilalla tai solmulla on tietoa siitä, kenellä pelaajalla on eniten hyötyä mahdollisesta liikkeestä.

Nyt saatat miettiä, mitä helvettiä ne kolmiot ovat jokaisen liikkeen alapuolella?

Alaspäin suuntautuva kolmio edustaa puussa sijaintia, jossa minimx minimoi vastustajan edun. Kun taas ylöspäin olevat kolmiot ovat paikkoja, joissa minimx maksimoi agentin edun.

Mutta minimax voi tietää kummankin pelaajan edun vain, jos se tietää puun polut, jotka johtavat kummankin pelaajan voittoon. Tämä tarkoittaa, että minimxin on kuljettava puun pohjalle jokaisen mahdollisen siirtosarjan kohdalla. Seuraavaksi sen on annettava jokin pisteet (esim. +1 voitolle ja -1 häviölle) ja levitettävä nämä luvut puun läpi. Tällä tavalla jokaisella puun pelitilalla tai solmulla on tietoa siitä, kenellä pelaajalla on eniten hyötyä mahdollisesta liikkeestä.

Tässä kuvassa voimme tehdä muutaman havainnon. Ensimmäinen minimx antaa numeron lopullisille pelituloksille lehtisolmuissa . Sitten se levittää niitä ylöspäin puun läpi ja suorittaa minimoinnit matkalla. Kun minimax on saanut puun täytettyä, se tietää tekoälyn vuorollaan, mitkä liikkeet johtavat todennäköisesti voittoon tai tappioon.

Toinen taso juurisolmun jälkeen näyttää sinisen soittimen (tekoälyagenttimme) seuraavat mahdolliset siirrot. Edustajamme haluaa maksimoida käytettävissä olevat pisteet vuoronsa aikana. Joten se valitsee liikkeen, joka on edustettuna oikeassa reunassa olevassa solmussa juurisolmun jälkeen. Super siisti!

Mutta onko järkevää määrittää pelituloksille vain +1 tai -1? Eikö tässä pisteessä tulisi ottaa huomioon, miten peli voitetaan tai häviää?

Spoilerivaroitus: vastaus on kyllä!

Heuristiset tulokset

Strategiapelien maailmassa heuristinen tulos on olennaisesti subjektiivinen arvo, jonka annamme jollekin pelitilalle. Tämä arvo perustuu ymmärrykseemme pelin voittamisesta ja häviämisestä. Valitsemalla hyvin harkitun heuristisen pistemäärän voimme opettaa tekoälyasiamiehellemme kuinka parhaiten valita seuraavat liikkeensa pelatessaan peliä Isolation.

Nyt voimme luultavasti rajattoman määrän heuristisia pisteitä. Mutta tässä tarkastelemme vain muutamia niistä lukuun ottamatta naiiveja pisteitä +1 ja -1.

Yksi idea voisi olla laskea kaikki seuraavat mahdolliset liikkeet, jotka jokaisella pelaajalla on milloin tahansa, koska useammat mahdolliset liikkeet tarkoittavat vähemmän mahdollisuuksia eristää. Kutsumme tätä avoimen liikkeen pisteeksi (OMS) .

Toinen idea voisi olla käyttää OMS: stä saatua arvoa ja vähentää mahdollisten seuraavien mahdollisten liikkeiden määrä vastustajalla. Syynä on se, että jokainen pelaaja haluaa lisätä siirtojen määrää vähentäen samalla vastustajansa määrää. Kutsumme tätä parannetuksi pisteeksi (IS) .

Yllä olevassa kuvassa esitetään voittokerrat monissa simuloiduissa eristyspeleissä, joita pelataan tekoälyagenttien välillä käyttäen erilaisia ​​heuristisia pisteitä. Nyt voit nähdä, kuinka erilaiset tulokset tekivät varsinaisen pelin aikana. Mutta oli joitain heuristisia tuloksia, jotka ylittivät keksimämme tulokset

Mielenkiintoista on, että kaksi parasta ovat melkein täsmälleen samat kuin paremmat pisteet. Kutsumme heitä aggressiivisiksi parannetuiksi pisteiksi (AIS) ja erittäin aggressiivisiksi parannetuiksi pisteiksi (SAIS) . Mutta näiden pisteiden ja alkuperäisen välillä on pieni ero. Kaksi ensimmäistä pistettä käyttävät kerrointa kaksi ja kolme arvoon, josta vähennät (vastustajan käytettävissä olevien siirtojen lukumäärä) laskettaessa parempaa pistemäärää.

Voit löytää optimaalisen "aggressiivisen tekijän", jota käytetään laskettaessa tätä pistemäärää!

Toinen spoilerihälytys - parempia arvoja on olemassa.

Mutta entä jos keksimme heuristisen pistemäärän, jonka laskeminen vie paljon aikaa? Entä jos puu on valtava? Onko AI-agentillamme tarpeeksi aikaa löytää seuraavat parhaat liikkeet, vaikka hän onkin riittävän reagoiva pelin aikana?

Iteratiivinen syventäminen

Nyt tiedämme, että tekoälyagenttimme voi mallintaa kaikki mahdolliset liikkeet hakupuun ja sen solmujen vastaavan heuristisen pistemäärän avulla. Mutta valitettavasti, kun pelataan eristämistä, puu on massiivinen. Puun etsiminen ja näiden arvojen laskeminen vie enemmän aikaa kuin isosta bangista on kulunut vuosia!

Syötä iteratiivinen syventäminen - peliagenttien ajanhallintastrategia. Tämän menetelmän avulla voimme lyhentää laskenta- ja hakuaikaa valitsemallemme maksimiaikaan. Tällä tavalla tekoälyagenttimme voi vastata ainakin yhtä nopeasti kuin ihminen voisi.

Mutta miten iteratiivinen syventäminen toimii?

Sen avulla minimx voi liikkua tasolta tasolle ja laskea heuristisia pisteitä tiettyyn aikarajaan saakka. Kun tämä aikaraja on saavutettu, tekoälyn agentti joutuu käyttämään parhaan löytämänsä liikkeen siirtyessään yhä syvemmälle puuhun.

Nyt tämä antaa jonkinlaisen käsityksen siitä, kuinka vaikeaa se voi olla. Tekoälyagentin luominen, joka on tarpeeksi älykäs ja reagoiva strategiapeleihin, voi olla melko hankalaa, jopa tekoälyvelhoille. Varsinkin jos tällaiset pelit sisältävät mahdollisuuksien maailman.

Valitettavasti tekoälyn edustajan "kuvittelemisen" eteenpäin siirtojen määrä on rajallinen. Joten on mahdollista, että se voi tehdä päätöksen, joka johtaa sen kuolemaan. Tämä on tunnettu ilmiö, jota kutsutaan horisonttiefektiksi . Mutta meidän on silti tarkasteltava epäilemättä tehokkainta aikaviivausalgoritmia, jota käytetään puiden etsinnässä.

Alfa-beeta-karsiminen

Okei, nämä ovat rusinoita eivätkä luumuja, mutta silti - miten nämä olivat koskaan asia? Tarkoitan vakavasti rusiniblues-ryhmää?

Olet ehkä jo arvannut, että alfa-beeta-karsinnalla ei ole mitään tekemistä luumujen kanssa ja enemmän hakupuun koon (karsimisen) pienentämisestä. Kun meillä on erittäin suuri hakupuu, käy ilmi, että ei aina tarvitse kulkea jokaisen solmun läpi käytettäessä minimxiä.

Meidän on annettava minimxille kyky lopettaa puun tietyn alueen etsiminen, kun se löytää taatun minimin tai maksimin tietyltä tasolta.

Jos voimme tehdä sen, se voi vähentää huomattavasti tekoälyn edustajamme vasteaikaa ja parantaa suorituskykyä.

Kuinka alfa-beeta-karsinta toimii?

Minimix-algoritmi liikkuu puun läpi käyttäen syvyyshakua. Se tarkoittaa, että se kulkee puun läpi vasemmalta oikealle ja kulkee aina syvimpään, mihin se voi mennä. Sitten se löytää arvot, jotka on määritettävä solmuille suoraan sen yläpuolelle, katsomatta koskaan puun muita oksia.

Alfa-beeta-karsinta antaa minimxille mahdollisuuden tehdä yhtä hyviä päätöksiä kuin minimx voisi tehdä yksin, mutta korkeammalla suorituskyvyllä.

Tarkastellaan seuraavaa kuvaa, jossa meillä on puu, jolla on eri pisteet kullekin solmulle. Jotkut solmut on varjostettu punaisella, mikä tarkoittaa, että niitä ei tarvitse tarkistaa.

Puun vasemmassa alakulmassa minimx tarkastelee arvoja 5 ja 6 alimmalla maksimitasolla. Se määrittää, että 5 on osoitettava sen yläpuolelle olevalle minitasolle. Käydä järkeen.

Mutta kun tarkastellaan 7 ja 4 oikean maksimitason haaraa, se ymmärtää, että yllä olevalle min-tason solmulle on annettava maksimiarvo 4. Koska toinen maksimitaso heti ensimmäisen min-tason yläpuolella vie maksimiarvon välillä 5 ja korkeintaan 4, on selvää, että se valitsee 5. Tämän jälkeen se jatkaisi puun kulkua suorittaakseen saman tarkan toiminnon puun muissa oksissa.

Alla on minimx-algoritminen esitys alfa-beeta-karsimisella.

Tämän menetelmän käyttö tarjoaa helpon tavan vähentää tekoälyhenkilöstön hakutilaa. Tällä tavalla alfa-beeta-karsinta antaa minimxille mahdollisuuden tehdä hyviä päätöksiä, jotka minimax voisi tehdä yksin, mutta korkeammalla suorituskyvyllä.

Isola-ter

Olemme tutkineet, kuinka rakentaa oma tekoälyagentti, joka voi pelata Isolation-peliä melko kilpailukykyisellä tasolla. Minmax-algoritmia käyttämällä näimme, kuinka tekoälyagentti voi mallintaa pelin ja tehdä päätöksiä heurististen pisteiden perusteella. Opimme myös määrittämään tarkkaan määritellyn heuristisen tehtävän (eristäminen).

Mutta huomasimme myös, että olisi liian laskennallisesti intensiivistä antaa minimaxin juosta villinä. Joten meidän piti käyttää tekniikoita, kuten iteratiivinen syventäminen ja alfa-beeta-karsiminen. Nämä pakottavat tekoäly agenttimme keksimään seuraavan siirron kohtuullisen ajan kuluessa. Mutta entä jos haluamme, että tekoälyagenttimme voittoaste olisi korkeampi, vaikka olisimme ainakin yhtä reagoivia kuin ihminen?

No, on olemassa muitakin tekniikoita, joita voimme tutkia agenttimme voittoprosentin ja vasteajan lisäämiseksi. Koskimme ajatusta heurististen pisteiden parametrien säätämisestä (muista "aggressiivinen tekijä"?). Voisimme jopa keksiä heuristisen pistemäärän, joka on räätälöity paremmin Isolationin pelaamiseen.

On myös heijastavia ominaisuuksia, jotka liittyvät mahdollisiin siirtoihin eristyslevyllä. Nämä käyvät ilmi, kun analysoimme täysin asuttua hakupuuta, mikä antaisi meille mahdollisuuden leikata paljon oksia hakupuusta. Lisäksi, jos päivitämme laitteistomme, tekoälyagenttimme olisi nopeampi - ja siten pystyisi tutkimaan enemmän mahdollisuuksia.

Jos haluat päästä käsiksi yksityiskohtiin, kuinka tämä toteutetaan itse, tutustu koodiin, jonka kirjoitin ongelman ratkaisemiseksi Udacity-tekoälyn nanodegree-laitteelleni. Löydät sen GitHub-reposta.

Hei, olen Grant! Olen freelance dev ja kvantti. Katso verkkosivustoni osoitteessa //freelancequant.com. Kippis!