M-am luptat ore întregi parcurgând tutoriale, vizionând videoclipuri și lovind capul pe birou încercând să construiesc un joc imbatabil Tic Tac Toe cu o inteligență artificială de încredere. Deci, dacă parcurgeți o călătorie similară, aș dori să vă prezint algoritmul Minimax.

La fel ca un șahist profesionist, acest algoritm vede câțiva pași înainte și se pune în locul adversarului său. Se continuă să joace înainte până ajunge la un aranjament terminal al plăcii (starea terminalului) rezultând o egalitate, o victorie sau o pierdere. Odată ajuns într-o stare terminală, AI va atribui un scor pozitiv arbitrar (+10) pentru o victorie, un scor negativ (-10) pentru o pierdere sau un scor neutru (0) pentru o egalitate.

În același timp, algoritmul evaluează mișcările care duc la o stare terminală pe baza rândului jucătorilor. Va alege mișcarea cu scor maxim atunci când este rândul AI și va alege mișcarea cu scorul minim atunci când este rândul jucătorului uman. Folosind această strategie, Minimax evită să piardă în fața jucătorului uman.

Încercați-o pentru dvs. în jocul următor, de preferință folosind un browser Chrome.

Un algoritm Minimax poate fi cel mai bine definit ca o funcție recursivă care face următoarele lucruri:

  1. returnează o valoare dacă se găsește o stare terminală (+10, 0, -10)
  2. treceți prin locurile disponibile pe tablă
  3. apelați funcția minimax pe fiecare loc disponibil (recursivitate)
  4. evaluați valorile returnate din apelurile de funcții
  5. și returnează cea mai bună valoare

Dacă sunteți nou la conceptul de recursivitate, vă recomand să urmăriți acest lucru video din CS50 de la Harvard.

Pentru a înțelege complet procesul de gândire al Minimax, să-l implementăm în cod și să-l vedem în acțiune în următoarele două secțiuni.

Minimax în cod

Pentru acest tutorial veți lucra la o stare finală aproape a jocului, care este prezentată în figura 2 de mai jos. Deoarece minimax evaluează fiecare stare a jocului (sute de mii), o stare finală aproape vă permite să urmăriți mai ușor apelurile recursive ale minimax (9).

Pentru următoarea figură, presupuneți că AI este X și jucătorul uman este O.

Cum sa ti faci jocul Tic Tac Toe imbatabil folosind algoritmul
figura 2 eșantion de starea jocului

Pentru a lucra mai ușor cu placa Ti Tac Toe, ar trebui să o definiți ca o matrice cu 9 articole. Fiecare articol va avea indicele său ca valoare. Acest lucru va fi util mai târziu. Deoarece placa de mai sus este deja populată cu unele mișcări X și Y, haideți să definim placa cu mișcările X și Y deja în ea (origBoard).

var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

Atunci declarați aiPlayer și huPlayer variabile și setați-le la „X” și respectiv „O”.

În plus, aveți nevoie de o funcție care caută combinații câștigătoare și revine adevărată dacă găsește una și de o funcție care listează indexurile locurilor disponibile în tablă.

/* the original board
 O |   | X
 ---------
 X |   | X
 ---------
   | O | O
 */
var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”];

// human
var huPlayer = “O”;

// ai
var aiPlayer = “X”;

// returns list of the indexes of empty spots on the board
function emptyIndexies(board){
  return  board.filter(s => s != "O" && s != "X");
}

// winning combinations using the board indexies
function winning(board, player){
 if (
 (board[0] == player && board[1] == player && board[2] == player) ||
 (board[3] == player && board[4] == player && board[5] == player) ||
 (board[6] == player && board[7] == player && board[8] == player) ||
 (board[0] == player && board[3] == player && board[6] == player) ||
 (board[1] == player && board[4] == player && board[7] == player) ||
 (board[2] == player && board[5] == player && board[8] == player) ||
 (board[0] == player && board[4] == player && board[8] == player) ||
 (board[2] == player && board[4] == player && board[6] == player)
 ) {
 return true;
 } else {
 return false;
 }
}

Acum să ne scufundăm în părțile bune definind funcția Minimax cu două argumente newBoard și jucător. Apoi, trebuie să găsiți indexurile locurilor disponibile în tablă și să le setați la o variabilă numită availSpots.

