Kuidas muuta oma Tic Tac Toe mäng ületamatuks, kasutades minimx-algoritmi

Ma nägin mitu tundi vaeva, sirvides õpetusi, vaadates videoid ja põrutades oma pead lauale, üritades ehitada usaldusväärse tehisintellektiga ületamatut mängu Tic Tac Toe. Nii et kui teete sarnast teekonda, siis tutvustaksin teile Minimaxi algoritmi.

Nagu professionaalne maletaja, näeb ka see algoritm paar sammu edasi ja seab end vastase kingadesse. Mängib edasi, kuni jõuab laua terminali paigutusse ( terminali olek ), mille tulemuseks on viik, võit või kaotus. Lõplikus olekus määrab tehisintellekt meelevaldse positiivse skoori (+10) võidu, negatiivse (-10) kaotuse või neutraalse skoori (0) viigi korral.

Samal ajal hindab algoritm mängijate käigu põhjal käike, mis viivad terminali olekusse. See valib maksimaalse punktisummaga käigu, kui on tehisintellekti kord, ja valib minimaalse punktisummaga käigu, kui on inimmängija kord. Seda strateegiat kasutades väldib Minimax inimmängijale kaotamist.

Proovige seda järgmises mängus ise, eelistatavalt Chromi brauseri abil.

Minimaxi algoritmi saab kõige paremini määratleda rekursiivse funktsioonina, mis teeb järgmisi asju:

  1. tagastab väärtuse, kui leitakse terminali olek (+10, 0, -10)
  2. läbima tahvlil olevad laigud
  3. helistada minimaalsele funktsioonile igas saadaolevas kohas (rekursioon)
  4. hinnata funktsioonikutsete tagasiväärtusi
  5. ja tagastab parima hinna

Kui rekursiooni mõiste on teie jaoks uus, soovitan seda videot vaadata Harvardi CS50-st.

Minimaxi mõtteprotsessi täielikuks mõistmiseks rakendame selle koodis ja näeme seda järgmises kahes osas.

Minimax koodis

Selle õpetuse jaoks töötate mängu lähedal oleva lõppseisundiga, mis on näidatud allpool joonisel 2. Kuna minimax hindab kõiki mänguseisundeid (sadu tuhandeid), võimaldab lähedane lõpp-olek teil minimaxi rekursiivsete kõnedega hõlpsamalt reageerida (9).

Järgmise joonise jaoks oletame, et tehisintellekt on X ja inimmängija on O.

Ti Tac Toe tahvliga hõlpsamaks töötamiseks peaksite määratlema selle kui 9 üksusega massiivi. Igal üksusel on väärtuseks indeks. See tuleb hiljem kasuks. Kuna ülaltoodud tahvel on juba asustatud mõningate X- ja Y-liigutustega, määratlegem tahvel, kus X ja Y liiguvad juba ( origBoard ).

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

Seejärel deklareerige muutujad aiPlayer ja huPlayer ning määrake neile vastavalt “X” ja “O” .

Lisaks vajate funktsiooni, mis otsib võidukombinatsioone ja tagastab tõese, kui see leitakse, ning funktsiooni, mis loetleb tahvlil saadaolevate kohtade indeksid.

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

Sukeldume nüüd headesse osadesse, määratledes funktsiooni Minimax kahe argumendiga newBoard ja player . Seejärel peate leidma tahvlilt saadaolevate kohtade indeksid ja määrama need muutujaks nimega availSpots .

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

Samuti peate kontrollima terminali olekuid ja vastava väärtuse tagastama. Kui O võidab, peaksite tagastama -10, kui X võidab, peaksite tagastama +10. Lisaks, kui saadaval oleva massiivi pikkus on null, tähendab see, et mängimiseks pole enam ruumi, mäng on viigistanud ja peaksite tagastama nulli.

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

Järgmisena peate hilisemaks hindamiseks koguma hinded kõigist tühjadest kohtadest. Seepärast tehke massiivi nimega käigud ja tehke tühjad kohad läbi, kogudes iga käigu indeksit ja skoori objektiks, mida nimetatakse käiguks .

Seejärel seadke indeksinumbrit tühja, mis oli salvestatud numbriga origBoard indeksi vara liikuda objekti. Hiljem määrake uue laua tühi koht praegusele mängijale ja kutsuge minimax funktsioon koos teise mängijaga ja äsja muudetud uus tahvel . Järgmisena peaksite salvestama funktsiooni minimx kutsest saadud objekti, mis sisaldab skoori omadust liikuva objekti skoori omadusele .

Kui minimax-funktsioon ei leia terminali olekut, jätkub see rekursiivselt taseme kaupa mängu sügavamal. See rekursioon toimub seni, kuni see jõuab lõppseisundisse ja annab tulemuse ühe taseme võrra kõrgemale.

Lõpuks Minimax taastab newBoard et mis see oli enne ja lükkab liikuda objekti liigub massiiv.

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

Seejärel Minimax algoritm peab hindama parim liikuda ka liigub massiiv. Tuleb valida liikuda kõrgeima punktisumma, kui AI mängib ja liikuda madalaima punktisumma kui inimese mängib. Seega, kui mängija on aiPlayer , seab see muutuja nimega bestScore väga madalale arvule ja viib liikumiste massiivi läbi , kui käigul on parem tulemus kui bestScoreil , salvestab algoritm selle liikumise . Juhul, kui leidub sarnase punktisummaga käike, salvestatakse ainult esimene.

