Tic Tac Toe Arduino'l koos AI -ga (Minimaxi algoritm): 3 sammu

2024 Autor: John Day | [email protected]. Viimati modifitseeritud: 2024-01-30 08:49

Selles juhendis näitan teile, kuidas ehitada Tic Tac Toe mäng AI abil Arduino abil. Võite mängida Arduino vastu või vaadata, kuidas Arduino enda vastu mängib.

Ma kasutan algoritmi nimega "minimax algoritm", mida saab kasutada mitte ainult Tic Tac Toe jaoks tehisintellekti loomiseks, vaid ka paljude muude mängude jaoks, nagu Four in a Row, kabe või isegi male. Sellised mängud nagu male on väga keerulised ja nõuavad palju täpsemaid algoritmi versioone. Tic Tac Toe mängu puhul saame kasutada algoritmi lihtsamat versiooni, mis on sellest hoolimata üsna muljetavaldav. Tegelikult on AI nii hea, et Arduinot on võimatu võita!

Mängu on lihtne ehitada. Teil on vaja ainult mõnda komponenti ja minu kirjutatud visandit. Lisasin ka algoritmi üksikasjalikuma selgituse, kui soovite aru saada, kuidas see toimib.

Samm: ehitage ja mängige

Mängu Tic Tac Toe ehitamiseks vajate järgmisi komponente:

• Arduino Uno
• 9 WS2812 RGB LED -i
• 9 surunuppu
• mõned juhtmed ja hüppajakaablid

Ühendage komponendid juhtmega, nagu on näidatud Fritzingi visandil. Seejärel laadige kood oma Arduinole üles.

Vaikimisi võtab Arduino esimese pöörde. Asjade natuke huvitavamaks muutmiseks valitakse esimene käik juhuslikult. Pärast esimest käiku kasutab Arduino minimaalse algoritmi parima võimaliku käigu määramiseks. Alustate uut mängu Arduino lähtestamisega.

Saate vaadata Arduino "mõtlemist", avades seeriamonitori. Iga võimaliku käigu jaoks arvutab algoritm reitingu, mis näitab, kas see käik toob Arduino võidu (väärtus 10) või kaotuse (väärtus -10) või viigi (väärtus 0).

Samuti saate vaadata Arduino enda vastu mängimist, kommenteerimata eskiisi alguses olevat rida "#define DEMO_MODE". Kui laadite muudetud visandi üles, teeb Arduino esimese käigu juhuslikult ja seejärel kasutab minimax -algoritmi, et määrata igale mängijale igal käigul parim käik.

Pange tähele, et te ei saa Arduino vastu võita. Iga mäng lõpeb viigiga või kaotate, kui teete vea. Seda seetõttu, et algoritm valib alati parima võimaliku käigu. Nagu teate, lõpeb Tic Tac Toe mäng alati viigiga, kui mõlemad mängijad ei eksi. Demorežiimis lõpeb iga mäng viigiga, sest nagu me kõik teame, ei tee arvutid kunagi vigu;-)

2. samm: Minimaxi algoritm

Algoritm koosneb kahest komponendist: hindamisfunktsioon ja otsingustrateegia. Hindamisfunktsioon on funktsioon, mis omistab tahvli positsioonidele numbrilise väärtuse. Kui positsioon on lõplik positsioon (st positsioon, kus sinine või punane mängija on võitnud või kus kumbki pole võitnud), on hindamisfunktsioon väga lihtne: Oletame, et Arduino mängib sinist ja inimene punast.. Kui positsioon on sinise jaoks võidupositsioon, määrab funktsioon sellele positsioonile väärtuse 10; kui see on punase jaoks võidupositsioon, määrab funktsioon positsioonile väärtuse -10; ja kui positsioon on viik, määrab funktsioon väärtuseks 0.

Kui on Arduino kord, soovib ta valida sammu, mis maksimeerib hindamisfunktsiooni väärtuse, sest väärtuse maksimeerimine tähendab, et ta eelistab võitu viigi ees (10 on suurem kui 0) ja eelistab viiki kaotuse asemel (0 on suurem kui -10). Analoogse argumendiga soovib vastane mängida nii, et ta minimeerib hindamisfunktsiooni väärtuse.

