Lautapeli Tekoäly: Minimax -algoritmi: 8 vaihetta

2024 Kirjoittaja: John Day | [email protected]. Viimeksi muokattu: 2024-01-30 09:01

Oletko koskaan miettinyt, miten tietokoneet, joita vastaan pelaat shakissa tai shakissa? Älä etsi enää kuin tämä Instructable, sillä se näyttää sinulle, kuinka tehdä yksinkertainen mutta tehokas tekoäly (AI) käyttämällä Minimax -algoritmia! Käyttämällä Minimax -algoritmia tekoäly tekee hyvin suunniteltuja ja harkittuja liikkeitä (tai ainakin jäljittelee ajatusprosessia). Voisin vain antaa sinulle tekemäni tekoälyn koodin, mutta se ei olisi hauskaa. Selitän tietokoneen valintojen logiikan.

Tässä ohjeessa opastan sinut vaiheiden tekemiseen tekoälyn luomiseksi Othellolle (AKA Reversi) pythonissa. Sinulla pitäisi olla välitön käsitys siitä, kuinka koodata pythonissa, ennen kuin ryhdyt käsittelemään tätä projektia. Tässä on muutamia hyviä verkkosivustoja, joita kannattaa tarkastella valmistautuaksesi tähän Instructable -ohjelmaan: w3schools tai learnpython. Tämän ohjeen lopussa sinulla pitäisi olla tekoäly, joka tekee laskettuja liikkeitä ja pystyy voittamaan useimmat ihmiset.

Koska tämä Instructable käsittelee ensisijaisesti tekoälyn tekemistä, en selitä kuinka suunnitella peli pythonissa. Sen sijaan annan pelin koodin, jossa ihminen voi pelata toista ihmistä vastaan ja muokata sitä niin, että voit pelata peliä, jossa ihminen pelaa tekoälyä vastaan.

Olen oppinut luomaan tämän tekoälyn Columbia SHAPEn kesäohjelman kautta. Minulla oli hauskaa siellä, joten vilkaise heidän verkkosivustoaan nähdäksesi, olisitko kiinnostunut.

Nyt kun saimme logistiikan pois tieltä, aloitetaan koodaus!

(Laitoin pari muistiinpanoa kuviin, joten muista katsoa ne)

Tarvikkeet

Tämä on helppoa:

1) Tietokone, jossa on python -ympäristö, kuten Spyder tai IDLE

2) Lataa Othello -pelin tiedostot GitHubista

3) Aivosi kärsivällisyys asennettu

Vaihe 1: Lataa tarvittavat tiedostot

Kun siirryt GitHubiin, sinun pitäisi nähdä 5 tiedostoa. Lataa kaikki 5 ja laita ne samaan kansioon. Ennen kuin aloitamme pelin, avaa kaikki tiedostot spyder -ympäristössä.

Tiedostot toimivat seuraavasti:

1) othello_gui.py Tämä tiedosto luo pelilaudan pelaajille, joilla he voivat pelata (olivatpa ne sitten ihmisiä tai tietokoneita)

2) othello_game.py Tämä tiedosto pelaa kahta tietokonetta toisiaan vastaan ilman pelilautaa ja näyttää vain pisteet ja siirtopaikat

3) ai_template.py tähän asetat kaikki koodisi tekoälysi luomiseen

4) randy_ai.py tämä on valmiiksi suunniteltu tekoäly, joka valitsee liikkeensä satunnaisesti

5) othello_shared.py joukko valmiita toimintoja, joiden avulla voit tehdä tekoälysi, esimerkiksi tarkistaa käytettävissä olevat liikkeet, pisteet tai hallituksen tilan

6) Kolme muuta tiedostoa: Puma.py, erika_5.py ja nathan.py, jotka olen tehnyt minä, Erika ja Nathan SHAPE -ohjelmasta, nämä ovat kolme erilaista tekoälyä, joilla on ainutlaatuiset koodit

Vaihe 2: Python Othellon avaaminen ja pelaaminen

Kun olet avannut kaikki tiedostot, kirjoita näytön oikeaan alakulmaan "run othello_gui.py" ja paina Enter-näppäintä IPython-konsolissa. Tai kirjoita Mac -päätelaitteeseen "python othello_gui.py" (kun olet tietysti oikeassa kansiossa). Tämän jälkeen näyttöön tulee ilmestyä taulu. Tämä tila on ihminen vs ihminen. Valo menee toiseksi ja pimeä ensin. Katso videoni, jos olet hämmentynyt. iYläreunassa on kunkin väriruudun pisteet. Jos haluat pelata, napsauta kelvollista siirtotilaa ja aseta laatta sinne ja anna tietokone vastustajallesi, joka tekee saman ja toistaa.

