Turinys:
2025 Autorius: John Day | [email protected]. Paskutinį kartą keistas: 2025-01-13 06:57
Šioje instrukcijoje aš jums parodysiu, kaip sukurti „Tic Tac Toe“žaidimą su AI naudojant „Arduino“. Galite žaisti prieš „Arduino“arba žiūrėti, kaip „Arduino“žaidžia prieš save.
Aš naudoju algoritmą, vadinamą „minimax algoritmu“, kuris gali būti naudojamas ne tik kuriant „Tic Tac Toe“AI, bet ir įvairiems kitiems žaidimams, tokiems kaip „Four in a Row“, šaškės ar net šachmatai. Tokie žaidimai kaip šachmatai yra labai sudėtingi ir reikalauja daug patobulintų algoritmo versijų. Savo žaidimui „Tic Tac Toe“galime naudoti paprasčiausią algoritmo versiją, kuri vis dėlto yra gana įspūdinga. Tiesą sakant, AI yra toks geras, kad neįmanoma įveikti „Arduino“!
Žaidimą lengva sukurti. Jums reikia tik kelių komponentų ir eskizo, kurį parašiau. Taip pat pridėjau išsamesnį algoritmo paaiškinimą, jei norite suprasti, kaip jis veikia.
1 žingsnis: kurkite ir žaiskite
Norėdami sukurti „Tic Tac Toe“žaidimą, jums reikės šių komponentų:
- „Arduino Uno“
- 9 WS2812 RGB šviesos diodai
- 9 mygtukai
- kai kurie laidai ir jungiamieji kabeliai
Prijunkite komponentus, kaip parodyta Fritzing eskize. Tada įkelkite kodą į „Arduino“.
Pagal numatytuosius nustatymus „Arduino“žengia pirmą posūkį. Kad viskas būtų šiek tiek įdomiau, pirmasis žingsnis pasirenkamas atsitiktinai. Po pirmojo ėjimo „Arduino“naudoja minimumx algoritmą, kad nustatytų geriausią įmanomą ėjimą. Pradedate naują žaidimą iš naujo nustatydami „Arduino“.
Galite stebėti „Arduino“mąstymą, atidarę serijinį monitorių. Kiekvienam įmanomam žingsniui algoritmas apskaičiuoja reitingą, nurodantį, ar dėl šio žingsnio „Arduino“laimės (vertė 10), ar pralaimės (vertė -10), ar lygiosiomis (vertė 0).
Taip pat galite žiūrėti, kaip „Arduino“žaidžia prieš save, pačioje eskizo pradžioje nekomentuodami eilutės „#define DEMO_MODE“. Jei įkelsite modifikuotą eskizą, „Arduino“pirmą žingsnį atliks atsitiktinai, o tada naudodamas „minimumx“algoritmą nustatys geriausią kiekvieno žaidėjo ėjimą kiekviename ėjime.
Atminkite, kad negalite laimėti prieš „Arduino“. Kiekvienas žaidimas baigsis lygiosiomis arba pralaimėsite, jei suklysite. Taip yra todėl, kad algoritmas visada pasirenka geriausią įmanomą žingsnį. Kaip žinote, „Tic Tac Toe“žaidimas visada baigsis lygiosiomis, jei abu žaidėjai neklysta. Demo režimu kiekvienas žaidimas baigiasi lygiosiomis, nes, kaip visi žinome, kompiuteriai niekada neklysta;-)
2 žingsnis: „Minimax“algoritmas
Algoritmą sudaro du komponentai: vertinimo funkcija ir paieškos strategija. Vertinimo funkcija yra funkcija, priskirianti skaitinę vertę lentos pozicijoms. Jei pozicija yra galutinė pozicija (ty pozicija, kurioje laimėjo mėlynasis arba raudonasis žaidėjas arba niekas nelaimėjo), vertinimo funkcija yra labai paprasta: tarkime, „Arduino“žaidžia mėlynai, o žmogus - raudonai. Jei pozicija yra laimėjusi mėlynos spalvos pozicija, funkcija šiai pozicijai priskiria 10 reikšmę; jei tai laimėjusi raudonos spalvos pozicija, funkcija priskiria pozicijai reikšmę -10; o jei padėtis lygi, funkcija priskiria 0 reikšmę.
Kai ateina „Arduino“eilė, jis nori pasirinkti ėjimą, kuris maksimaliai padidina vertinimo funkcijos vertę, nes maksimaliai padidinus vertę, pirmenybė teikiama pergalei, o ne lygiosioms (10 yra daugiau nei 0), o lygiosioms - pralaimėjimui (0 yra didesnis nei -10). Analogišku argumentu priešininkė nori žaisti taip, kad sumažintų vertinimo funkcijos vertę.
Ne galutinei pozicijai algoritmas apskaičiuoja vertinimo funkcijos vertę pagal rekursinę paieškos strategiją. Pradedant nuo dabartinės padėties, jis pakaitomis imituoja visus judesius, kuriuos gali atlikti mėlynas ir raudonas žaidėjas. Tai galima vizualizuoti kaip medį, kaip parodyta diagramoje. Kai jis pasiekia galutinę padėtį, jis pradeda atsitraukti, perkeldamas vertinimo funkcijos vertę iš žemesnio rekursijos lygio į aukštesnį rekursijos lygį. Jis priskiria maksimalią (jei atitinkamame rekursijos etape - mėlynojo žaidėjo eilė) arba mažiausią (jei atitinkamame rekursijos etape - raudonojo žaidėjo eilė) vertinimo funkcijos reikšmes iš žemesnio rekursijos lygio į padėtį aukštesnis rekursijos lygis. Galiausiai, kai algoritmas baigia atsitraukti ir vėl pasiekia dabartinę padėtį, jis ima tą judesį (arba vieną iš judesių), kuris turi didžiausią vertinimo funkcijos vertę.
Tai gali atrodyti šiek tiek abstrakčiai, tačiau iš tikrųjų tai nėra taip sunku. Apsvarstykite diagramos viršuje parodytą padėtį. Pirmajame rekursijos etape yra trys skirtingi mėlynos spalvos judesiai. Mėlyna mėgina maksimaliai padidinti vertinimo funkcijos vertę. Kiekvienam mėlynam judesiui gali būti du raudoni judesiai. Raudona spalva stengiasi sumažinti vertinimo funkcijos vertę. Apsvarstykite žingsnį, kai mėlynė žaidžia viršutiniame dešiniajame kampe. Jei raudona spalva žaidžia centre, raudona laimėjo (-10). Kita vertus, jei centrinėje apatinėje dėžutėje žaidžia raudona spalva, kitą žingsnį laimės mėlyna spalva (10). Taigi, jei viršutiniame dešiniajame kampe žaidžia mėlyna spalva, centrinėje dėžutėje bus raudona, nes tai sumažina vertinimo funkcijos vertę. Analogiškai, jei mėlyna spalva žaidžia apatinėje apatinėje dėžutėje, raudona vėl pasirodys centrinėje dėžutėje, nes tai sumažina vertinimo funkciją. Kita vertus, jei mėlyna žaidžia centrinėje aikštėje, nesvarbu, koks raudonas žingsnis, mėlyna visada laimės (10). Kadangi mėlyna spalva nori maksimaliai padidinti vertinimo funkciją, ji bus rodoma centrinėje dėžutėje, nes dėl šios padėties vertinimo funkcija (10) bus didesnė nei kiti du judesiai (-10).
3 veiksmas: trikčių šalinimas ir tolesni veiksmai
Jei paspausite mygtuką ir užsidegs kitas šviesos diodas nei tas, kuris atitinka mygtuką, greičiausiai susimaišė laidai ant kaiščių A0-A2 arba 4-6, arba prijungėte šviesos diodus netinkama tvarka.
Taip pat atkreipkite dėmesį, kad algoritmas nebūtinai visada pasirenka ėjimą, kuris leis „Arduino“laimėti kuo greičiau. Tiesą sakant, aš praleidau šiek tiek laiko derindamas algoritmą, nes „Arduino“nepasirinko žingsnio, kuris būtų buvęs laimėtas žingsnis. Prireikė šiek tiek laiko, kol supratau, kad ji pasirinko žingsnį, garantuojantį, kad vėliau jis laimės vieną žingsnį. Jei norite, galite pabandyti pakeisti algoritmą taip, kad jis visada pirmenybę teiktų laimėjusiam, o ne vėlesniam laimėjimui.
Galimas šio projekto pratęsimas būtų naudoti algoritmą 4x4 ar net 5x5 „Tic Tac Toe“AI sukūrimui. Tačiau atminkite, kad algoritmui reikalingų pozicijų skaičius labai sparčiai auga. Turėsite rasti būdų, kaip padaryti intelektualesnę vertinimo funkciją, vertes vertinant ne galutinėse pozicijose, atsižvelgiant į tikimybę, kad pozicija yra gera ar bloga atitinkamam žaidėjui. Taip pat galite pabandyti padaryti paiešką protingesnę, sustabdydami rekursiją anksti, jei pasirodo, kad žingsnis yra mažiau vertas tolesnio tyrimo nei alternatyvūs judesiai.
„Arduino“tikriausiai nėra geriausia platforma tokiems plėtiniams dėl ribotos atminties. Rekursija leidžia kaminui augti vykdant programą, o jei krūva auga per daug, ji gali sugadinti programos atmintį ir sukelti gedimus ar netinkamą elgesį. Aš pasirinkau „Arduino“šiam projektui daugiausia todėl, kad norėjau sužinoti, ar tai galima padaryti, ir švietimo tikslais, o ne todėl, kad tai geriausias pasirinkimas šiai problemai spręsti.