// the main minimax function
function minimax(newBoard, player){
  
    //available spots
    var availSpots = emptyIndexies(newBoard);

De asemenea, trebuie să verificați stările terminalului și să returnați o valoare în consecință. Dacă O câștigă, ar trebui să întoarceți -10, dacă X câștigă, ar trebui să întoarceți +10. În plus, dacă lungimea disponibileSpots matricea este zero, ceea ce înseamnă că nu mai este loc de jucat, jocul a dus la egalitate și ar trebui să întoarceți zero.


  // checks for the terminal states such as win, lose, and tie 
  //and returning a value accordingly
  if (winning(newBoard, huPlayer)){
     return {score:-10};
  }
	else if (winning(newBoard, aiPlayer)){
    return {score:10};
	}
  else if (availSpots.length === 0){
  	return {score:0};
  }

Apoi, trebuie să colectați scorurile din fiecare dintre locurile goale pentru a le evalua ulterior. Prin urmare, faceți o matrice numită mișcări și parcurgeți punctele goale în timp ce colectați indexul și scorul fiecărei mișcări într-un obiect numit mișcare.

Apoi, setați numărul de index al punctului gol care a fost stocat ca număr în origBoard la proprietatea index a mișcare obiect. Mai târziu, setați locul gol pe tablă nouă la playerul curent și apelați minimax funcționează cu alt jucător și cu noul schimbat tablă nouă. Apoi, ar trebui să stocați obiectul rezultat din minimax apel de funcție care include un scor proprietate la scor proprietate a mișcare obiect.

Dacă funcția minimax nu găsește o stare terminală, se menține recursiv nivel cu nivel mai adânc în joc. Această recursivitate se întâmplă până când ajunge la o stare terminală și returnează un scor cu un nivel în sus.

În cele din urmă, Minimax se resetează newBoard la ceea ce era înainte și împinge mișcare obiectează la mișcări matrice.

// an array to collect all the objects
  var moves = [];

  // loop through available spots
  for (var i = 0; i < availSpots.length; i++){
    //create an object for each and store the index of that spot 
    var move = {};
  	move.index = newBoard[availSpots[i]];

    // set the empty spot to the current player
    newBoard[availSpots[i]] = player;

    /*collect the score resulted from calling minimax 
      on the opponent of the current player*/
    if (player == aiPlayer){
      var result = minimax(newBoard, huPlayer);
      move.score = result.score;
    }
    else{
      var result = minimax(newBoard, aiPlayer);
      move.score = result.score;
    }

    // reset the spot to empty
    newBoard[availSpots[i]] = move.index;

    // push the object to the array
    moves.push(move);
  }

Apoi, algoritmul minimax trebuie să evalueze cel mai bun mișcare în mișcări matrice. Ar trebui să aleagă mișcare cu cel mai mare scor când AI joacă și mișcare cu scorul cel mai mic atunci când omul joacă. Prin urmare, dacă jucător este aiPlayer, setează o variabilă numită cel mai bun scor la un număr foarte mic și parcurge prin mișcări matrice, dacă a mișcare are o mai mare scor decât cel mai bun scor, algoritmul stochează că mișcare. În cazul în care există mișcări cu scor similar, doar prima va fi stocată.

Același proces de evaluare se întâmplă atunci când jucător este huPlayer, dar de data asta cel mai bun scor ar fi setat la un număr mare și Minimax caută o mișcare cu cel mai mic scor de stocat.

La final, Minimax returnează obiectul stocat în bestMove.

// if it is the computer's turn loop over the moves and choose the move with the highest score
  var bestMove;
  if(player === aiPlayer){
    var bestScore = -10000;
    for(var i = 0; i < moves.length; i++){
      if(moves[i].score > bestScore){
        bestScore = moves[i].score;
        bestMove = i;
      }
    }
  }else{

// else loop over the moves and choose the move with the lowest score
    var bestScore = 10000;
    for(var i = 0; i < moves.length; i++){
      if(moves[i].score < bestScore){
        bestScore = moves[i].score;
        bestMove = i;
      }
    }
  }

// return the chosen move (object) from the moves array
  return moves[bestMove];
}

Asta este pentru funcția minimax. 🙂 Puteți găsi algoritmul de mai sus pe github și codepen. Jucați-vă cu diferite panouri și verificați rezultatele în consolă.

În secțiunea următoare, să trecem peste codul rând cu rând pentru a înțelege mai bine cum se comportă funcția minimax, având în vedere placa prezentată în figura 2.

Minimax în acțiune

Folosind următoarea figură, să urmărim apelurile funcției algoritmului (FC) unul câte unul.

Notă: În figura 3, numerele mari reprezintă fiecare apel funcțional, iar nivelurile se referă la câți pași înainte de joc se joacă algoritmul.

1611599410 528 Cum sa ti faci jocul Tic Tac Toe imbatabil folosind algoritmul
Figura 3 Apel funcție Minimax după apel funcție

1.origBoard și aiPlayer este alimentat algoritmului. Algoritmul face o listă cu cele trei locuri goale pe care le găsește, verifică stările terminale și parcurge fiecare loc gol începând cu primul. Apoi, modifică newBoard prin plasarea aiPlayer în primul loc gol. Dupa aceea, se numește cu newBoard si huPlayer și așteaptă ca FC să returneze o valoare.

2. În timp ce primul FC funcționează în continuare, al doilea începe prin a face o listă cu cele două locuri goale pe care le găsește, verifică stările terminale și trece prin locul gol începând cu primul. Apoi, modifică newBoard prin plasarea huPlayer în primul loc gol. Dupa aceea se numește cu newBoard si aiPlayer și așteaptă ca FC să returneze o valoare.

