Stol o'yini sun'iy intellekt: Minimax algoritmi: 8 qadam

2024 Muallif: John Day | [email protected]. Oxirgi o'zgartirilgan: 2024-01-30 13:25

Siz shaxmat yoki shashkada o'ynaydigan kompyuterlar qanday ishlab chiqarilgani haqida hech o'ylab ko'rganmisiz? Bu ko'rsatmaga qarang, chunki u sizga Minimax algoritmi yordamida oddiy, ammo samarali sun'iy intellektni (AI) qanday qilishni ko'rsatib beradi! Minimax algoritmidan foydalanib, AI yaxshi rejalashtirilgan va o'ylangan harakatlarni amalga oshiradi (yoki hech bo'lmaganda fikrlash jarayoniga taqlid qiladi). Endi men sizga o'zim yaratgan AI kodini bera olardim, lekin bu qiziq bo'lmaydi. Men kompyuter tanlovining mantig'ini tushuntiraman.

Bu yo'riqnomada men sizni pitonda Otello (AKA Reversi) uchun sun'iy intellektni yaratish bo'yicha qadamlar bilan tanishtiraman. Ushbu loyihani hal qilishdan oldin siz pythonda qanday kodlash haqida oraliq tushunchaga ega bo'lishingiz kerak. Mana bu ko'rsatmaga tayyorgarlik ko'rish uchun bir nechta yaxshi veb -saytlar: w3schools yoki learnpython. Ushbu ko'rsatma oxirida siz hisob -kitoblarni amalga oshiradigan va ko'pchilik odamlarni mag'lub qila oladigan AIga ega bo'lishingiz kerak.

Ushbu ko'rsatma asosan AIni qanday yasash bilan bog'liq bo'lgani uchun, men pythonda o'yinni qanday loyihalashni tushuntirmayman. Buning o'rniga, men odamning boshqa odamga qarshi o'ynashi mumkin bo'lgan o'yin kodini beraman va siz odam AIga qarshi o'ynaydigan o'yin o'ynashingiz uchun o'zgartirasiz.

Men bu sun'iy intellektni Kolumbiya SHAPE yozgi dasturi orqali qanday yaratishni o'rgandim. Men u erda yaxshi vaqt o'tkazdim, shuning uchun sizni qiziqtiradimi yoki yo'qligini bilish uchun ularning veb -saytiga qarang.

Endi biz logistika bilan shug'ullana olmadik, kodlashni boshlaylik!

(Men rasmlarga bir nechta eslatmalarni joylashtirdim, shuning uchun ularga diqqat bilan qarang)

Ta'minotlar

Bu oson:

1) Spyder yoki IDLE kabi piton muhitiga ega kompyuter

2) Otello o'yini uchun fayllarni GitHub -dan yuklab oling

3) Sizning miyangizga sabr -toqat o'rnatilgan

1 -qadam: Kerakli fayllarni yuklab oling

GitHub -ga kirganingizda 5 ta faylni ko'rishingiz kerak. Hammasini 5 -ni yuklab oling va hammasini bitta papkaga joylashtiring. O'yinni boshlashdan oldin, barcha fayllarni josuslik muhitida oching.

Bu erda fayllar nima qiladi:

1) othello_gui.py bu fayl o'yinchilar uchun o'ynash uchun o'yin taxtasini yaratadi (xoh odam, xoh kompyuter)

2) othello_game.py bu fayl ikkita kompyuterni o'yin taxtasi bo'lmagan holda o'ynaydi va faqat hisobni ko'rsatadi va pozitsiyalarini o'zgartiradi.

3) ai_template.py bu erda siz AIni yaratish uchun barcha kodlaringizni kiritasiz

4) randy_ai.py - bu o'z harakatlarini tasodifiy tanlaydigan oldindan tayyorlangan AI

5) othello_shared.py sizning AI-ni mavjud harakatlar, ballar yoki taxtalar holatini tekshirish kabi ishlatishingiz mumkin bo'lgan oldindan tayyorlangan funktsiyalar to'plami.

6) Boshqa uchta fayllar: Puma.py, erika_5.py va nathan.py, men, Erika va Neytan tomonidan SHAPE dasturidan olingan bo'lib, ular noyob kodli uch xil AI.

2 -qadam: Python Otello -ni qanday ochish va o'ynash

Barcha fayllar ochilgach, ekranning o'ng pastki burchagiga "run othello_gui.py" yozing va IPython Console-ga kiriting. Yoki Mac terminalida "python othello_gui.py" yozing (albatta kerakli papkada bo'lganingizdan keyin). Shundan so'ng, ekranda doska paydo bo'lishi kerak. Bu rejim inson va inson rejimi. Nur ikkinchi, qorong'i - birinchi. Agar siz adashgan bo'lsangiz, mening videomga qarang. iAgar tepada har bir rangli kafelning bahosi bor. O'ynash uchun bo'sh joyni bosing va u erda plitka qo'ying, keyin kompyuterni raqibingizga bering, u ham xuddi shunday qiladi va takrorlaydi.

