Ishning nomi: Evristik qidiruv. Qidiruv usullarini o’rganish. O’yinlarda qidiruv algoritmlarini qo’llash. Minimax algoritmini o’rganish. Alfa-beta qidiruv, NegaMax algoritmi va boshqa qidiruv algoritmlari Ishdan maqsad

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Kafedra: Suniy intellekt

Fan nomi: Suniy intellekt asoslari

Amaliy ishi-3

Mavzu: Evristik qidiruv. Qidiruv usullarini o’rganish. O’yinlarda qidiruv algoritmlarini qo’llash. Minimax algoritmini o’rganish. Alfa-beta qidiruv, NegaMax algoritmi va boshqa qidiruv algoritmlari

Guruh: 211-18 Kif

Bajardi: G’afforov Shaxzodbek
O’qituvchi: Rahimov Mehriddin
Ishning nomi: Evristik qidiruv. Qidiruv usullarini o’rganish. O’yinlarda qidiruv algoritmlarini qo’llash. Minimax algoritmini o’rganish. Alfa-beta qidiruv, NegaMax algoritmi va boshqa qidiruv algoritmlari
Ishdan maqsad: Hozirda mavjud sun’iy intellekt sohadagi o’yinlarda qidiruv algoritmlarini qo’llash bo’yicha qo’shimcha ma’lumotlarni shakllantirish.


Alpha-Beta aslida yangi algoritm emas, balki minimaks algoritmi uchun optimallashtirish texnikasi. 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, chunki yaxshiroq harakat allaqachon mavjud. Bu alfa-beta kesish deb ataladi, chunki u minimax funktsiyasida ikkita qo'shimcha parametr, ya'ni alfa va betadan o'tadi.
Alfa va beta parametrlarini aniqlaymiz. 
Alfa - bu maksimal daraja yoki undan yuqori darajalarda hozirda kafolatlashi mumkin bo'lgan eng yaxshi qiymat .
BetaMinimizator hozirda shu darajada yoki undan yuqorida kafolatlashi mumkin bo'lgan eng yaxshi qiymatdir .

Psevdokod:

function minimax(node, depth, isMaximizingPlayer, alpha, beta):


if node is a leaf node :
return value of the node

if isMaximizingPlayer :
bestVal = -INFINITY
for each child node :
value = minimax(node, depth+1, false, alpha, beta)
bestVal = max( bestVal, value)
alpha = max( alpha, bestVal)
if beta <= alpha:
break
return bestVal


else :
bestVal = +INFINITY
for each child node :
value = minimax(node, depth+1, true, alpha, beta)
bestVal = min( bestVal, value)
beta = min( beta, bestVal)
if beta <= alpha:
break
return bestVal