Tic Tac Toe az Arduino -n AI -val (Minimax algoritmus): 3 lépés

2024 Szerző: John Day | [email protected]. Utoljára módosítva: 2024-01-30 09:43

Ebben az utasításban megmutatom, hogyan lehet Tic Tac Toe játékot építeni AI -val egy Arduino segítségével. Játszhatsz az Arduino ellen, vagy nézheted, hogy az Arduino maga ellen játszik.

A "minimumx algoritmus" nevű algoritmust használom, amely nemcsak mesterséges intelligencia létrehozására használható a Tic Tac Toe számára, hanem számos más játékhoz is, mint például a Négy sorban, dáma vagy akár a sakk. Az olyan játékok, mint a sakk, nagyon bonyolultak, és az algoritmus sokkal kifinomultabb verzióit igénylik. A Tic Tac Toe játékunkhoz az algoritmus legegyszerűbb verzióját használhatjuk, ami ennek ellenére nagyon lenyűgöző. Valójában az AI olyan jó, hogy lehetetlen legyőzni az Arduino -t!

A játék könnyen felépíthető. Csak néhány összetevőre és az általam írt vázlatra van szüksége. Hozzáadtam az algoritmus részletesebb magyarázatát is, ha meg akarod érteni, hogyan működik.

1. lépés: Építs és játssz

A Tic Tac Toe játék felépítéséhez a következő összetevőkre lesz szüksége:

• Egy Arduino Uno
• 9 WS2812 RGB LED
• 9 nyomógomb
• néhány drót és áthidaló kábel

Csatlakoztassa az alkatrészeket a Fritzing vázlat szerint. Ezután töltse fel a kódot Arduino készülékére.

Alapértelmezés szerint az Arduino veszi az első kanyart. Hogy egy kicsit érdekesebb legyen a dolog, az első lépést véletlenszerűen választják ki. Az első lépés után az Arduino a minimumx algoritmust használja a lehető legjobb lépés meghatározásához. Új játékot indít az Arduino alaphelyzetbe állításával.

Megnézheti az Arduino "gondolkodását" a Soros monitor megnyitásával. Az algoritmus minden lehetséges lépésnél kiszámít egy értékelést, amely azt jelzi, hogy ez a lépés győzelemhez (10 -es érték) vagy veszteséghez (-10 érték) vezet -e az Arduino -hoz vagy döntetlenhez (0 -ás érték).

Azt is megnézheti, hogyan játszik az Arduino önmagával szemben, ha a vázlat legelején megjegyzi a "#define DEMO_MODE" sort. Ha feltölti a módosított vázlatot, az Arduino véletlenszerűen megteszi az első lépést, majd a minimumx algoritmus segítségével meghatározza a legjobb lépést minden játékosnak minden körben.

Ne feledje, hogy nem nyerhet az Arduino ellen. Minden játék döntetlennel végződik, vagy veszít, ha hibázik. Ennek oka az, hogy az algoritmus mindig a lehető legjobb lépést választja. Mint tudják, a Tic Tac Toe játéka mindig döntetlennel végződik, ha mindkét játékos nem hibázik. Demó módban minden játék döntetlennel végződik, mert mint tudjuk, a számítógépek soha nem követnek el hibákat;-)

2. lépés: A Minimax algoritmus

Az algoritmus két komponensből áll: értékelési funkcióból és keresési stratégiából. Az értékelési funkció egy olyan funkció, amely számértéket rendel a tábla pozícióihoz. Ha a pozíció egy végső pozíció (azaz olyan pozíció, ahol vagy a kék játékos, vagy a piros játékos nyert, vagy ahol egyik játékos sem nyert), az értékelési funkció nagyon egyszerű: Tegyük fel, hogy az Arduino kék, az ember pedig piros. Ha a pozíció nyerő pozíció a kék számára, akkor a függvény 10 értéket rendel ehhez a pozícióhoz; ha ez nyerő pozíció a piros számára, a függvény -10 értéket rendel a pozícióhoz; és ha a helyzet döntetlen, akkor a függvény 0 értéket rendel hozzá.

Amikor az Arduino -n van a sor, olyan lépést szeretne választani, amely maximalizálja az értékelési funkció értékét, mert az érték maximalizálása azt jelenti, hogy a győzelmet részesíti előnyben a döntetlennel szemben (10 nagyobb, mint 0), és a döntetlent a vesztéssel szemben (0 nagyobb, mint -10). Hasonló érveléssel az ellenfél úgy akar játszani, hogy minimalizálja az értékelési funkció értékét.

