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

2024 Autor: John Day | [email protected]. Naposledy změněno: 2024-01-30 08:23

V tomto Instructable vám ukážu, jak vytvořit hru Tic Tac Toe s AI pomocí Arduina. Můžete buď hrát proti Arduinu, nebo sledovat, jak Arduino hraje proti sobě.

Používám algoritmus nazvaný "minimax algoritmus", který lze použít nejen k vytvoření AI pro Tic Tac Toe, ale také pro řadu dalších her, jako je Čtyři v řadě, dáma nebo dokonce šachy. Hry jako šachy jsou velmi složité a vyžadují mnohem propracovanější verze algoritmu. Pro naši hru Tic Tac Toe můžeme použít nejjednodušší verzi algoritmu, která je přesto docela působivá. Ve skutečnosti je AI tak dobrá, že není možné porazit Arduino!

Hra se snadno staví. Potřebujete jen několik komponent a náčrt, který jsem napsal. Také jsem přidal podrobnější vysvětlení algoritmu, pokud chcete pochopit, jak funguje.

Krok 1: Budujte a hrajte

K vytvoření hry Tic Tac Toe budete potřebovat následující komponenty:

• Arduino Uno
• 9 WS2812 RGB LED
• 9 tlačítek
• nějaké drátové a propojovací kabely

Zapojte součásti podle obrázku ve Fritzingově skice. Poté nahrajte kód do svého Arduina.

Ve výchozím nastavení má Arduino první kolo. Aby byly věci trochu zajímavější, je první tah vybrán náhodně. Po prvním tahu Arduino pomocí algoritmu minimax určí nejlepší možný tah. Novou hru spustíte resetováním Arduina.

Arduino můžete „přemýšlet“sledovat otevřením sériového monitoru. Algoritmus pro každý možný tah vypočítá hodnocení, které indikuje, zda tento krok povede k výhře (hodnota 10) nebo ke ztrátě (hodnota -10) pro Arduino nebo k remíze (hodnota 0).

Můžete také sledovat, jak Arduino hraje proti sobě, odkomentováním řádku „#define DEMO_MODE“na samém začátku náčrtu. Pokud nahrajete upravenou skicu, Arduino provede první tah náhodně a poté pomocí algoritmu minimax určí nejlepší tah pro každého hráče v každém tahu.

Pamatujte, že proti Arduinu nemůžete vyhrát. Každá hra buď skončí remízou, nebo prohrajete, pokud uděláte chybu. Důvodem je, že algoritmus vždy zvolí nejlepší možný tah. Jak možná víte, hra Tic Tac Toe vždy skončí remízou, pokud oba hráči neudělají chybu. V demo režimu každá hra končí remízou, protože, jak všichni víme, počítače nikdy nedělají chyby;-)

Krok 2: Algoritmus Minimax

Algoritmus se skládá ze dvou složek: vyhodnocovací funkce a vyhledávací strategie. Vyhodnocovací funkce je funkce, která pozicím desky přiřazuje číselnou hodnotu. Pokud je pozice konečná pozice (tj. Pozice, kde vyhrál buď modrý hráč, nebo červený hráč, nebo kde žádný hráč nevyhrál), je funkce hodnocení velmi jednoduchá: Řekněme, že Arduino hraje modře a lidský hráč hraje červeně. Pokud je pozice vítěznou pozicí pro modrou, funkce přiřadí této pozici hodnotu 10; pokud je to výherní pozice pro červenou, funkce přiřadí pozici -10 pozici; a pokud je pozice remízou, funkce přiřadí hodnotu 0.

Když je na řadě Arduino, chce zvolit tah, který maximalizuje hodnotu hodnotící funkce, protože maximalizace hodnoty znamená, že bude dávat přednost výhře před remízou (10 je větší než 0) a udělí remízu před prohrou (0 je větší než -10). Obdobným argumentem chce soupeřka hrát tak, aby minimalizovala hodnotu hodnotící funkce.

