Tic Tac Toe på Arduino Med AI (Minimax -algoritme): 3 trinn

2024 Forfatter: John Day | [email protected]. Sist endret: 2024-01-30 11:24

I denne instruksen skal jeg vise deg hvordan du bygger et Tic Tac Toe -spill med AI ved hjelp av en Arduino. Du kan enten spille mot Arduino eller se Arduino spille mot seg selv.

Jeg bruker en algoritme kalt "minimax algoritme", som ikke bare kan brukes til å bygge en AI for Tic Tac Toe, men også til en rekke andre spill som Four in a Row, brikker eller til og med sjakk. Spill som sjakk er veldig komplekse og krever mye mer raffinerte versjoner av algoritmen. For vårt Tic Tac Toe -spill kan vi bruke den enkleste versjonen av algoritmen, som likevel er ganske imponerende. Faktisk er AI så god at det er umulig å slå Arduino!

Spillet er enkelt å bygge. Du trenger bare noen få komponenter og skissen jeg har skrevet. Jeg har også lagt til en mer detaljert forklaring av algoritmen, hvis du vil forstå hvordan den fungerer.

Trinn 1: Bygg og spill

For å bygge Tic Tac Toe -spillet trenger du følgende komponenter:

• En Arduino Uno
• 9 WS2812 RGB -lysdioder
• 9 trykknapper
• noen ledninger og startkabler

Koble sammen komponentene som vist i Fritzing -skissen. Last deretter opp koden til Arduino.

Som standard tar Arduino den første svingen. For å gjøre ting litt mer interessant, velges det første trekket tilfeldig. Etter det første trekket bruker Arduino minimax -algoritmen for å bestemme det best mulige trekket. Du starter et nytt spill ved å tilbakestille Arduino.

Du kan se Arduino "tenke" ved å åpne Serial Monitor. For hvert mulig trekk beregner algoritmen en vurdering som indikerer om dette trekket vil føre til en gevinst (verdi på 10) eller et tap (verdi på -10) for Arduino eller uavgjort (verdi på 0).

Du kan også se Arduino spille mot seg selv ved å ikke kommentere linjen "#define DEMO_MODE" helt i begynnelsen av skissen. Hvis du laster opp den endrede skissen, gjør Arduino det første trekket tilfeldig og bruker deretter minimax -algoritmen til å bestemme det beste trekket for hver spiller i hver sving.

Vær oppmerksom på at du ikke kan vinne mot Arduino. Hver kamp ender enten uavgjort eller du taper hvis du gjør en feil. Dette er fordi algoritmen alltid velger det best mulige trekket. Som du kanskje vet vil en omgang Tic Tac Toe alltid ende uavgjort hvis begge spillerne ikke gjør noen feil. I demomodus ender hvert spill uavgjort fordi datamaskiner aldri gjør feil, som vi alle vet;-)

Trinn 2: Minimax -algoritmen

Algoritmen består av to komponenter: en evalueringsfunksjon og en søkestrategi. Evalueringsfunksjonen er en funksjon som tilordner en numerisk verdi til styreposisjoner. Hvis stillingen er en siste posisjon (dvs. en posisjon der enten den blå spilleren eller den røde spilleren har vunnet eller hvor ingen av spillerne har vunnet), er evalueringsfunksjonen veldig enkel: La oss si at Arduino spiller blått og den menneskelige spilleren spiller rødt. Hvis posisjonen er en vinnende posisjon for blå, tildeler funksjonen en verdi på 10 til den posisjonen; hvis det er en vinnende posisjon for rødt, tilordner funksjonen en verdi på -10 til posisjonen; og hvis stillingen er uavgjort, tilordner funksjonen en verdi på 0.

Når det er Arduino sin tur, ønsker den å velge et trekk som maksimerer verdien av evalueringsfunksjonen, fordi maksimering av verdien betyr at den vil foretrekke en seier fremfor uavgjort (10 er større enn 0) og foretrekker uavgjort fremfor å tape (0 er større enn -10). Ved et analogt argument ønsker motstanderen å spille på en slik måte at hun minimerer verdien av evalueringsfunksjonen.

