Tic Tac Toe na Arduine s AI (algoritmus Minimax): 3 kroky

2024 Autor: John Day | [email protected]. Naposledy zmenené: 2024-01-30 12:00

V tomto návode vám ukážem, ako vytvoriť hru Tic Tac Toe s AI pomocou Arduina. Môžete buď hrať proti Arduinu, alebo sa pozerať, ako Arduino hrá proti sebe.

Používam algoritmus nazývaný „minimax algoritmus“, ktorý je možné použiť nielen na zostavenie AI pre Tic Tac Toe, ale aj pre množstvo ďalších hier, ako sú Štyri v rade, dáma alebo dokonca šach. Hry ako šach sú veľmi komplexné a vyžadujú si oveľa prepracovanejšie verzie algoritmu. Pre našu hru Tic Tac Toe môžeme použiť najjednoduchšiu verziu algoritmu, ktorá je napriek tomu dosť pôsobivá. V skutočnosti je AI taká dobrá, že nie je možné poraziť Arduino!

Hra sa ľahko stavia. Potrebujete iba niekoľko komponentov a náčrt, ktorý som napísal. Tiež som pridal podrobnejšie vysvetlenie algoritmu, ak chcete pochopiť, ako funguje.

Krok 1: Stavajte a hrajte

Na zostavenie hry Tic Tac Toe budete potrebovať nasledujúce komponenty:

• Arduino Uno
• 9 LED diód WS2812 RGB
• 9 tlačidiel
• niektoré drôtové a prepojovacie káble

Zapojte komponenty podľa obrázku vo Fritzingovej skici. Potom nahrajte kód do svojho Arduina.

Arduino štandardne zaberá prvé kolo. Aby boli veci ešte zaujímavejšie, prvý krok je vybraný náhodne. Po prvom ťahu Arduino použije algoritmus minimax na určenie najlepšieho možného ťahu. Novú hru spustíte resetovaním Arduina.

Otvorené okno Sériový monitor vám umožní sledovať „premýšľanie“Arduina. Algoritmus pre každý možný ťah vypočíta hodnotenie, ktoré indikuje, či tento krok povedie k výhre (hodnota 10) alebo k strate (hodnota –10) pre Arduino alebo k remíze (hodnota 0).

Arduino môžete hrať aj proti sebe, ak odkomentujete riadok „#define DEMO_MODE“na úplnom začiatku náčrtu. Ak nahráte upravenú skicu, Arduino vykoná prvý ťah náhodne a potom pomocou algoritmu minimax určí najlepší ťah pre každého hráča v každom ťahu.

Upozorňujeme, že proti Arduinu nemôžete vyhrať. Ak urobíte chybu, každá hra sa skončí remízou alebo prehráte. Dôvodom je, že algoritmus vždy vyberie najlepší možný krok. Ako možno viete, hra Tic Tac Toe sa vždy skončí remízou, ak sa obaja hráči nemýlia. V demo režime sa každá hra skončí remízou, pretože, ako všetci vieme, počítače nikdy nerobia chyby;-)

Krok 2: Algoritmus Minimax

Algoritmus sa skladá z dvoch zložiek: hodnotiacej funkcie a stratégie vyhľadávania. Hodnotiaca funkcia je funkcia, ktorá priraďuje pozíciám dosiek číselnú hodnotu. Ak je pozícia konečnou pozíciou (tj. Pozícia, kde vyhral buď modrý alebo červený hráč, alebo kde nevyhral ani jeden z hráčov), je hodnotiaca funkcia veľmi jednoduchá: povedzme, že Arduino hrá modrú a ľudský hráč hrá červenú. Ak je pozícia víťaznou pozíciou pre modrú, funkcia priradí tejto pozícii hodnotu 10; ak je to víťazná pozícia pre červenú, funkcia priradí pozícii hodnotu -10; a ak je pozícia remíza, funkcia priradí hodnotu 0.

Keď je na rade Arduino, chce zvoliť ťah, ktorý maximalizuje hodnotu hodnotiacej funkcie, pretože maximalizácia hodnoty znamená, že bude uprednostňovať výhru pred remízou (10 je väčšie ako 0) a uprednostniť remízu pred prehrou (0 je väčšia ako -10). Analogickým argumentom je, že súperka chce hrať tak, aby minimalizovala hodnotu hodnotiacej funkcie.

