Tic Tac Toe på Arduino Med AI (Minimax Algoritme): 3 trin

2024 Forfatter: John Day | [email protected]. Sidst ændret: 2024-01-30 08:29

I denne Instructable vil jeg vise dig, hvordan du bygger et Tic Tac Toe -spil med en AI ved hjælp af en Arduino. Du kan enten spille mod Arduino eller se Arduino spille mod sig selv.

Jeg bruger en algoritme kaldet "minimax algoritme", som ikke kun kan bruges til at bygge en AI til Tic Tac Toe, men også til en række andre spil som Four in a Row, brikker eller endda skak. Spil som skak er meget komplekse og kræver meget mere raffinerede versioner af algoritmen. Til vores Tic Tac Toe -spil kan vi bruge den enkleste version af algoritmen, som ikke desto mindre er ret imponerende. Faktisk er AI så god, at det er umuligt at slå Arduino!

Spillet er let at bygge. Du behøver kun et par komponenter og den skitse, jeg har skrevet. Jeg tilføjede også en mere detaljeret forklaring af algoritmen, hvis du vil forstå, hvordan den fungerer.

Trin 1: Byg og spil

For at bygge Tic Tac Toe -spillet skal du bruge følgende komponenter:

• En Arduino Uno
• 9 WS2812 RGB lysdioder
• 9 trykknapper
• nogle ledninger og jumperkabler

Tilslut komponenterne som vist på Fritzing -skitsen. Upload derefter koden til din Arduino.

Som standard tager Arduino den første sving. For at gøre tingene lidt mere interessante, er det første træk valgt tilfældigt. Efter det første træk bruger Arduino minimax -algoritmen til at bestemme det bedst mulige træk. Du starter et nyt spil ved at nulstille Arduino.

Du kan se Arduino "tænke" ved at åbne den serielle skærm. For hvert muligt træk beregner algoritmen en rating, der angiver, om dette træk vil føre til en gevinst (værdi på 10) eller et tab (værdi på -10) for Arduino eller et uafgjort (værdi på 0).

Du kan også se Arduino spille mod sig selv ved at kommentere linjen "#define DEMO_MODE" i begyndelsen af skitsen. Hvis du uploader den ændrede skitse, foretager Arduino det første træk tilfældigt og bruger derefter minimax -algoritmen til at bestemme det bedste træk for hver spiller i hver tur.

Bemærk, at du ikke kan vinde mod Arduino. Hvert spil ender enten uafgjort, eller du taber, hvis du laver en fejl. Dette skyldes, at algoritmen altid vælger det bedst mulige træk. Som du måske ved, vil en omgang Tic Tac Toe altid ende uafgjort, hvis begge spillere ikke begår fejl. I demo-tilstand ender hvert spil uafgjort, fordi computere som vi alle ved aldrig laver fejl;-)

Trin 2: Minimax -algoritmen

Algoritmen består af to komponenter: en evalueringsfunktion og en søgestrategi. Evalueringsfunktionen er en funktion, der tildeler en numerisk værdi til bestyrelsesposter. Hvis positionen er en sidste position (dvs. en position, hvor enten den blå spiller eller den røde spiller har vundet, eller hvor ingen spiller har vundet), er evalueringsfunktionen meget enkel: Lad os sige, at Arduino spiller blå, og den menneskelige spiller spiller rødt. Hvis positionen er en vindende position for blå, tildeler funktionen en værdi på 10 til denne position; hvis det er en vindende position for rød, tildeler funktionen en værdi på -10 til positionen; og hvis positionen er uafgjort, tildeler funktionen en værdi på 0.

Når det er Arduinoens tur, vil den vælge et træk, der maksimerer værdien af evalueringsfunktionen, fordi maksimering af værdien betyder, at den foretrækker en sejr frem for en uafgjort (10 er større end 0) og foretrækker en uafgjort frem for at tabe (0 er større end -10). Ved et analogt argument ønsker modstanderen at spille på en sådan måde, at hun minimerer værdien af evalueringsfunktionen.