Jos et tiedä miten pelata Othelloa, lue nämä säännöt ultralaudan verkkosivustolta:

Musta liikkuu aina ensin. Liike tehdään asettamalla pelaajan värinen kiekko laudalle asentoon, joka "ulottuu" yhden tai useamman vastustajan kiekon ulkopuolelle. Levy tai lautasrivi on reunustettuna, kun sitä ympäröivät päistään päinvastaiset levyt. Levy voi ylittää minkä tahansa määrän levyjä yhdessä tai useammassa rivissä mihin tahansa suuntaan (vaakasuora, pystysuora, lävistäjä)…. (lopeta lukeminen heidän verkkosivuillaan)

Ero alkuperäisen pelin ja tämän python -pelin välillä on, että kun yhdelle pelaajalle ei ole jäljellä kelvollisia siirtoja, peli päättyy

Nyt kun voit pelata peliä ystävän kanssa, luomme tekoälyn, jolla voit pelata.

Vaihe 3: Minimax -algoritmi: Skenaarioiden luominen

Ennen kuin puhumme siitä, miten tämä kirjoitetaan koodiksi, käydään läpi sen takana oleva logiikka. Minimx-algoritmi on päätöksenteko-, jälkiseuranta-algoritmi, ja sitä käytetään tyypillisesti kahden pelaajan vuoropohjaisissa peleissä. Tämän AI: n tavoitteena on löytää seuraavaksi paras siirto ja seuraavat parhaat liikkeet, kunnes se voittaa pelin.

Miten algoritmi määrittäisi nyt, mikä liike on paras? Pysähdy ja mieti, miten valitsisit seuraavan liikkeen. Useimmat ihmiset valitsisivat liikkeen, joka antaisi heille eniten pisteitä, eikö? Tai jos he ajattelivat eteenpäin, he valitsisivat liikkeen, joka loisi tilanteen, jossa he voisivat saada vielä enemmän pisteitä. Jälkimmäinen ajattelutapa on tapa, jolla Minimax -algoritmi ajattelee. Se katselee kaikkia tulevia levyasennuksia ja tekee siirron, joka johtaisi eniten pisteitä.

Kutsuin tätä taaksepäin suuntautuvaksi algoritmiksi, koska se alkaa ensin luomalla ja arvioimalla kaikki tulevat hallituksen tilat ja niihin liittyvät arvot. Tämä tarkoittaa, että algoritmi pelaa peliä niin monta kuin tarvitsee (tekee liikkeet itselleen ja vastustajalleen), kunnes jokainen peliskenaario on pelattu. Jotta voimme seurata kaikkia levyn tiloja (skenaarioita), voimme piirtää puun (katso kuvia). Yllä olevan kuvan puu on yksinkertainen esimerkki Connect 4 -pelistä. Jokaista laudan kokoonpanoa kutsutaan laudan tilaksi ja sen paikkaa puussa solmuksi. Kaikki puun alareunassa olevat solmut ovat viimeiset levyn tilat kaikkien liikkeiden jälkeen. On selvää, että jotkut hallituksen tilat ovat parempia yhdelle pelaajalle kuin toiset. Joten nyt meidän on tehtävä AI valitsemaan, mihin hallituksen tilaan se haluaa päästä.

Vaihe 4: Minimax: Board Configuration -arvioiden arviointi

Jotta voimme antaa arvoja hallituksen valtioille, meidän on opittava pelaamamme pelin strategiat: tässä tapauksessa Othellon strategiat. Koska tämä peli on taistelua vastustajan ja levyjesi kääntämisestä, parhaat levyn paikat ovat vakaat ja niitä ei voi kääntää. Kulma on esimerkiksi paikka, jossa levyä asetettaessa sitä ei voi vaihtaa toiseen väriin. Paikka olisi siis erittäin arvokas. Muita hyviä paikkoja ovat laudan sivut, joiden avulla voit ottaa paljon kiviä. Tällä sivustolla on enemmän strategioita.