U pozice, která není konečná, algoritmus vypočítá hodnotu funkce vyhodnocení pomocí rekurzivní strategie hledání. Vychází z aktuální pozice a střídavě simuluje všechny tahy, které může provést modrý a červený hráč. To lze zobrazit jako strom, jako v diagramu. Když dorazí do konečné polohy, začne ustupovat a přenáší hodnotu vyhodnocovací funkce z nižší úrovně rekurze do vyšší úrovně rekurze. Přiřadí maximum (pokud je v odpovídajícím rekurzním kroku na řadě modrý hráč) nebo minimum (pokud je v odpovídajícím rekurzním kroku řada na červeném hráči) hodnot hodnotící funkce z nižší úrovně rekurze do pozice na vyšší úroveň rekurze. Nakonec, když algoritmus dokončí krok zpět a znovu dosáhne aktuální polohy, vezme ten tah (nebo jeden z tahů), který má maximální hodnotu funkce vyhodnocení.

Může to znít trochu abstraktně, ale ve skutečnosti to není tak obtížné. Zvažte polohu uvedenou v horní části diagramu. V prvním kroku rekurze existují tři různé pohyby, které může modrá provést. Blue se snaží maximalizovat hodnotu hodnotící funkce. Pro každý z tahů, které může modrý provést, existují dva tahy, které může červený provést. Red se snaží minimalizovat hodnotu hodnotící funkce. Zvažte tah, kde hraje modrá v pravém horním rohu. Pokud hraje červená ve středovém poli, červená zvítězila (-10). Pokud naopak hraje červená ve středním dolním poli, modrá vyhraje v dalším tahu (10). Pokud tedy modrá hraje v pravém horním rohu, červená bude hrát ve středovém poli, protože to minimalizuje hodnotu hodnotící funkce. Analogicky, pokud modrá hraje ve středním dolním poli, červená bude opět hrát ve středovém poli, protože to minimalizuje vyhodnocovací funkci. Pokud naopak hraje modrá ve středovém poli, je jedno, jaký tah červená bere, modrá vždy vyhraje (10). Protože modrá chce maximalizovat hodnotící funkci, bude hrát ve středovém poli, protože tato pozice má za následek větší hodnotu hodnotící funkce (10) než zbývající dva tahy (-10).

Krok 3: Odstraňování problémů a další kroky

Pokud stisknete tlačítko a rozsvítí se jiná LED, než která odpovídá tlačítku, pravděpodobně došlo k záměně vodičů na pinech A0-A2 nebo 4-6, nebo jste LED diody zapojili ve špatném pořadí.

Všimněte si také, že algoritmus nemusí vždy zvolit tah, který umožní Arduinu vyhrát co nejrychleji. Ve skutečnosti jsem strávil nějaký čas laděním algoritmu, protože Arduino nevybral tah, který by byl tahem vítězným. Trvalo mi nějaký čas, než jsem si uvědomil, že místo toho zvolil tah, který zaručoval, že vyhraje o jeden tah později. Pokud chcete, můžete zkusit upravit algoritmus tak, aby vždy dával přednost vítěznému tahu před pozdější výhrou.

Možným rozšířením tohoto projektu by bylo použití algoritmu k vybudování AI pro 4x4 nebo dokonce 5x5 Tic Tac Toe. Všimněte si však, že počet pozic, které musí algoritmus zkoumat, velmi rychle roste. Budete muset najít způsoby, jak učinit funkci hodnocení inteligentnější přiřazením hodnot pozicím, které nejsou konečné, na základě pravděpodobnosti, že pozice je pro dotyčného hráče dobrá nebo špatná. Můžete se také pokusit učinit hledání inteligentnějším včasným zastavením rekurze, pokud se ukáže, že tah je méně hoden dalšího zkoumání než alternativní pohyby.

Arduino pravděpodobně není nejlepší platforma pro taková rozšíření, protože má omezenou paměť. Rekurze umožňuje, aby se zásobník během provádění programu zvětšoval, a pokud se zásobník zvětší příliš, může dojít k poškození paměti programu, což vede k pádům nebo nevyrovnanému chování. Arduino jsem si pro tento projekt vybral hlavně proto, že jsem chtěl zjistit, zda by to šlo udělat, a pro vzdělávací účely, ne proto, že je to nejlepší volba pro tento druh problému.