Tic Tac Toe juu ya Arduino Pamoja na AI (Minimax Algorithm): 3 Hatua

2024 Mwandishi: John Day | [email protected]. Mwisho uliobadilishwa: 2024-01-30 12:54

Katika hii ya kufundisha nitakuonyesha jinsi ya kujenga mchezo wa Tic Tac Toe na AI ukitumia Arduino. Unaweza kucheza dhidi ya Arduino au uangalie Arduino ikicheza dhidi yake.

Ninatumia algorithm inayoitwa "minimax algorithm", ambayo inaweza kutumika sio tu kujenga AI ya Tic Tac Toe, lakini pia kwa anuwai ya michezo mingine kama Nne kwenye safu, checkers au hata chess. Michezo kama chess ni ngumu sana na inahitaji matoleo mengi yaliyosafishwa ya algorithm. Kwa mchezo wetu wa Tic Tac Toe, tunaweza kutumia toleo rahisi zaidi la algorithm, ambayo hata hivyo inavutia sana. Kwa kweli, AI ni nzuri sana kwamba haiwezekani kumpiga Arduino!

Mchezo ni rahisi kujenga. Unahitaji tu vitu vichache na mchoro ambao nimeandika. Niliongeza pia maelezo ya kina zaidi ya algorithm, ikiwa unataka kuelewa jinsi inavyofanya kazi.

Hatua ya 1: Jenga na Ucheze

Ili kujenga mchezo wa Tic Tac Toe utahitaji vifaa vifuatavyo:

• Arduino Uno
• LED za 9 WS2812 RGB
• Vifungo 9 vya kushinikiza
• nyaya za waya na jumper

Funga vifaa kama inavyoonyeshwa kwenye mchoro wa Fritzing. Kisha pakia nambari hiyo kwa Arduino yako.

Kwa chaguo-msingi, Arduino inachukua zamu ya kwanza. Ili kufanya mambo ya kuvutia zaidi, hatua ya kwanza imechaguliwa bila mpangilio. Baada ya hoja ya kwanza, Arduino hutumia algorithm ya minimax kuamua hoja bora zaidi. Unaanza mchezo mpya kwa kuweka upya Arduino.

Unaweza kutazama "fikiria" ya Arduino kwa kufungua Monitor Serial. Kwa kila hoja inayowezekana, algorithm inakadiria ukadiriaji ambao unaonyesha ikiwa hoja hii itasababisha kushinda (thamani ya 10) au hasara (thamani ya -10) kwa Arduino au sare (thamani ya 0).

Unaweza pia kutazama Arduino ikicheza dhidi yake kwa kukomesha laini "#fafanua DEMO_MODE" mwanzoni kabisa mwa mchoro. Ukipakia mchoro uliobadilishwa, Arduino hufanya hatua ya kwanza bila mpangilio na kisha hutumia algorithm ya minimax kuamua hoja bora kwa kila mchezaji kila upande.

Kumbuka kuwa huwezi kushinda dhidi ya Arduino. Kila mchezo utaisha kwa sare au utapoteza, ikiwa utafanya makosa. Hii ni kwa sababu algorithm huchagua hoja bora kila wakati. Kama unavyojua, mchezo wa Tic Tac Toe utamalizika kwa sare kila wakati ikiwa wachezaji wote hawatakosea. Katika hali ya onyesho, kila mchezo huisha kwa sare kwa sababu, kama sisi sote tunavyojua, kompyuta hazifanyi makosa;-)

Hatua ya 2: Algorithm ya Minimax

Algorithm inajumuisha vitu viwili: kazi ya tathmini na mkakati wa utaftaji. Kazi ya tathmini ni kazi ambayo inapeana nambari ya nambari kwa nafasi za bodi. Ikiwa nafasi ni nafasi ya mwisho (yaani, nafasi ambayo mchezaji wa bluu au mchezaji nyekundu ameshinda au ambapo hakuna mchezaji ameshinda), kazi ya tathmini ni rahisi sana: Wacha tuseme Arduino inacheza bluu na mchezaji wa kibinadamu anacheza nyekundu. Ikiwa nafasi ni nafasi ya kushinda kwa hudhurungi, kazi inapeana thamani ya 10 kwa nafasi hiyo; ikiwa ni nafasi ya kushinda nyekundu, kazi inapeana dhamana ya -10 kwa msimamo; na ikiwa msimamo ni sare, kazi inapeana thamani ya 0.

Wakati ni zamu ya Arduino, inataka kuchagua mwendo ambao unakuza thamani ya kazi ya tathmini, kwa sababu kuongeza thamani kunamaanisha kuwa itapendelea kushinda juu ya sare (10 ni kubwa kuliko 0) na inaelekeza sare juu ya kupoteza (0 ni kubwa kuliko -10). Kwa hoja inayofanana, mpinzani anataka kucheza kwa njia ambayo hupunguza thamani ya kazi ya tathmini.

