Kako učiniti svoju igru ​​Tic Tac Toe nenadmašnom pomoću minimax algoritma

Satima sam se mučio listajući tutorijale, gledajući videozapise i udarajući glavom o stol pokušavajući izgraditi nenadmašnu igru ​​Tic Tac Toe s pouzdanom umjetnom inteligencijom. Dakle, ako prolazite kroz slično putovanje, želio bih vas upoznati s Minimax algoritmom.

Poput profesionalnog šahista, ovaj algoritam vidi nekoliko koraka unaprijed i stavlja se na mjesto svog protivnika. Nastavlja igrati dok ne postigne terminalni raspored ploče ( stanje terminala ) što rezultira neriješenim rezultatom, pobjedom ili porazom. Jednom u terminalnom stanju, AI će dodijeliti proizvoljan pozitivan rezultat (+10) za pobjedu, negativan rezultat (-10) za poraz ili neutralni rezultat (0) za izjednačenje.

Istodobno, algoritam procjenjuje poteze koji vode u terminalno stanje na temelju okreta igrača. Odabrat će potez s maksimalnim brojem bodova kada je red na AI, a potez s minimalnim rezultatom kada je red na ljudskog igrača. Koristeći ovu strategiju, Minimax izbjegava izgubiti od ljudskog igrača.

Isprobajte sami u sljedećoj igri, po mogućnosti pomoću preglednika Chrom.

Minimax algoritam može se najbolje definirati kao rekurzivna funkcija koja čini sljedeće stvari:

  1. vrati vrijednost ako je pronađeno stanje terminala (+10, 0, -10)
  2. prođite kroz dostupna mjesta na ploči
  3. pozvati funkciju minimax na svakom dostupnom mjestu (rekurzija)
  4. procijeniti povratne vrijednosti iz poziva funkcije
  5. i vratiti najbolju vrijednost

Ako ste novi u konceptu rekurzije, preporučujem da pogledate ovaj video s Harvardovog CS50.

Da bismo u potpunosti shvatili proces razmišljanja Minimaxa, primijenimo ga u kodu i u akcijama ga pogledajte u sljedeća dva odjeljka.

Minimax u kodu

Za ovaj tutorial radit ćete na skoro završenom stanju igre koje je prikazano na slici 2 dolje. Budući da minimax procjenjuje svako stanje igre (stotine tisuća), blisko završno stanje omogućuje vam lakše praćenje minimaxovih rekurzivnih poziva (9).

Za sljedeću sliku pretpostavimo da je AI X, a ljudski igrač O.

Za lakši rad s pločicom Ti Tac Toe trebali biste je definirati kao niz s 9 predmeta. Svaka stavka imat će svoj indeks kao vrijednost. Ovo će vam dobro doći kasnije. Budući da je gornja ploča već popunjena s nekim potezima X i Y, definirajmo ploču s X i Y potezima koji su već u njoj ( origBoard ).

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

Zatim deklarirajte aiPlayer i huPlayer varijable i postavite ih na "X" odnosno "O" .

Uz to, trebate funkciju koja traži dobitne kombinacije i vraća true ako je pronađe, te funkciju koja navodi indekse dostupnih mjesta na ploči.

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

Sada zaronimo u dobre dijelove definiranjem funkcije Minimax s dva argumenta newBoard i player . Zatim trebate pronaći indekse dostupnih mjesta na ploči i postaviti ih na varijablu koja se naziva availSpots .

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

Također, trebate provjeriti stanja terminala i u skladu s tim vratiti vrijednost. Ako O pobjedi trebali biste vratiti -10, ako X pobijedi trebali biste vratiti +10. Osim toga, ako je duljina polja availableSpots jednaka nuli, to znači da više nema mjesta za igru, igra je rezultirala neriješenim rezultatom i trebali biste vratiti nulu.

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

Dalje, morate prikupiti bodove sa svakog praznog mjesta da biste ih kasnije procijenili. Stoga napravite niz koji se zove potezi i petljajte kroz prazna mjesta dok prikupljate indeks i rezultat svakog poteza u objektu koji se zove potez .

Zatim postavite indeksni broj praznog mjesta koje je pohranjeno kao broj u origBoardu na svojstvo indeksa objekta premještanja . Kasnije, prazno mjesto na novoj ploči postavite na trenutni igrač i pozovite minimax funkciju s drugim igračem i novo promijenjenom novom pločom . Zatim, trebate spremiti objekt nije proizašla iz Minimax poziva funkcije koja uključuje rezultat imovine na rezultat imovine potez objekta.

Ako funkcija minimax ne pronađe terminalno stanje, ona nastavlja rekurzivno ići nivo po nivo dublje u igru. Ta se rekurzija događa sve dok ne dosegne terminalno stanje i vrati rezultat jedan nivo više.

Konačno, Minimax resetira newBoard na ono što je bilo prije i gura potez objekt na poteze polje.

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

Zatim, algoritam minimax treba procijeniti najbolji potez u nizu poteza . Treba odabrati potez s najvećom ocjenom kada igra AI i potez s najnižom ocjenom kada čovjek igra. Dakle, ako je igrač je aiPlayer , postavlja varijablu nazvanu bestScore na vrlo malom broju i petlje kroz poteze polje, ako je potez ima višu ocjenu nego bestScore , algoritam trgovinama koje potez . U slučaju da postoje potezi sa sličnim rezultatom, pohranit će se samo prvi.

