algoritm Minimax cu tăiere alfa-beta

încă de la apariția inteligenței artificiale (AI), jocul a fost una dintre cele mai interesante aplicații ale AI.

primele programe de șah au fost scrise de Claude Shannon și de Alan Turing în 1950, aproape imediat ce computerele au devenit programabile.

jocuri precum șah, tic-tac-toe și Go sunt interesante deoarece oferă o abstracție pură a competiției dintre cele două armate.

această abstractizare face ca jocul să fie o zonă atractivă pentru cercetarea AI.

în acest articol, vom trece prin elementele de bază ale algoritmului Minimax împreună cu funcționarea algoritmului.

vom analiza, de asemenea, optimizarea algoritmului minimax, tăierea alfa-beta.

ce este algoritmul Minimax?

Minimax este un algoritm recursiv care este folosit pentru a alege o mișcare optimă pentru un jucător presupunând că și celălalt jucător joacă optim.

este folosit în jocuri precum tic-tac-toe, go, șah, Isola, dame și multe alte jocuri cu doi jucători.

astfel de jocuri sunt numite jocuri de informații perfecte, deoarece este posibil să se vadă toate mișcările posibile ale unui anumit joc.

pot exista jocuri cu doi jucători care nu sunt de informații perfecte, cum ar fi Scrabble, deoarece mișcarea adversarului nu poate fi prezisă.

este similar cu modul în care gândim atunci când jucăm un joc: „dacă fac această mișcare, atunci adversarul meu poate face doar aceste mișcări” și așa mai departe.

Minimax este numit astfel, deoarece ajută la minimizarea pierderii atunci când celălalt jucător alege strategia având pierderea maximă.

terminologie

• arborele de joc: este o structură sub forma unui copac format din toate mișcările posibile care vă permit să treceți de la o stare a jocului la următoarea stare.

un joc poate fi definit ca o problemă de căutare cu următoarele componente:

• starea inițială: cuprinde poziția Consiliului și arată a cărui mișcare este.
• funcție succesoare: Acesta definește ceea ce se mută legale un jucător poate face sunt.
• starea terminalului: este poziția plăcii atunci când jocul se termină.
• funcția de utilitate: este o funcție care atribuie o valoare numerică pentru rezultatul unui joc. De exemplu, în șah sau tic-tac-toe, rezultatul este fie o victorie, o pierdere, sau o remiză, iar acestea pot fi reprezentate de valorile +1, -1, sau 0, respectiv. Există jocuri care au o gamă mult mai mare de rezultate posibile; de exemplu, utilitățile din table variază de la +192 la -192. O funcție de utilitate poate fi numită și funcție de plată.

cum funcționează algoritmul?

există doi jucători implicați într-un joc, numit MIN și MAX. Jucătorul MAX încearcă să obțină cel mai mare scor posibil, iar MIN încearcă să obțină cel mai mic scor posibil, adică MIN și MAX încearcă să acționeze opus unul altuia.

procesul general al algoritmului Minimax este următorul:

Pasul 1: în primul rând, generați întregul arbore de joc începând cu poziția curentă a jocului până la stările terminale. Acesta este modul în care arborele de joc arata ca pentru jocul tic-tac-toe.

să ne înțelegem terminologia definită în ceea ce privește diagrama de mai sus.

1. starea inițială este primul strat care definește că placa este goală, este rândul lui MAX să joace.
2. funcția succesor listează toate posibilele mutări succesor. Este definit pentru toate straturile din copac.
3. starea terminală este ultimul strat al arborelui care arată starea finală, adică dacă jucătorul MAX câștigă, pierde sau leagă cu adversarul.
4. utilitățile în acest caz pentru stările terminale sunt 1, 0 și -1 așa cum am discutat mai devreme și pot fi utilizate și pentru a determina utilitățile celorlalte noduri.

Pasul 2: aplicați funcția utility pentru a obține valorile utility pentru toate stările terminale.
Pasul 3: determinați utilitățile nodurilor superioare cu ajutorul utilităților nodurilor terminale. De exemplu, în diagrama de mai jos, avem utilitățile pentru stările terminale scrise în pătrate.

să calculăm utilitatea pentru nodul stâng (roșu) al stratului de deasupra terminalului. Deoarece este mutarea jucătorului MIN, vom alege minimul tuturor utilităților. Pentru acest caz, trebuie să evaluăm min{3, 5, 10}, despre care știm că este cu siguranță 3. Deci utilitatea pentru nodul roșu este 3.

în mod similar, pentru nodul verde din același strat, va trebui să evaluăm min{2,2} care este 2.

Pasul 4: Calculați valorile utilității cu ajutorul frunzelor, luând în considerare un strat la un moment dat până la rădăcina copacului.
Pasul 5: în cele din urmă, toate valorile susținute ajung la rădăcina copacului, adică punctul cel mai de sus. În acel moment, MAX trebuie să aleagă cea mai mare valoare.

în exemplul nostru, avem doar 3 straturi, așa că am ajuns imediat la rădăcină, dar în jocurile reale, vor exista mai multe straturi și noduri. Deci, trebuie să evaluăm max{3,2} care este 3.

