[0:00]Hello friends, welcome to Gate Smasher. Aaj ki is video mein hum discuss karne ja rahe hain Minimax algorithm ke bare mein aur Minimax algorithm ke bare mein is video mein hum saare important point discuss karne ja rahe hain. Jo aapke competitive exams ke point of view se ya fir theory level ke exam ke point of view se baat karein toh dono mein hi bahut beneficial honge. Aur aap in saare points ko note kar sakte hain, in theory points ko. Toh sabse pehla point hai humare paas, it is a backtracking algorithm. Backtracking ka funda kya hota hai ki hum bilkul root level se pehle hum leaf level pe jaate hain, ya terminal pe jaate hain. Terminal pe hum values ko calculate karke un calculated values ko dobara propagate karte hain root level pe. Aur phir hum decide karte hain ki kaun si move hume choose karni hai, toh ye bahut hi important point hai yahan pe, it is a backtracking algorithm. Aur game playing mein bahut hi important ye question puchte hain ki breadth first search algorithm hum kyun nahi use karte hain, matlab BFS technique kyun nahi use karte hain hum game playing mein? Kyunki game playing ka simple sa funda kya hai ki let's say agar main yahan pe khel raha hu aur mere paas do choice hain, ya toh B jaun ya C jaun. Toh obviously humare paas ek hi move hoti hai.
[1:21]Toh ek move agar main chala toh uske baad opponent ki move hai yahan pe, lekin breadth first search ka funda kya hota hai, wo level order pe chalta hai, matlab har ek level ki saari moves ko pehle wo follow karega. Matlab wo pehle bolega, maine idhar bhi chalna hai aur phir wo ho sakta hai wo chaal wapis karke wo doosri chaal chale. Nahi, ye cheez hum allow nahi kar sakte game playing mein. Jo move ek baar chal gaya ab opponent ki turn hai. Toh ye jo breadth first search ka funda hai, ye hum ismein use isliye nahi kar sakte kyunki wo level of level by level jo hai wo follow karta hai. Lekin humein yahan pe use karna hai backtracking algorithm ka concept. Then best move strategy used. Best move ka funda kya hai? Let's say yahan pe do player hain, main khel raha hu aur aap khel rahe hain. Toh meri yahan pe, matlab priority kya rahegi? Meri yahan pe priority rahegi ya koshish kya rahegi ki main best move chalun jisse main jeetun aur aapki bhi priority kya rahegi ki aap bhi best move chalo aur mujhe jeetne na do. Toh yahi actual mein concept tha game playing ka ki game playing ka jo concept aaya tha toh ek taraf human being ek taraf machine. Toh machine ko is hisaab se learning diya gaya tha ki wo human ko beat kar sake. Toh yahan pe agar main as a human player kar raha hu, toh main agar main apni chaal ko kya karunga? Main apni move ko best karne ki koshish karunga taaki main jeetun. Aur saamne wala matlab jo computer hai wo meri chaal ke according kya chalega? Wo bhi best move hi chalega jisse main haru. Toh ye jo point hai best move strategy ka hi hum yahan pe use karte hain. Then max and min yahan pe jaisa ki humara algorithm ka naam hai minimax. Ye minimax ka funda kya hai yahan pe do player hai, max hai aur min hai. Toh main yahan pe bata deta hu. Let's say ki main as a max player play kar raha hu. Matlab jo human being hai wo max hai aur jo machine hai wo min hai, matlab opponent jo hai wo aapka min hai.
[2:58]Toh humare paas sabse pehle kiski turn hai? Let's say max. Hum hamesha max se hi start karte hain. Matlab pehle meri turn hai, toh maine jab apni turn choose ki, matlab maine apne choice jo hai apni move choose karunga. Toh main apni move ko maximum karunga. Toh yahan pe yahi line ki hui hai, ki max will try to maximize its utility. Yahan pe jo ye max word hai, student bahut baar confuse ho jaate hain ki ye max ka funda kya hai? Max ka matlab hai ki humne apni utility ko maximum karna hai. Utility ka matlab kya hai ki jeetne ke baad jo mujhe reward milega, jo point milenge. Jaisa ki humne introduction to game playing mein maine discuss kiye the ye saare keywords toh aap ek baar wo video check kar le jis se aapko idea ho jaye ki unmein humne kya-kya jo basic point discuss kiye the. Utility ka simple sa funda kya hai ki jo jeetne ke baad matlab winning ke kitne points hai loss ke kitne point hai ye wala jo concept hai. Toh main apni move ko best karunga so that meri utility maximum ho. Aur saamne wala matlab jo opponent hai wo minimum, minimum will try to minimize utility. Matlab wo meri utility ko minimize karne ki koshish karega by choosing the worst move. Worst move ka matlab uske hisaab se worst nahi hai. Wo mere according worst hai. Uske hisaab se toh wo best hi rahegi, lekin obviously wo mere liye kya rahegi worst move. Toh ye do bahut hi important point hai that is max will try to maximize, min will try to minimize. Toh sabse pehle agar hum baat karein yahan pe max toh ye mere paas ek game tree hai. Game tree mein yahan pe hum start karte hain let's say A se. Toh A ne matlab yahan pe hum A position pe hain root level pe hain. Toh root level pe max ke paas do choice hain ek B hai aur ek C hai. Toh ya toh wo B ko choose kar sakta hai ya C ko choose kar sakta hai. Agar wo B ko choose karega toh ab min ki turn aayegi aur min apni chaal chalega. Is tareeke se hume khelna hai jaise hum normal game khelte hain. Humne ek move choose ki aur ab doosre wale bande ne opponent ne move choose ki phir humne is tareeke se hume yahan pe move karna hai. Lekin yahan pe jo important point hai wo yahi hai ki humne jaise hi humne yahan pe choose kiya. Let's say humne yahan pe last mein leaf level pe terminal pe utilities mention ki hui hai. Toh yahan pe mere paas plus eight jo yahan pe dikh raha hai matlab agar main ye wali move chalunga toh ye mera jo utility hai mera jo profit hai, meri jo winning reward hai wo maximum hoga. Toh hume lagta hai ki haan yaar mujhe toh B choose karna chahiye, B ke baad mujhe D choose karna chahiye like that. Agar main is tareeke se chalunga toh meri jo winning probability hai wo bahut zyada high ho jayegi aur mere ko reward jo hai wo maximum milega. Lekin yahi game ke andar important point hai. Game mein aap apni strategy decide kar sakte ho lekin saamne wala kya chaal chalega wo aap decide nahi kar paye toh wo aapko harane ki poori koshish kar raha hai. Toh yahan pe aapko apni chaal chalni hai, next to next chaal kya hogi wo aapke opponent ki chaal ke upar depend karta hai. Toh yahan pe aapne kya karna hai max choose karna hai toh B aur C mein se jo bhi maximum hai. Aur phir uske baad min ki turn aayegi min minimum value ko choose karega is tareeke se hum aage move karenge. Phir again humare paas max hai aur max ne kya karna hai again max value ko choose karna hai. Toh agar hum baat karein yahan pe jaisa ki humne bola ki backtracking, backtracking pe jaane ke baad hi hume pata lagega ki humne kis method pe kis move ki taraf jaye toh humari winning jo hai wo pakki hai ya humara loss jo hai wo hoga. Toh yahan pe hum terminal pe aate hain sabse pehle toh terminal pe baat karein sabse pehle is taraf toh ye jo D hai matlab yahan pe humare paas max hai kyunki sabse pehle max chalega phir min phir max. Toh max yahan pe kya karega minus one aur eight do values hain mere paas. Agar main ye wali chaal chalta hu toh mere paas answer milega ya mere paas jo utility milegi minus one aur agar main ye wala chalta hu toh eight. Toh obviously in dono mein se wo kya karega? Max will try to maximize. Jaisa ki main yahan pe bola max will try to maximize toh dono mein se maximum kaun hai? Eight. Toh isne value kaun si choose karni hai? Eight. Matlab ye is taraf jayega so that iske paas jo profit aaye jo utility aaye wo maximum aaye. Then agar hum baat karein is wale particular node pe toh E pe agar dekho agar wo is taraf jaata hai toh minus three, is taraf jaata hai toh minus one. Toh minus three aur minus one mein se maximum value kaun si hai? Obviously wo sochega ki minus one theek hai. Halaanki ismein mere ko ghata ho raha hai, lekin isse toh kam hi ho raha hai ghata. Toh obviously yahan pe wo is move ko choose karne ki koshish karega toh yahan pe maximum value kya aayi minus one aur direction kaun si aayi aapki ek tarah se ye wali direction. Then agar hum baat karein yahan pe again max jo hai max yahan pe kya karega? Two aur one mein se maximum value ko choose karega. Toh maximum kaun si hai yahan pe? Two. Aur obviously kaun si direction hai ye wali. Then humare paas aata hai G. Toh G ke paas bhi do choice hai minus three, four. Obviously max ne kya karna hai? Apni utility ko maximum karna hai. Toh maximum kaun si hai ye wali? Toh obviously kaun si value hai maximum four aur direction kaun si hai ye wali? Toh ye kya kiya? Maximum ne apne according jo hai wo decide kar liya ki agar main ye wali chaal chalta hu ya ye chalta hu ya ye chalta hu toh meri jo utility hai wo is tareeke se maximum mil jayegi. Lekin jaisa ki maine bataya ki yahan pe depend karta hai opponent ke upar. Opponent matlab jo humara min hai. Ab min kya kar raha hai? Min will try to minimize the utility, matlab wo meri utility ko minimize karne ki koshish karega taaki uska zyada faida ho.
[8:26]Toh yahi point hum yahan pe discuss kar rahe hain. Toh min ki ab turn aayi. Min ne kya karna hai? Agar wo D ki taraf jaata hai, dhyaan se dekho, agar wo D ki taraf jaata hai toh usko kya lag raha hai? Usko pata lagega, arre max ko toh eight ka faida hoga. Yaani mere ko matlab min ko eight ka ghata hoga. Aur agar wo is taraf jaata hai E ki taraf toh min ko minus ek matlab ek ka faida hoga aur max ko ghata hoga. Toh obviously wo in dono mein se minimum value ko choose karega aur minimum value kaun si hai minus one. Simple sa point hai. Agar wo eight choose kar lega toh max toh fatfat eight wali value choose karke maximum utility eight leke jeet jayega. Toh obviously wo kya chahega ki maximum ki utility ko kam kiya jaye. Toh usne minimum value choose ki kaun si? Minus one. Matlab ye wali. Aur agar hum baat karein yahan pe C ki, agar hum C ki baat karein toh C ke point of view se yahan pe two hai aur four hai. Toh two aur four mein se minimum kaun hai? Two aur four mein se minimum hai two. Toh obviously wo kya karega utility ko kam karne ki koshish karega by choosing the minimum value that is two. Ab yahan pe agar hum baat karein max ki toh max jo hai wo starting mein kaun si value choose karne ki koshish karega? Max matlab wo minus one ki taraf jayega ya two ki taraf jayega? Agar wo minus one ki taraf gaya, obviously usko pata hai ki yahan pe meri jo utility hai wo minus one ki taraf ja rahi hai, matlab utility pehle hi negative mein ja rahi hai. Toh obviously wo kaun si choose karega? Two wali that is a positive side. Toh yahan pe usko guarantee hai agar wo ye wali strategy choose karta hai toh is strategy mein usko guarantee hai ki wo jeetega hi jeetega aur uski jo winning hai wo two usko utility milegi hi milegi. Kaun si direction? Agar C ki taraf jaata hai, C se wo F ki taraf jaata hai aur F se wo niche is terminal pe jaata hai. Toh is tareeke se uski jo winning hai wo two milegi hi milegi utility. Toh is tareeke se jo Minimax algorithm kaam karta hai. So time complexity of Minimax algorithm is order of B ki power D where B is the branching factor and D is the depth. Depth ya isko hum bol dete hain ply. Ply matlab moves jo hai hum yahan pe depth mein jitni depth mein jayenge that is the D and B is the branching factor. Branching factor matlab choices. Humare paas kitne children jo hai wo possible hain. Toh yahan pe agar hum baat karein Minimax mein jaisa ki aapko yahan pe dikh raha hai hum saari nodes ko ek ek baar zaroor traverse kar rahe hain. Toh yahan pe complexity B ki power D ka funda yahan pe kya hai ki agar humare paas number of children hain three aur D jo hai matlab depth hai two toh yaani meri time complexity kitni ho gayi nine. Which is feasible matlab hum is itni time complexity ko bear kar sakte hain. Lekin kai games aisi hain like chess. Chess ki agar hum baat karein toh chess mein on an average humare paas 35 choices possible hain. Matlab 35 moves possible hain that is a average value. Ye depend karta hai alag alag time pe. Lekin agar hum baat karein 35 choices possible hain humare paas aur number of moves kitni hai matlab depth kitni ho sakti hai depth ho sakti hai ek player ke liye on an average 50 aur obviously do player ke hisaab se total kitni ho gayi 100 moves possible hain. Toh 100 moves possible hain, 35 on an average choices hain toh jo game tree hai, game tree ka aap dekh sakte ho number of nodes kitni possible hain, 35 raise to power 100. Matlab itna bada game tree banega jisko aap traverse karna hi mushkil ho jayega. Toh isliye hum Minimax algorithm ko aise nahi ki saari games mein hi hum use kar sakte hain. Sirf kuch games hain like tic-tac-toe mein hum use kar sakte hain, nim mein use kar sakte hain. Nim game ke andar bhi hum isko use kar sakte hain. Lekin aise nahi ki saari games ke andar hum use kar sakte hain because iska jo tree hai wo bahut zyada vast ban jayega. Toh isko hum kam karne ke liye aur ismein efficiency laane ke liye hum alpha beta pruning method ko use karte hain. Thank you.