Isti postupak evaluacije događa kada igrač je huPlayer , ali ovaj put bestScore će biti postavljena na veći broj, i Minimax traži potez s najmanjim brojem bodova u trgovini.

Na kraju, Minimax vraća objekt pohranjen u 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  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]; }
To je to za funkciju minimax. :) gornji algoritam možete pronaći na githubu i codepenu. Poigrajte se različitim pločama i provjerite rezultate na konzoli.

U sljedećem odjeljku idemo preko redaka koda da bismo bolje razumjeli kako se ponaša funkcija minimax s obzirom na ploču prikazanu na slici 2.

Minimax u akciji

Koristeći sljedeću sliku, slijedimo redom pozive funkcija algoritma ( FC ).

Napomena: Na slici 3, veliki brojevi predstavljaju svaki poziv funkcije, a razine se odnose na to koliko koraka ispred igre algoritam igra.

1. origBoard i aiPlayer napajaju se algoritmom. Algoritam izrađuje popis tri prazna mjesta koja pronalazi, provjerava stanja terminala i pregledava svako prazno mjesto počevši od prvog. Zatim mijenja novu ploču postavljanjem aiPlayer- a na prvo prazno mjesto.Nakon toga,poziva se s newBoard i huPlayer i čeka da FC vrati vrijednost.

2. Dok je prvi FC još uvijek aktivan, drugi započinje sastavljanjem popisa dva prazna mjesta koja pronalazi, provjerava stanja terminala i petlja kroz prazno mjesto počevši od prvog. Zatim mijenja novu ploču postavljanjem huPlayer na prvo prazno mjesto.Nakon togapoziva sebe s newBoard i aiPlayer i čeka da FC vrati vrijednost.

3. Napokon algoritam pravi popis praznih mjesta i pronalazi dobitak za ljudskog igrača nakon provjere stanja terminala. Stoga vraća objekt sa svojstvom ocjene i vrijednošću -10.

Budući da je drugi FC naveo dva prazna mjesta, Minimax mijenja novu ploču postavljanjem huPlayer na drugo prazno mjesto. Zatim se sam poziva s novom pločom i aiPlayerom .

4. Algoritam pravi popis praznih mjesta i pronalazi dobitak za ljudskog igrača nakon provjere stanja terminala. Stoga vraća objekt sa svojstvom ocjene i vrijednošću -10.

Na drugom FC algoritam prikuplja vrijednosti koje dolaze s nižih razina (3. i 4. FC). Budući da je red huPlayera rezultirao dvjema vrijednostima, algoritam odabire najnižu od dvije vrijednosti. Budući da su obje vrijednosti slične, odabire prvu i vraća je na prvu FC. U ovom je trenutku prvi FC procijenio rezultat pomicanja aiPlayer- a na prvom praznom mjestu. Dalje, mijenja novu ploču postavljanjem aiPlayer na drugo prazno mjesto. Zatim se sam poziva s newBoard i huPlayer .

5. Na petom FC-u, algoritam pravi popis praznih mjesta i pronalazi dobitak za ljudskog igrača nakon provjere stanja terminala. Stoga vraća objekt sa svojstvom ocjene i vrijednošću +10.

Nakon toga, prvi FC kreće promjenom nove ploče i postavljanjem aiPlayer- a na treće prazno mjesto. Zatim se sam poziva novom pločom i huPlayerom .

6. 6. FC započinje sastavljanjem popisa dva prazna mjesta koja pronalazi, provjerava stanja terminala i pregledava dva prazna mjesta počevši od prvog. Zatim mijenja novu ploču postavljanjem huPlayer na prvo prazno mjesto.Nakon toga,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,algoritam pravi prazan popis praznih mjesta i pronalazi dobitak za aiPlayer nakon provjere stanja terminala. Stoga vraća objekt sa svojstvom rezultata i vrijednošću od +10 za jedan nivo više (7. FC).

7. FC dobio je samo jednu pozitivnu vrijednost s nižih razina (8. FC). Budući da je okretanje aiPlayera rezultiralo tom vrijednošću, algoritam mora vratiti najveću vrijednost koju je primio s nižih razina. Stoga vraća svoju jedinu pozitivnu vrijednost (+10) za jednu razinu više (6. FC). Budući da je 6. FC ispisao dva prazna mjesta, Minimax mijenja novu ploču postavljanjem huPlayer na drugo prazno mjesto. Zatim se poziva s novom pločom i aiPlayerom .

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.

U ovom trenutku, 6 FC mora birati između rezultata (+10) koji je poslan sa 7. FC (vraćen izvorno iz 8 FC) i rezultata (-10) koji je vraćen iz 9. FC. Budući da je zaokret huPlayer rezultirao s te dvije vraćene vrijednosti, algoritam pronalazi minimalni rezultat (-10) i vraća ga prema gore kao objekt koji sadrži svojstva rezultata i indeksa. Konačno, procijenjene su sve tri grane prvog FC (-10, +10, -10). No budući da je red aiPlayera rezultirao tim vrijednostima, algoritam vraća objekt koji sadrži najvišu ocjenu (+10) i njegov indeks (4).

U gornjem scenariju, Minimax zaključuje da pomicanje X na sredinu ploče rezultira najboljim ishodom. :)

Kraj!

By now you should be able to understand the logic behind the Minimax algorithm. Using this logic try to implement a Minimax algorithm yourself or find the above sample ongithub or codepen and optimize it.

Thanks for reading! If you liked this story, don't forget to share it on social media.

Special thanks to Tuba Yilmaz, Rick McGavin, and Javid Askerovfor reviewing this article.