Masa Oyunu Süni Zəka: Minimax Alqoritmi: 8 Addım

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

Şahmat və ya dama qarşı oynadığınız kompüterlərin necə hazırlandığını heç düşündünüzmü? Minimax Alqoritmini istifadə edərək sadə, lakin təsirli bir süni intellektin (AI) necə qurulacağını sizə göstərəcək, çünki bu Təlimat kitabına baxmayın! Minimax Alqoritmini istifadə edərək, AI yaxşı planlaşdırılmış və düşünülmüş hərəkətlər edir (və ya heç olmasa düşüncə prosesini təqlid edir). İndi sizə hazırladığım AI -nin kodunu verə bilərəm, amma bu əyləncəli olmaz. Kompüter seçimlərinin arxasındakı məntiqi izah edəcəyəm.

Bu Təlimat kitabında, sizi pitonda Othello (AKA Reversi) üçün AI hazırlamağın addımları ilə tanış edəcəyəm. Bu layihəni həll etməzdən əvvəl pythonda necə kod yazılacağını orta səviyyədə bilməlisiniz. Sizi bu Təlimata hazırlamaq üçün baxmaq üçün bir neçə yaxşı veb sayt var: w3schools və ya learnpython. Bu Təlimatın sonunda, hesablanmış hərəkətlər edəcək və əksər insanları məğlub etməyi bacarmalı olan bir AI -yə sahib olmalısınız.

Bu Təlimat ilk növbədə süni intellektin necə yaradılacağına aid olacağından pythonda bir oyunun necə dizayn ediləcəyini izah etməyəcəyəm. Bunun əvəzinə, bir insanın başqa bir insana qarşı oynaya biləcəyi oyunun kodunu verəcəyəm və bir insanın AI -yə qarşı oynadığı bir oyunu oynayacaqsınız.

Columbia SHAPE -da bir yay proqramı vasitəsilə bu AI -nin necə yaradılacağını öyrəndim. Orada yaxşı vaxt keçirdim, buna görə maraqlanıb -maraqlanmayacaqlarını öyrənmək üçün veb saytlarına baxın.

Logistika yolundan çıxdıqdan sonra kodlamağa başlayaq!

(Şəkillərə bir neçə qeyd qoydum, onlara baxdığınızdan əmin olun)

Təchizat

Bu asandır:

1) Spyder və ya IDLE kimi bir piton mühiti olan kompüter

2) Otello oyunu üçün faylları GitHub -dan yükləyin

3) Səbrlə beyniniz qurulub

Addım 1: Lazımi faylları yükləyin

GitHub -a girəndə 5 fayl görməlisiniz. Hamısını yükləyin və hamısını eyni qovluğa yerləşdirin. Oyuna başlamazdan əvvəl casus mühitində bütün faylları açın.

Faylların etdikləri budur:

1) othello_gui.py bu fayl oyunçuların oynaması üçün oyun lövhəsi yaradır (istər insan olsun, istər kompüter)

2) othello_game.py, bu fayl oyun lövhəsi olmadan bir -birinə qarşı iki kompüter oynayır və yalnız hesab və hərəkət mövqelərini göstərir

3) ai_template.py, AI -ni yaratmaq üçün bütün kodlarınızı qoyacağınız yerdir

4) randy_ai.py, təsadüfi olaraq hərəkətlərini seçən əvvəlcədən hazırlanmış bir AI -dir

5) othello_shared.py, AI-ni hazırlamaq üçün istifadə edə biləcəyiniz bir çox əvvəlcədən hazırlanmış funksiyalar, məsələn, mövcud hərəkətləri, hesabları və ya lövhə vəziyyətini yoxlamaq

6) Üç digər fayl: sırasıyla SHAPE proqramından mənim, Erika və Nathan tərəfindən hazırlanan Puma.py, erika_5.py və nathan.py, bunlar unikal kodları olan üç fərqli AI -dir.

Addım 2: Python Otello -nu necə açmaq və oynamaq olar

Bütün faylları açdıqdan sonra, ekranın sağ alt küncündə "run othello_gui.py" yazın və IPython Konsoluna daxil edin. Və ya Mac terminalında "python othello_gui.py" yazın (əlbəttə ki, doğru qovluğa daxil olduqdan sonra). Sonra ekranda bir lövhə görünməlidir. Bu rejim insan və insan rejimidir. İşıq ikinci, qaranlıq isə birinci olur. Çaşqınsınızsa videoya baxın. iAt, hər rəng kafel hesab var. Oynamaq üçün bir kafel yerləşdirmək üçün etibarlı bir hərəkət yerini vurun və sonra kompüteri eyni şeyi edəcək və təkrar edəcək rəqibinizə verin.

