Cuprins:
2025 Autor: John Day | [email protected]. Modificat ultima dată: 2025-01-13 06:58
În acest Instructable vă voi arăta cum să construiți un joc Tic Tac Toe cu un AI folosind un Arduino. Puteți juca împotriva Arduino sau puteți urmări cum Arduino se joacă împotriva sa.
Folosesc un algoritm numit „algoritm minimax”, care poate fi folosit nu numai pentru a construi un AI pentru Tic Tac Toe, ci și pentru o varietate de alte jocuri precum Four in a Row, dame sau chiar șah. Jocurile precum șahul sunt foarte complexe și necesită versiuni mult mai rafinate ale algoritmului. Pentru jocul nostru Tic Tac Toe, putem folosi cea mai simplă versiune a algoritmului, care este totuși destul de impresionantă. De fapt, AI este atât de bun încât este imposibil să învingi Arduino!
Jocul este ușor de construit. Ai nevoie doar de câteva componente și de schița pe care am scris-o. Am adăugat, de asemenea, o explicație mai detaliată a algoritmului, dacă doriți să înțelegeți cum funcționează.
Pasul 1: Construiește și joacă
Pentru a construi jocul Tic Tac Toe veți avea nevoie de următoarele componente:
- Un Arduino Uno
- 9 LED-uri RGB WS2812
- 9 butoane
- niște cabluri de sârmă și jumper
Conectați componentele așa cum se arată în schița Fritzing. Apoi încărcați codul pe Arduino.
În mod implicit, Arduino ia primul rând. Pentru a face lucrurile puțin mai interesante, prima mișcare este aleasă la întâmplare. După prima mișcare, Arduino folosește algoritmul minimax pentru a determina cea mai bună mișcare posibilă. Începeți un joc nou resetând Arduino.
Puteți urmări „gândirea” Arduino deschizând Serial Monitor. Pentru fiecare mișcare posibilă, algoritmul calculează o evaluare care indică dacă această mișcare va duce la un câștig (valoare de 10) sau o pierdere (valoare de -10) pentru Arduino sau o remiză (valoare de 0).
De asemenea, puteți urmări cum Arduino se joacă împotriva sa, descomentând linia „#define DEMO_MODE” chiar la începutul schiței. Dacă încărcați schița modificată, Arduino face prima mișcare aleatoriu și apoi folosește algoritmul minimax pentru a determina cea mai bună mișcare pentru fiecare jucător în fiecare tură.
Rețineți că nu puteți câștiga împotriva Arduino. Fiecare joc se va încheia fie la egalitate, fie vei pierde, dacă greșești. Acest lucru se datorează faptului că algoritmul alege întotdeauna cea mai bună mișcare posibilă. După cum ați știut, un joc de Tic Tac Toe se va încheia întotdeauna într-o remiză dacă ambii jucători nu greșesc. În modul demo, fiecare joc se termină într-o remiză, deoarece, după cum știm cu toții, computerele nu greșesc niciodată;-)
Pasul 2: Algoritmul Minimax
Algoritmul constă din două componente: o funcție de evaluare și o strategie de căutare. Funcția de evaluare este o funcție care atribuie o valoare numerică pozițiilor consiliului. Dacă poziția este o poziție finală (adică o poziție în care a câștigat fie jucătorul albastru, fie jucătorul roșu sau în care niciun jucător nu a câștigat), funcția de evaluare este foarte simplă: Să presupunem că Arduino joacă albastru și jucătorul uman joacă roșu. Dacă poziția este o poziție câștigătoare pentru albastru, funcția atribuie o valoare de 10 acelei poziții; dacă este o poziție câștigătoare pentru roșu, funcția atribuie o valoare de -10 poziției; iar dacă poziția este o remiză, funcția atribuie o valoare 0.
Când este rândul lui Arduino, vrea să aleagă o mișcare care să maximizeze valoarea funcției de evaluare, deoarece maximizarea valorii înseamnă că va prefera o victorie în fața unei remize (10 este mai mare decât 0) și să permită o remiză în locul pierderii (0 este mai mare decât -10). Printr-un argument analog, adversara vrea să joace în așa fel încât să minimizeze valoarea funcției de evaluare.
Pentru o poziție non-finală, algoritmul calculează valoarea funcției de evaluare printr-o strategie de căutare recursivă. Pornind de la poziția actuală, acesta simulează alternativ toate mișcările pe care jucătorul albastru și jucătorul roșu le pot face. Acest lucru poate fi vizualizat ca un copac, ca în diagramă. Când ajunge la o poziție finală, începe să facă un pas înapoi, purtând valoarea funcției de evaluare de la nivelul de recursivitate inferior la nivelul de recursivitate superior. Atribuie maximul (dacă în pasul de recursie corespunzător este rândul jucătorului albastru) sau minimul (dacă în pasul de recursie corespunzător este rândul jucătorului roșu) al valorilor funcției de evaluare de la nivelul de recursie inferior la poziția de pe nivel mai mare de recursivitate. În cele din urmă, când algoritmul a terminat pasul înapoi și a ajuns din nou la poziția curentă, este nevoie de acea mișcare (sau una dintre mișcări) care are valoarea maximă a funcției de evaluare.
Acest lucru poate suna puțin abstract, dar de fapt nu este atât de dificil. Luați în considerare poziția prezentată în partea de sus a diagramei. În primul pas de recursivitate, există trei mișcări diferite pe care albastru le poate face. Albastru încearcă să maximizeze valoarea funcției de evaluare. Pentru fiecare dintre mișcările pe care le poate face albastru, există două mișcări pe care roșul le poate lua. Roșu încearcă să minimizeze valoarea funcției de evaluare. Luați în considerare mișcarea în care albastrul se joacă în colțul din dreapta sus. Dacă roșul joacă în careul central, roșul a câștigat (-10). Dacă, pe de altă parte, roșul joacă în caseta din centru, albastru va câștiga în următoarea mutare (10). Deci, dacă albastrul se joacă în colțul din dreapta sus, roșu va juca în caseta centrală, deoarece aceasta minimizează valoarea funcției de evaluare. În mod similar, dacă albastrul se joacă în caseta centrală de jos, roșul va reda din nou în caseta centrală, deoarece aceasta minimizează funcția de evaluare. Dacă, pe de altă parte, albastrul joacă în caseta centrală, nu contează ce mișcare are roșu, albastru va câștiga întotdeauna (10). Deoarece albastrul dorește să maximizeze funcția de evaluare, acesta va juca în caseta centrală, deoarece poziția respectivă are ca rezultat o valoare mai mare a funcției de evaluare (10) decât celelalte două mișcări (-10).
Pasul 3: Depanare și pași suplimentari
Dacă apăsați un buton și un LED diferit de cel care corespunde butonului se aprinde, probabil că fie ați amestecat firele de pe pinii A0-A2 sau 4-6, fie ați conectat LED-urile în ordinea greșită.
De asemenea, rețineți că algoritmul nu alege întotdeauna neapărat o mișcare care să lase Arduino să câștige cât mai repede posibil. De fapt, am petrecut ceva timp depanând algoritmul, deoarece Arduino nu a ales o mișcare care ar fi fost o mișcare câștigătoare. Mi-a luat ceva timp până când mi-am dat seama că, în schimb, a ales o mișcare care să garanteze că va câștiga o mișcare mai târziu. Dacă doriți, puteți încerca să modificați algoritmul astfel încât acesta să prefere întotdeauna o mișcare câștigătoare decât o victorie ulterioară.
O posibilă extensie a acestui proiect ar fi utilizarea algoritmului pentru a construi un AI pentru un 4x4 sau chiar un 5x5 Tic Tac Toe. Cu toate acestea, rețineți că numărul de poziții pe care algoritmul trebuie să le examineze crește foarte rapid. Va trebui să găsiți modalități de a face funcția de evaluare mai inteligentă prin asocierea valorilor la poziții care nu sunt finale, pe baza probabilității ca poziția să fie bună sau rea pentru jucătorul în cauză. S-ar putea să încercați, de asemenea, să faceți căutarea mai inteligentă, oprind recursiunea mai devreme dacă o mișcare se dovedește a fi mai puțin demnă de o explorare suplimentară decât mișcările alternative.
Arduino nu este probabil cea mai bună platformă pentru astfel de extensii datorită memoriei sale limitate. Recursiunea permite stivei să crească în timpul execuției programului și, dacă stiva crește prea mult, poate deteriora memoria programului, ducând la blocări sau comportament neregulat. Am ales Arduino pentru acest proiect în principal pentru că am vrut să văd dacă se poate face și în scopuri educaționale, nu pentru că este cea mai bună alegere pentru acest tip de problemă.