Nyt voimme määrittää arvot kunkin hallituksen tilan hallituksen asemille. Kun teko on tekoälyn osassa, annat tietyn määrän pisteitä sijainnista riippuen. Esimerkiksi taululla, jossa tekoälyn pala on nurkassa, voit antaa 50 pisteen bonuksen, mutta jos se olisi epäsuotuisassa paikassa, palan arvo voi olla 0. Kun olet ottanut huomioon kaikki sijainnit, määrität hallituksen tilan arvon. Jos esimerkiksi tekoälyllä on pala kulmassa, laudan tila voi saada 50 pistettä, kun taas toisella korttitilalla, jonka tekoäly on keskellä, on 10 pistettä.

Tähän on monia tapoja, ja minulla on kolme erilaista heuristiikkaa arvioidakseni levypalat. Kehotan sinua tekemään oman tyyppisen heuristisen. Latasin kolme eri tekoälyä githubiini kolmelta eri valmistajalta, joilla on kolme erilaista heuristiikkaa: Puma.py, erika5.py, nathanh.py.

Vaihe 5: Minimax -algoritmi: Parhaimman liikkeen valitseminen

Nyt olisi mukavaa, jos tekoäly voisi vain valita kaikki liikkeet päästäkseen hallituksen tilaan, jolla on korkein pisteet. Muista kuitenkin, että tekoäly valitsi myös vastustajan liikkeet, kun se loi kaikki lautatilat, ja jos vastustaja on fiksu, se ei salli tekoälyn saavuttaa korkeimpia lautapisteitä. Sen sijaan älykäs vastustaja tekisi askeleen saadakseen AI: n siirtymään alimpaan hallituksen tilaan. Algoritmissa kutsumme kahta pelaajaa maksimoivaksi pelaajaksi ja minimoivaksi pelaajaksi. Tekoäly olisi maksimoiva pelaaja, koska se haluaa saada eniten pisteitä itselleen. Vastustaja olisi minimoiva pelaaja, koska vastustaja yrittää tehdä siirron siellä, missä tekoäly saa vähiten pisteitä.

Kun kaikki levyn tilat on luotu ja arvot on määritetty levyille, algoritmi alkaa verrata kortin tiloja. Kuvissa loin puun, joka edustaa sitä, miten algoritmi valitsee liikkeensä. Jokainen haaran jako on eri liike, jonka tekoäly tai vastustaja voi pelata. Kirjoitin solmurivien vasemmalle puolelle, meneekö maksimointi vai minimointi pelaaja. Alimmalla rivillä näkyvät kaikki piirilevyjen arvot. Jokaisen solmun sisällä on numero ja nämä ovat pisteitä, jotka annamme kullekin levylle: mitä korkeammat ne ovat, sitä parempi AI: n olla.

Määritelmät: vanhempi solmu - solmu, joka tuottaa tai luo solmuja sen alle; alisolmujen alkuperä - solmut, jotka tulevat samasta vanhemmasta solmusta

Tyhjät solmut edustavat sitä, mikä tekoäly siirtää päästäkseen parhaaseen levytilaan. Se alkaa vertaamalla vasemmanpuoleisimman solmun lapsia: 10, -3, 5. Koska maksimoiva pelaaja tekisi liikkeen, se valitsisi liikkeen, joka antaisi sille eniten pisteitä: 10. Joten, valitsemme ja tallennamme sen liikkua taulukoiden pisteiden kanssa ja kirjoittaa ne pääsolmuun. Nyt kun 10 on pääsolmussa, nyt on minimoivien pelaajien vuoro. Solmu, johon vertaamme 10, on kuitenkin tyhjä, joten meidän on arvioitava solmu ensin, ennen kuin minimoiva pelaaja voi valita. Joten palaamme maksimoivan pelaajan vuoroon ja vertaamme viereisen solmun lapsia: 8, -2. Maksimointi valitsee 8 ja kirjoitamme sen tyhjään ylätason solmuun. Nyt kun algoritmi on täyttänyt tyhjät tilat sen yläpuolella olevan solmun lapsille, minimoiva pelaaja voi verrata näitä lapsia - 10 ja 8 ja valita 8. Algoritmi toistaa tämän prosessin, kunnes koko puu on täytetty. Tämän esimerkin lopussa meillä on pisteet 8. Se on korkein laudan tila, jonka tekoäly voi pelata olettaen, että vastustaja pelaa optimaalisesti. Joten tekoäly valitsee ensimmäisen siirron, joka johtaa kahdeksan laudan tilaan, ja jos vastustaja pelaa optimaalisesti, tekoälyn tulee pelata kaikki liikkeet päästäkseen lautatilaan 8. (Seuraa kuvieni huomautuksia)