Otello oynamağı bilmirsinizsə, ultra lövhələr veb saytından bu qaydaları oxuyun:

Qara həmişə ilk növbədə hərəkət edir. Oyunçunun rəngli bir diskini lövhədə rəqibin disklərindən birini və ya bir neçəsini "kənardan kənara çıxarıb" yerləşdirməklə hərəkət edilir. Bir disk və ya bir sıra disklər, ucları əks rəngli disklərlə əhatə olunduqda kənarda olur. Disk istənilən istiqamətdə (üfüqi, şaquli, diaqonal) bir və ya bir neçə sətirdə istənilən sayda diskin kənarına çıxa bilər. (veb saytında oxumağı bitirin)

Orijinal oyunla bu piton oyunu arasındakı fərq, bir oyunçu üçün heç bir etibarlı hərəkət qalmadıqda oyunun bitməsidir

Oyunu bir dostunuzla oynaya biləcəyiniz üçün, oynaya biləcəyiniz bir AI yaradaq.

Addım 3: Minimax Alqoritmi: Ssenarilər Yaratmaq

Bunu kodda necə yazacağımızdan əvvəl, arxasındakı məntiqə nəzər salaq. Minimax alqoritmi qərar qəbul etmə, geri izləmə alqoritmidir və adətən iki oyunçulu, növbəyə əsaslanan oyunlarda istifadə olunur. Bu AI -nin məqsədi, oyunu qazanana qədər növbəti ən yaxşı hərəkəti və ən yaxşı hərəkətləri tapmaqdır.

İndi alqoritm hansı hərəkətin ən yaxşı hərəkət olduğunu necə təyin edəcək? Durun və növbəti hərəkəti necə seçəcəyinizi düşünün. Əksər insanlar onlara ən çox xal verəcək hərəkəti seçərdilər, elə deyilmi? Ya da əvvəlcədən düşünsəydilər, daha çox xal qazana biləcək bir vəziyyət yaradan hərəkəti seçərdilər. Sonuncu düşüncə tərzi, Minimax Alqoritminin düşüncə tərzidir. Gələcəkdəki bütün lövhə quruluşlarına baxır və ən çox xal gətirəcək hərəkəti edir.

Buna geri çəkilmə alqoritmi dedim, çünki əvvəlcə bütün gələcək lövhə vəziyyətlərini əlaqəli dəyərləri ilə yaratmaq və qiymətləndirməklə başlayır. Bu o deməkdir ki, alqoritm oyunu hər ssenari oynanana qədər oyunu lazım olduğu qədər oynayacaq (özü və rəqibi üçün hərəkətlər edəcək). Bütün lövhə vəziyyətlərini (ssenariləri) izləmək üçün bir ağac çəkə bilərik (şəkillərə baxın). Yuxarıdakı şəkildəki ağac Connect 4 oyununun sadə bir nümunəsidir. Hər lövhənin konfiqurasiyasına lövhə vəziyyəti deyilir və ağacdakı yerinə düyün deyilir. Ağacın altındakı bütün qovşaqlar, bütün hərəkətləri etdikdən sonra son lövhə vəziyyətləridir. Aydındır ki, bəzi idarə heyətləri bir oyunçu üçün digərindən daha yaxşıdır. Beləliklə, indi AI -yə hansı idarə heyəti vəziyyətinə gəlmək istədiyini seçməliyik.

Addım 4: Minimax: Board Konfiqurasiyalarının Qiymətləndirilməsi

İdarə heyətinə dəyərlər vermək üçün oynadığımız oyunun strategiyalarını öyrənməliyik: bu halda Otello strategiyaları. Bu oyun rəqibin və disklərin sürüşdürülməsi uğrunda bir döyüş olduğundan, ən yaxşı disk mövqeləri sabit və çevrilə bilməyən mövqelərdir. Künc, məsələn, bir disk yerləşdirildikdə digər rəngə dəyişdirilə bilməyəcəyi yerdir. Beləliklə, bu yer son dərəcə dəyərli olardı. Digər yaxşı mövqelər, bir çox daş götürməyinizə imkan verən lövhənin tərəflərini əhatə edir. Bu veb saytında daha çox strategiya var.

