Tic Tac Toe op Arduino Met AI (Minimax -algoritme): 3 stappe

2024 Outeur: John Day | [email protected]. Laas verander: 2024-01-30 07:27

In hierdie Instructable gaan ek jou wys hoe om 'n Tic Tac Toe -speletjie te bou met 'n AI met behulp van 'n Arduino. U kan óf teen die Arduino speel óf kyk hoe die Arduino teen homself speel.

Ek gebruik 'n algoritme genaamd 'minimax -algoritme', wat nie net gebruik kan word om 'n AI vir Tic Tac Toe te bou nie, maar ook vir 'n verskeidenheid ander speletjies soos Four in a Row, dam of selfs skaak. Speletjies soos skaak is baie kompleks en vereis baie meer verfynde weergawes van die algoritme. Vir ons Tic Tac Toe -spel kan ons die eenvoudigste weergawe van die algoritme gebruik, wat nogtans redelik indrukwekkend is. Die AI is eintlik so goed dat dit onmoontlik is om die Arduino te verslaan!

Die spel is maklik om te bou. U benodig slegs 'n paar komponente en die skets wat ek geskryf het. Ek het ook 'n meer gedetailleerde verduideliking van die algoritme bygevoeg as u wil verstaan hoe dit werk.

Stap 1: Bou en speel

Om die Tic Tac Toe -speletjie te bou, benodig u die volgende komponente:

• 'N Arduino Uno
• 9 WS2812 RGB LED's
• 9 drukknoppies
• 'n paar draad- en springkabels

Draai die komponente vas soos in die Fritzing -skets getoon. Laai dan die kode op na u Arduino.

Die Arduino neem standaard die eerste draai. Om dinge 'n bietjie interessanter te maak, word die eerste stap lukraak gekies. Na die eerste beweging gebruik die Arduino die minimax -algoritme om die beste moontlike beweging te bepaal. U begin 'n nuwe speletjie deur die Arduino terug te stel.

U kan sien hoe die Arduino 'dink' deur die Serial Monitor oop te maak. Vir elke moontlike beweging bereken die algoritme 'n gradering wat aandui of hierdie skuif sal lei tot 'n oorwinning (waarde van 10) of 'n verlies (waarde van -10) vir die Arduino of 'n gelykop (waarde van 0).

U kan ook kyk hoe die Arduino teen homself speel deur die reël "#define DEMO_MODE" heel aan die begin van die skets uit te voer. As u die gewysigde skets oplaai, maak die Arduino lukraak die eerste skuif en gebruik dan die minimax -algoritme om die beste beweging vir elke speler in elke beurt te bepaal.

Let daarop dat u nie teen die Arduino kan wen nie. Elke wedstryd eindig gelykop of verloor as u 'n fout maak. Dit is omdat die algoritme altyd die beste moontlike stap kies. Soos u dalk weet, sal 'n spel Tic Tac Toe altyd gelykop eindig as albei spelers geen fout maak nie. In die demo-modus eindig elke wedstryd gelykop, want soos ons almal weet, maak rekenaars nooit foute nie;-)

Stap 2: Die Minimax -algoritme

Die algoritme bestaan uit twee komponente: 'n evalueringsfunksie en 'n soekstrategie. Die evalueringsfunksie is 'n funksie wat 'n numeriese waarde aan raadsposte toeken. As die posisie 'n finale posisie is (dit wil sê 'n posisie waar óf die blou speler óf die rooi speler gewen het of waar geen speler gewen het nie), is die evalueringsfunksie baie eenvoudig: Kom ons sê die Arduino speel blou en die mens speel rooi. As die posisie 'n wenposisie vir blou is, ken die funksie 'n waarde van 10 toe aan die posisie; as dit 'n wenposisie vir rooi is, ken die funksie 'n waarde van -10 toe aan die posisie; en as die posisie gelykop is, ken die funksie 'n waarde van 0 toe.

As dit die beurt van die Arduino is, wil hy 'n stap kies wat die waarde van die evalueringsfunksie maksimaliseer, want die maksimalisering van die waarde beteken dat dit 'n oorwinning bo 'n gelykopuitslag (10 groter as 0) sal verkies en 'n gelykopuitslag bo die verlies (0 is groter as -10). Deur 'n analoog argument wil die teenstander op so 'n manier speel dat sy die waarde van die evalueringsfunksie tot 'n minimum beperk.