Agar siz Otello qanday o'ynashni bilmasangiz, ultra taxtalar veb -saytidan ushbu qoidalarni o'qing:

Qora har doim birinchi bo'lib harakat qiladi. Harakat, o'yinchi rangidagi diskni taxtaga, raqibning bir yoki bir nechta diskini "chetga" chiqaradigan joyga qo'yish orqali amalga oshiriladi. Disk yoki disklar qatori chetidan qarama -qarshi rangdagi disklar bilan o'ralgan bo'lsa, uning tashqarisida bo'ladi. Disk har qanday yo'nalishda (gorizontal, vertikal, diagonal) bir yoki bir nechta qatorda har qanday diskdan ustun bo'lishi mumkin. (o'z veb -saytida o'qishni tugating)

Asl o'yin va bu piton o'yinining farqi shundaki, bitta o'yinchi uchun to'g'ri harakatlar qolmaganida, o'yin tugaydi

Endi siz do'stingiz bilan o'yin o'ynashingiz mumkin, keling, siz bilan o'ynaydigan AIni yarataylik.

3 -qadam: Minimax algoritmi: ssenariylarni yaratish

Buni kodda qanday yozish haqida gapirishdan oldin, keling, uning mantig'ini ko'rib chiqaylik. Minimax algoritmi-bu qaror qabul qilish, orqaga qaytish algoritmi va odatda ikki o'yinchi, navbatga asoslangan o'yinlarda ishlatiladi. Bu sun'iy intellektning maqsadi - o'yinda g'alaba qozonmaguncha keyingi eng yaxshi harakatni va keyingi eng yaxshi harakatlarni topish.

Endi algoritm qaysi harakat eng yaxshi ekanligini qanday aniqlaydi? To'xtang va keyingi harakatni qanday tanlashni o'ylab ko'ring. Ko'pchilik o'zlariga eng ko'p ball beradigan harakatni tanlagan bo'lardi, to'g'rimi? Yoki ular oldindan o'ylashganda, ular ko'proq ball to'plashlari mumkin bo'lgan vaziyatni o'rnatadigan harakatni tanlagan bo'lardilar. Oxirgi fikrlash usuli - bu Minimax algoritmi qanday o'ylashi. U bo'lajak taxtaning barcha sozlamalarini kutadi va eng ko'p ochkoga olib keladigan harakatni amalga oshiradi.

Men buni orqaga qaytish algoritmi deb atadim, chunki u avvalo barcha bo'lajak shtatlar bilan bog'liq qiymatlarni yaratish va baholashdan boshlanadi. Bu shuni anglatadiki, algoritm o'yinni har bir stsenariy o'ynaguncha kerakli darajada o'ynaydi (o'zi va raqib uchun harakatlarni amalga oshiradi). Kengashning barcha holatlarini (stsenariylarni) kuzatib borish uchun biz daraxt chizishimiz mumkin (rasmlarga qarang). Yuqoridagi rasmdagi daraxt Connect 4 o'yinining oddiy namunasidir. Har bir taxta konfiguratsiyasi taxta holati va uning daraxtdagi joyi tugun deb ataladi. Daraxtning pastki qismidagi barcha tugunlar, barcha harakatlardan so'ng, taxtaning oxirgi holatidir. Ko'rinib turibdiki, ba'zi futbolchilar boshqasiga qaraganda yaxshiroq. Shunday qilib, endi biz AIga qaysi boshqaruv shtatiga kirishni xohlashini tanlashimiz kerak.

4 -qadam: Minimax: taxta konfiguratsiyalarini baholash

Kengashga qiymat berish uchun biz o'ynayotgan o'yin strategiyasini o'rganishimiz kerak: bu holda Otello strategiyasi. Bu o'yin raqib va sizning disklaringizni siljitish uchun kurash bo'lgani uchun, disklarning eng yaxshi pozitsiyasi - bu barqaror va ularni ag'darib bo'lmaydi. Burchak, masalan, disk joylashganda uni boshqa rangga o'zgartirib bo'lmaydi. Shunday qilib, bu joy juda qimmatli bo'ladi. Boshqa yaxshi pozitsiyalarga taxtaning yon tomonlari kiradi, bu sizga ko'p toshlarni olish imkonini beradi. Ushbu veb -saytda ko'proq strategiyalar mavjud.

