AI ilə Arduino -da Tic Tac Toe (Minimax Alqoritmi): 3 addım

2024 Müəllif: John Day | [email protected]. Son dəyişdirildi: 2024-01-30 07:47

Bu Təlimat kitabında sizə Arduino istifadə edərək AI ilə Tic Tac Toe oyununun necə qurulacağını göstərəcəyəm. Ya Arduinoya qarşı oynaya bilərsən, ya da Arduinonun özünə qarşı oyununa baxa bilərsən.

"Minimax alqoritmi" adlı bir alqoritmdən istifadə edirəm ki, bu da yalnız Tic Tac Toe üçün AI qurmaq üçün deyil, həm də Dörd Sıra, dama və ya hətta şahmat kimi digər oyunlar üçün də istifadə edilə bilər. Şahmat kimi oyunlar çox mürəkkəbdir və alqoritmin daha zərif versiyalarını tələb edir. Tic Tac Toe oyunumuz üçün alqoritmin ən sadə versiyasından istifadə edə bilərik, buna baxmayaraq olduqca təsir edicidir. Əslində, AI o qədər yaxşıdır ki, Arduinoya qalib gəlmək mümkün deyil!

Oyun qurmaq asandır. Yalnız bir neçə komponentə və yazdığım eskizə ehtiyacınız var. Alqoritmin necə işlədiyini başa düşmək istəyirsinizsə daha ətraflı bir şərh əlavə etdim.

Addım 1: Yarat və Oyna

Tic Tac Toe oyununu qurmaq üçün aşağıdakı komponentlərə ehtiyacınız olacaq:

• Bir Arduino Uno
• 9 WS2812 RGB LED
• 9 düymə
• bəzi tel və tullanan kabellər

Fritzing eskizində göstərildiyi kimi komponentləri bağlayın. Sonra kodu Arduino -ya yükləyin.

Varsayılan olaraq, ilk növbədə Arduino gəlir. Hər şeyi bir az daha maraqlı etmək üçün ilk hərəkət təsadüfi seçilir. İlk hərəkətdən sonra, Arduino mümkün olan ən yaxşı hərəkəti təyin etmək üçün minimax alqoritmindən istifadə edir. Arduino'yu sıfırlayaraq yeni bir oyuna başlayarsınız.

Serial Monitoru açaraq Arduinonun "düşünməsini" izləyə bilərsiniz. Alqoritm, mümkün olan hər bir hərəkət üçün, Arduino üçün qalibiyyətə (10 dəyər) və ya məğlubiyyətə (-10 dəyər) və ya heç -heçəyə (0 dəyəri) səbəb olub olmadığını göstərən bir reytinq hesablayır.

Eskizin əvvəlindəki "#define DEMO_MODE" xəttini şərh etmədən Arduinonun özünə qarşı oynadığını da izləyə bilərsiniz. Dəyişdirilmiş eskizi yükləsəniz, Arduino ilk hərəkəti təsadüfi edir və sonra hər növbədə hər oyunçu üçün ən yaxşı hərəkəti təyin etmək üçün minimax alqoritmindən istifadə edir.

Arduinoya qalib gələ bilməyəcəyinizi unutmayın. Hər oyun ya heç -heçə ilə bitəcək, ya da səhv etsəniz uduzacaqsınız. Bunun səbəbi, alqoritmin hər zaman mümkün olan ən yaxşı hərəkəti seçməsidir. Bildiyiniz kimi, Tic Tac Toe oyunu hər iki oyunçu səhv etmirsə həmişə heç -heçə ilə başa çatacaq. Demo rejimində hər oyun heç-heçə ilə başa çatır, çünki hamımızın bildiyimiz kimi kompüterlər heç vaxt səhv etmirlər;-)

Addım 2: Minimax Alqoritmi

Alqoritm iki komponentdən ibarətdir: qiymətləndirmə funksiyası və axtarış strategiyası. Qiymətləndirmə funksiyası lövhə mövqelərinə ədədi dəyər verən bir funksiyadır. Mövqe son mövqedirsə (yəni, mavi oyunçunun və ya qırmızı oyunçunun qalib gəldiyi və ya heç bir oyunçunun qalib olmadığı bir mövqe), qiymətləndirmə funksiyası çox sadədir: Tutaq ki, Arduino mavi, insan oyunçusu qırmızı oynayır. Mövqe mavi üçün qazanan bir mövqedirsə, funksiya bu mövqeyə 10 dəyər verir; qırmızı üçün qazanan bir mövqedirsə, funksiya mövqeyə -10 dəyərini təyin edir; və mövqe heç -heçə olarsa, funksiya 0 dəyərini təyin edir.

Arduino növbəsi gəldikdə, qiymətləndirmə funksiyasının dəyərini maksimuma çatdıran bir hərəkət seçmək istəyir, çünki dəyəri maksimuma çatdırmaq, heç -heçə üzərində qələbəni (10 -dan böyükdür) və uduzmaq əvəzinə heç -heçəni (0 -10 -dan böyükdür). Bənzər bir arqument olaraq, rəqib qiymətləndirmə funksiyasının dəyərini minimuma endirəcək şəkildə oynamaq istəyir.