Mitte-lõpliku positsiooni puhul arvutab algoritm hindamisfunktsiooni väärtuse rekursiivse otsingustrateegia abil. Alates praegusest positsioonist simuleerib see vaheldumisi kõiki liigutusi, mida sinine mängija ja punane mängija saavad teha. Seda saab visualiseerida puuna, nagu diagrammil. Lõplikku positsiooni jõudes hakkab ta tagasi astuma, kandes hindamisfunktsiooni väärtuse madalamalt rekursioonitasemelt kõrgemale rekursioonitasemele. See määrab hindamisfunktsiooni väärtuste maksimaalse (kui vastavas rekursiooni etapis on sinise mängija kord) või minimaalse (kui vastavas rekursioonisammas on punase mängija kord) alumisest rekursioonitasemest positsioonile kõrgem rekursioonitase. Lõpuks, kui algoritm on tagasi astunud ja jõudnud uuesti praegusesse asendisse, võtab see käigu (või ühe käigu), millel on maksimaalne hindamisfunktsiooni väärtus.

See võib tunduda pisut abstraktne, kuid tegelikult pole see nii raske. Mõelge diagrammi ülaosas näidatud positsioonile. Esimeses rekursioonietapis on kolm erinevat sinist käiku. Sinine üritab maksimeerida hindamisfunktsiooni väärtust. Iga sinise käigu jaoks on kaks punast käiku. Punane üritab hindamisfunktsiooni väärtust minimeerida. Kaaluge käiku, kus sinine mängib paremas ülanurgas. Kui punane mängib kesklinnas, on punane võitnud (-10). Kui aga alumises keskosas mängib punane, võidab sinine järgmisel käigul (10). Niisiis, kui sinine mängib paremas ülanurgas, mängib punane keskkast, kuna see vähendab hindamisfunktsiooni väärtust. Analoogselt, kui keskmises alumises kastis mängib sinine, mängib punane uuesti keskmises kastis, kuna see minimeerib hindamisfunktsiooni. Kui aga sinine mängib keskväljal, pole vahet, mis punase käigu võtab, võidab alati sinine (10). Kuna sinine soovib hindamisfunktsiooni maksimeerida, mängib see keskses kastis, kuna selle positsiooni tulemuseks on hindamisfunktsiooni (10) suurem väärtus kui kahel teisel käigul (-10).

Samm: tõrkeotsing ja edasised sammud

Kui vajutate nuppu ja süttib mõni muu valgusdiood kui nupule vastav LED, süttib tõenäoliselt juhtmete pingel A0-A2 või 4-6 segi või ühendasite LED-id vales järjekorras.

Pange tähele ka seda, et algoritm ei pruugi alati valida käiku, mis laseb Arduino'l võimalikult kiiresti võita. Tegelikult veetsin mõnda aega algoritmi silumist, sest Arduino ei valinud käiku, mis oleks olnud võidukas käik. Mul läks natuke aega, kuni mõistsin, et see oli hoopis valinud käigu, mis tagas selle, et see võidab ühe käigu hiljem. Kui soovite, võite proovida algoritmi muuta nii, et see eelistaks alati võidukäiku hilisemale võidule.

Selle projekti võimalik laiendus oleks algoritmi kasutamine 4x4 või isegi 5x5 Tic Tac Toe jaoks AI loomiseks. Siiski arvestage, et algoritmil vajalike positsioonide arv kasvab väga kiiresti. Peate leidma viise hindamisfunktsiooni intelligentsemaks muutmiseks, määrates väärtused positsioonidele, mis ei ole lõplikud, tuginedes tõenäosusele, et positsioon on kõnealuse mängija jaoks hea või halb. Samuti võite proovida otsingut intelligentsemaks muuta, peatades rekursiooni varakult, kui käik osutub vähem väärt edasiseks uurimiseks kui alternatiivsed käigud.

Arduino ei ole ilmselt selliste laienduste jaoks parim platvorm oma piiratud mälu tõttu. Rekursioon laseb virna programmi täitmise ajal kasvada ja kui see kasvab liiga palju, võib see rikkuda programmi mälu, põhjustades krahhi või ebaregulaarset käitumist. Valisin Arduino selle projekti jaoks peamiselt seetõttu, et tahtsin näha, kas seda on võimalik teha, ja hariduslikel eesmärkidel, mitte sellepärast, et see oleks parim valik sellise probleemi jaoks.