Endi biz har bir shtat kengashining lavozimlariga qiymatlarni belgilashimiz mumkin. Qachonki AI sun'iy yo'ldosh pozitsiyasini egallasa, siz pozitsiyaga qarab ma'lum miqdordagi ball berasiz. Masalan, sun'iy intellekt bo'lagi burchakda joylashgan taxtada siz 50 balllik bonus berishingiz mumkin, lekin agar u yoqimsiz joyda bo'lsa, uning qiymati 0 bo'lishi mumkin. lavozimlar, siz boshqaruv kengashining qiymatini belgilaysiz. Masalan, agar AI burchagida bo'lak bo'lsa, taxtaning holati 50 ball bo'lishi mumkin, o'rtada AI bo'lagi bo'lgan boshqa taxtaning holati 10 ball.

Buning ko'p usullari bor va men taxta qismlarini baholash uchun uch xil evristikaga egaman. Men sizga o'z turingizni evristik qilishni taklif qilaman. Men o'zimning github -ga uch xil ishlab chiqaruvchi tomonidan uchta turli xil evristikani yuklaganman: Puma.py, erika5.py, nathanh.py.

5 -qadam: Minimax algoritmi: Eng yaxshi harakatni tanlash

Agar sun'iy intellekt kengashi holatiga eng yuqori ball bilan o'tish uchun barcha harakatlarni tanlasa yaxshi bo'lardi. Shuni yodda tutingki, AI ham barcha taxtalarni ishlab chiqarganda raqib uchun harakatlarni tanlagan va agar raqib aqlli bo'lsa, u AIga eng yuqori ball olishiga yo'l qo'ymaydi. Buning o'rniga, aqlli raqib sun'iy yo'ldoshni eng past holatiga o'tkazishga harakat qiladi. Algoritmda biz ikkita o'yinchini maksimal va minimallashtiruvchi o'yinchi deb ataymiz. AI maksimal darajadagi o'yinchi bo'ladi, chunki u o'zi uchun eng ko'p ball olishni xohlaydi. Raqib minimallashtiruvchi o'yinchi bo'lar edi, chunki raqib sun'iy yo'ldosh eng kam ochko oladigan harakatni amalga oshirmoqchi.

Kengashning barcha holatlari tuzilgach va taxtalarga qiymatlar tayinlangandan so'ng, algoritm taxta holatini solishtirishni boshlaydi. Rasmlarda men algoritm o'z harakatlarini qanday tanlashini ko'rsatish uchun daraxt yaratdim. Filiallardagi har bir bo'linish - bu AI yoki raqib o'ynashi mumkin bo'lgan boshqa harakat. Tugunlar satrining chap tomonida, men o'yinchini kattalashtirish yoki minimallashtirish ketayotganini yozdim. Pastki qatorda barcha davlatlar o'z qiymatlari ko'rsatilgan. Bu tugunlarning har birining ichida raqam bor va biz har bir taxtaga qo'yadigan ballarimiz: ular qanchalik baland bo'lsa, sun'iy intellektga ega bo'lish yaxshiroqdir.

Ta'riflar: ota -ona tuguni - uning ostidagi tugunlarni hosil qiladigan yoki yaratadigan tugun; bolalar tugunlarining kelib chiqishi - bitta ota -ona tugunidan chiqqan tugunlar

Bo'sh tugunlar sun'iy intellektning eng yaxshi holatiga o'tish uchun qanday harakat qilishini ko'rsatadi. Bu eng chap tugunning bolalarini taqqoslashdan boshlanadi: 10, -3, 5. Maksimallashtiruvchi o'yinchi harakat qilgani uchun, u eng ko'p ochko beradigan harakatni tanlagan bo'lardi: 10. Shunday qilib, biz uni tanlaymiz va saqlaymiz. doska ballari bilan harakatlaning va uni ota -ona tuguniga yozing. Endi 10 ta ota -ona tugunida, endi minimallashtiruvchi o'yinchilar navbatida. Biroq, biz 10 -ni taqqoslaydigan tugun bo'sh, shuning uchun minimallashtiruvchi o'yinchi tanlashidan oldin biz bu tugunni baholashimiz kerak. Shunday qilib, biz o'yinchining maksimal darajasiga qaytamiz va qo'shni tugunning bolalarini taqqoslaymiz: 8, -2. Maksimallashtirish 8 ni tanlaydi va biz buni bo'sh ota -ona tuguniga yozamiz. Endi algoritm tepadagi tugun bolalari uchun bo'sh joylarni to'ldirishni tugatdi, minimallashtiruvchi o'yinchi o'sha bolalarni solishtirishi mumkin - 10 va 8 va 8 ni tanlash. Algoritm keyin butun daraxt to'ldirilguncha bu jarayonni takrorlaydi. Bu misolning oxirida bizda 8 ball bor. Bu AIning raqibi optimal o'ynayotganini taxmin qilish uchun o'ynashi mumkin bo'lgan eng yuqori ko'rsatkich. Shunday qilib, AI 8 ta taxtaga olib keladigan birinchi harakatni tanlaydi va agar raqib optimal o'ynasa, AI 8 -holatiga o'tish uchun barcha harakatlarni bajarishi kerak. (Mening rasmlarimdagi izohlarga amal qiling)