prin urmare, cea mai bună mișcare de deschidere pentru MAX este nodul stâng(sau cel roșu). Această mișcare se numește decizia minimax, deoarece maximizează utilitatea urmând presupunerea că adversarul joacă, de asemenea, optim pentru a-l minimiza.

pentru a rezuma,

decizie Minimax = MAX{MIN{3,5,10}, MIN{2,2}}
= MAX{3,2}
= 3

Psuedocod:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

optimizare

copacii de joc sunt, în general, foarte consumatoare de timp pentru a construi, și este doar pentru jocuri simple, care pot fi generate într-un timp scurt.

dacă există\ (b\) mișcări legale, adică.,\ (B\) noduri la fiecare punct și adâncimea maximă a arborelui este\ (m\), complexitatea în timp a algoritmului minimax este de ordinul\(b^m(O (b^m))\).

pentru a reduce această situație, există câteva optimizări care pot fi adăugate algoritmului.

din fericire, este viabil să găsiți decizia minimax reală fără să vă uitați măcar la fiecare nod al arborelui de joc. Prin urmare, eliminăm nodurile din copac fără a analiza, iar acest proces se numește tăiere.

tăiere alfa-beta

metoda pe care o vom căuta în acest articol se numește tăiere alfa-beta.

dacă aplicăm tăierea alfa-beta unui algoritm minimax standard, acesta returnează aceeași mișcare ca cea standard, dar elimină (prune) toate nodurile care nu afectează eventual decizia finală.

să înțelegem mai întâi intuiția din spatele acestui lucru și apoi vom formaliza algoritmul. Să presupunem că avem următorul arbore de joc:

în acest caz,
decizie Minimax = MAX{MIN{3,5,10}, MIN{2, A, b}, MIN{2,7,3}}
= MAX{3, c,2}
= 3

ai fi surprins!

cum am putea calcula maximul cu o valoare lipsă? Iată trucul. MIN{2,A, b} ar fi cu siguranță mai mică sau egală cu 2, adică c<=2 și, prin urmare,MAX{3,c, 2} trebuie să fie 3.

întrebarea acum este chiar trebuie să calculăm c? Bineînțeles că nu.

am fi putut ajunge la o concluzie fără să ne uităm la acele noduri. Și aici intră în imagine tăierea alfa-beta.

câteva definiții:

Alpha: este cea mai bună alegere de până acum pentru jucătorul MAX. Vrem să obținem cea mai mare valoare posibilă aici.
Beta: Este cea mai bună alegere de până acum pentru MIN și trebuie să fie cea mai mică valoare posibilă.

notă: Fiecare nod trebuie să țină evidența valorilor sale alfa și beta. Alpha poate fi actualizat numai atunci când este rândul lui MAX și, în mod similar, beta poate fi actualizat numai atunci când este șansa lui MIN.

cum funcționează tăierea alfa-beta?

1. inițializați alpha = -infinity și beta = infinity ca fiind cele mai grave cazuri posibile. Condiția de a tăia un nod este atunci când alfa devine mai mare sau egal cu beta.
2. începeți cu atribuirea valorilor inițiale ale alfa și beta la rădăcină și din moment ce alfa este mai mică decât beta, nu o tăiem.
3. transportați aceste valori ale alfa și beta la nodul copil din stânga. Și acum din valoarea utilității stării terminale, vom actualiza valorile alpha și be, deci nu trebuie să actualizăm valoarea beta. Din nou, nu tăiem, deoarece starea rămâne aceeași. În mod similar, al treilea nod copil, de asemenea. Și apoi înapoi la rădăcină setăm alpha = 3 pentru că aceasta este valoarea minimă pe care alpha o poate avea.
   
4. acum, alfa = 3 și beta = infinit la rădăcină. Deci, noi nu prune. Transportând acest lucru la nodul central și calculând min{2, infinit}, obținem alfa=3 și beta=2.
5. tăiați al doilea și al treilea nod copil, deoarece alfa este acum mai mare decât beta.
6. alfa la rădăcină rămâne 3 deoarece este mai mare decât 2. Transportând acest lucru la nodul copil din dreapta, evaluați min{infinity, 2} = 2. Actualizați beta la 2 și alfa rămâne 3.
7. tăiați al doilea și al treilea nod copil, deoarece alfa este acum mai mare decât beta.
8. prin urmare, obținem 3, 2, 2 la nodurile MIN stânga, centru și, respectiv, dreapta. Și calculând max{3,2,2}, obținem 3. Prin urmare, fără să ne uităm chiar la patru frunze, am putea găsi corect decizia minimax.

pseudocod (Sursa: curs NPTEL):

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

concluzie

jocurile sunt foarte atrăgătoare și scrierea programelor de joc este poate și mai interesantă. Ce curse Grand Prix este pentru industria auto, Jocul este pentru AI.

la fel cum nu ne-am aștepta ca o mașină de curse să ruleze perfect pe un drum accidentat, nu ar trebui să ne așteptăm ca algoritmii de joc să fie perfecți pentru orice situație.

la fel și algoritmul minimax. Este posibil să nu fie cea mai bună soluție pentru toate tipurile de jocuri pe calculator care trebuie să aibă AI.

dar având în vedere o implementare bună, poate crea un concurent dur.