Qeyri-son mövqe üçün alqoritm rekursiv axtarış strategiyası ilə qiymətləndirmə funksiyasının dəyərini hesablayır. Mövcud mövqedən başlayaraq, mavi oyunçu ilə qırmızı oyunçunun edə biləcəyi bütün hərəkətləri simulyasiya edir. Bunu diaqramdakı kimi bir ağac kimi görmək olar. Son mövqeyə gəldikdə, qiymətləndirmə funksiyasının dəyərini aşağı rekursiya səviyyəsindən daha yüksək rekursiya səviyyəsinə daşıyaraq geri çəkilməyə başlayır. Aşağıdakı rekursiya səviyyəsindən qiymətləndirmə funksiyasının dəyərlərini maksimum (müvafiq rekursiya mərhələsində mavi oyunçunun növbəsidirsə) və ya minimumunu (müvafiq rekursiya mərhələsində qırmızı oyunçunun növbəsidir) təyin edir. daha yüksək rekursiya səviyyəsi. Nəhayət, alqoritm geri çəkilməyi bitirib yenidən cari vəziyyətə gəldikdə, maksimum qiymətləndirmə funksiyası dəyərinə malik olan bu hərəkəti (və ya hərəkətlərdən birini) götürür.

Bu bir qədər mücərrəd görünə bilər, amma əslində o qədər də çətin deyil. Diaqramın yuxarı hissəsində göstərilən mövqeyi nəzərdən keçirin. İlk yineleme addımında, göyün edə biləcəyi üç fərqli hərəkət var. Mavi, qiymətləndirmə funksiyasının dəyərini maksimum dərəcədə artırmağa çalışır. Göyün edə biləcəyi hər hərəkət üçün qırmızı gedə biləcək iki hərəkət var. Qırmızı qiymətləndirmə funksiyasının dəyərini minimuma endirməyə çalışır. Göyün sağ üst küncdə oynadığı hərəkəti düşünün. Qırmızı mərkəzi qutuda oynayırsa, qırmızı qazandı (-10). Digər tərəfdən, qırmızı alt alt qutuda oynayırsa, mavi növbəti hərəkətdə qalib gələcək (10). Beləliklə, mavi sağ üst küncdə oynayırsa, qırmızı orta qutuda oynayacaq, çünki bu qiymətləndirmə funksiyasının dəyərini minimuma endirir. Eynilə, mavi alt alt qutuda oynayırsa, qırmızı yenidən orta qutuda oynayacaq, çünki bu qiymətləndirmə funksiyasını minimuma endirir. Digər tərəfdən, mavi mərkəzi qutuda oynayırsa, qırmızıdan hansı hərəkətin getməsinin əhəmiyyəti yoxdur, mavi həmişə qalib gələcək (10). Mavi, qiymətləndirmə funksiyasını maksimum dərəcədə artırmaq istədiyi üçün, orta mövqedə oynayacaq, çünki bu mövqe qiymətləndirmə funksiyasının (10) digər iki hərəkətdən (-10) daha böyük bir dəyəri ilə nəticələnir.

Addım 3: Problem Giderme və Əlavə Adımlar

Bir düyməni basarsanız və düyməyə uyğun olaraq fərqli bir LED yanarsa, ehtimal ki, A0-A2 və ya 4-6 pinlərindəki telləri qarışdırmışsınız və ya LEDləri səhv qaydada bağlamısınız.

Həm də unutmayın ki, alqoritm həmişə Arduinonun mümkün qədər tez qalib gəlməsinə imkan verəcək bir hərəkət seçmir. Əslində, bir müddət alqoritmi düzəltməklə məşğul oldum, çünki Arduino qazanan bir hərəkət seçməmişdi. Bunun əvəzinə daha sonra bir hərəkət qazanacağını zəmanət verən bir hərəkət seçdiyini başa düşməyimə qədər bir müddət keçdi. İstəyirsinizsə, alqoritmi dəyişdirməyə çalışa bilərsiniz ki, sonrakı qalibiyyətdən daha çox qələbə qazanmağa üstünlük versin.

Bu layihənin mümkün bir uzantısı, 4x4 və ya hətta 5x5 Tic Tac Toe üçün AI qurmaq üçün alqoritmdən istifadə etmək olar. Ancaq alqoritmin araşdırması lazım olan mövqelərin sayının çox sürətlə artdığını unutmayın. Vəziyyətin söz mövzusu oyunçu üçün yaxşı və ya pis olması ehtimalına əsaslanaraq, son olmayan mövqelərə dəyərlər verərək qiymətləndirmə funksiyasını daha ağıllı etmək yollarını tapmalısınız. Alternativ hərəkətlərdən daha çox araşdırmaya daha az layiq olduğu ortaya çıxsa, rekursiyanı erkən dayandıraraq, axtarışın daha ağıllı olmasına çalışa bilərsiniz.

Yaddaşı məhdud olduğundan Arduino, ehtimal ki, bu cür uzantılar üçün ən yaxşı platforma deyil. Rekursiya, proqramın icrası zamanı yığının böyüməsinə imkan verir və yığın çox artarsa, proqram yaddaşını korlaya bilər, bu da çökməyə və ya nizamsız davranışa səbəb ola bilər. Arduino'yu bu layihə üçün seçdim, çünki bunun mümkün olub -olmadığını və təhsil məqsədləri üçün yox, bu cür problem üçün ən yaxşı seçim olduğuna görə.