Vir 'n nie-finale posisie, bereken die algoritme die waarde van die evalueringsfunksie deur 'n rekursiewe soekstrategie. Vanaf die huidige posisie, simuleer dit afwisselend al die bewegings wat die blou speler en die rooi speler kan neem. Dit kan as 'n boom voorgestel word, soos in die diagram. As dit by 'n finale posisie kom, begin dit terugstap en dra die waarde van die evalueringsfunksie van die laer rekursievlak na die hoër rekursievlak. Dit gee die maksimum (as in die ooreenstemmende rekursiestap die beurt aan die blou speler is) of die minimum (as dit in die ooreenstemmende rekursiestap die beurt is aan die rooi speler) van die waardes van die evalueringsfunksie van die laer rekursievlak tot die posisie op die hoër rekursievlak. Uiteindelik, as die algoritme klaar is met terugstap en weer by die huidige posisie aangekom het, neem dit die beweging (of een van die bewegings) met die maksimum waarde van die evalueringsfunksie.

Dit klink miskien 'n bietjie abstrak, maar dit is eintlik nie so moeilik nie. Beskou die posisie bo -aan die diagram. In die eerste rekursiestap is daar drie verskillende bewegings wat blou kan neem. Blue probeer om die waarde van die evalueringsfunksie te maksimeer. Vir elk van die bewegings wat blou kan neem, is daar twee bewegings wat rooi kan neem. Rooi probeer die waarde van die evalueringsfunksie tot 'n minimum beperk. Beskou die beweging waar blou in die regter boonste hoek speel. As rooi in die middelste boks speel, het rooi gewen (-10). As daar egter rooi in die middelste onderste boks speel, sal blou in die volgende stap (10) wen. As blou in die regter boonste hoek speel, speel rooi in die middelste boks, aangesien dit die waarde van die evalueringsfunksie tot 'n minimum beperk. Analoog, as blou in die middelste onderste boks speel, sal rooi weer in die middelste boks speel, want dit verminder die evalueringsfunksie. As daar egter blou in die middelste boks speel, maak dit nie saak watter beweging rooi neem nie, blou sal altyd wen (10). Aangesien blou die evalueringsfunksie wil maksimeer, speel dit in die middelste boks, aangesien die posisie 'n groter waarde van die evalueringsfunksie (10) tot gevolg het as die ander twee bewegings (-10).

Stap 3: Probleemoplossing en verdere stappe

As u op 'n knoppie druk en 'n ander LED as die een wat met die knoppie ooreenstem, brand, het u waarskynlik die drade op penne A0-A2 of 4-6 gemeng, of u het die LED's in die verkeerde volgorde gekoppel.

Let ook daarop dat die algoritme nie noodwendig altyd 'n stap kies waarmee die Arduino so vinnig as moontlik kan wen nie. Eintlik het ek 'n geruime tyd daaraan gesoek om die algoritme te ontfout omdat die Arduino nie 'n skuif gekies het wat 'n wenbeweging sou gewees het nie. Dit het my 'n geruime tyd geneem totdat ek besef het dat dit eerder 'n skuif gekies het wat verseker het dat dit 'n stap later sou wen. As u wil, kan u die algoritme probeer wysig sodat dit altyd 'n wenbeweging bo 'n latere oorwinning sal verkies.

'N Moontlike uitbreiding van hierdie projek sou wees om die algoritme te gebruik om 'n AI vir 'n 4x4 of selfs 'n 5x5 Tic Tac Toe te bou. Let egter daarop dat die aantal posisies wat die algoritme moet ondersoek baie vinnig groei. U sal maniere moet vind om die evalueringsfunksie intelligenter te maak deur waardes toe te ken aan posisies wat nie finaal is nie, gebaseer op die waarskynlikheid dat die posisie goed of sleg is vir die betrokke speler. U kan ook probeer om die soektog intelligenter te maak deur die rekursie vroeg te stop as 'n beweging minder waardig is om verder te ondersoek as alternatiewe bewegings.

Vanweë die beperkte geheue is die Arduino waarskynlik nie die beste platform vir sulke uitbreidings nie. Met rekursie kan die stapel groei tydens die uitvoering van die program, en as die stapel te veel groei, kan dit die geheue van die program beskadig, wat kan lei tot ineenstortings of wisselvallige gedrag. Ek het die Arduino vir hierdie projek gekies, hoofsaaklik omdat ek wou kyk of dit moontlik is en vir opvoedkundige doeleindes, nie omdat dit die beste keuse vir hierdie soort probleme is nie.