Tic Tac Toe Arduinolla tekoälyllä (Minimax -algoritmi): 3 vaihetta

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

Tässä ohjeessa näytän sinulle, kuinka rakentaa Tic Tac Toe -peli AI: llä Arduinon avulla. Voit joko pelata Arduinoa vastaan tai katsella Arduinoa itseään vastaan.

Käytän algoritmia nimeltä "minimax -algoritmi", jota voidaan käyttää paitsi tekoälyn rakentamiseen Tic Tac Toe: lle, myös moniin muihin peleihin, kuten Four in a Row, shakki tai jopa shakki. Shakin kaltaiset pelit ovat hyvin monimutkaisia ja vaativat paljon hienostuneempia versioita algoritmista. Tic Tac Toe -pelissämme voimme käyttää algoritmin yksinkertaisinta versiota, joka on kuitenkin melko vaikuttava. Itse asiassa tekoäly on niin hyvä, että on mahdotonta voittaa Arduinoa!

Peli on helppo rakentaa. Tarvitset vain muutamia komponentteja ja luonnoksen, jonka olen kirjoittanut. Lisäsin myös tarkemman selityksen algoritmille, jos haluat ymmärtää, miten se toimii.

Vaihe 1: Rakenna ja pelaa

Tic Tac Toe -pelin rakentamiseen tarvitset seuraavat komponentit:

• Arduino Uno
• 9 WS2812 RGB -LEDiä
• 9 painonappia
• joitakin johto- ja hyppyjohtoja

Johdotkaa komponentit Fritzing -luonnoksen mukaisesti. Lataa sitten koodi Arduinoosi.

Oletuksena Arduino ottaa ensimmäisen kierroksen. Jotta asiat olisivat hieman mielenkiintoisempia, ensimmäinen siirto valitaan sattumanvaraisesti. Ensimmäisen siirron jälkeen Arduino määrittää minimax -algoritmin parhaan mahdollisen liikkeen määrittämiseksi. Aloitat uuden pelin nollaamalla Arduinon.

Voit katsella Arduinon "ajattelevan" avaamalla sarjamonitorin. Jokaiselle mahdolliselle liikkeelle algoritmi laskee arvosanan, joka osoittaa, johtaako tämä siirto voittoon (arvo 10) tai tappioon (arvo -10) Arduinolle tai tasapeliin (arvo 0).

Voit myös katsoa Arduinon pelaavan itseään vastaan poistamalla kommentin "#define DEMO_MODE" luonnoksen alussa. Jos lataat muokatun luonnoksen, Arduino tekee ensimmäisen siirron satunnaisesti ja käyttää sitten minimx -algoritmia määrittääkseen parhaan liikkeen jokaiselle pelaajalle jokaisessa vuorossa.

Huomaa, että et voi voittaa Arduinoa vastaan. Jokainen peli päättyy tasapeliin tai häviät, jos teet virheen. Tämä johtuu siitä, että algoritmi valitsee aina parhaan mahdollisen liikkeen. Kuten ehkä tiedät, Tic Tac Toe -peli päättyy aina tasapeliin, jos molemmat pelaajat eivät erehdy. Demotilassa jokainen peli päättyy tasapeliin, koska kuten me kaikki tiedämme, tietokoneet eivät koskaan tee virheitä;-)

Vaihe 2: Minimax -algoritmi

Algoritmi koostuu kahdesta osasta: arviointitoiminto ja hakustrategia. Arviointitoiminto on toiminto, joka antaa numeerisen arvon laudan paikoille. Jos asema on lopullinen (eli paikka, jossa joko sininen pelaaja tai punainen pelaaja on voittanut tai jossa kumpikaan pelaaja ei ole voittanut), arviointitoiminto on hyvin yksinkertainen: Oletetaan, että Arduino pelaa sinistä ja ihminen pelaa punaista.. Jos asema on sinisen voittava asema, funktio antaa sille arvon 10; jos se on punaisen voittava asema, funktio antaa sijalle arvon -10; ja jos paikka on tasapeli, funktio antaa arvon 0.

Kun on Arduinon vuoro, se haluaa valita siirron, joka maksimoi arviointitoiminnon arvon, koska arvon maksimointi tarkoittaa sitä, että se pitää parempana voittoa kuin tasapeli (10 on suurempi kuin 0) ja pitää tasapeliä häviön sijaan (0 on suurempi kuin -10). Vastaavalla argumentilla vastustaja haluaa pelata niin, että hän minimoi arviointitoiminnon arvon.

