Hogyan lehet a Tic Tac Toe játékot verhetetlenné tenni a minimumx algoritmus használatával

Órákig kínlódtam, miközben végigpásztáztam az oktatóanyagokat, videókat néztem, és fejemet az asztalra vertem, és megpróbáltam egy verhetetlen Tic Tac Toe játékot építeni, megbízható mesterséges intelligenciával. Tehát, ha hasonló utat él meg, akkor szeretném megismertetni a Minimax algoritmussal.

Mint egy profi sakkozó, ez az algoritmus is lát néhány lépést előre, és az ellenfél cipőjébe helyezi magát. Addig játszik előre, amíg el nem éri a tábla terminálelrendezését ( terminálállapot ), ami döntetlent, győzelmet vagy veszteséget eredményez. Végső állapotba kerülve az AI tetszőleges pozitív pontszámot (+10) rendel egy győzelemhez, negatív pontszámot (-10) veszteséghez vagy semleges pontszámot (0) a döntetlenhez.

Ugyanakkor az algoritmus a játékosok fordulata alapján értékeli azokat a mozdulatokat, amelyek végállapothoz vezetnek. Kiválasztja a maximális pontszámmal járó lépést, amikor az AI-n a sor, és a legkevesebb ponttal rendelkező lépést választja, amikor az emberi játékoson a sor. Ezt a stratégiát alkalmazva a Minimax elkerüli az emberi játékos veszteségét.

Próbálja ki magának a következő játékban, lehetőleg Chrom böngészővel.

A Minimax algoritmus rekurzív függvényként határozható meg legjobban, amely a következő dolgokat hajtja végre:

  1. adjon vissza egy értéket, ha terminálállapotot találunk (+10, 0, -10)
  2. végigmenni a táblán elérhető helyeken
  3. hívja meg a minimx függvényt minden elérhető helyen (rekurzió)
  4. értékelje a függvényhívásokból származó visszatérő értékeket
  5. és adja vissza a legjobb értéket

Ha még nem ismeri a rekurzió fogalmát, javasoljuk, hogy nézze meg ezt a videót a Harvard CS50-jéből.

A Minimax gondolkodási folyamatának teljes megértése érdekében valósítsuk meg kódban, és lássuk működés közben a következő két szakaszban.

Minimax a kódban

Ehhez az oktatóanyaghoz a játék közeli végállapotán fog dolgozni, amely az alábbi 2. ábrán látható. Mivel a minimumx kiértékeli a játék minden állapotát (százezrek), a közeli végállapot lehetővé teszi, hogy könnyebben kövesse nyomon a minimx rekurzív hívásait (9).

A következő ábra esetében tegyük fel, hogy az AI X, az emberi játékos pedig O.

Ahhoz, hogy a Ti Tac Toe táblával könnyebben dolgozzon, meg kell határoznia, hogy egy tömb 9 elemből áll. Minden elemnek értéke lesz az indexe. Ez később hasznos lesz. Mivel a fenti tábla már be van töltve néhány X és Y mozdulattal, definiáljuk a táblát az X és Y mozdulatokkal már benne ( origBoard ).

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

Ezután deklarálja az aiPlayer és a huPlayer változókat, és állítsa őket „X”, illetve „O” értékre .

Szüksége van továbbá egy függvényre, amely megkeresi a nyerő kombinációkat és igaz, ha talál ilyet, valamint egy olyan funkcióra, amely felsorolja a tábla elérhető helyeinek indexeit.

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

Merüljünk bele a jó részekbe úgy, hogy meghatározzuk a Minimax függvényt két argumentummal: newBoard és player . Ezután meg kell találnia az elérhető helyek indexeit a táblán, és be kell állítania őket az availSpots nevű változóba .

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

Ezenkívül ellenőriznie kell a terminál állapotát, és ennek megfelelően vissza kell adnia egy értéket. Ha O nyer, akkor vissza kell adnia -10, ha X nyer, akkor vissza kell térnie +10. Ezenkívül, ha az availableSpots tömb hossza nulla, ez azt jelenti, hogy nincs több hely a játékra, a játék döntetlent eredményezett, és vissza kell adnia a nullát.

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

Ezután össze kell gyűjtenie a pontszámokat az egyes üres helyekről, hogy később értékelje őket. Ezért készítsen egy mozdulatoknak nevezett tömböt, és haladjon az üres foltok között, miközben összegyűjti az egyes mozdulatok indexét és pontszámát a mozgás nevű objektumban .

Ezután állítsa be az origBoardban számként tárolt üres hely indexszámát a mozgatás objektum index tulajdonságához . Később, az üres helyet a newboard a jelenlegi játékos, és hívja a minimax funkciót másik játékos, és az újonnan megváltozott newboard . Ezután kell az objektum tárolására eredő minimax függvényhívás, amely magában foglalja a pontszám tulajdonság a pontszám tulajdona mozog objektumot.

Ha a minimumx függvény nem talál terminális állapotot, akkor rekurzívan halad szintről szintre a játék mélyén. Ez a rekurzió addig történik, amíg el nem éri a végállapotot, és egy szinttel feljebb egy pontszámot ad vissza.

Végül a Minimax visszaállítja a newBoardot arra, ami korábban volt, és a move objektumot a move tömbhöz tolja .

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

