Tic Tac Toe uz Arduino ar AI (Minimax algoritms): 3 soļi

2025 Autors: John Day | [email protected]. Pēdējoreiz modificēts: 2025-01-23 14:59

Šajā pamācībā es jums parādīšu, kā izveidot Tic Tac Toe spēli ar AI, izmantojot Arduino. Jūs varat spēlēt pret Arduino vai skatīties, kā Arduino spēlē pret sevi.

Es izmantoju algoritmu ar nosaukumu "minimax algoritms", ko var izmantot ne tikai, lai izveidotu mākslīgā intelekta Tic Tac Toe, bet arī daudzām citām spēlēm, piemēram, Četri rindā, dambrete vai pat šahs. Spēles, piemēram, šahs, ir ļoti sarežģītas, un tām ir vajadzīgas daudz izsmalcinātākas algoritma versijas. Mūsu Tic Tac Toe spēlei mēs varam izmantot vienkāršāko algoritma versiju, kas tomēr ir diezgan iespaidīga. Patiesībā AI ir tik labs, ka nav iespējams pārspēt Arduino!

Spēli ir viegli veidot. Jums ir vajadzīgas tikai dažas sastāvdaļas un mana uzrakstītā skice. Es arī pievienoju detalizētāku algoritma skaidrojumu, ja vēlaties saprast, kā tas darbojas.

1. darbība. Veidojiet un spēlējiet

Lai izveidotu spēli Tic Tac Toe, jums būs nepieciešami šādi komponenti:

• Arduino Uno
• 9 WS2812 RGB gaismas diodes
• 9 spiedpogas
• daži vadi un savienojuma kabeļi

Pievienojiet komponentus vadiem, kā parādīts Fritzing skicē. Pēc tam augšupielādējiet kodu savā Arduino.

Pēc noklusējuma Arduino uzņem pirmo pagriezienu. Lai padarītu lietas mazliet interesantākas, pirmais gājiens tiek izvēlēts nejauši. Pēc pirmā gājiena Arduino izmanto minimuma algoritmu, lai noteiktu labāko iespējamo gājienu. Jūs sākat jaunu spēli, atiestatot Arduino.

Jūs varat skatīties, kā Arduino "domā", atverot sērijas monitoru. Katram iespējamajam gājienam algoritms aprēķina vērtējumu, kas norāda, vai šī kustība novedīs pie Arduino uzvaras (vērtība 10) vai zaudējuma (vērtība -10) vai neizšķirta (vērtība 0).

Varat arī skatīties, kā Arduino spēlē pret sevi, pašā skices sākumā nekomentējot rindiņu "#define DEMO_MODE". Ja augšupielādējat modificēto skici, Arduino pirmo gājienu veic nejauši un pēc tam izmanto minimuma algoritmu, lai noteiktu labāko gājienu katram spēlētājam katrā gājienā.

Ņemiet vērā, ka jūs nevarat uzvarēt pret Arduino. Katra spēle vai nu beigsies neizšķirti, vai arī jūs zaudēsit, ja pieļausit kļūdu. Tas ir tāpēc, ka algoritms vienmēr izvēlas labāko iespējamo gājienu. Kā jūs zināt, Tic Tac Toe spēle vienmēr beigsies neizšķirti, ja abi spēlētāji nekļūdās. Demo režīmā katra spēle beidzas ar neizšķirtu, jo, kā mēs visi zinām, datori nekad nekļūdās;-)

2. solis: Minimax algoritms

Algoritms sastāv no divām sastāvdaļām: novērtēšanas funkcijas un meklēšanas stratēģijas. Novērtēšanas funkcija ir funkcija, kas piešķir skaitlisku vērtību valdes pozīcijām. Ja pozīcija ir galīgā pozīcija (ti, pozīcija, kurā uzvarējis zilais vai sarkanais spēlētājs vai neviens no spēlētājiem), novērtēšanas funkcija ir ļoti vienkārša: pieņemsim, ka Arduino spēlē zilu, bet cilvēks - sarkanu.. Ja pozīcija ir zilā uzvara, funkcija šai pozīcijai piešķir vērtību 10; ja tā ir uzvarētāja pozīcija sarkanā krāsā, funkcija piešķir pozīcijai vērtību -10; un, ja pozīcija ir neizšķirts, funkcija piešķir vērtību 0.

Kad pienāk Arduino kārta, tas vēlas izvēlēties gājienu, kas maksimāli palielina vērtēšanas funkcijas vērtību, jo vērtības palielināšana nozīmē, ka tā dod priekšroku uzvarai, nevis neizšķirtam (10 ir lielāka par 0), bet dod priekšroku neizšķirtam, nevis zaudējumam (0 ir lielāks par -10). Ar līdzīgu argumentu pretiniece vēlas spēlēt tā, lai viņa samazinātu novērtēšanas funkcijas vērtību.