Ei-lopulliselle sijainnille algoritmi laskee arviointitoiminnon arvon rekursiivisen hakustrategian avulla. Nykyisestä sijainnista lähtien se vuorotellen simuloi kaikkia sinisen ja punaisen pelaajan liikkeitä. Tämä voidaan visualisoida puuna, kuten kaaviossa. Kun se saavuttaa lopullisen asennon, se alkaa astua taaksepäin ja siirtää arviointitoiminnon arvon alemmalta rekursiotasolta korkeammalle rekursiotasolle. Se määrittää enimmäismäärän (jos vastaavassa rekursiovaiheessa on sinisen pelaajan vuoro) tai vähimmäisarvon (jos vastaavassa rekursiovaiheessa on punaisen pelaajan vuoro) arviointitoiminnon arvoista alemmalta rekursiotasolta asemalle korkeampi rekursiotaso. Lopuksi, kun algoritmi on lopettanut askeleen taaksepäin ja saapunut uudelleen nykyiseen paikkaan, se ottaa sen liikkeen (tai yhden liikkeen), jolla on suurin arviointitoiminnon arvo.

Tämä saattaa kuulostaa hieman abstraktilta, mutta se ei itse asiassa ole niin vaikeaa. Harkitse kaavion yläosassa näkyvää asentoa. Ensimmäisessä rekursiovaiheessa on kolme erilaista sinistä liikettä. Sininen yrittää maksimoida arviointitoiminnon arvon. Jokaisella sinisellä otettavalla liikkeellä on kaksi punaista liikettä. Punainen yrittää minimoida arviointitoiminnon arvon. Harkitse siirtoa, jossa sininen soi oikeassa yläkulmassa. Jos punainen on keskellä, punainen on voittanut (-10). Jos toisaalta punainen soi keskimmäisessä alalaatikossa, sininen voittaa seuraavassa siirrossa (10). Joten jos sininen soi oikeassa yläkulmassa, punainen tulee keskimmäiseen ruutuun, koska se minimoi arviointitoiminnon arvon. Vastaavasti, jos sininen soi keskimmäisessä alalaatikossa, punainen soi jälleen keskellä, koska se minimoi arviointitoiminnon. Jos toisaalta sininen pelaa keskikentässä, ei ole väliä, mikä punaisen liikkeen ottaa, sininen voittaa aina (10). Koska sininen haluaa maksimoida arviointitoiminnon, se soittaa keskellä olevaan ruutuun, koska tämä sijainti johtaa suurempaan arviointitoiminnon arvoon (10) kuin kaksi muuta liikettä (-10).

Vaihe 3: Vianmääritys ja lisävaiheet

Jos painat painiketta ja eri merkkivalo syttyy kuin sitä vastaava valo, luultavasti joko olet sekoittanut johdot nastoissa A0-A2 tai 4-6 tai liitit LEDit väärässä järjestyksessä.

Huomaa myös, että algoritmi ei välttämättä aina valitse liikettä, joka antaa Arduinon voittaa mahdollisimman nopeasti. Itse asiassa vietin jonkin aikaa algoritmin virheenkorjauksessa, koska Arduino ei valinnut liikettä, joka olisi ollut voittava siirto. Kesti jonkin aikaa, ennen kuin tajusin, että se oli sen sijaan valinnut liikkeen, joka takaa, että se voittaa yhden siirron myöhemmin. Jos haluat, voit yrittää muokata algoritmia siten, että se suosii aina voittavaa siirtoa myöhempään voittoon.

Tämän projektin mahdollinen jatke olisi algoritmin käyttäminen tekoälyn rakentamiseen 4x4 tai jopa 5x5 Tic Tac Toe. Huomaa kuitenkin, että algoritmin tutkittavien paikkojen määrä kasvaa erittäin nopeasti. Sinun on löydettävä tapoja tehdä arviointitoiminnasta älykkäämpi määrittelemällä arvot positioille, jotka eivät ole lopullisia, sen todennäköisyyden perusteella, että tilanne on hyvä tai huono kyseiselle pelaajalle. Voit myös yrittää tehdä hausta älykkäämmän pysäyttämällä rekursion aikaisin, jos siirto osoittautuu vähemmän tutkimisen arvoiseksi kuin vaihtoehtoiset liikkeet.

Arduino ei luultavasti ole paras alusta tällaisille laajennuksille sen rajoitetun muistin vuoksi. Rekursio antaa pinon kasvaa ohjelman suorittamisen aikana, ja jos pino kasvaa liikaa, se voi vioittaa ohjelmamuistia ja johtaa kaatumisiin tai virheelliseen käyttäytymiseen. Valitsin Arduinon tähän projektiin pääasiassa siksi, että halusin nähdä, voidaanko se tehdä ja opetustarkoituksiin, ei siksi, että se olisi paras valinta tällaiseen ongelmaan.