|
O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI
Fan: Sun’iy Intellekt asoslari
AMALIY ISHI № 9-13
Guruh: 210-18 KIF
Bajardi: Turaqulov Toshpolat
Tekshirdi: Raximov Mehriddin
Toshkent 2022
Alpha-Beta algoritmi minimax algoritmini optimallashtirish usulidir. Bu hisoblash vaqtini sezilarli darajada qisqartiradi. Bu bizga tezroq qidirish va hatto o'yin daraxtida chuqurroq darajalarga kirish imkonini beradi. U o'yin daraxtidagi novdalarni kesib tashlaydi, ularni qidirish kerak emas.
Minimax funktsiyasida ikkita qo'shimcha parametr, ya'ni alfa va betadan o'tganligi uchun u Alpha-Beta deb ataladi.
Alfa - bu maksimal daraja yoki undan yuqori darajalarda hozirda kafolatlashi mumkin bo'lgan eng yaxshi qiymat.
Beta - bu minimallashtiruvchi hozirda o'sha yoki undan yuqori darajada kafolatlashi mumkin bo'lgan eng yaxshi qiymat.
U qanday ishlaydi
Aytaylik, harakat qilish navbati Uaytga keldi va biz 2 chuqurlikda qidirmoqdamiz (ya'ni, biz Oqning barcha harakatlari va bu har bir harakatga Blackning barcha javoblarini hisobga olamiz.) Avval biz Oqning mumkin bo'lgan harakatlaridan birini tanlaymiz - keling, buni №1 mumkin bo'lgan harakat deb ataylik. Biz bu harakatni va bu harakatga har qanday javobni qora deb hisoblaymiz. Ushbu tahlildan so'ng, №1 mumkin bo'lgan harakatni amalga oshirish natijasi teng pozitsiya ekanligini aniqlaymiz. Keyin, biz davom etamiz va Uaytning boshqa mumkin bo'lgan harakatlarini ko'rib chiqamiz (Mumkin bo'lgan harakat №2.) Qoraning birinchi mumkin bo'lgan qarama-qarshi harakatini ko'rib chiqsak, bu o'yin qora tanlilarning Rookni yutishiga olib kelishini aniqlaymiz! Bunday vaziyatda biz Blekning №2 mumkin bo'lgan boshqa barcha mumkin bo'lgan javoblarini e'tiborsiz qoldira olamiz, chunki biz №1 mumkin bo'lgan harakat yaxshiroq ekanligini allaqachon bilamiz. Biz haqiqatan ham№2 mumkin bo'lgan harakat qanchalik yomonroq . Ehtimol, boshqa mumkin bo'lgan javob qirolichani yutadi, ammo bu muhim emas, chunki biz Possible Move №1 o'yinini o'ynash orqali hech bo'lmaganda teng o'yinga erishishimiz mumkinligini bilamiz . №1 mumkin bo'lgan harakatning to'liq tahlili bizga pastki chegarani berdi . Biz hech bo'lmaganda bunga erishishimiz mumkinligini bilamiz, shuning uchun aniqroq yomonroq bo'lgan hamma narsani e'tiborsiz qoldirish mumkin.
Vaziyat 3 yoki undan kattaroq qidiruv chuqurligiga o'tganimizda yanada murakkablashadi, chunki endi ikkala o'yinchi ham o'yin daraxtiga ta'sir qiladigan tanlovlarni amalga oshirishi mumkin. Endi biz pastki chegarani ham , yuqori chegarani ham saqlashimiz kerak ( Alfa va Beta deb ataladi .) Biz pastki chegarani saqlab qolamiz, chunki agar harakat juda yomon bo'lsa, biz buni hisobga olmaymiz. Lekin biz ham yuqori chegarani saqlab qolishimiz kerak, chunki agar 3 yoki undan yuqori chuqurlikdagi harakat juda yaxshi davom etishiga olib kelsa, boshqa o'yinchi bunga yo'l qo'ymaydi, chunki o'yin daraxtida yuqoriroqda yaxshiroq harakat bor edi. bu vaziyatdan qochish uchun o'ynashi mumkin edi. Bir o'yinchining pastki chegarasi boshqa o'yinchining yuqori chegarasidir.
Minimax algoritmi nima?
Minimax - bu o'yinchi uchun optimal harakatni tanlash uchun ishlatiladigan rekursiv algoritm bo'lib, boshqa o'yinchi ham optimal tarzda o'ynaydi.
U tic-tac-toe, go, shaxmat, Isola, shashka va boshqa ko'plab ikki o'yinchi o'yinlari kabi o'yinlarda qo'llaniladi.
Bunday o'yinlar mukammal ma'lumot o'yinlari deb ataladi, chunki u muayyan o'yinning barcha mumkin bo'lgan harakatlarini ko'rish mumkin.
Scrabble kabi mukammal ma'lumotga ega bo'lmagan ikki o'yinchili o'yinlar bo'lishi mumkin, chunki raqibning harakatini oldindan aytib bo'lmaydi.
Bu o'yinni o'ynaganimizda qanday fikrlashimizga o'xshaydi: "agar men bu harakatni qilsam, raqibim faqat shu harakatlarni amalga oshirishi mumkin" va hokazo.
Minimax shunday nomlanadi, chunki u boshqa o'yinchi maksimal yo'qotish strategiyasini tanlaganida yo'qotishni minimallashtirishga yordam beradi.
Terminologiya
O'yin daraxti : Bu o'yin holatidan keyingi holatga o'tishga imkon beruvchi barcha mumkin bo'lgan harakatlardan iborat daraxt ko'rinishidagi tuzilma.
O'yinni quyidagi komponentlar bilan qidirish muammosi sifatida aniqlash mumkin:
Boshlang'ich holat : U kengashning joylashishini va kimning harakati ekanligini ko'rsatadi.
Voris funktsiyasi : Bu o'yinchi qanday qonuniy harakatlar qilishi mumkinligini belgilaydi.
Terminal holati : Bu o'yin tugagandan so'ng taxtaning holati.
Foydali funktsiya : Bu o'yin natijasi uchun raqamli qiymatni belgilaydigan funksiya. Masalan, shaxmat yoki tic-tac-toe o'yinlarida natija g'alaba, mag'lubiyat yoki dbo'lib, ular mos ravishda +1, -1 yoki 0 qiymatlari bilan ifodalanishi mumkin. Mumkin bo'lgan natijalar ancha kengroq bo'lgan o'yinlar mavjud; Masalan, tavladagi yordamchi dasturlar +192 dan -192 gacha o'zgarib turadi. Foydali funktsiyani to'lov funktsiyasi deb ham atash mumkin.
Algoritm qanday ishlaydi?
O'yinda MIN va MAX deb nomlangan ikkita o'yinchi ishtirok etadi. MAX o'yinchi mumkin bo'lgan eng yuqori ballni olishga, MIN esa eng past ball olishga harakat qiladi, ya'ni MIN va MAX bir-biriga qarama-qarshi harakat qilishga harakat qiladi.
Minimax algoritmining umumiy jarayoni quyidagicha:
1-qadam : Birinchidan, o'yinning joriy holatidan boshlab, terminal holatigacha bo'lgan butun o'yin daraxtini yarating. O'yin daraxti o'yin tic-tac-toe uchun shunday ko'rinadi.
Keling, yuqoridagi diagramma nuqtai nazaridan belgilangan terminologiyani tushunaylik.
Dastlabki holat - bu doskaning bo'shligini belgilaydigan birinchi qatlam, uni o'ynash navbati MAX.
Voris funktsiyasi barcha mumkin bo'lgan voris harakatlarining ro'yxatini beradi. U daraxtning barcha qatlamlari uchun belgilangan.
Terminal holati - yakuniy holatni ko'rsatadigan daraxtning oxirgi qatlami, ya'ni MAX o'yinchisi g'alaba qozonadimi, yutqazadimi yoki raqib bilan bog'lanadi.
Terminal holatlari uchun bu holatda yordamchi dasturlar yuqorida ko'rib chiqilganidek 1, 0 va -1 dir va ular boshqa tugunlarning yordamchi dasturlarini aniqlash uchun ham ishlatilishi mumkin.
2-qadam : Barcha terminal holatlari uchun yordamchi dastur qiymatlarini olish uchun yordamchi funktsiyani qo'llang.
3-qadam : Terminal tugunlarining yordamchi dasturlari yordamida yuqori tugunlarning yordam dasturlarini aniqlang. Misol uchun, quyidagi diagrammada bizda kvadratlarda yozilgan terminal holatlari uchun yordamchi dasturlar mavjud.
Terminal ustidagi qatlamning chap tugunining (qizil) yordam dasturini hisoblaylik. Bu MIN o'yinchisining harakati bo'lgani uchun biz barcha yordamchi dasturlarning minimalini tanlaymiz. Bu holatda, biz MIN{3, 5, 10} ni baholashimiz kerak, bu biz aniq 3 ekanligini bilamiz. Demak, qizil tugun uchun yordamchi dastur 3 ga teng.
Xuddi shunday, xuddi shu qatlamdagi yashil tugun uchun biz MIN{2,2} ni baholashimiz kerak, ya'ni 2.
Minimax algoritmi
4-qadam : Daraxtning ildizigacha bir vaqtning o'zida bir qatlamni hisobga olgan holda barglar yordamida foydali qiymatlarni hisoblang.
5-qadam : Oxir-oqibat, barcha zaxiralangan qiymatlar daraxtning ildiziga, ya'ni eng yuqori nuqtaga etib boradi. Bu vaqtda MAX eng yuqori qiymatni tanlashi kerak.
Bizning misolimizda bizda faqat 3 ta qatlam bor, shuning uchun biz darhol ildizga erishdik, ammo haqiqiy o'yinlarda yana ko'p qatlamlar va tugunlar bo'ladi. Shunday qilib, biz MAX{3,2} ni baholashimiz kerak, bu 3.
Shuning uchun, MAX uchun eng yaxshi ochilish harakati chap tugun (yoki qizil). Ushbu harakat minimaks qaror deb ataladi, chunki u raqib ham uni minimallashtirish uchun optimal o'ynayapti degan taxmindan keyin foydani maksimal darajada oshiradi.
Xulosa qilish uchun,
Minimaks qaror = MAX{MIN{3,5,10},MIN{2,2}}
= MAX{3,2}
= 3
Algaritmi
minimax funktsiyasi (tugun, chuqurlik, maximizingPlayer)
agar chuqurlik = 0 yoki tugun terminal tugun bo'lsa
tugunning yordam dasturini qaytaring
agar maximizingPlayer bo'lsa
eng yaxshi qiymat := ??
tugunning har bir bolasi uchun
v := minimaks(bola, chuqurlik ? 1, FALSE)
bestValue:= maks (eng yaxshi qiymat, v)
eng yaxshi qiymatni qaytaring
boshqa (* o'yinchini minimallashtirish *)
eng yaxshi qiymat:= +?
tugunning har bir bolasi uchun
v := minimaks(bola, chuqurlik ? 1, TRUE)
bestValue:= min(eng yaxshi qiymat, v)
eng yaxshi qiymatni qaytaring
Xulosa:
O'yinlar juda jozibali va o'yin o'ynash dasturlarini yozish, ehtimol, yanada qiziqarli. Avtomobil sanoati uchun Gran-pri poygasi nima bo'lsa, AI uchun o'yin o'ynash.
Biz poyga mashinasining notekis yo'lda mukammal ishlashini kutmaganimizdek, o'yin o'ynash algoritmlari har qanday vaziyat uchun mukammal bo'lishini kutmasligimiz kerak.
Minimax algoritmi ham shunday. Bu sun'iy intellektga ega bo'lishi kerak bo'lgan barcha turdagi kompyuter o'yinlari uchun eng yaxshi yechim bo'lmasligi mumkin.
Ammo yaxshi amalga oshirilsa, u qattiq raqobatchini yaratishi mumkin.
|