Tiedän, että se oli paljon. Jos olet yksi niistä tyypeistä, joiden täytyy saada joku puhumaan kanssasi ymmärtääksesi jotain, tässä on muutamia videoita, jotka katselin auttaakseni ymmärtämään tämän takana olevan ajatuksen: 1, 2, 3.

Vaihe 6: Minimax -algoritmi: Pseudokoodi

Kun olet ymmärtänyt minimax -algoritmin logiikan, katso tämä pseudokoodi (toiminnot, jotka ovat universaaleja kaikille koodeille) wikipediasta:

toiminto minimax (solmu, syvyys, maksimoiva pelaaja) on

jos syvyys = 0 tai solmu on päätesolmu

palauttaa solmun heuristisen arvon

jos maksimoiPlayer sitten

arvo: = −∞

jokaiselle solmun lapselle

arvo: = max (arvo, minimix (lapsi, syvyys - 1, EPÄTOSI))

palautusarvo

else (* minimoi pelaaja *)

arvo: = +∞

jokaiselle solmun lapselle

arvo: = min (arvo, minimix (lapsi, syvyys - 1, TOSI))

palautusarvo

Tämä on rekursiivinen toiminto, eli se kutsuu itseään uudestaan ja uudestaan, kunnes se saavuttaa pysähdyskohdan. Ensinnäkin funktio ottaa kolme arvoa, solmu, syvyys ja sen vuoro. Solmun arvo on paikka, josta haluat ohjelman aloittavan haun. Syvyys on se, kuinka pitkälle haluat ohjelman hakevan. Esimerkiksi puunäkymässäni sen syvyys on 3, koska se etsi kaikki levyn tilat kolmen liikkeen jälkeen. Haluamme tietysti, että tekoäly tarkistaa jokaisen laudan tilan ja valitsee voittavan voiton, mutta useimmissa peleissä, joissa on tuhansia ellei miljoonia pelikokoonpanoja, kannettava tietokone kotona ei pysty käsittelemään kaikkia näitä kokoonpanoja. Rajoitamme siis tekoälyn hakusyvyyttä ja siirrämme sen parhaaseen levytilaan.

Tämä pseudokoodi toistaa prosessin, jonka selitin kahdessa edellisessä vaiheessa. Otetaan nyt tämä askel pidemmälle ja korjataan tämä python -koodissa.

Vaihe 7: Tee tekoälysi Ai_template.py avulla

Ennen kuin katsot Minimax-AI-koodiani, yritä tehdä oma tekoäly ai_template.py-tiedoston ja pseudokoodin avulla, josta puhuimme viimeisessä vaiheessa. Ai -mallissa on kaksi toimintoa nimeltä: def minimax_min_node (taulu, väri) ja def minimax_max_node (board, color). Sen sijaan, että minimax -funktio kutsuisi itseään rekursiivisesti, meillä on kaksi eri funktiota, jotka kutsuvat toisiaan. Jos haluat luoda heuristiikan arvioidaksesi hallituksen tiloja, sinun on luotava oma toiminto. Othello_shared.py -tiedostossa on valmiita toimintoja, joiden avulla voit rakentaa tekoälysi.

Kun sinulla on tekoäly, kokeile käyttää sitä, randy_ai.py. Jos haluat ajaa kaksi aisia toisiaan vastaan, kirjoita Mac -päätelaitteeseen "python othello_gui.py (lisää ai -tiedoston nimi).py (lisää tiedoston nimi).py" tai kirjoita "run othello_gui.py (lisää ai -tiedoston nimi).py) (lisää tiedoston nimi).py "ja varmista, että olet oikeassa hakemistossa. Katso myös videostani tarkat vaiheet.

Vaihe 8: Aika taistella tekoälyä vastaan

Hanki nyt joukko tietokoneystäviäsi ja tee heidät suunnittelemaan oma tekoäly! Sitten voit tehdä kilpailun ja saada tekoälysi heittämään sen ulos. Toivottavasti, vaikka et pystyisi rakentamaan omaa tekoälyäsi, pystyit ymmärtämään, kuinka minimax -algoritmi toimii. Jos sinulla on kysyttävää, voit lähettää kysymyksiä alla oleviin kommentteihin.