Nem végleges pozíció esetén az algoritmus rekurzív keresési stratégiával számítja ki az értékelési funkció értékét. Az aktuális pozícióból kiindulva felváltva szimulálja az összes lépést, amelyet a kék és a piros játékos tehet. Ez a diagramhoz hasonlóan faként is megjeleníthető. Amikor eléri a végső pozíciót, hátrálni kezd, és az értékelési funkció értékét az alsó rekurziós szintről a magasabb rekurziós szintre viszi. Hozzárendeli a kiértékelő funkció értékeinek maximumát (ha a megfelelő rekurziós lépésben a kék játékos köre) vagy a minimumot (ha a megfelelő rekurziós lépésben a piros játékosé) az alsó rekurziós szintről a pozícióra magasabb rekurziós szint. Végül, amikor az algoritmus befejezte a visszalépést, és ismét megérkezett az aktuális pozícióba, akkor azt a lépést (vagy az egyik lépést) veszi meg, amelynek a maximális kiértékelési funkció értéke van.

Ez kissé elvontnak tűnhet, de valójában nem olyan nehéz. Tekintsük a diagram tetején látható pozíciót. Az első rekurziós lépésben három különböző kék lépést lehet végrehajtani. A kék megpróbálja maximalizálni az értékelési funkció értékét. A kék lépések mindegyikéhez két piros lépést lehet végrehajtani. A piros megpróbálja minimalizálni az értékelési funkció értékét. Fontolja meg a lépést, ahol a kék játszik a jobb felső sarokban. Ha a piros játszik a középső mezőben, a piros nyert (-10). Ha viszont a piros játszik a középső alsó mezőben, a kék nyer a következő lépésben (10). Tehát, ha a kék a jobb felső sarokban játszik, a piros a középső mezőben, mivel ez minimalizálja az értékelési funkció értékét. Hasonlóképpen, ha a kék szín jelenik meg a középső alsó mezőben, a piros ismét a középső mezőben, mert ez minimalizálja az értékelési funkciót. Ha viszont a kék játszik a középső mezőben, nem számít, melyik piros lépést teszi meg, a kék mindig nyer (10). Mivel a kék a lehető legnagyobbra szeretné értékelni az értékelési funkciót, a középső mezőben fog játszani, mivel ez a pozíció nagyobb értéket eredményez az értékelő függvényben (10), mint a másik két lépés (-10).

3. lépés: Hibaelhárítás és további lépések

Ha megnyom egy gombot, és a LED-től eltérő LED világít, akkor valószínűleg az A0-A2 vagy a 4-6 érintkezők vezetékei keveredtek össze, vagy rossz sorrendben csatlakoztatta a LED-eket.

Azt is vegye figyelembe, hogy az algoritmus nem feltétlenül mindig olyan lépést választ, amely lehetővé teszi, hogy az Arduino a lehető leggyorsabban nyerjen. Valójában egy kis időt töltöttem az algoritmus hibakeresésével, mert az Arduino nem választott olyan lépést, amely nyerő lépés lett volna. Beletelt egy kis időbe, mire rájöttem, hogy ehelyett egy olyan lépést választott, amely garantálja, hogy később nyer egy lépést. Ha szeretné, megpróbálhatja úgy módosítani az algoritmust, hogy az mindig a győztes lépést részesítse előnyben a későbbi győzelem mellett.

Ennek a projektnek a lehetséges kiterjesztése az lenne, ha az algoritmust felhasználva mesterséges intelligenciát építenének 4x4 -es vagy akár 5x5 -ös Tic Tac Toe számára. Ne feledje azonban, hogy az algoritmus által megvizsgálandó pozíciók száma nagyon gyorsan növekszik. Meg kell találnia a módját, hogy intelligensebbé tegye az értékelési funkciót azáltal, hogy értékeket rendel a pozíciókhoz, amelyek nem véglegesek, annak valószínűsége alapján, hogy a helyzet jó vagy rossz az adott játékos számára. Azt is megpróbálhatja intelligensebbé tenni a keresést, ha korán leállítja a rekurziót, ha egy lépés kevésbé érdemes további kutatásra, mint az alternatív lépések.

Az Arduino valószínűleg nem a legjobb platform az ilyen kiterjesztésekhez a korlátozott memória miatt. A rekurzió lehetővé teszi a verem növekedését a program végrehajtása során, és ha a verem túl sokat növekszik, akkor megsérülhet a programmemória, ami összeomlásokhoz vagy szabálytalan viselkedéshez vezethet. Főleg azért választottam az Arduino -t ehhez a projekthez, mert meg akartam nézni, hogy megvalósítható -e és oktatási célokra, nem pedig azért, mert ez a legjobb választás az ilyen jellegű problémákra.