For en ikke-endelig position beregner algoritmen værdien af evalueringsfunktionen ved hjælp af en rekursiv søgestrategi. Fra den nuværende position simulerer den skiftevis alle de træk, som den blå spiller og den røde spiller kan tage. Dette kan visualiseres som et træ, som i diagrammet. Når den ankommer til en endelig position, begynder den at træde tilbage og bære værdien af evalueringsfunktionen fra det lavere rekursionsniveau til det højere rekursionsniveau. Det tildeler maksimum (hvis det i det tilsvarende rekursionstrin er den blå spillers tur) eller minimum (hvis det i det tilsvarende rekursionstrin er den røde spillers tur) af evalueringsfunktionens værdier fra det lavere rekursionsniveau til positionen på højere rekursionsniveau. Endelig, når algoritmen er færdig med at træde tilbage og er nået frem til den aktuelle position igen, tager den den bevægelse (eller et af træk), der har den maksimale evalueringsfunktionsværdi.

Det lyder måske lidt abstrakt, men det er faktisk ikke så svært. Overvej placeringen vist øverst i diagrammet. I det første rekursionstrin er der tre forskellige træk, blå kan tage. Blue forsøger at maksimere værdien af evalueringsfunktionen. For hvert af de træk, blå kan tage, er der to træk, rød kan tage. Rød forsøger at minimere værdien af evalueringsfunktionen. Overvej trækket, hvor blå spiller i øverste højre hjørne. Hvis rød spiller i midterfeltet, har rød vundet (-10). Hvis der på den anden side spiller rød i den midterste bundboks, vinder blå i det næste træk (10). Så hvis blå spiller i øverste højre hjørne, spiller rødt i midterboksen, da det minimerer værdien af evalueringsfunktionen. Analogt, hvis blå spiller i den midterste nederste boks, vil rød igen spille i midterboksen, fordi det minimerer evalueringsfunktionen. Hvis der på den anden side spiller blå i midterfeltet, er det ligegyldigt hvilket træk rødt tager, vil blå altid vinde (10). Da blå ønsker at maksimere evalueringsfunktionen, vil den spille i midterboksen, da denne position resulterer i en større værdi af evalueringsfunktionen (10) end de to andre træk (-10).

Trin 3: Fejlfinding og yderligere trin

Hvis du trykker på en knap og en anden LED end den, der svarer til knappen, lyser, har du sandsynligvis enten blandet ledningerne på ben A0-A2 eller 4-6, eller du har tilsluttet lysdioderne i den forkerte rækkefølge.

Bemærk også, at algoritmen ikke nødvendigvis altid vælger et træk, der lader Arduino vinde så hurtigt som muligt. Faktisk brugte jeg noget tid på at fejlsøge algoritmen, fordi Arduino ikke valgte et træk, der ville have været et vindende træk. Det tog mig noget tid, indtil jeg indså, at det i stedet havde valgt et træk, der garanterede, at det ville vinde et træk senere. Hvis du vil, kan du prøve at ændre algoritmen, så den altid foretrækker et vindende træk frem for en senere sejr.

En mulig forlængelse af dette projekt ville være at bruge algoritmen til at bygge en AI til en 4x4 eller endda en 5x5 Tic Tac Toe. Bemærk dog, at antallet af positioner, algoritmen skal undersøge, vokser meget hurtigt. Du bliver nødt til at finde måder at gøre evalueringsfunktionen mere intelligent ved at fastsætte værdier til positioner, der ikke er endelige, baseret på sandsynligheden for, at positionen er god eller dårlig for den pågældende spiller. Du kan også prøve at gøre søgningen mere intelligent ved at stoppe rekursionen tidligt, hvis et træk viser sig at være mindre værd at udforske end alternative træk.

Arduino er sandsynligvis ikke den bedste platform for sådanne udvidelser på grund af sin begrænsede hukommelse. Rekursion lader stakken vokse under programkørsel, og hvis stakken vokser for meget, kan den ødelægge programmets hukommelse, hvilket kan føre til nedbrud eller uregelmæssig adfærd. Jeg valgte Arduino til dette projekt hovedsageligt fordi jeg ville se, om det kunne lade sig gøre og til uddannelsesmæssige formål, ikke fordi det er det bedste valg til denne slags problemer.