Tic Tac Toe på Arduino med AI (Minimax -algoritm): 3 steg

2024 Författare: John Day | [email protected]. Senast ändrad: 2024-01-30 12:46

I denna instruktionsbok ska jag visa dig hur man bygger ett Tic Tac Toe -spel med en AI med hjälp av en Arduino. Du kan antingen spela mot Arduino eller titta på Arduino spela mot sig själv.

Jag använder en algoritm som kallas "minimax algoritm", som kan användas inte bara för att bygga en AI för Tic Tac Toe, utan också för en mängd andra spel som Four in a Row, dam eller till och med schack. Spel som schack är mycket komplexa och kräver mycket mer raffinerade versioner av algoritmen. För vårt Tic Tac Toe -spel kan vi använda den enklaste versionen av algoritmen, som ändå är ganska imponerande. Faktum är att AI är så bra att det är omöjligt att slå Arduino!

Spelet är enkelt att bygga. Du behöver bara några komponenter och skissen som jag har skrivit. Jag har också lagt till en mer detaljerad förklaring av algoritmen om du vill förstå hur den fungerar.

Steg 1: Bygg och spela

För att bygga Tic Tac Toe -spelet behöver du följande komponenter:

• En Arduino Uno
• 9 WS2812 RGB -lysdioder
• 9 tryckknappar
• några tråd- och bygelkablar

Anslut komponenterna enligt Fritzing -skissen. Ladda sedan upp koden till din Arduino.

Som standard tar Arduino den första svängen. För att göra saker lite mer intressanta väljs det första steget slumpmässigt. Efter det första draget använder Arduino minimax -algoritmen för att bestämma bästa möjliga drag. Du startar ett nytt spel genom att återställa Arduino.

Du kan se Arduino "tänka" genom att öppna seriemonitorn. För varje möjligt drag beräknar algoritmen ett betyg som anger om detta drag kommer att leda till en vinst (värde 10) eller en förlust (värde -10) för Arduino eller oavgjort (värde 0).

Du kan också se Arduino spela mot sig själv genom att inte kommentera raden "#define DEMO_MODE" i början av skissen. Om du laddar upp den modifierade skissen gör Arduino det första steget slumpmässigt och använder sedan minimax -algoritmen för att bestämma det bästa draget för varje spelare i varje varv.

Observera att du inte kan vinna mot Arduino. Varje spel kommer antingen att sluta oavgjort eller du förlorar om du gör ett misstag. Detta beror på att algoritmen alltid väljer bästa möjliga drag. Som du kanske vet kommer en omgång Tic Tac Toe alltid att sluta oavgjort om båda spelarna inte gör något misstag. I demoläge slutar varje spel oavgjort eftersom, som vi alla vet, datorer aldrig gör misstag;-)

Steg 2: Minimax -algoritmen

Algoritmen består av två komponenter: en utvärderingsfunktion och en sökstrategi. Utvärderingsfunktionen är en funktion som tilldelar styrelsens positioner ett numeriskt värde. Om positionen är en slutposition (dvs. en position där antingen den blå spelaren eller den röda spelaren har vunnit eller där ingen av spelarna har vunnit) är utvärderingsfunktionen mycket enkel: Låt oss säga att Arduino spelar blå och den mänskliga spelaren spelar rött. Om positionen är en vinnande position för blå, tilldelar funktionen ett värde på 10 till den positionen; om det är en vinnande position för rött tilldelar funktionen värdet -10 till positionen; och om positionen är oavgjort tilldelar funktionen ett värde på 0.

När det är Arduino -tur, vill den välja ett drag som maximerar värdet av utvärderingsfunktionen, eftersom maximering av värdet innebär att det föredrar en vinst framför ett oavgjort (10 är större än 0) och föredrar ett oavgjort framför att förlora (0 är större än -10). Genom ett analogt argument vill motståndaren spela på ett sådant sätt att hon minimerar värdet av utvärderingsfunktionen.

