Sådan gør du dit Tic Tac Toe-spil uovertruffen ved hjælp af minimax-algoritmen

Jeg kæmpede i timevis med at rulle gennem tutorials, se videoer og banke mit hoved på skrivebordet for at prøve at opbygge et uovertruffen Tic Tac Toe-spil med en pålidelig kunstig intelligens. Så hvis du gennemgår en lignende rejse, vil jeg gerne introducere dig til Minimax-algoritmen.

Ligesom en professionel skakspiller ser denne algoritme et par skridt foran og sætter sig i skoene til sin modstander. Det fortsætter med at spille foran, indtil det når et terminalarrangement på brættet ( terminaltilstand ), hvilket resulterer i uafgjort, sejr eller tab. En gang i en terminal tilstand tildeler AI en vilkårlig positiv score (+10) for en sejr, en negativ score (-10) for et tab eller en neutral score (0) for uafgjort.

Samtidig evaluerer algoritmen de bevægelser, der fører til en terminaltilstand, baseret på spillerens tur. Det vælger træk med maksimal score, når det er AI's tur, og vælger træk med minimumscore, når det er den menneskelige spillers tur. Ved hjælp af denne strategi undgår Minimax at miste for den menneskelige spiller.

Prøv det selv i det følgende spil, helst ved hjælp af en Chrom-browser.

En Minimax-algoritme kan bedst defineres som en rekursiv funktion, der udfører følgende ting:

  1. returnere en værdi, hvis der findes en terminaltilstand (+10, 0, -10)
  2. gå gennem ledige pletter på tavlen
  3. ring til minimax-funktionen på hvert ledigt sted (rekursion)
  4. evaluere returnerende værdier fra funktionsopkald
  5. og returner den bedste værdi

Hvis du er ny med begrebet rekursion, anbefaler jeg at se denne video fra Harvards CS50.

For at forstå Minimax's tankeproces fuldstændigt, lad os implementere den i kode og se den i aktion i de følgende to sektioner.

Minimax i kode

Til denne vejledning arbejder du på en næsten sluttilstand for spillet, som er vist i figur 2 nedenfor. Da minimax evaluerer hver tilstand af spillet (hundreder af tusinder), giver en nær-ende tilstand dig mulighed for at følge op med minimax's rekursive opkald lettere (9).

For den følgende figur antages, at AI er X, og den menneskelige spiller er O.

For at arbejde med Ti Tac Toe-kortet lettere, skal du definere det som en matrix med 9 emner. Hver vare har sit indeks som en værdi. Dette vil komme praktisk senere. Da ovenstående bord allerede er befolket med nogle X- og Y-bevægelser, lad os definere brættet med X- og Y-bevægelserne allerede i det ( origBoard ).

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

Erklær derefter aiPlayer- og huPlayer- variabler, og indstil dem til henholdsvis “X” og “O” .

Derudover har du brug for en funktion, der ser efter vindende kombinationer og returnerer sand, hvis den finder en, og en funktion, der viser indekserne over tilgængelige pletter i tavlen.

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

Lad os nu dykke ned i de gode dele ved at definere Minimax-funktionen med to argumenter newBoard og player . Derefter skal du finde indekserne over de tilgængelige pletter i tavlen og indstille dem til en variabel kaldet availSpots .

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

Du skal også tjekke for terminaltilstande og returnere en værdi i overensstemmelse hermed. Hvis O vinder, skal du returnere -10, hvis X vinder, skal du returnere +10. Derudover, hvis længden af ​​den tilgængeligeSpots- array er nul, betyder det, at der ikke er mere plads til at spille, spillet har resulteret i uafgjort, og du skal returnere nul.

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

Dernæst skal du samle score fra hver af de tomme pletter for at evaluere senere. Lav derfor et array kaldet træk og løb gennem tomme pletter, mens du samler hvert træks indeks og scorer i et objekt kaldet træk .

Indstil derefter indeks nummeret på den tomme plet, der blev opbevaret som et nummer i origBoard til indekset ejendom flytte objektet. Senere skal du indstille det tomme sted på newboardet til den aktuelle afspiller og ringe til minimax- funktionen med en anden afspiller og det nyligt ændrede newboard . Dernæst bør du gemme objektet skyldes den minimax funktionskald, der omfatter en score ejendom til score ejendom flytte objektet.

Hvis minimax-funktionen ikke finder en terminaltilstand, fortsætter den rekursivt niveau for niveau dybere ind i spillet. Denne rekursion sker, indtil den når en terminal tilstand og returnerer en score et niveau op.

Endelig nulstiller Minimax newBoard til det, det var før, og skubber bevægelsesobjektet til moves- arrayet.

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

Derefter skal minimax-algoritmen evaluere det bedste træk i moves- arrayet. Det skal vælge det træk med den højeste score, når AI spiller, og træk med den laveste score, når mennesket spiller. Derfor, hvis spilleren er aiPlayer , indstiller den en variabel kaldet bestScore til et meget lavt tal og løber gennem moves- arrayet, hvis et træk har en højere score end bestScore , gemmer algoritmen den bevægelse . Hvis der er træk med lignende score, gemmes kun den første.

