Kā padarīt Tic Tac Toe spēli par nepārspējamu, izmantojot minimx algoritmu

Es stundām ilgi pūlējos, ritinot mācību materiālus, skatoties videoklipus un dauzot galvu uz rakstāmgalda, mēģinot uzbūvēt nepārspējamu Tic Tac Toe spēli ar uzticamu mākslīgo intelektu. Tāpēc, ja jūs iziet līdzīgu ceļojumu, es vēlētos jūs iepazīstināt ar Minimax algoritmu.

Tāpat kā profesionāls šahists, arī šis algoritms redz dažus soļus uz priekšu un nostājas pretinieka ādā. Tas turpina spēlēt uz priekšu, līdz tas sasniedz dēļa gala izkārtojumu ( termināla stāvokli ), kā rezultātā ir neizšķirts, uzvarēts vai zaudēts. Nonākot gala stāvoklī, AI piešķirs patvaļīgu pozitīvu rezultātu (+10) uzvarai, negatīvu punktu skaitu (-10) zaudējumiem vai neitrālu punktu skaitu (0) neizšķirta rezultāta gadījumā.

Tajā pašā laikā algoritms, pamatojoties uz spēlētāju pagriezienu, novērtē kustības, kas noved pie gala stāvokļa. Tas izvēlēsies gājienu ar maksimālo punktu skaitu, kad būs AI kārta, un izvēlēsies gājienu ar minimālo punktu skaitu, kad tā būs cilvēka spēlētāja kārta. Izmantojot šo stratēģiju, Minimax izvairās zaudēt cilvēku spēlētājam.

Izmēģiniet to pats nākamajā spēlē, vēlams, izmantojot Chrom pārlūku.

Minimax algoritmu vislabāk var definēt kā rekursīvu funkciju, kas veic šādas darbības:

  1. atgriež vērtību, ja tiek atrasts gala stāvoklis (+10, 0, -10)
  2. iziet uz kuģa pieejamās vietas
  3. izsaukt minimx funkciju katrā pieejamā vietā (rekursija)
  4. novērtēt atgriešanās vērtības no funkciju izsaukumiem
  5. un atgrieziet vislabāko vērtību

Ja rekursijas jēdziens jums ir jauns, iesaku noskatīties šo video no Hārvardas CS50.

Lai pilnībā izprastu Minimax domāšanas procesu, ieviesīsim to kodā un redzēsim to darbībā divās nākamajās sadaļās.

Minimālais kods

Šajā apmācībā jūs strādājat pie spēles gandrīz beigu stāvokļa, kas parādīts 2. attēlā. Tā kā minimx novērtē katru spēles stāvokli (simtiem tūkstošu), tuvu gala stāvoklis ļauj jums vieglāk sekot līdzi minimx rekurzīvajiem zvaniem (9).

Pieņemsim, ka šajā attēlā AI ir X un cilvēka spēlētājs ir O.

Lai vieglāk strādātu ar Ti Tac Toe dēli, tas jādefinē kā masīvs ar 9 vienumiem. Katra vienuma vērtība būs tā indekss. Tas noderēs vēlāk. Tā kā iepriekšējais dēlis jau ir apdzīvots ar dažiem X un Y gājieniem, definēsim dēli ar X un Y gājieniem jau tajā ( origBoard ).

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

Pēc tam paziņojiet mainīgos aiPlayer un huPlayer un iestatiet tos attiecīgi uz “X” un “O” .

Turklāt jums ir nepieciešama funkcija, kas meklē uzvarošās kombinācijas un atgriež patieso vērtību, ja tāda tiek atrasta, un funkcija, kurā uzskaitīti tāfelē pieejamo vietu rādītāji.