For en ikke-endelig posisjon beregner algoritmen verdien av evalueringsfunksjonen ved hjelp av en rekursiv søkestrategi. Fra den nåværende posisjonen simulerer den vekselvis alle trekkene som den blå spilleren og den røde spilleren kan ta. Dette kan visualiseres som et tre, som i diagrammet. Når den kommer til en endelig posisjon, begynner den å gå tilbake og bære verdien av evalueringsfunksjonen fra det lavere rekursjonsnivået til det høyere rekursjonsnivået. Den tildeler maksimum (hvis det i det tilsvarende rekursjonstrinnet er den blå spillerens tur) eller minimum (hvis det i det tilsvarende rekursjonstrinnet er den røde spillerens tur) til verdiene til evalueringsfunksjonen fra det lavere rekursjonsnivået til posisjonen på høyere rekursjonsnivå. Til slutt, når algoritmen er ferdig med å gå tilbake og har kommet til gjeldende posisjon igjen, tar den bevegelsen (eller ett av trekkene) som har maksimal evalueringsfunksjonsverdi.

Dette høres kanskje litt abstrakt ut, men det er faktisk ikke så vanskelig. Vurder posisjonen vist øverst i diagrammet. I det første rekursjonstrinnet er det tre forskjellige trekk som blått kan ta. Blue prøver å maksimere verdien av evalueringsfunksjonen. For hvert av trekkene blå kan ta, er det to trekk som rødt kan ta. Rød prøver å minimere verdien av evalueringsfunksjonen. Tenk på trekket der blå spiller i øvre høyre hjørne. Hvis rødt spiller i midtfeltet, har rødt vunnet (-10). Hvis derimot rødt spiller i den midtre nederste boksen, vinner blått i neste trekk (10). Så hvis blå spiller i øvre høyre hjørne, vil rødt spille i midtboksen, siden det minimerer verdien av evalueringsfunksjonen. Analogt, hvis blå spiller i den midtre nederste boksen, vil rødt igjen spille i midtboksen fordi det minimerer evalueringsfunksjonen. Hvis derimot blått spiller i midtboksen, spiller det ingen rolle hvilket trekk rødt tar, vil blått alltid vinne (10). Siden blå ønsker å maksimere evalueringsfunksjonen, vil den spille i midtboksen, siden den posisjonen resulterer i en større verdi av evalueringsfunksjonen (10) enn de to andre trekkene (-10).

Trinn 3: Feilsøking og ytterligere trinn

Hvis du trykker på en knapp og en annen LED enn den som tilsvarer knappen lyser, har du sannsynligvis enten blandet ledningene på pinnene A0-A2 eller 4-6, eller du har koblet LEDene i feil rekkefølge.

Vær også oppmerksom på at algoritmen ikke nødvendigvis alltid velger et trekk som lar Arduino vinne så fort som mulig. Faktisk brukte jeg litt tid på å feilsøke algoritmen fordi Arduino ikke valgte et trekk som ville vært et vinnende trekk. Det tok litt tid før jeg innså at det i stedet hadde valgt et trekk som garanterte at det ville vinne ett trekk senere. Hvis du vil, kan du prøve å endre algoritmen slik at den alltid vil foretrekke et vinnende trekk fremfor en senere seier.

En mulig forlengelse av dette prosjektet vil være å bruke algoritmen til å bygge en AI for en 4x4 eller til og med en 5x5 Tic Tac Toe. Vær imidlertid oppmerksom på at antallet posisjoner algoritmen trenger å undersøke vokser veldig raskt. Du må finne måter å gjøre evalueringsfunksjonen mer intelligent ved å tilordne verdier til posisjoner som ikke er endelige, basert på sannsynligheten for at posisjonen er god eller dårlig for den aktuelle spilleren. Du kan også prøve å gjøre søket mer intelligent ved å stoppe rekursjonen tidlig hvis et trekk viser seg å være mindre verdig til videre utforskning enn alternative trekk.

Arduino er sannsynligvis ikke den beste plattformen for slike utvidelser på grunn av sitt begrensede minne. Rekursjon lar bunken vokse under programkjøring, og hvis bunken vokser for mye, kan den ødelegge programminnet, noe som kan føre til krasj eller uberegnelig oppførsel. Jeg valgte Arduino for dette prosjektet hovedsakelig fordi jeg ønsket å se om det kunne gjøres og for utdanningsformål, ikke fordi det er det beste valget for denne typen problemer.