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

Sun'iy intellektda Mini-Maks algoritmi

• 
  Mini-max algoritmi qaror qabul qilish va o'yin nazariyasida qo'llaniladigan rekursiv yoki orqaga qaytish algoritmidir. Bu o'yinchi uchun optimal harakatni ta'minlaydi, chunki raqib ham optimal o'ynayapti.
  
• 
  Mini-Max algoritmi o'yin daraxti bo'ylab qidirish uchun rekursiyadan foydalanadi.
  
• 
  Min-Max algoritmi asosan sun'iy intellektda o'yin o'ynash uchun ishlatiladi. Shaxmat, shashka, tic-tac-toe, go va turli xil o'yinchilar o'yinlari. Ushbu algoritm joriy holat uchun minimal qarorni hisoblaydi.
  
• 
  Ushbu algoritmda ikkita o'yinchi o'ynaydi, biri MAX, ikkinchisi esa MIN deb ataladi.
  
• 
  Ikkala o'yinchi ham u bilan kurashadi, chunki raqib o'yinchisi minimal foyda oladi, ular maksimal foyda oladi.
  
• 
  O'yinning ikkala o'yinchisi ham bir-biriga raqib bo'lib, MAX maksimal qiymatni, MIN esa minimallashtirilgan qiymatni tanlaydi.
  
• 
  Minimax algoritmi to'liq o'yin daraxtini o'rganish uchun birinchi chuqur qidiruv algoritmini amalga oshiradi.
  
• 
  Minimax algoritmi daraxtning terminal tuguniga qadar davom etadi, so'ngra daraxtni rekursiya sifatida orqaga qaytaradi.
  

Pseudo-code for MinMax Algorithm:

function minimax(node, depth, maximizingPlayer) is
if depth ==0 or node is a terminal node then
return static evaluation of node

if MaximizingPlayer then
maxEva= -infinity
 for each child of node do
 eva= minimax(child, depth-1, false)
maxEva= max(maxEva,eva)
return maxEva

else
 minEva= +infinity
 for each child of node do
 eva= minimax(child, depth-1, true)
 minEva= min(minEva, eva)
 return minEva 

Min-Maks algoritmining ishlashi:

• 
  Minimax algoritmining ishlashini misol yordamida osongina tasvirlash mumkin. Quyida biz ikki o'yinchi o'yinini ifodalovchi o'yin daraxti misolini oldik.
  
• 
  Ushbu misolda ikkita o'yinchi bor, biri Maximizer, ikkinchisi Minimizer deb ataladi.
  
• 
  Maksimallashtiruvchi maksimal mumkin bo'lgan ballni olishga harakat qiladi va Minimizer mumkin bo'lgan minimal ballni olishga harakat qiladi.
  
• 
  Ushbu algoritm DFS-ni qo'llaydi, shuning uchun ushbu o'yin daraxtida terminal tugunlariga erishish uchun barglar bo'ylab o'tishimiz kerak.
  
• 
  Terminal tugunida terminal qiymatlari berilgan, shuning uchun biz ushbu qiymatni solishtiramiz va dastlabki holat paydo bo'lguncha daraxtni orqaga qaytaramiz. Ikki o'yinchi o'yin daraxtini hal qilishning asosiy bosqichlari quyidagilardir:
  

1-qadam: Birinchi bosqichda algoritm butun o'yin daraxtini yaratadi va terminal holatlari uchun foydali qiymatlarni olish uchun yordamchi funktsiyani qo'llaydi. Quyidagi daraxt diagrammasida, keling, A daraxtning boshlang'ich holatini olaylik. Faraz qilaylik, maksimizator eng yomon boshlang'ich qiymati =- cheksiz bo'lgan birinchi burilishni oladi va minimallashtiruvchi eng yomon holatdagi boshlang'ich qiymati = + cheksiz bo'lgan keyingi burilishni oladi.

2-qadam: Endi biz birinchi navbatda Maximizer uchun yordamchi dasturlar qiymatini topamiz, uning boshlang'ich qiymati -∞, shuning uchun terminal holatidagi har bir qiymatni Maximizerning boshlang'ich qiymati bilan solishtiramiz va yuqori tugun qiymatlarini aniqlaymiz. U hamma orasida maksimalni topadi.

• 
  D tugun uchun max(-1,- -∞) => max(-1,4)= 4
  
• 
  E tugun uchun max(2, -∞) => max(2, 6)= 6
  
• 
  F tugun uchun max(-3, -∞) => max(-3,-5) = -3
  
• 
  G tugun uchun max(0, -∞) = max(0, 7) = 7