/* 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; } }

Tagad ienirsim labajās daļās, definējot funkciju Minimax ar diviem argumentiem newBoard un player . Pēc tam jums ir jāatrod tabulā pieejamo vietu rādītāji un jāiestata tie uz mainīgo, ko sauc par availSpots .

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

Jums arī jāpārbauda, ​​vai nav termināļu stāvokļu, un attiecīgi jāatgriež vērtība. Ja O uzvar, jums jāatgriežas -10, ja X uzvar, jāatgriež +10. Turklāt, ja pieejamāSpots masīva garums ir nulle, tas nozīmē, ka vairs nav vietas spēlēšanai, spēles rezultāts ir neizšķirts, un jums jāatgriež nulle.

 // 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}; }

Pēc tam jums jāapkopo rādītāji no visiem tukšajiem punktiem, lai tos novērtētu vēlāk. Tāpēc izveidojiet masīvu, ko sauc par kustībām, un veiciet cilpu pa tukšiem punktiem, vienlaikus vācot katra kustības indeksu un punktus objektā, ko sauc par kustību .

Pēc tam iestatiet tukšās vietas indeksa numuru, kas tika saglabāts kā skaitlis origBoard , pārvietotā objekta indeksa rekvizītam . Vēlāk, noteikt tukšā vietā uz newboard uz pašreizējo spēlētāju un izsaukt Minimax funkcija ar citu spēlētāju, un nesen mainīta newboard . Tālāk jums jāuzglabā objekts, kas izriet no minimx funkcijas izsaukuma, kurā iekļauts rādītāja rekvizīts līdz pārvietotā objekta punktu īpašībai .

Ja minimx funkcija neatrod gala stāvokli, tā turpina rekursīvi iet pa līmeni pa līmeni dziļāk spēlē. Šī rekursija notiek līdz brīdim, kad tā sasniedz terminālo stāvokli un atgriež rezultātu par vienu līmeni augstāk.

Visbeidzot, Minimax atiestata newBoard uz iepriekšējo un pārvieto objektu uz kustību masīvu.

// 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); }

Tad Minimax algoritms ir nepieciešams, lai novērtētu vislabāko pārvietoties šajā pārceļas masīvs. Tam vajadzētu izvēlēties kustību ar visaugstāko punktu skaitu, kad spēlē AI, un kustību ar zemāko punktu skaitu, kad spēlē cilvēks. Tādēļ, ja spēlētājs ir aiPlayer , tas iestata mainīgo lielumu bestScore uz ļoti mazu skaitli un veic kustību masīvu, ja kustībai ir augstāks rādītājs nekā bestScore , algoritms saglabā pārvietoto . Gadījumā, ja ir gājieni ar līdzīgu rezultātu, tiks saglabāts tikai pirmais.

Tas pats vērtēšanas process notiek arī tad, kad spēlētājs ir huPlayer , taču šoreiz bestScore būtu iestatīts uz lielu skaitu, un Minimax meklē kustību ar zemāko punktu skaitu, ko uzglabāt.

Beigās Minimax atgriež bestMove saglabāto objektu .

// 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  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]; }
Tas ir minimx funkcijai. :) Jūs varat atrast iepriekš minēto algoritmu par github un codepen. Spēlējiet ar dažādiem dēļiem un pārbaudiet rezultātus konsolē.

Nākamajā sadaļā ejam pa kodu pa rindām, lai labāk saprastu, kā darbojas minimx, ņemot vērā tāfelīti, kas parādīta 2. attēlā.

Minimax darbībā

Izmantojot šo attēlu, sekosim algoritma funkciju izsaukumiem ( FC ) pa vienam.

Piezīme: 3. attēlā lieli skaitļi apzīmē katru funkciju izsaukumu, un līmeņi norāda, cik soli pirms spēles algoritms spēlē.

1. algBoard un aiPlayer tiek ievadīti algoritmā. Algoritms izveido sarakstu ar trim atrastajiem tukšajiem punktiem, pārbauda gala stāvokļus un veic cilpu caur katru tukšo vietu, sākot no pirmā. Tad tas maina newBoard , ievietojot aiPlayer pirmajā tukšajā vietā.Pēc tam,tas sevi sauc ar newBoard un huPlayer un gaida, kamēr FC atgriezīs vērtību.

2. Kamēr pirmais FC joprojām darbojas, otrais sākas, izveidojot sarakstu ar diviem atrastajiem tukšajiem punktiem, pārbaudot gala stāvokļus un veicot tukšo vietu, sākot no pirmā. Tad tas maina newBoard , ievietojot huPlayer pirmajā tukšajā vietā.Pēc tamtas sevi sauc ar newBoard un aiPlayer un gaida, kamēr FC atgriezīs vērtību.

3. Visbeidzot, algoritms izveido tukšo vietu sarakstu un pēc termināļa stāvokļu pārbaudes atrod cilvēka spēlētāja uzvaru. Tāpēc tas atgriež objektu ar punktu īpašību un vērtību -10.

Tā kā otrajā FC uzskaitītas divas tukšas vietas, Minimax maina newBoard , ievietojot huPlayer otrajā tukšajā vietā. Tad tā sevi sauc ar jauno dēli un aiPlayer .

4. Algoritms izveido tukšo vietu sarakstu un pēc termināla stāvokļu pārbaudes atrod cilvēka spēlētāja uzvaru. Tāpēc tas atgriež objektu ar punktu īpašību un vērtību -10.

Otrajā FC algoritms apkopo vērtības, kas nāk no zemākiem līmeņiem (3. un 4. FC). Tā kā huPlayer kārta izraisīja abas vērtības, algoritms izvēlas zemāko no abām vērtībām. Tā kā abas vērtības ir līdzīgas, tā izvēlas pirmo un atdod to pirmajam FC. Šajā brīdī pirmais FC ir novērtējis aiPlayer pārvietošanās rezultātu pirmajā tukšajā vietā. Pēc tam tas maina newBoard , ievietojot aiPlayer otrajā tukšajā vietā. Tad tas sevi sauc ar newBoard un huPlayer .

5. Piektajā FC algoritms izveido tukšo vietu sarakstu un pēc termināla stāvokļu pārbaudes atrod cilvēka spēlētāja uzvaru. Tāpēc tas atgriež objektu ar rezultāta īpašību un vērtību +10.

Pēc tam pirmais FC dodas tālāk, mainot newBoard un ievietojot aiPlayer trešajā tukšajā vietā. Tad tas sevi sauc ar jauno dēli un huPlayer .

6. Sestais FC sākas ar sarakstu ar diviem atrastajiem tukšajiem punktiem, pārbaudot gala stāvokļus un veicot cilpu pa diviem tukšajiem punktiem, sākot no pirmā. Tad tas maina newBoard , ievietojot huPlayer pirmajā tukšajā vietā.Pēc tam,it calls itself with newBoard and the aiPlayer and waits for the FC to return a score.

7. Now the algorithm is two level deep into the recursion. It makes a list of the one empty spot it finds, checks for terminal states, and changes the newBoard by placing the aiPlayer in the empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a score so it can evaluate it.

8. On the 8th FC,algoritms izveido tukšu tukšo vietu sarakstu un pēc termināļu stāvokļu pārbaudes atrod aiPlayer uzvaru . Tāpēc tas atgriež objektu ar punktu īpašību un vērtību +10 vienu līmeni uz augšu (7. FC).

7. FC saņēma tikai vienu pozitīvu vērtību no zemākiem līmeņiem (8. FC). Tā kā aiPlayer pagrieziena rezultātā tika iegūta šī vērtība, algoritmam jāatgriež augstākā vērtība, ko tas ir saņēmis no zemākiem līmeņiem. Tāpēc tā atgriež vienīgo pozitīvo vērtību (+10) par vienu līmeni uz augšu (6. FC). Tā kā 6. FC uzskaitīja divas tukšas vietas, Minimax maina newBoard , ievietojot huPlayer otrajā tukšajā vietā. Tad zvana pati ar jauno dēli un aiPlayer .

9. Next, the algorithm makes a list of the empty spots, and finds a win for the aiPlayer after checking for terminal states. Therefore, it returns an object with score properties and value of +10.

Šajā brīdī 6 FC ir jāizvēlas starp rezultātu (+10), kas tika nosūtīts no 7. FC (sākotnēji atgriezās no 8 FC), un rezultātu (-10), kas atgriezās no 9. FC. Tā kā huPlayer kārta radīja šīs divas atgrieztās vērtības, algoritms atrod minimālo punktu skaitu (-10) un atgriež to uz augšu kā objektu, kas satur rādītāja un indeksa īpašības. Visbeidzot, ir novērtētas visas trīs pirmās FC filiāles (-10, +10, -10). Bet tā kā aiPlayer pagrieziena rezultātā tika iegūtas šīs vērtības, algoritms atgriež objektu, kas satur visaugstāko punktu skaitu (+10) un tā indeksu (4).

Iepriekšminētajā scenārijā Minimax secina, ka X pārvietošana uz dēļa vidusdaļu nodrošina labāko rezultātu. :)

Beigas!

Tagad jums jāspēj saprast Minimax algoritma loģiku. Izmantojot šo loģiku, mēģiniet pats ieviest Minimax algoritmu vai atrodiet iepriekš minēto paraugugithub vai codepen un to optimizēt.

Paldies, ka lasījāt! Ja jums patika šis stāsts, neaizmirstiet to kopīgot sociālajos tīklos.

Īpašs paldies Tubai Jilmazai, Rikam Makgavinam un Javidam Askerovam par šī raksta pārskatīšanu.