Ezután a minimax algoritmus azt kell értékelni, hogy a legjobb lépés a mozog tömbben. Meg kell választania a legmagasabb pontszámot tartalmazó lépést , amikor AI játszik, és azt a lépést , amelyik a legalacsonyabb pontszámú, amikor az ember játszik. Ezért, ha a játékos nem aiPlayer , ez határozza meg a változó nevű bestScore nagyon alacsony száma és hurkok a mozog tömb, ha a lépés magasabb pontszámot , mint bestScore , az algoritmus áruházak mozog . Abban az esetben, ha vannak hasonló pontszámú mozdulatok, csak az elsőt tároljuk.

Ugyanez történik, ha értékelési folyamat játékos van huPlayer , de ezúttal bestScore lenne beállítva nagy számú és Minimax néz ki a lépés a legalacsonyabb pontszámot tárolni.

A végén a Minimax visszaadja a bestMove-ban tárolt objektumot .

// 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]; }
Ez a minimumx függvény. :) a fenti algoritmus megtalálható a githubon és a codepenen. Játsszon különböző táblákkal, és ellenőrizze az eredményeket a konzolon.

A következő részben menjünk át soronként a kódokon, hogy jobban megértsük, hogyan viselkedik a minimumx függvény a 2. ábrán látható tábla alapján.

Minimax akcióban

A következő ábra segítségével kövessük egyenként az algoritmus függvényhívásait ( FC ).

Megjegyzés: A 3. ábrán nagy számok jelzik az egyes függvényhívásokat, a szintek pedig azt jelzik, hogy az algoritmus a játék előtt hány lépéssel játszik.

1. Az origBoard és az aiPlayer betáplálása az algoritmusba. Az algoritmus felsorolja a megtalált három üres helyet, ellenőrzi a terminálállapotokat, és az elsőtől kezdve körbevezet minden üres helyet. Ezután megváltoztatja az új táblát azáltal, hogy az aiPlayer- t az első üres helyrehelyezi.Azután,hívja magát az newBoard és a huPlayer segítségével, és várja, hogy az FC visszaadjon egy értéket.

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.

Mivel a második FC két üres helyet sorolt ​​fel, a Minimax megváltoztatja az új táblát úgy, hogy a huPlayer- t a második üres helyre helyezi . Ezután felhívja magát az új táblával és az aiPlayerrel .

4. Az algoritmus felsorolja az üres helyeket, és a terminál állapotának ellenőrzése után nyerést talál az emberi játékos számára. Ezért egy olyan objektumot ad vissza, amelynek pontszámtulajdonsága és értéke -10.

A második FC-n az algoritmus összegyűjti az alacsonyabb szintekről érkező értékeket (3. és 4. FC). Mivel a huPlayer fordulata eredményezte a két értéket, az algoritmus a két érték közül a legkisebbet választja. Mivel mindkét érték hasonló, az elsőt választja, és visszaadja az első FC-nek. Ezen a ponton az első FC értékelte az aiPlayer mozgatásának eredményét az első üres helyen. Ezután megváltoztatja az newBoardot azáltal, hogy az aiPlayert a második üres helyre helyezi . Ezután hívja magát az newBoard és a huPlayer használatával .

5. Az ötödik FC-n az algoritmus felsorolja az üres helyeket, és a terminál állapotának ellenőrzése után nyerést talál az emberi játékos számára. Ezért egy olyan objektumot ad vissza, amelynek ponttulajdonsága és értéke +10.

Ezt követően az első FC tovább lép az új tábla megváltoztatásával és az aiPlayert a harmadik üres helyre helyezve . Ezután felhívja magát az új táblával és a huPlayerrel .

6. A 6. FC azzal kezdi, hogy összeállít egy listát két megtalált üres helyről, ellenőrzi a végállapotokat, és az elsőtől kezdve körbevezeti a két üres helyet. Ezután megváltoztatja az újTáblát azáltal, hogy a huPlayert az első üres helyre helyezi .Azután,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,az algoritmus üres listákat készít az üres helyekről, és a terminál állapotának ellenőrzése után nyerést talál az aiPlayer számára. Ezért egy olyan objektumot ad vissza, amelynek pontszámtulajdonsága és értéke +10 egy szinttel feljebb (7. FC).

A 7. FC csak egy pozitív értéket kapott az alacsonyabb szintekről (8. FC). Mivel az aiPlayer sorozata ezt az értéket eredményezte, az algoritmusnak vissza kell adnia a legmagasabb értéket, amelyet az alacsonyabb szintekről kapott. Ezért egyetlen szinttel feljebb adja az egyetlen pozitív értékét (+10) (6. FC). Mivel a 6. FC két üres helyet sorolt ​​fel, a Minimax úgy változtatja meg az új táblát , hogy a huPlayert a második üres helyre helyezi . Ezután felhívja magát az új táblával és az aiPlayerrel .

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.

Ezen a ponton a 6 FC-nek választania kell a 7. FC-ből küldött pontszám (+10) (eredetileg a 8 FC-ről érkezett) és a 9. FC-től kapott pontszám (-10) között. Mivel a huPlayer sora eredményezte ezt a két visszaadott értéket, az algoritmus megtalálja a minimális pontszámot (-10), és felfelé adja vissza pontszámot és index tulajdonságokat tartalmazó objektumként. Végül az első FC mindhárom ágát kiértékeltük (-10, +10, -10). De mivel az aiPlayer fordulata eredményezte ezeket az értékeket, az algoritmus egy olyan objektumot ad vissza, amely a legmagasabb pontszámot (+10) és annak indexét (4) tartalmazza.

A fenti forgatókönyv szerint a Minimax arra a következtetésre jut, hogy az X mozgatása a tábla közepére a legjobb eredményt eredményezi. :)

Vége!

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.