Fai001-2 talabasi Erkinov Jamshid Amaliy ishlar – 9-13 Ishning nomi

3-qadam: Keyingi bosqichda bu minimallashtiruvchi uchun navbat, shuning uchun u barcha tugunlar qiymatini +∞ bilan solishtiradi va 3 ^- qavat tugun qiymatlarini topadi .

• 
  B tugun uchun= min(4,6) = 4
  
• 
  Tugun uchun C= min (-3, 7) = -3
  

4-qadam: Endi navbat Maximizer-ga keldi va u yana barcha tugunlarning maksimal qiymatini tanlaydi va ildiz tugunining maksimal qiymatini topadi. Ushbu o'yin daraxtida faqat 4 ta qatlam mavjud, shuning uchun biz darhol ildiz tuguniga etib boramiz, ammo haqiqiy o'yinlarda 4 dan ortiq qatlam bo'ladi.

• 
  A tugun uchun max(4, -3)= 4
  

Bu minimax ikki o'yinchi o'yinining to'liq ish jarayoni edi.

Mini-Max algoritmining xususiyatlari:

• 
  To'liq - Min-Maks algoritmi to'liq. Bu, albatta, (agar mavjud bo'lsa) cheklangan qidiruv daraxtida yechim topadi.
  
• 
  Optimal- Min-Maks algoritmi, agar ikkala raqib ham optimal o'ynasa, optimal hisoblanadi.
  
• 
  Vaqt murakkabligi- O'yin daraxti uchun DFS ni bajarganidek, Min-Max algoritmining vaqt murakkabligi ham O(b ^m ) ga teng, bu erda b o'yin daraxtining shoxlanish omili va m - daraxtning maksimal chuqurligi.
  
• 
  Kosmik murakkablik - Mini-max algoritmining fazoviy murakkabligi ham O(bm) bo'lgan DFS ga o'xshaydi .
  

Minimaks algoritmini cheklash:

Minimax algoritmining asosiy kamchiligi shundaki, u Chess, go va hokazo kabi murakkab o'yinlar uchun haqiqatan ham sekinlashadi. Bu turdagi o'yinlar katta tarmoqlanish omiliga ega va o'yinchi qaror qilish uchun juda ko'p tanlovga ega. Minimax algoritmining bu cheklanishini biz keyingi mavzuda muhokama qilgan alfa-beta kesish orqali yaxshilash mumkin.

Alpha-Beta Qidiruv algoritmi

• 
  Alpha-beta Azizillo - bu minimax algoritmining o'zgartirilgan versiyasi. Bu minimaks algoritmi uchun optimallashtirish texnikasi.
  
• 
  Minimax qidiruv algoritmida ko'rganimizdek, u o'rganishi kerak bo'lgan o'yin holatlari soni daraxtning chuqurligida eksponentdir. Chunki biz ko'rsatkichni yo'q qila olmaymiz, lekin uni yarmiga qisqartirishimiz mumkin. Shunday qilib, o'yin daraxtining har bir tugunini tekshirmasdan to'g'ri minimax qarorini hisoblashimiz mumkin bo'lgan texnika mavjud va bu usul Azizillo deb ataladi . Bu kelajakda kengayish uchun ikkita chegara parametrlari Alpha va beta o'z ichiga oladi, shuning uchun u alfa-beta Azizillo deb ataladi . U Alfa-Beta algoritmi deb ham ataladi .
  
• 
  Alpha-beta Azizillo daraxtning har qanday chuqurligida qo'llanilishi mumkin va ba'zida u nafaqat daraxt barglarini, balki butun pastki daraxtni ham kesib tashlaydi.
  
• 
  Ikki parametrni quyidagicha aniqlash mumkin:
  

1.