Den samme evalueringsproces sker, når spilleren er huPlayer , men denne gang vil bestScore blive sat til et højt tal, og Minimax ser efter et træk med den laveste score at gemme.

I slutningen returnerer Minimax det objekt, der er gemt i 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]; }
Det er det til minimax-funktionen. :) Du kan finde ovenstående algoritme på github og codepen. Spil rundt med forskellige brædder og kontroller resultaterne i konsollen.

I det næste afsnit, lad os gå over koden linje for linje for bedre at forstå, hvordan minimax-funktionen opfører sig i betragtning af kortet vist i figur 2.

Minimax i aktion

Brug følgende figur til at følge algoritmens funktionsopkald ( FC ) en efter en.

Bemærk: I figur 3 repræsenterer stort antal hvert funktionsopkald, og niveauer refererer til, hvor mange skridt foran spillet algoritmen spiller.

1. origBoard og aiPlayer tilføres algoritmen. Algoritmen opretter en liste over de tre tomme pletter, den finder, kontrollerer for terminaltilstande og sløjfer gennem hvert tomt sted startende fra det første. Derefter ændrer den den nye Board ved at placere aiPlayer på det første tomme sted.Efter det,det kalder sig selv med newBoard og huPlayer og venter på, at FC returnerer en værdi.

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.

Da den anden FC angav to tomme pletter, ændrer Minimax det nye Board ved at placere huPlayer på det andet tomme sted. Derefter kalder det sig selv med det nye bord og aiPlayer .

4. Algoritmen opretter en liste over de tomme pletter og finder en gevinst for den menneskelige spiller efter kontrol af terminaltilstande. Derfor returnerer det et objekt med en scoreegenskab og en værdi på -10.

På den anden FC samler algoritmen de værdier, der kommer fra lavere niveauer (3. og 4. FC). Da huPlayer 's tur resulterede i de to værdier, vælger algoritmen den laveste af de to værdier. Fordi begge værdier er ens, vælger den den første og returnerer den til den første FC. På dette tidspunkt har den første FC vurderet resultatet af at flytte aiPlayer til det første tomme sted. Dernæst ændrer det newBoard ved at placere aiPlayer på det andet tomme sted. Derefter kalder det sig selv med newBoard og huPlayer .

5. På den femte FC opretter algoritmen en liste over de tomme pletter og finder en gevinst for den menneskelige spiller efter kontrol af terminaltilstande. Derfor returnerer det et objekt med en scoreegenskab og en værdi på +10.

Derefter går den første FC videre ved at ændre det nye Board og placere aiPlayer på det tredje tomme sted. Derefter kalder det sig selv med det nye bord og huPlayer .

6. 6. FC starter med at oprette en liste over to tomme pletter, den finder, kontrollerer for terminaltilstande og sløjfer gennem de to tomme pletter startende fra den første. Derefter ændrer det newBoard ved at placere huPlayer på det første tomme sted.Efter det,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,algoritmen opretter en tom liste over tomme pletter og finder en gevinst for aiPlayer efter kontrol af terminaltilstande. Derfor returnerer det et objekt med scoreegenskab og værdi på +10 et niveau op (7. FC).

Den 7. FC modtog kun en positiv værdi fra lavere niveauer (8. FC). Da aiPlayer's tur resulterede i denne værdi, skal algoritmen returnere den højeste værdi, den har modtaget fra lavere niveauer. Derfor returnerer den sin eneste positive værdi (+10) et niveau op (6. FC). Da 6. FC opførte to tomme pletter, skifter Minimax newBoard ved at placere huPlayer på det andet tomme sted. Derefter kalder det sig med det nye tavle og 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.

På dette tidspunkt skal 6 FC vælge mellem den score (+10), der blev sendt op fra den 7. FC (returneret oprindeligt fra fra 8 FC), og resultatet (-10) returneret fra den 9. FC. Da huPlayer 's tur resulterede i disse to returnerede værdier, finder algoritmen minimumscore (-10) og returnerer den opad som et objekt, der indeholder score- og indeksegenskaber . Endelig er alle tre grene af den første FC blevet evalueret (-10, +10, -10). Men fordi aiPlayer's tur resulterede i disse værdier, returnerer algoritmen et objekt, der indeholder den højeste score (+10) og dets indeks (4).

I ovenstående scenarie konkluderer Minimax, at flytning af X til midten af ​​brættet resulterer i det bedste resultat. :)

Enden!

Nu skal du være i stand til at forstå logikken bag Minimax-algoritmen. Brug denne logik til at prøve at implementere en Minimax-algoritme selv eller find ovenstående prøve pågithub eller codepen og optimer det.

Tak for læsningen! Hvis du kunne lide denne historie, så glem ikke at dele den på sociale medier.

Særlig tak til Tuba Yilmaz, Rick McGavin og Javid Askerov for at have gennemgået denne artikel.