İndi hər bir idarə heyəti üçün vəzifələrə dəyərlər təyin edə bilərik. AI parçası bir mövqe tutduqda, mövqedən asılı olaraq müəyyən sayda xal verirsiniz. Məsələn, AI parçasının küncdə olduğu bir lövhə vəziyyəti, 50 bal bonus verə bilərsiniz, ancaq əlverişsiz bir yerdə olsaydı, parça 0 dəyərində ola bilər. Bütün dəyərləri nəzərə aldıqdan sonra vəzifələr, lövhə vəziyyətinə bir dəyər verirsiniz. Məsələn, AI -nin küncdə bir parçası varsa, lövhənin vəziyyəti 50, ortasında AI parçası olan başqa bir lövhənin vəziyyəti 10 ola bilər.

Bunun bir çox yolu var və lövhə parçalarını qiymətləndirmək üçün üç fərqli heuristika var. Özünüzə heuristik bir növ hazırlamağı məsləhət görürəm. Github -a üç fərqli istehsalçı tərəfindən üç fərqli heuristika ilə üç fərqli AI yüklədim: Puma.py, erika5.py, nathanh.py.

Addım 5: Minimax Alqoritmi: Ən Yaxşı Hərəkətin Seçilməsi

AI, ən yüksək bal toplayan dövlətə keçmək üçün bütün hərəkətləri seçsəydi yaxşı olardı. Ancaq unutmayın ki, AI bütün lövhə vəziyyətlərini yaratarkən rəqibin hərəkətlərini də seçirdi və rəqib ağıllıdırsa, AI -nin ən yüksək lövhəyə çatmasına icazə verməyəcək. Bunun əvəzinə, ağıllı bir rəqib, AI -nin ən aşağı idarəetmə vəziyyətinə keçməsini təmin edəcək. Alqoritmdə iki oyunçunu maksimuma çıxaran və kiçildən bir oyunçu adlandırırıq. AI özü üçün ən çox xal qazanmaq istədiyi üçün maksimuma çatan oyunçu olardı. Rəqib, AI -nin ən az xal aldığı yerə getməyə çalışdığı üçün rəqib minimuma endirən oyunçu olardı.

Bütün lövhə vəziyyətləri yaradıldıqdan və lövhələrə dəyərlər təyin edildikdən sonra, alqoritm lövhə vəziyyətlərini müqayisə etməyə başlayır. Şəkillərdə alqoritmin hərəkətlərini necə seçəcəyini əks etdirmək üçün bir ağac yaratdım. Budaqlardakı hər bir bölmə, AI və ya rəqibin oynaya biləcəyi fərqli bir hərəkətdir. Düyün sıralarının solunda, oyunçunun böyütdüyünü və ya kiçilddiyini yazdım. Alt sıra, dəyərləri olan bütün lövhələrdir. Bu qovşaqların hər birinin içərisində bir rəqəm var və bu lövhələrin hər birinə verdiyimiz ballardır: nə qədər yüksəkdirsə, AI -nin olması daha yaxşıdır.

Təriflər: ana düyün - onun altında düyün yaradan və ya yaradan bir qovşaq; uşaq qovşaqlarının mənşəyi - eyni ana düyündən gələn düyünlər

Boş qovşaqlar, AI -nin ən yaxşı lövhə vəziyyətinə çatmaq üçün hansı hərəkəti edəcəyini təmsil edir. Ən soldakı düyünün uşaqlarını müqayisə etməklə başlayır: 10, -3, 5. Maksimuma çatdıran oyunçu hərəkəti edəcəyi üçün ona ən çox xal verəcək hərəkəti seçərdi: 10. Beləliklə, biz onu seçib saxlayırıq. lövhə balı ilə hərəkət edin və ana qovluğa yazın. İndi 10 ana qovşaqda olduğu üçün indi oyunçuları minimuma endirir. Bununla birlikdə, 10 ilə müqayisə edəcəyimiz qovşaq boşdur, buna görə minimuma endirən oyunçu seçməzdən əvvəl bu düyünü qiymətləndirməliyik. Maksimum oyunçunun növbəsinə qayıdırıq və bitişik düyünün uşaqlarını müqayisə edirik: 8, -2. Maksimumlaşdırma 8 seçəcək və bunu boş ana qovşaqda yazırıq. İndi alqoritm yuxarıdakı düyünün uşaqları üçün boş yerləri doldurmağı bitirdikdən sonra, minimuma endirən oyunçu həmin uşaqları müqayisə edə bilər - 10 və 8 və 8 -i seçərək alqoritm bütün ağac doldurulana qədər bu prosesi təkrarlayır. Bu nümunənin sonunda 8 hesabımız var. Bu, AI -nin rəqibin optimal oynadığını düşünmək üçün oynaya biləcəyi ən yüksək vəziyyətdir. Beləliklə, AI 8 lövhə vəziyyətinə gətirən ilk hərəkəti seçəcək və rəqib optimal oynasa, AI 8 -ci vəziyyətə düşmək üçün bütün hərəkətləri oynamalıdır. (Şəkillərimdəki qeydləri izləyin)