The same evaluation process happens when player is huPlayer, but this time bestScore would be set to a high number and Minimax looks for a move with the lowest score to store.

At the end, Minimax returns the object stored in 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]; }
That is it for the minimax function. :) you can find the above algorithm on github and codepen. Play around with different boards and check the results in the console.

In the next section, let’s go over the code line by line to better understand how the minimax function behaves given the board shown in figure 2.

Minimax in action

Using the following figure, let’s follow the algorithm’s function calls (FC) one by one.

Note: In figure 3, large numbers represent each function call and levels refer to how many steps ahead of the game the algorithm is playing.

1.origBoard and aiPlayer is fed to the algorithm. The algorithm makes a list of the three empty spots it finds, checks for terminal states, and loops through every empty spot starting from the first one. Then, it changes the newBoard by placing the aiPlayer in the first empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a value.

2. While the first FC is still running, the second one starts by making a list of the two empty spots it finds, checks for terminal states, and loops through the empty spot starting from the first one. Then, it changes the newBoard by placing the huPlayer in the first empty spot.After thatit calls itself with newBoard and the aiPlayer and waits for the FC to return a value.

3. Finally the algorithm makes a list of the empty spots, and finds a win for the human player after checking for terminal states. Therefore, it returns an object with a score property and value of -10.

Kuna teine ​​FC loetles kaks tühja kohta, muudab Minimax uue laua , asetades huPlayer teise tühja kohta. Seejärel kutsub ta ennast koos uue tahvli ja aiPlayeriga .

4. Algoritm koostab tühjade kohtade loendi ja leiab pärast terminali olekute kontrollimist inimmängijale võidu. Seetõttu tagastab ta objekti, mille punktisumma on omadus ja väärtus -10.

Teisel FC-l kogub algoritm madalamatelt tasemetelt (3. ja 4. FC) tulevad väärtused. Kuna huPlayeri kord andis kaks väärtust, valib algoritm kahest väärtusest madalaima. Kuna mõlemad väärtused on sarnased, valib ta esimese ja tagastab selle esimesele FC-le. Siinkohal on esimene FC hinnanud aiPlayeri liikumise skoori esimeses tühjas kohas. Järgmisena muudab see uut tahvlit , asetades aiPlayer teise tühja kohta. Seejärel kutsub see end koos newBoardi ja huPlayeriga .

5. Viiendal FC-l koostab algoritm tühjade kohtade loendi ja leiab pärast lõppseisundite kontrollimist inimmängijale võidu. Seetõttu tagastab objekti skooromaduse ja väärtusega +10.

Pärast seda liigub esimene FC, vahetades uue Boardi ja asetades aiPlayer kolmandasse tühja kohta. Seejärel kutsub ta ennast koos uue tahvli ja huPlayeriga .

6. Kuues FC alustab loendi koostamisest kahest leitud tühjast kohast, kontrollib terminali olekuid ja viib läbi kahe tühja koha, alustades esimesest. Seejärel muudab see uut tahvlit , asetades huPlayeri esimesse tühja kohta.Pärast seda,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,algoritm koostab tühjade kohtade tühja loendi ja leiab aiPlayerile võidu pärast terminalide olekute kontrollimist. Seetõttu tagastab see objekti, mille punktisumma omadus ja väärtus on +10 ühe taseme võrra kõrgemal (7. FC).

7. FC sai madalamatelt tasemetelt ainult ühe positiivse väärtuse (8. FC). Kuna aiPlayeri kord andis selle väärtuse, peab algoritm tagastama kõrgeima väärtuse, mille ta on madalamatelt tasemetelt saanud. Seetõttu tagastab see oma ainsa positiivse väärtuse (+10) ühe taseme võrra kõrgemale (6. FC). Kuna 6. FC loetles kaks tühja kohta, muudab Minimax uut lauda , asetades huPlayer teise tühja kohta. Seejärel kutsub end uue tahvli ja aiPlayeriga .

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.

Siinkohal peab 6 FC valima 7. FC-st üles saadetud (algselt 8-lt FC-lt tagasi saadetud) ja 9. FC-lt tagastatud tulemuse (-10) vahel. Kuna huPlayeri kord andis tulemuseks need kaks tagastatud väärtust, leiab algoritm minimaalse punktisumma (-10) ja tagastab selle ülespoole skoori ja indeksi omadusi sisaldava objektina. Lõpuks on hinnatud esimese FC kõik kolm haru (-10, +10, -10). Kuid kuna aiPlayeri käigust saadi need väärtused, tagastab algoritm objekti, mis sisaldab kõige rohkem punkte (+10) ja selle indeksit (4).

Ülaltoodud stsenaariumi korral järeldab Minimax, et X nihutamine tahvli keskele annab parima tulemuse. :)

Lõpp!

Nüüdseks peaksite saama aru Minimaxi algoritmi taga olevast loogikast. Selle loogika abil proovige ise Minimaxi algoritmi rakendada või leidke ülaltoodud näidisgithub või codepen ja optimeerida seda.

Täname lugemast! Kui teile see lugu meeldis, ärge unustage seda sotsiaalmeedias jagada.

Eriline tänu Tuba Yilmazile, Rick McGavinile ja Javid Askerovile selle artikli ülevaatamise eest.