Bilaman, bu juda ko'p edi. Agar siz kimnidir biror narsani tushunishi uchun siz bilan gaplashishi kerak bo'lgan turlardan bo'lsangiz, mana bu g'oyaning mohiyatini tushunishga yordam berish uchun men ko'rgan ikkita video.

6 -qadam: Minimax algoritmi: Pseudocode

Minimax algoritmining mantig'ini tushunganingizdan so'ng, vikipediyadan ushbu psevdokodni (barcha kodlar uchun universal bo'lgan funktsiyalarni) ko'rib chiqing:

minimax funktsiyasi (tugun, chuqurlik, maximizingPlayer)

agar chuqurlik = 0 yoki tugun terminal tugun bo'lsa

tugunning evristik qiymatini qaytarish

agar maximizingPlayer bo'lsa

qiymati: = -∞

tugunning har bir bolasi uchun bajaring

qiymat: = maksimal (qiymat, minimax (bola, chuqurlik - 1, FALSE))

qaytish qiymati

boshqa (* o'yinchini minimallashtirish *)

qiymati: = +∞

tugunning har bir bolasi uchun bajaring

qiymat: = min (qiymat, minimax (bola, chuqurlik - 1, TRUE))

qaytarish qiymati

Bu rekursiv funktsiya, ya'ni to'xtash nuqtasiga yetguncha o'zini qayta -qayta chaqiradi. Birinchidan, funktsiya uchta qiymatni oladi: tugun, chuqurlik va kimga navbat. Tugun qiymati - bu dastur qidirishni boshlagan joy. Chuqurlik - bu dasturni qanchalik qidirishni xohlayotganingiz. Misol uchun, mening daraxt misolimda u 3 chuqurlikka ega, chunki u 3 ta harakatdan so'ng barcha taxtaning holatini qidirgan. Albatta, biz AI har bir taxtaning holatini tekshirib, g'alabali g'alabani tanlashini xohlardik, lekin ko'pchilik o'yinlarda, agar konfiguratsiyasi millionlab bo'lmasa, millionlab bo'lsa, uydagi noutbukingiz bu konfiguratsiyalarni qayta ishlay olmaydi. Shunday qilib, biz AIning qidirish chuqurligini cheklaymiz va uni eng yaxshi taxta holatiga o'tkazamiz.

Bu psevdokod men oldingi ikki bosqichda tushuntirgan jarayonni takrorlaydi. Keling, buni bir qadam oldinga suramiz va buni python kodida to'g'rilaymiz.

7 -qadam: AI -ni Ai_template.py yordamida yaratish

Mening Minimax AI kodimni ko'rib chiqishdan oldin, ai_template.py fayli va oxirgi bosqichda biz aytgan soxta kod yordamida o'z AI ni yaratishga urinib ko'ring. Ai shablonida ikkita funktsiya mavjud: def minimax_min_node (taxta, rang) va def minimax_max_node (taxta, rang). Minimax funktsiyasi o'zini rekursiv ravishda chaqirish o'rniga, bizda bir -birini chaqiradigan ikki xil funktsiya mavjud. Kengash holatini baholash uchun evristikni yaratish uchun siz o'zingizning funktsiyangizni yaratishingiz kerak bo'ladi. Othello_shared.py faylida AIni yaratish uchun foydalanishingiz mumkin bo'lgan oldindan tayyorlangan funktsiyalar mavjud.

AIga ega bo'lgandan so'ng, uni randy_ai.py ga qarshi ishlatishga harakat qiling. Bir -biriga qarshi ikkita AISni ishga tushirish uchun mac terminaliga "python othello_gui.py (ai fayl nomini kiriting).py (fayl nomini kiriting).py" buyrug'ini kiriting yoki "run othello_gui.py (ai fayl nomini kiriting).py" buyrug'ini kiriting. (fayl nomini kiriting).py "va to'g'ri katalogda ekanligingizga ishonch hosil qiling. Bundan tashqari, aniq qadamlar uchun mening videomga qarang.

8 -qadam: AI bilan kurashish vaqti keldi

Endi bir nechta kompyuter do'stlarini oling va ularni o'z AIlarini yaratishga majbur qiling! Keyin siz raqobat qilishingiz mumkin va sizning AI gersogingiz bo'lishi mumkin. Umid qilamanki, siz o'zingizning AI -ni qura olmagan bo'lsangiz ham, siz minimax algoritmining qanday ishlashini tushuna oldingiz. Agar sizda biron bir savol bo'lsa, quyidagi izohlarda savollaringizni yozib yuboring.