TechCodeview

• Algoritmul Mini-max este un algoritm recursiv sau de backtracking care este utilizat în luarea deciziilor și în teoria jocurilor. Oferă o mișcare optimă jucătorului, presupunând că și adversarul joacă în mod optim.
• Algoritmul Mini-Max folosește recursiunea pentru a căuta prin arborele de joc.
• Algoritmul Min-Max este folosit mai ales pentru jocul în AI. Cum ar fi șah, dame, tic-tac-toe, go și diverse jocuri de remorcare. Acest algoritm calculează decizia minimax pentru starea curentă.
• În acest algoritm doi jucători joacă jocul, unul se numește MAX și celălalt se numește MIN.
• Ambii jucători luptă pe măsură ce adversarul primește beneficiul minim, în timp ce ei obțin beneficiul maxim.
• Ambii jucători ai jocului sunt adversari unul altuia, unde MAX va selecta valoarea maximizată și MIN va selecta valoarea minimizată.
• Algoritmul minimax realizează un algoritm de căutare în profunzime pentru explorarea întregului arbore de joc.
• Algoritmul minimax continuă până la nodul terminal al arborelui, apoi face înapoi arborele ca recursivitate.

Pseudo-cod pentru algoritmul MinMax:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

Apel inițial:

Minimax(nodul, 3, adevărat)

Funcționarea algoritmului Min-Max:

• Funcționarea algoritmului minimax poate fi descrisă cu ușurință folosind un exemplu. Mai jos am luat un exemplu de arbore de joc care reprezintă jocul cu doi jucători.
• În acest exemplu, există doi jucători, unul se numește Maximizer și celălalt se numește Minimizer.
• Maximizer va încerca să obțină scorul maxim posibil, iar Minimizer va încerca să obțină scorul minim posibil.
• Acest algoritm aplică DFS, așa că în acest arbore de joc, trebuie să mergem până la capăt prin frunze pentru a ajunge la nodurile terminale.
• La nodul terminal, valorile terminale sunt date, astfel încât vom compara acele valori și vom reveni înapoi în arbore până când apare starea inițială. Mai jos sunt pașii principali implicați în rezolvarea arborelui jocului pentru doi jucători:

Pasul 1: În primul pas, algoritmul generează întregul arbore de joc și aplică funcția de utilitate pentru a obține valorile de utilitate pentru stările terminale. În diagrama arborelui de mai jos, să considerăm că A este starea inițială a arborelui. Să presupunem că maximizatorul ia primul rând care are valoarea inițială în cel mai rău caz =- infinit, iar minimizatorul va lua rândul următor care are valoarea inițială în cel mai rău caz = + infinit.

Pasul 2: Acum, mai întâi găsim valoarea utilităților pentru Maximizer, valoarea sa inițială este -∞, așa că vom compara fiecare valoare în starea terminală cu valoarea inițială a Maximizer și determinăm valorile mai mari ale nodurilor. Va găsi maximul dintre toate.

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

Pasul 3: În pasul următor, este un rând pentru minimizator, așa că va compara valoarea tuturor nodurilor cu +∞ și va găsi cele 3^rdvalorile nodului stratului.

• Pentru nodul B= min(4,6) = 4
• Pentru nodul C= min (-3, 7) = -3

Pasul 4: Acum este rândul lui Maximizer și va alege din nou valoarea maximă a tuturor nodurilor și va găsi valoarea maximă pentru nodul rădăcină. În acest arbore de joc, există doar 4 straturi, prin urmare ajungem imediat la nodul rădăcină, dar în jocurile reale, vor exista mai mult de 4 straturi.

• Pentru nodul A max(4, -3)= 4

Acesta a fost fluxul de lucru complet al jocului minimax pentru doi jucători.

Proprietățile algoritmului Mini-Max:

Complet-Algoritmul Min-Max este Complet. Cu siguranță va găsi o soluție (dacă există), în arborele de căutare finit.optim-Algoritmul Min-Max este optim dacă ambii adversari joacă optim.complexitatea timpului-Deoarece efectuează DFS pentru arborele de joc, complexitatea de timp a algoritmului Min-Max este O(b^m) , unde b este factorul de ramificare al arborelui de joc și m este adâncimea maximă a arborelui.Complexitatea spațială-Complexitatea spațială a algoritmului Mini-max este, de asemenea, similară cu DFS, care este Despre .

Limitarea algoritmului minimax:

Principalul dezavantaj al algoritmului minimax este că devine foarte lent pentru jocuri complexe, cum ar fi șah, go, etc. Acest tip de jocuri are un factor de ramificare uriaș, iar jucătorul are o mulțime de opțiuni de decis. Această limitare a algoritmului minimax poate fi îmbunătățită de la tăierea alfa-beta despre care am discutat în subiectul următor.