Kwa nafasi isiyo ya mwisho, algorithm huhesabu thamani ya kazi ya tathmini na mkakati wa utaftaji wa kurudia. Kuanzia nafasi ya sasa, inaiga hatua zote ambazo mchezaji wa bluu na mchezaji nyekundu wanaweza kuchukua. Hii inaweza kuonyeshwa kama mti, kama kwenye mchoro. Inapofika katika nafasi ya mwisho, huanza kurudi nyuma, ikibeba dhamana ya kazi ya tathmini kutoka kiwango cha chini cha kurudia hadi kiwango cha juu cha kurudia. Inatoa kiwango cha juu (ikiwa katika hatua inayofanana ya kurudia ni zamu ya mchezaji wa bluu) au kiwango cha chini (ikiwa katika hatua inayofanana ya kurudia ni zamu ya mchezaji nyekundu) ya maadili ya kazi ya tathmini kutoka kiwango cha chini cha kurudia hadi nafasi kwenye kiwango cha juu cha kujirudia. Mwishowe, wakati algorithm imemaliza kurudi nyuma na imefika katika nafasi ya sasa tena, inachukua hoja hiyo (au moja ya hoja) ambayo ina kiwango cha juu cha kazi ya tathmini.

Hii inaweza kusikika kuwa ya kufikirika, lakini sio ngumu sana. Fikiria nafasi iliyoonyeshwa juu ya mchoro. Katika hatua ya kwanza ya kurudia, kuna hatua tatu tofauti ambazo bluu inaweza kuchukua. Bluu inajaribu kuongeza thamani ya kazi ya tathmini. Kwa kila moja ya bluu inayoweza kuchukua, kuna hatua mbili nyekundu zinaweza kuchukua. Nyekundu inajaribu kupunguza thamani ya kazi ya tathmini. Fikiria hoja ambayo bluu inacheza kona ya juu kulia. Ikiwa nyekundu inacheza kwenye sanduku la katikati, nyekundu imeshinda (-10). Ikiwa, kwa upande mwingine, nyekundu inacheza kwenye sanduku la chini la katikati, bluu itashinda katika hoja inayofuata (10). Kwa hivyo, ikiwa bluu inacheza kona ya juu kulia, nyekundu itacheza kwenye kisanduku cha katikati, kwani hiyo inapunguza thamani ya kazi ya tathmini. Analog, ikiwa bluu inacheza kwenye sanduku la chini la katikati, nyekundu itacheza tena kwenye sanduku la katikati kwa sababu hiyo inapunguza kazi ya tathmini. Ikiwa, kwa upande mwingine, bluu inacheza kwenye sanduku la katikati, haijalishi ni nyekundu ipi inachukua, bluu itashinda kila wakati (10). Kwa kuwa bluu inataka kuongeza kazi ya tathmini, itacheza kwenye kisanduku cha katikati, kwa kuwa nafasi hiyo inasababisha dhamana kubwa ya kazi ya tathmini (10) kuliko hatua zingine mbili (-10).

Hatua ya 3: Utatuzi na Hatua zaidi

Ikiwa unasukuma kitufe na mwangaza tofauti na ile inayolingana na kitufe, basi labda umepata waya kwenye pini A0-A2 au 4-6 iliyochanganywa, au umeunganisha LED kwa mpangilio usiofaa.

Pia kumbuka kuwa algorithm sio lazima kila wakati ichague hoja ambayo itawaruhusu Arduino kushinda haraka iwezekanavyo. Kwa kweli, nilitumia muda kumaliza utatuzi kwa sababu Arduino hakuchagua hoja ambayo ingekuwa hatua ya kushinda. Ilinichukua muda hadi nikagundua kuwa badala yake ilichagua hoja ambayo ilihakikisha kwamba itashinda hoja moja baadaye. Ikiwa unataka, unaweza kujaribu kurekebisha algorithm ili iweze kupendelea hoja ya kushinda kwa ushindi wa baadaye.

Ugani unaowezekana wa mradi huu itakuwa kutumia algorithm kujenga AI kwa 4x4 au hata 5x5 Tic Tac Toe. Walakini, kumbuka kuwa idadi ya nafasi ambazo algorithm inahitaji kuchunguza inakua haraka sana. Utahitaji kutafuta njia za kufanya kazi ya tathmini iwe na akili zaidi kwa kudhibitisha maadili kwa nafasi ambazo sio za mwisho, kwa kuzingatia uwezekano kwamba nafasi hiyo ni nzuri au mbaya kwa mchezaji anayehusika. Unaweza pia kujaribu kufanya utaftaji uwe na akili zaidi kwa kusimamisha marudio mapema ikiwa hoja inageuka kuwa haistahili uchunguzi zaidi kuliko hatua mbadala.

Arduino labda sio jukwaa bora la upanuzi kama huo kwa sababu ya kumbukumbu yake ndogo. Kurudiwa huacha stack ikue wakati wa utekelezaji wa programu, na ikiwa stack inakua sana, inaweza kuharibu kumbukumbu ya programu, na kusababisha shambulio au tabia mbaya. Nilichagua Arduino kwa mradi huu haswa kwa sababu nilitaka kuona ikiwa inaweza kufanywa na kwa madhumuni ya kielimu, sio kwa sababu ni chaguo bora kwa aina hii ya shida.