Bilirəm ki, çox idi. Kiminsə bir şeyi başa düşməsi üçün sizinlə danışması lazım olanlardan birisinizsə, bunun arxasındakı fikri anlamağa kömək etmək üçün izlədiyim bir neçə video var: 1, 2, 3.

Addım 6: Minimax Alqoritmi: Pseudocode

Minimax alqoritminin arxasındakı məntiqi başa düşdükdən sonra vikipediyadan bu yalançı koda (bütün kodlar üçün universal olan funksiyalara) baxın:

minimax funksiyası (node, dərinlik, maximizingPlayer) dir

əgər dərinlik = 0 və ya düyün bir terminal düyündürsə

düyünün evristik dəyərini qaytarın

maximizingPlayer varsa

dəyər: = ∞

hər bir uşaq üçün

dəyər: = maksimum (dəyər, minimum (uşaq, dərinlik - 1, YANLIŞ))

qaytarma dəyəri

başqa (* oyunçunu kiçiltmək *)

dəyər: = +∞

hər bir uşaq üçün

dəyər: = min (dəyər, minimum) (uşaq, dərinlik - 1, HAQQI))

qaytarma dəyəri

Bu, yineləmə funksiyasıdır, yəni dayanma nöqtəsinə çatana qədər özünü dəfələrlə çağırır. Birincisi, funksiya üç dəyər alır: düyün, dərinlik və növbəsi kimdir. Düyün dəyəri, proqramın axtarmağa başlamasını istədiyiniz yerdir. Dərinlik, proqramın nə qədər axtarmasını istədiyinizdir. Məsələn, ağac nümunəmdə 3 dərinliyə malikdir, çünki 3 hərəkətdən sonra bütün lövhə vəziyyətlərini axtardı. Əlbəttə ki, AI -nin hər lövhə vəziyyətini yoxlamasını və qalibiyyət qazanmasını istəyərdik, amma milyonlarla deyil, minlərlə lövhə konfiqurasiyasının olduğu əksər oyunlarda, evdəki dizüstü kompüteriniz bütün bu konfiqurasiyaları işlədə bilməyəcək. Beləliklə, AI -nin axtarış dərinliyini məhdudlaşdırırıq və ən yaxşı lövhə vəziyyətinə gətirməliyik.

Bu yalançı kod, əvvəlki iki addımda izah etdiyim prosesi təkrarlayır. İndi bunu bir addım daha ataq və bunu python kodunda düzəldək.

Addım 7: Ai_template.py ilə AI -ni hazırlayın

Minimax AI koduma baxmadan əvvəl ai_template.py faylı və son addımda bəhs etdiyimiz yalançı kodla öz AI-nizi yaratmağa çalışın. Ai şablonunda iki funksiya var: def minimax_min_node (board, color) və def minimax_max_node (board, color). Minimax funksiyasının özünü rekursiv adlandırmaq əvəzinə, bir -birimizi çağıran iki fərqli funksiyamız var. Lövhə vəziyyətlərini qiymətləndirmək üçün heuristik yaratmaq üçün öz funksiyanızı yaratmalı olacaqsınız. Othello_shared.py faylında AI qurmaq üçün istifadə edə biləcəyiniz əvvəlcədən hazırlanmış funksiyalar var.

AI -ni əldə etdikdən sonra, randy_ai.py -ə qarşı işləməyə çalışın. Bir -birinə qarşı iki ais işə salmaq üçün mac terminalına "python othello_gui.py (ai fayl adı daxil edin).py (fayl adı daxil edin.. Py") yazın və ya "run othello_gui.py (ai fayl adı daxil edin).py yazın. (fayl adını daxil edin).py "yazın və doğru qovluqda olduğunuzdan əmin olun. Ayrıca, dəqiq addımlar üçün videoya baxın.

Addım 8: AI ilə mübarizə aparmaq vaxtıdır

İndi kompüter dostlarınızdan bir dəstə əldə edin və onları öz AI -lərini hazırlamağa məcbur edin! Sonra bir rəqabət yarada və süni intellektinizə bunu göstərə bilərsiniz. İnşallah, öz AI qura bilməsəniz də, minimax alqoritminin necə işlədiyini anlaya bildiniz. Hər hansı bir sualınız varsa, aşağıdakı şərhlərdə suallarınızı yazmaqdan çekinmeyin.