För en icke-slutlig position beräknar algoritmen värdet av utvärderingsfunktionen genom en rekursiv sökstrategi. Från och med den nuvarande positionen simulerar den växelvis alla drag som den blå spelaren och den röda spelaren kan ta. Detta kan visualiseras som ett träd, som i diagrammet. När den kommer till en slutposition börjar den gå tillbaka och bära värdet av utvärderingsfunktionen från den lägre rekursionsnivån till den högre rekursionsnivån. Det tilldelar maximalt (om det i motsvarande rekursionssteg är den blå spelarens tur) eller minimum (om det i motsvarande rekursionssteg är den röda spelarens tur) för värdena för utvärderingsfunktionen från den lägre rekursionsnivån till positionen på högre rekursionsnivå. Slutligen, när algoritmen har slutat gå tillbaka och har kommit fram till den aktuella positionen igen, tar det det drag (eller ett av drag) som har det maximala värdet för utvärderingsfunktionen.

Det här låter kanske lite abstrakt, men det är faktiskt inte så svårt. Tänk på positionen som visas överst i diagrammet. I det första rekursionssteget finns det tre olika drag som blå kan ta. Blue försöker maximera värdet av utvärderingsfunktionen. För vart och ett av de drag blå kan ta, finns det två drag som rött kan ta. Röd försöker minimera värdet av utvärderingsfunktionen. Tänk på rörelsen där blå spelar i det övre högra hörnet. Om rött spelar i mittfältet har rött vunnit (-10). Om däremot rött spelar i den nedre rutan i mitten, vinner blått i nästa drag (10). Så om blått spelas i det övre högra hörnet, kommer rött att spela i mittrutan, eftersom det minimerar värdet av utvärderingsfunktionen. Analogt, om blått spelas i den nedre rutan i mitten, kommer rött igen att spela i mittrutan eftersom det minimerar utvärderingsfunktionen. Om blått däremot spelar i mittfältet spelar det ingen roll vilket drag rött tar, blått kommer alltid att vinna (10). Eftersom blå vill maximera utvärderingsfunktionen kommer den att spelas i mittrutan, eftersom den positionen resulterar i ett större värde för utvärderingsfunktionen (10) än de andra två rörelserna (-10).

Steg 3: Felsökning och ytterligare steg

Om du trycker på en knapp och en annan lysdiod än den som motsvarar knappen tänds har du antingen blandat ihop kablarna på stift A0-A2 eller 4-6 eller så har du anslutit lysdioderna i fel ordning.

Observera också att algoritmen inte nödvändigtvis alltid väljer ett drag som låter Arduino vinna så snabbt som möjligt. Faktum är att jag ägnade tid åt att felsöka algoritmen eftersom Arduino inte valde ett drag som skulle ha varit ett vinnande drag. Det tog lite tid innan jag insåg att det istället hade valt ett drag som garanterade att det skulle vinna ett drag senare. Om du vill kan du försöka ändra algoritmen så att den alltid kommer att föredra ett vinnande drag framför en senare vinst.

En möjlig förlängning av detta projekt skulle vara att använda algoritmen för att bygga en AI för en 4x4 eller till och med en 5x5 Tic Tac Toe. Observera dock att antalet positioner som algoritmen behöver undersöka växer mycket snabbt. Du måste hitta sätt att göra utvärderingsfunktionen mer intelligent genom att fastställa värden till positioner som inte är slutgiltiga, baserat på sannolikheten att positionen är bra eller dålig för spelaren i fråga. Du kan också försöka göra sökningen mer intelligent genom att stoppa rekursionen tidigt om ett drag visar sig vara mindre värt att utforska än alternativa drag.

Arduino är förmodligen inte den bästa plattformen för sådana tillägg på grund av sitt begränsade minne. Rekursion låter stacken växa under programkörning, och om stacken växer för mycket kan det skada programminnet, vilket kan leda till kraschar eller oregelbundna beteenden. Jag valde Arduino för det här projektet främst för att jag ville se om det kunde göras och för utbildningsändamål, inte för att det är det bästa valet för den här typen av problem.