3. În cele din urmă, algoritmul face o listă a punctelor goale și găsește un câștig pentru jucătorul uman după verificarea stărilor terminale. Prin urmare, returnează un obiect cu o proprietate de scor și o valoare de -10.

Deoarece al doilea FC a enumerat două locuri goale, Minimax schimbă newBoard prin plasare huPlayer în al doilea loc gol. Apoi, se numește cu noua placă și cu aiPlayer.

4. Algoritmul face o listă a punctelor goale și găsește un câștig pentru jucătorul uman după verificarea stărilor terminalului. Prin urmare, returnează un obiect cu o proprietate de scor și o valoare de -10.

Pe cel de-al doilea FC, algoritmul colectează valorile provenite de la niveluri inferioare (3 și 4 FC). De cand huPlayerLa rândul său a rezultat cele două valori, algoritmul alege cea mai mică dintre cele două valori. Deoarece ambele valori sunt similare, alege prima și o întoarce la primul FC.

În acest moment, primul FC a evaluat scorul mișcării aiPlayer în primul loc gol. Apoi, modifică newBoard prin plasare aiPlayer în al doilea loc gol. Apoi, se numește cu newBoard si huPlayer.

5. În cel de-al cincilea FC, algoritmul face o listă a locurilor goale și găsește un câștig pentru jucătorul uman după verificarea stărilor terminale. Prin urmare, returnează un obiect cu o proprietate de scor și o valoare de +10.

După aceea, primul FC trece prin schimbarea newBoard și plasarea aiPlayer în al treilea loc gol. Apoi, se numește cu noua placă și cu huPlayer.

6. Cel de-al 6-lea FC începe prin a face o listă cu două locuri goale pe care le găsește, verifică stările terminale și parcurge cele două locuri goale începând cu primul. Apoi, modifică newBoard prin plasarea huPlayer în primul loc gol. Dupa aceea, se numește cu newBoard si aiPlayer și așteaptă ca FC să întoarcă un scor.

7. Acum algoritmul este la două niveluri adânc în recursivitate. Face o listă a locului gol pe care îl găsește, verifică starea terminalului și modifică newBoard prin plasarea aiPlayer în locul gol. Dupa aceea, se numește cu newBoard si huPlayer și așteaptă ca FC să returneze un scor pentru a-l putea evalua.

8. În al 8-lea FC, algoritmul face o listă goală de locuri goale și găsește un câștig pentru aiPlayer după verificarea stărilor terminale. Prin urmare, returnează un obiect cu proprietate de scor și valoare de +10 cu un nivel mai sus (al 7-lea FC).

Cel de-al 7-lea FC a primit o singură valoare pozitivă de la nivelurile inferioare (al 8-lea FC). pentru că rândul lui aiPlayer rezultând în acea valoare, algoritmul trebuie să returneze cea mai mare valoare pe care a primit-o de la niveluri inferioare. Prin urmare, își returnează singura valoare pozitivă (+10) cu un nivel mai sus (al 6-lea FC).

Din moment ce al 6-lea FC a enumerat două locuri goale, Minimax se schimbă newBoard prin plasare huPlayer în al doilea loc gol. Apoi, se numește cu noua placă și cu aiPlayer.

9. Apoi, algoritmul face o listă a punctelor goale și găsește un câștig pentru aiPlayer după verificarea stărilor terminale. Prin urmare, returnează un obiect cu proprietăți de scor și valoare de +10.

În acest moment, cei 6 FC trebuie să aleagă între scorul (+10) trimis de la cel de-al 7-lea FC (returnat inițial de la 8 FC) și scorul (-10) returnat de la cel de-al 9-lea FC. De cand huPlayerLa rândul său, a rezultat acele două valori returnate, algoritmul găsește scorul minim (-10) și îl întoarce în sus ca obiect care conține scor și proprietăți index.

În cele din urmă, au fost evaluate toate cele trei ramuri ale primului FC (-10, +10, -10). Dar, deoarece rândul lui aiPlayer a dus la acele valori, algoritmul returnează un obiect care conține cel mai mare scor (+10) și indicele acestuia (4).

În scenariul de mai sus, Minimax concluzionează că deplasarea X la mijlocul tabloului are ca rezultat cel mai bun rezultat. 🙂

Sfarsit!

Până acum ar trebui să puteți înțelege logica din spatele algoritmului Minimax. Folosind această logică încercați să implementați singur un algoritm Minimax sau să găsiți exemplul de mai sus github sau codepen și optimizează-l.

Mulțumesc pentru lectură! Dacă ți-a plăcut această poveste, nu uita să o împărtășești pe social media.

Mulțumiri speciale lui Tuba Yilmaz, Rick McGavin și Javid Askerov pentru revizuirea acestui articol.