Pre nefinálnu pozíciu algoritmus vypočíta hodnotu hodnotiacej funkcie pomocou rekurzívnej stratégie vyhľadávania. Počnúc aktuálnou pozíciou striedavo simuluje všetky pohyby, ktoré môže urobiť modrý a červený hráč. Toto je možné zobraziť ako strom, ako na obrázku. Keď sa dostane do konečnej polohy, začne cúvať a prenáša hodnotu hodnotiacej funkcie z nižšej rekurzívnej úrovne do vyššej rekurzívnej úrovne. Priraďuje maximum (ak je v zodpovedajúcom rekurzívnom kroku na rade modrý hráč) alebo minimum (ak je v zodpovedajúcom rekurzívnom kroku na rade červený hráč) hodnôt hodnotiacej funkcie z nižšej rekurzívnej úrovne do polohy na vyššia úroveň rekurzie. Nakoniec, keď algoritmus skončí krok späť a opäť sa dostane do aktuálnej polohy, vykoná ten ťah (alebo jeden z ťahov), ktorý má maximálnu hodnotu hodnotiacej funkcie.

Môže to znieť trochu abstraktne, ale v skutočnosti to nie je také ťažké. Zvážte polohu uvedenú v hornej časti diagramu. V prvom kroku rekurzie existujú tri rôzne pohyby, ktoré môže modrá urobiť. Modrá sa pokúša maximalizovať hodnotu hodnotiacej funkcie. Pri každom z ťahov, ktoré môže modrá urobiť, existujú dva ťahy, ktoré môže červená urobiť. Red sa pokúša minimalizovať hodnotu hodnotiacej funkcie. Zvážte ťah, kde hrá modrá v pravom hornom rohu. Ak hrá červená v stredovom poli, červená zvíťazila (-10). Ak naopak hrá červená v strednom dolnom poli, modrá vyhrá v nasledujúcom ťahu (10). Ak teda modrá hrá v pravom hornom rohu, červená bude hrať v stredovom poli, pretože to minimalizuje hodnotu hodnotiacej funkcie. Analogicky, ak modrá hrá v strednom dolnom poli, červená bude opäť hrať v stredovom poli, pretože to minimalizuje funkciu hodnotenia. Ak naopak modrá hrá v stredovom poli, nezáleží na tom, ktorý ťah červená zaberie, modrá vždy vyhrá (10). Pretože modrá chce maximalizovať hodnotiacu funkciu, bude hrať v stredovom poli, pretože táto pozícia má za následok väčšiu hodnotu hodnotiacej funkcie (10) ako ostatné dva ťahy (-10).

Krok 3: Riešenie problémov a ďalšie kroky

Ak stlačíte tlačidlo a rozsvieti sa iná LED dióda, než ktorá zodpovedá tlačidlu, pravdepodobne ste zamiešali vodiče na kolíkoch A0-A2 alebo 4-6, alebo ste LED diódy zapojili v zlom poradí.

Všimnite si tiež, že algoritmus nemusí vždy zvoliť krok, ktorý umožní Arduinu vyhrať čo najrýchlejšie. V skutočnosti som strávil nejaký čas ladením algoritmu, pretože Arduino si nevybral ťah, ktorý by bol víťazným. Trvalo mi nejaký čas, kým som si uvedomil, že si namiesto toho vybral ťah, ktorý zaručoval, že neskôr vyhrá jeden ťah. Ak chcete, môžete sa pokúsiť upraviť algoritmus tak, aby vždy uprednostňoval víťazný ťah pred neskorším víťazstvom.

Možným rozšírením tohto projektu by bolo použitie algoritmu na vybudovanie AI pre 4x4 alebo dokonca 5x5 Tic Tac Toe. Všimnite si však, že počet polôh, ktoré musí algoritmus skúmať, veľmi rýchlo rastie. Budete musieť nájsť spôsoby, ako urobiť funkciu hodnotenia inteligentnejšou priradením hodnôt pozíciám, ktoré nie sú konečné, na základe pravdepodobnosti, že pozícia je pre daného hráča dobrá alebo zlá. Môžete sa tiež pokúsiť urobiť inteligentnejšie vyhľadávanie včasným zastavením rekurzie, ak sa ukáže, že pohyb je menej hodný ďalšieho skúmania ako alternatívne pohyby.

Arduino pravdepodobne nie je najlepšou platformou pre takéto rozšírenia kvôli obmedzenej pamäti. Rekurzia necháva zásobník rásť počas vykonávania programu, a ak sa zásobník príliš rozrastá, môže poškodiť pamäť programu, čo môže viesť k zlyhaniam alebo nepravidelnému správaniu. Arduino som si vybral pre tento projekt hlavne preto, že som chcel zistiť, či sa to dá urobiť, a na vzdelávacie účely, nie preto, že je to najlepšia voľba pre tento druh problému.