Algoritmul Min Max în AI: Componente, Proprietăți, Avantaje și Limitări

Algoritmul min max în AI, cunoscut în mod popular sub numele de minimax, este un algoritm de backtracking utilizat în luarea deciziilor, teoria jocurilor și inteligența artificială (AI). Este folosit pentru a găsi mișcarea optimă pentru un jucător, presupunând că și adversarul joacă optim. Jocurile populare pentru doi jucători pe computer sau online, cum ar fi șah, Tic-Tac-Toe, Checkers, Go etc. folosesc acest algoritm.

Un algoritm de backtracking este utilizat pentru a găsi o soluție la problemele de calcul în așa fel încât un candidat să fie construit în mod incremental către o soluție, pas la un moment dat. Iar candidatul care nu reușește să finalizeze o soluție este imediat abandonat.

Cum functioneazã?

În algoritmul min max în AI, există doi jucători, Maximiser și Minimiser. Ambii acești jucători joacă jocul în timp ce unul încearcă să obțină cel mai mare scor posibil sau beneficiul maxim, în timp ce adversarul încearcă să obțină cel mai mic scor sau beneficiul minim.

Fiecare tablă de joc are un punctaj de evaluare atribuit, astfel încât Maximizatorul va selecta valoarea maximizată, iar Minimizerul va selecta valoarea minimizată cu mișcări contrare. Dacă Maximizatorul are avantajul, atunci scorul de pe tablă va fi o valoare pozitivă, iar dacă Minimiserul are avantajul, atunci scorul de la tablă va fi o valoare negativă.

Acesta se bazează pe conceptul de joc cu sumă zero, în care scorul total al utilității este împărțit între cei doi jucători. Astfel, o creștere a scorului unui jucător duce la o scădere a scorului adversarului, făcând ca scorul total să fie întotdeauna zero. Deci, pentru ca un jucător să câștige, celălalt trebuie să piardă.

Alăturați-vă cursurilor online de certificare de învățare automată și IA de la cele mai bune universități din lume. Câștigă Masters, Executive PGP sau ACP pentru a-ți accelera cariera.

Defalcarea algoritmului min max în AI

Arborele complet al jocului este explorat cu un algoritm de căutare în profunzime în algoritmul min max în AI. Se coboară complet până la nodul terminal al arborelui și apoi se întoarce înapoi prin arbore.

Scopul este de a găsi cea mai bună mișcare posibilă pentru un jucător. Acest lucru se poate face prin alegerea nodului cu cel mai bun scor de evaluare. Cea mai bună alegere va fi făcută după evaluarea tuturor mișcărilor potențiale ale adversarului. Algoritmul analizează toate valorile posibile până la sfârșit și ia o decizie pentru jucător.

Sursă

Arborele de joc de mai sus este o structură de date imbricată care este folosită pentru a evalua mișcările. Aici nodul rădăcină este Nivelul 0, care se ramifică în Nivelul 1 sau nodurile părinte, care se ramifică în continuare în Nivelul 2 sau nodurile copil. Ramificarea poate continua la mai multe niveluri, având potențialul de niveluri infinite. Nivelul 0 este ca starea curentă a tablei, în timp ce Nivelul 1 reprezintă toate stările posibile ale tablelor în funcție de următoarea mișcare.

Astfel, dacă Jucătorul 2 a făcut o mutare, putem presupune că nodul rădăcină este starea curentă a tablei, așteptând mutarea Jucătorului 1. Nodurile de nivel 1 conțin toate mișcările posibile pentru jucătorul 1, iar nodurile de nivel 2 conțin toate mișcările posibile pentru jucătorul 2 pe baza fiecărei mișcări posibile a jucătorului 1.

Luați în considerare un exemplu în care există patru stări finale și calea pentru a ajunge la acestea este de la rădăcină la cele patru frunze ale unui copac. Valorile celor patru frunze sunt 3, 6 în stânga și 4, 7 în dreapta. Este rândul Maximizatorului/Jucătorului 1 să facă o mișcare. Pentru a rula algoritmul, trebuie făcute ipoteze pentru fiecare mișcare.

Dacă Jucătorul 1 alege să meargă la stânga, Minimiserul/Jucătorul 2 trebuie să aleagă cel mai puțin între 3 și 6, și astfel ar alege 3. În timp ce dacă Jucătorul 1 alege dreapta, Jucătorul 2 va alege 4, care este minimul dintre cele două valori, 4 și 7. Deci, Nivelul 1 are acum valorile 3 și 4.

Deoarece este rândul Jucătorului 1/Maximizatorul, aceștia trebuie să aleagă maximum de noduri de Nivel 1. Astfel, vor alege 3. Atunci alegerea optimă este să mergi la stânga.

Pașii pentru algoritmul min max în AI pot fi indicați după cum urmează:

1. Creați întregul arbore de joc.
2. Evaluați scorurile pentru nodurile frunzelor pe baza funcției de evaluare.
3. Backtrack de la frunză la nodurile rădăcină:

Pentru Maximizer, alegeți nodul cu scorul maxim.

Pentru Minimizer, alegeți nodul cu scorul minim.

4. La nodul rădăcină, alegeți nodul cu valoarea maximă și selectați mutarea respectivă.

Citește și: Idei de proiecte de învățare automată

Proprietăți ale algoritmului min max în AI

• Algoritmul este complet, adică într-un arbore de căutare finit, cu siguranță se va găsi o soluție.
• Este optim dacă ambii jucători joacă optim.
• Datorită Depth-First Search (DFS) pentru arborele de joc, complexitatea temporală a algoritmului este O(b m ), unde b este factorul de ramificare și m este adâncimea maximă a arborelui.
• Ca și DFS, complexitatea spațială a acestui algoritm este O(bm).

Avantaje

• Se efectuează o evaluare amănunțită a spațiului de căutare.
• Luarea deciziilor în IA este ușor posibilă.
• Cu acest algoritm sunt dezvoltate mașini noi și inteligente.

Limitări

• Din cauza factorului uriaș de ramificare, procesul de atingere a scopului este mai lent.
• Evaluarea și căutarea tuturor nodurilor și ramurilor posibile degradează performanța și eficiența motorului.
• Ambii jucători au prea multe opțiuni din care să decidă.
• Dacă există o restricție de timp și spațiu, nu este posibil să explorați întregul copac.

Dar cu Alpha-Beta Pruning, algoritmul poate fi îmbunătățit.

Concluzie

Acest articol explică toate aspectele algoritmului min-max în AI. În primul rând, o introducere a teoriei este oferită cu exemple de unde este utilizată, după care există o descriere a modului în care algoritmul funcționează într-un joc.

Algoritmul este defalcat pentru a explica modul în care se ia decizia de a face o mișcare optimă pe baza mișcărilor și contra mișcărilor jucătorilor. Sunt apoi enumerate proprietățile algoritmului. În sfârșit, sunt prezentate avantajele și dezavantajele algoritmului.

Dacă sunteți interesat să aflați mai multe despre învățarea automată, consultați Programul Executive PG de la IIIT-B și upGrad în Învățare automată și IA, care este conceput pentru profesioniști care lucrează și oferă peste 450 de ore de pregătire riguroasă, peste 30 de studii de caz și sarcini, IIIT -B Statut de absolvenți, peste 5 proiecte practice practice și asistență pentru locuri de muncă cu firme de top.