Attiecībā uz pozīciju, kas nav galīga, algoritms aprēķina novērtēšanas funkcijas vērtību, izmantojot rekursīvu meklēšanas stratēģiju. Sākot no pašreizējās pozīcijas, tas pārmaiņus simulē visas kustības, ko var veikt zilais un sarkanais spēlētājs. To var vizualizēt kā koku, piemēram, diagrammā. Kad tas nonāk galīgajā pozīcijā, tas sāk atkāpties, pārnesot novērtēšanas funkcijas vērtību no zemākā rekursijas līmeņa uz augstāko rekursijas līmeni. Tas piešķir maksimālo (ja attiecīgajā rekursijas posmā ir zilā spēlētāja kārta) vai minimālo (ja attiecīgajā rekursijas solī ir sarkanā spēlētāja kārta) vērtēšanas funkcijas vērtības no zemākā rekursijas līmeņa uz pozīciju augstāks rekursijas līmenis. Visbeidzot, kad algoritms ir pabeidzis atkāpšanos un atkal sasniedzis pašreizējo pozīciju, tas aizņem šo gājienu (vai vienu no gājieniem), kuram ir maksimālā novērtēšanas funkcijas vērtība.

Tas var likties nedaudz abstrakti, bet patiesībā tas nav tik grūti. Apsveriet pozīciju, kas parādīta diagrammas augšpusē. Pirmajā rekursijas solī ir trīs dažādas zilās kustības. Zils mēģina palielināt novērtēšanas funkcijas vērtību. Katrai zilajai kustībai ir divas sarkanas. Sarkans mēģina samazināt novērtēšanas funkcijas vērtību. Apsveriet gājienu, kur zilais spēlē augšējā labajā stūrī. Ja centra lodziņā spēlē sarkanā krāsa, sarkanā krāsa ir uzvarējusi (-10). Savukārt, ja centrā apakšējā lodziņā spēlē sarkanā krāsa, nākamajā gājienā uzvarēs zilā krāsa (10). Tātad, ja augšējā labajā stūrī tiek atskaņots zils, centrālajā lodziņā tiks atskaņots sarkans, jo tas samazina novērtēšanas funkcijas vērtību. Līdzīgi, ja apakšējā apakšējā lodziņā spēlē zils, tad centrālajā lodziņā atkal tiks atskaņots sarkans, jo tas samazina novērtēšanas funkciju. Savukārt, ja centra lodziņā spēlē zils, nav nozīmes tam, kurš gājiens ir sarkans, zils vienmēr uzvarēs (10). Tā kā zilā krāsa vēlas palielināt novērtēšanas funkciju, tā tiks atskaņota centrālajā lodziņā, jo šī pozīcija rada lielāku novērtēšanas funkcijas vērtību (10) nekā pārējās divas kustības (-10).

3. darbība: problēmu novēršana un turpmākās darbības

Ja nospiežat pogu un iedegas cita gaismas diode, nevis tā, kas atbilst pogai, iespējams, ka esat sajaukuši vadus uz tapām A0-A2 vai 4-6, vai arī pievienojāt gaismas diodes nepareizā secībā.

Ņemiet vērā arī to, ka algoritms ne vienmēr izvēlas gājienu, kas ļaus Arduino uzvarēt pēc iespējas ātrāk. Patiesībā es kādu laiku pavadīju algoritma atkļūdošanā, jo Arduino neizvēlējās gājienu, kas būtu uzvarējis. Pagāja kāds laiks, līdz es sapratu, ka tā vietā ir izvēlēts gājiens, kas garantēja, ka tas uzvarēs vienu gājienu vēlāk. Ja vēlaties, varat mēģināt modificēt algoritmu tā, lai tas vienmēr dotu priekšroku uzvarošam solim, nevis vēlākam laimējumam.

Iespējamais šī projekta paplašinājums būtu izmantot algoritmu, lai izveidotu AI 4x4 vai pat 5x5 Tic Tac Toe. Tomēr ņemiet vērā, ka algoritmam pārbaudāmo pozīciju skaits pieaug ļoti strauji. Jums būs jāatrod veidi, kā padarīt novērtēšanas funkciju saprātīgāku, nosakot vērtības pozīcijām, kas nav galīgas, pamatojoties uz varbūtību, ka attiecīgā spēlētāja pozīcija ir laba vai slikta. Varat arī mēģināt padarīt meklēšanu saprātīgāku, pārtraucot rekursiju agri, ja gājiens izrādās mazāk cienīgs tālākai izpētei nekā alternatīvi gājieni.

Arduino, iespējams, nav labākā platforma šādiem paplašinājumiem, jo tai ir ierobežota atmiņa. Rekursija ļauj kaudzei augt programmas izpildes laikā, un, ja kaudze aug pārāk daudz, tā var sabojāt programmas atmiņu, izraisot avārijas vai nepareizu darbību. Es izvēlējos Arduino šim projektam galvenokārt tāpēc, ka vēlējos noskaidrot, vai to var izdarīt, un izglītības nolūkos, nevis tāpēc, ka tā ir labākā izvēle šāda veida problēmām.