Py@Codette #4 3. Algoritmul Minimax
Pentru a patra ediție Py@Codette, ne-am gândit să explorăm puțin, la nivel de începători, atât un domeniu vast de cercetare pentru AI, și anume partea de Teoria Jocurilor, cât și un subdomeniu din AI, zona de Machine Learning, mai concret, partea de învățare supervizată îndreptată către Natural Language Processing.
În secțiunea aceasta ne concentrăm pe partea de game programming, mai exact un joc de x&0 pentru care construim un mod "Play against computer", în care computer-ul este capabil să vadă cu muulți pași înainte (chiar să prevadă cum se va termina jocul în funcție de mutarea pe care o alege). Vom face asta folosind algoritmul Minimax și vom vedea apoi o mare îmbunătățire pe care o putem aduce acestuia așa încât să reducem timpul de "gândire" al bot-ului programat.
Minimax este un algoritm aplicabil în teoria jocurilor, adică în probleme de decision making. Asta-l face să aibă treabă cu zona de AI. În rest, putem să vedem Minimax, mai degrabă ca pe o aplicație a Breadth First Search. (Poți citi aici mai multe despre asta).
Minimax este cel mai popular algoritm pentru jocuri cu o tablă pe care se joacă, și în care jucătorii mută pe rând. Deși extrem de potrivit pentru jocurile în care cunoaștem perfect regulile, s-ar putea totuși ca pentru jocuri ca și GO, unde factorul de ramificare este mare, să nu vrem să folosim Minimax. Nu putem spune că realizează tocmai cele mai înalte scopuri din zona de AI, dar pentru probleme de tipul celor din jocuri, unde avem niște reguli bine stabilite și cunoaștem care este starea "cea mai convenabilă" de finalizare a jocului, Minimax poate fi soluția.
Ca și aplicabilitate, putem spune că Minimax se mulează foarte bine pe jocurile bazate pe rând, cu doi jucători, eventual zero-sum games (adică dacă adun scorurile celor doi playeri, ajung la zero = cât câștigă un jucător, atât pierde celălalt, sau au egalitate la zero). O explicație mai pe larg despre zero-sum games, avem aici.
Fun fact: Primul AI care să fi bătut la șah un campion mondial a fost Deep Blue, în anul 1997. Și ghiciți ce algoritm folosea... O să vă scutesc de efort :)) și o să vă spun că Minimax. Deci merită studiat și înțeles acest algoritm. Mai ales că este și destul de simpluț.
Scopul este să găsim, într-o stare dată (a se citi dată fiind configurația curentă a board-ului), cea mai bună mutare pt player-ul nostru. Ca să putem compara mutări, avem nevoie de un scor. Dar în zero-sum games (căci pe asta vom lucra noi astăzi), nu obținem acest scor până abia la frunze. Deci trebuie să mergem recursiv până acolo: simulăm un curs al jocului alternând rândul nostru cu rândul adversarului, până se termină jocul și avem un scor disponibil, apoi îi facem backpropagation acestuia, către rădăcină.
Ce face acest algoritm este să aplice aceeași logică pe care ar aplica-o și un utilizator uman. Pentru că adevărul este că noi nu ne uităm un pas înainte când jucăm șah sau x&0 (de exemplu). Ne facem un scenariu și ne uităm câțiva pași înainte. Ei bine, pentru un computer, treaba asta cu uitatul înainte se poate face mult mai rapid. Iar minimax-ul duce la extrem totul, uitându-se la toate scenariile posibile începând din starea curentă, și până la finalul jocului. Minimax știe exact ce mutare să facă la un moment dat pentru a nu ajunge la un rezultat defavorabil lui. Pentru asta, el se pune și "în pantofii adversarului". Astfel în arborele acela de stări pe care el și-l construiește la fiecare nouă mutare, pe nivelul de max va juca el și va alege acțiuni care să-i maximizeze starea, pe nivelurile de min, va juca precum ar fi oponentul lui și va încerca să-și scadă scorul. Astfel el vede unde-l duce fiecare mutare, din punctul de vedere al finalului de joc. Și de aceea cu un bot ce implementează MiniMax poți să faci cel mult "egal" tu, ca utilizator uman.
Când bot-ul nostru simulează un joc până la final și joacă ca el însuși, pornește de la o utilitate inițializată la un nr foarte mic și tot face mutări uitându-se la utilități și păstrând doar acea mutare care are utilitate maximă.
Atunci când bot-ul este pe ramura de min din simulare, spunem că aici el se pune în pantofii adversarului și vom alege mutările cu utilitate minimă.
Ne uităm oare doar la mutarea curentă? Eu aș zice că dacă avem un dram de înțelepciune ne uităm câțiva pași înainte. Vrem să ne jucăm x&0 cu un adversar pe măsură. Și ce modalitate mai fun, dacă nu să ne construim un AI care să facă ce ar face orice player uman într-un așa joc: o căutare prin spațiul stărilor, printr-un game tree apoi să determine dacă o mutare ar aduce un rezultat favorabil sau nu.
A state space is the set of states reachable from the initial state by any sequence of actions. Rusell and Norvig
Pentru un X&0 de exemplu, starea inițială este felul cum arată grila la începutul jocului. Adică o matrice 3x3 cu pătrățelele necompletate.
După fiecare mutare, trecem într-o nouă stare (board-ul arată diferit). Stările reachable/posibile care construiesc acest spațiu al stărilor sunt acelea în care putem ajunge urmând o secvență de acțiuni (mutări) conforme cu regulile jocului.
Vedem mai jos un arbore parțial pt X&0. Așa ne facem noi AI-ul să simuleze jocuri la fiecare mutare și să determine cam care ar fi scorul obținut de fiecare dată. În funcție de asta, el va alege mutarea cea mai convenabilă.
O să vorbim puțin despre ce ne-ar fi necesar pentru a implementa un AI care să joace X&0, folosind algoritmul Minimax. Ca și pași, putem să ne gândim la o funcție recursivă care face următoarele:
- Returnează o valoare din mulțimea (+10, 0, -10) dacă o stare terminală a fost atinsă.
- Merge prin căsuțele goale de pe tablă (stările disponibile)
- Cheamă funcția minimax pentru fiecare stare disponibilă (recursion)
- Evaluează valorile returnate de apelurile funcției
- Returnează cea mai bună valoare. Asta înseamnă că noi o să alegem acțiunea cu cel mai mare scor posibil.
Detalii de implementare:
- Ne ținem starea (tabla) ca pe un dicționar de poziții pe tablă drept cheie și simbol ca și valoare:
- “ “ - dacă am liber în căsuță
- “X” sau “0”
- Ne trebuie două funcții care să verifice finalizarea jocului:
- check_win: caută configurații câștigătoare pe tablă "3 in a row".
- check_tie: ne spune dacă nu mai există căsuțe disponibile.
- Ca să cuantificăm valoarea fiecărei stări considerăm o funcție de utilitate U:State->R. Astfel, scopul nostru va fi să maximizăm această utilitate pentru noi, în timp ce oponentul va încerca minimizarea ei:
- 10: câștig
- (-10): pierdem
- 0: egal
Mai jos avem o exemplificare vizuală despre cum funcționează Minimax, în context de X&0.
NOTĂ
De reținut că în cazul Minimax la X&0, vorbim de recursivitate și vorbim de propagarea înapoi dinspre frunze spre rădăcină a utilității stărilor.
Prin urmare, trebuie ajuns într-o stare terminală ca să putem vorbi despre a cunoaște utilitățile stărilor ce au precedat-o pe un subarbore dat.
Aici vedem desfășurarea jocului dintr-o stare dată. Cum știe bot-ul că o să piardă / facă egal dacă mută așa încât să ajungă în starea 8.? Păi joacă pe rând până la final, pe toate scenariile posibile: odată ca el însuși, pe urmă din punctul de vedere al adversarului. Tot alternează așa, încercând să-și maximizeze recompensa când este el însuși (max) și să o minimizeze, când e adversar (min).
Algoritmul pentru ce s-a discutat aici îl putem vedea în code listing-ul următor:
MINIMAX(s)
For every a ∊ Actions(s)
if MIN-VALUE(RESULT(s, a)) > UTILITY(RESULT(s, best))
best = a
return best
MIN-VALUE(s)
If GAME-OVER(s)
return UTILITY(s)
For every a ∊ Actions(s)
sim-utility = MAX-VALUE(RESULT(s, a))
if sim-utility < worst
worst = sim-utility
return worst
MAX-VALUE(s)
If GAME-OVER(s)
return UTILITY(s)
For every a ∊ Actions(s)
sim-utility = MIN-VALUE(RESULT(s, a))
if sim-utility > best
best = sim-utility
return best
Note despre rulare:
-
Timp de rulare: O(bn), unde b ne dă nr maxim de mutări valide la un rând, iar n este adâncimea maximă a arborelui.
-
Acest AI va juca într-un fel în care presupune că adversarul lui este rațional și că va încerca doar mutări optimale. Lucru care, dacă nu e adevărat, nu ne va afecta cu nimic, dimpotrivă, înfrângerea adversarului se va întâmpla mai repede.
Problema atunci când folosim Minimax ar putea să fie o explozie de stări. Cu asta ne-am confrunta la un șah, dar pentru X&0 nu este o problemă așa mare dimensiunea spațiului stărilor. Chiar dacă ar fi, există o metodă îmbunătățită de Mini-Max, Alpa-Beta-Prunning (despre care vom vorbi în continuare), în care tăiem din start ramurile arborelui care se dovedesc a nu duce la câștig.
Haideți să vedem ce zic numerele despre grija exploziei de stări:
-
Să presupunem: Computer-ul este primul => 9 mutări posibile pt el
-
Apoi trebuie să simuleze câte o mutare posibilă a omului pentru fiecare mutare a sa. => 8 mutări
-
Apoi trece înapoi la a fi computer => 7 mutări rămase … => 9! = 362.880 mutări de evaluat de către computer inițial.
-
Apoi la a doua mutare vom avea => 7! = 5,040 states
Dacă jocul durează până mai avem o singură mutare disponibilă pentru computer => 9! + 7! + 5! + 3! + 1! = 368,047 total states
Poate părea mult, dar să luăm ca termen de comparație ce se întâmplă la șah, unde avem aproximativ 10^154 stări în arbore.
Prin urmare, se înțelege (sper eu) de ce folosim MiniMax ca și algoritm, mai ales pentru că este destul de fezabil să căutăm prin Game Tree în cazul MiniMax.
Am spus mai sus că în cazul X&0 nu este vorba tocmai despre o explozie de stări, fiind un joc mai micuț. Totuși este extrem de ineficient să lăsăm algoritmul să exploreze tot spațiul stărilor, când el deja și-a găsit o mutare optimă. Prin urmare, o să optimizăm aici folosind Alpha-Beta Prunning. Acest nou algoritm se rezumă la următoarea explicație: aplicăm Minimax și o să obținem tot mutarea care să dea rezultate optime, doar că nu mai generăm tot arborele.
Dacă aplicăm Alpha-Beta Prunning unui Minimax standard, ne va returna aceleași mutări ca și acesta, dar tăind acele ramuri care nu au cum să afecteze decizia finală. Altfel spus, dacă am găsit un maxim pe ramura curentă, nu ne ducem să mai explorăm și ceilalți subarbori.
Mai jos avem o reprezentare grafică preluată de aici, care ilustrează foarte bine cam cum se întâmplă tăierile în Alpha-Beta:
Se inițializează score-urile la cazul cel mai nasol:
- alpha = -inf
- beta = inf
Aici, tăierea ALPHA se întâmplă pe ramura MAX, iar BETA pe MIN. Condiția de a face prune: alpha >= beta.
Pseudocod:
evaluate (node, alpha, beta)
if node is a leaf
return the utility value of node
if node is a minimizing node
for each child of node
beta = min (beta, evaluate (child, alpha, beta))
if beta <= alpha
return beta
return beta
if node is a maximizing node
for each child of node
alpha = max (alpha, evaluate (child, alpha, beta))
if beta <= alpha
return alpha
return alpha
Alpha-beta pruning caută să reducă numărul de noduri de evaluat în arborele de căutare construit de Minimax. De exemplu, în tăierea alpha, de vreme ce nodul D returnează 1, nodul C (MIN) nu poate să fie mai mult de 1. Dar nodul B este 4. Nu e nevoie să ne mai uităm la ceilalți copii ai nodului C, de vreme ce nodul A o să aleagă oricum B în defavoarea lui C.
În acest algoritm, așa cum am menționat și mai sus, avem nevoie de doi parametri:
- alpha - valoare care ține cea mai bună valoare MAX găsită pe un nod MAX;
- beta - valoare care ține cea mai bună valoare MIN găsită pe un nod MIN.
Cum am zis, copii rămași pentru evaluare pot să fie abandonați dacă alpha ≥ beta, atât pentru tăierea alpha cât și pentru beta. Alpha și beta sunt inițializați la -∞ și +∞ respectiv.
Breadth First Search and Depth First Search
Introduction to Minimax Algorithm
How to make your Tic Tac Toe game unbeatable by using the minimax algorithm
Building an AI algorithm for the Tic-Tac-Toe challenge
Building an AI algorithm for the Tic-Tac-Toe challenge (video)
C code for Minimax applied to Tic-Tac-Toe
Tic-Tac-Toe - Understanding the Minimax Algorithm
Java Graphics Tutorial. Case Study on Tic-Tac-Toe Part 2: With AI.