ミニマックスアルゴリズムを使用して、Tic TacToeゲームを無敵にする方法

チュートリアルをスクロールしたり、ビデオを見たり、机の上で頭を叩いたりして、信頼できる人工知能を備えた無敵のTic TacToeゲームを構築しようと何時間も苦労しました。したがって、同様の旅をしている場合は、ミニマックスアルゴリズムを紹介したいと思います。

プロチェスプレーヤーのように、このアルゴリズムは数歩先を見て、対戦相手の立場になります。ボードの端末配置(端末状態)に到達して同点、勝ち、または負けになるまで、先に進み続けます。最終状態になると、AIは勝ちに任意の正のスコア(+10)、負けに負のスコア(-10)、または引き分けにニュートラルスコア(0)を割り当てます。

同時に、アルゴリズムは、プレイヤーのターンに基づいて、終了状態につながる動きを評価します。AIの番になるとスコアが最大の手が選ばれ、人間の番になるとスコアが最小の手が選ばれます。この戦略を使用して、ミニマックスは人間のプレイヤーに負けることを回避します。

できればChromブラウザを使用して、次のゲームで試してみてください。

ミニマックスアルゴリズムは、次のことを行う再帰関数として最もよく定義できます。

  1. 最終状態が見つかった場合は値を返します(+ 10、0、-10)
  2. ボード上の利用可能なスポットを通過します
  3. 利用可能な各スポットでミニマックス関数を呼び出す(再帰)
  4. 関数呼び出しからの戻り値を評価する
  5. 最高の値を返します

再帰の概念に慣れていない場合は、ハーバードのCS50からこのビデオを視聴することをお勧めします。

ミニマックスの思考プロセスを完全に理解するために、それをコードで実装し、次の2つのセクションで実際に動作することを確認しましょう。

コードのミニマックス

このチュートリアルでは、下の図2に示すゲームの近端状態に取り組みます。minimaxはゲームのすべての状態(数十万)を評価するため、近端状態では、minimaxの再帰呼び出しを簡単にフォローアップできます(9)。

次の図では、AIがXで、人間のプレイヤーがOであると想定しています。

Ti Tac Toeボードを簡単に操作するには、9項目の配列として定義する必要があります。各アイテムには、値としてのインデックスがあります。これは後で便利になります。上記のボードにはすでにいくつかのXとYの動きが入力されているので、XとYの動きがすでに含まれているボードを定義しましょう(origBoard)。

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

そして、宣言aiPlayerhuPlayer変数をそれぞれ「X」と「O」にそれらを設定します

さらに、勝ちの組み合わせを探し、見つかった場合はtrueを返す関数と、ボード内の利用可能なスポットのインデックスを一覧表示する関数が必要です。

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

次に、2つの引数newBoardplayerを使用してMinimax関数を定義することにより、適切な部分について詳しく見ていきましょう。次に、ボード内の使用可能なスポットのインデックスを見つけて、それらをavailSpotsという変数に設定する必要があります。

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

また、端末の状態を確認し、それに応じて値を返す必要があります。Oが勝った場合は-10を返し、Xが勝った場合は+10を返す必要があります。さらに、availableSpots配列の長さがゼロの場合、つまりプレイする余地がない場合、ゲームは引き分けになり、ゼロを返す必要があります。

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

次に、後で評価するために、各空のスポットからスコアを収集する必要があります。したがって、アレイと呼ばする移動オブジェクトと呼ばれる、各移動の指標とスコアを収集しながら、空のスポットを通ってループを移動します

次に、origBoardに数値として格納されていた空のスポットのインデックス番号をmoveオブジェクトのindexプロパティに設定します。後で、ニューボードの空の場所を現在のプレーヤーに設定し、他のプレーヤーと新しく変更されたニューボードでミニマックス関数を呼び出します。次に、scoreプロパティを含むminimax関数呼び出しの結果のオブジェクトをmoveオブジェクトのscoreプロパティに格納する必要があります。

ミニマックス関数が終了状態を検出しない場合、ゲームのより深いレベルで再帰的にレベルを上げ続けます。この再帰は、最終状態に到達して1レベル上のスコアを返すまで発生します。

最後に、MinimaxはnewBoardを以前の状態にリセットし、moveオブジェクトをmoves配列にプッシュします。

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

次に、ミニマックスアルゴリズムは、moves配列内の最適なmoveを評価する必要があります。それは選ぶべき動きAIが再生されている最も高いスコアとして動く人間が再生されている最低のスコアを。場合したがって、プレイヤーはあるaiPlayer、それはと呼ばれる変数セットbestScore介して非常に低い数及びループに移動させる場合には、アレイを動きは、より高い有しスコアよりbestScore、アルゴリズムストアその移動。同様のスコアの動きがある場合、最初の動きのみが保存されます。

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.

第FCは、2つの空のスポットを列挙しているので、ミニマックスは変化newBoardを配置することによってhuPlayerを第二の空のスポットに。次に、新しいボードとaiPlayerで自分自身を呼び出します

4.アルゴリズムは空のスポットのリストを作成し、ターミナルの状態をチェックした後、人間のプレーヤーの勝利を見つけます。したがって、scoreプロパティと値が-10のオブジェクトを返します。

2番目のFCで、アルゴリズムは下位レベル(3番目と4番目のFC)からの値を収集します。以来huPlayerのターン2つの値の結果、アルゴリズムは、2つの値の最低を選択します。両方の値が類似しているため、最初の値を選択して、最初のFCに返します。この時点で、最初のFCは、最初の空の場所でaiPlayerを移動するスコアを評価しました。次に、それが変化しnewBoardを配置することによって、 aiPlayerを第二の何もない場所で。その後、それはで自分自身を呼び出しnewBoardhuPlayer

5. 5番目のFCで、アルゴリズムは空のスポットのリストを作成し、端末の状態を確認した後、人間のプレーヤーの勝利を見つけます。したがって、スコアプロパティと値が+10のオブジェクトを返します。

その後、最初のFCは、 newBoard変更し、 aiPlayer3番目の空の場所に配置することによって進みます。次に、新しいボードとhuPlayerで自分自身を呼び出します

6. 6番目のFCは、検出した2つの空のスポットのリストを作成し、端末の状態をチェックし、最初の空のスポットから2つの空のスポットをループします。その後、それが変化しnewBoardを配置することによって、huPlayerを最初の何もない場所で。その後、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,アルゴリズムは空のスポットの空のリストを作成し、端末の状態をチェックした後、aiPlayerの勝利を見つけます。したがって、スコアプロパティと値が1レベル上の+10(7番目のFC)のオブジェクトを返します。

7番目のFCは、下位レベルから1つの正の値のみを受け取りました(8番目のFC)。aiPlayerの順番でその値が得られたため、アルゴリズムは下位レベルから受け取った最大値を返す必要があります。したがって、1レベル上の(6番目のFC)唯一の正の値(+10)を返します。6番目のFCが2つの空のスポットをリストしたので、MinimaxはhuPlayer2番目の空のスポットに配置することによってnewBoardを変更します。次に、新しいボードと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.

この時点で、6 FCは、7番目のFCから送信されたスコア(+10)(元々は8 FCから返された)と9番目のFCから返されたスコア(-10)のどちらかを選択する必要があります。以来huPlayerの順番はこれら二つの戻り値が得られ、アルゴリズムは、最小スコア(-10)とリターンを見つけ、それ上方スコアとインデックスプロパティを含むオブジェクトとして。最後に、最初のFCの3つのブランチすべてが評価されました(-10、+ 10、-10)。ただし、aiPlayerの順番でこれらの値が得られたため、アルゴリズムは最高スコア(+10)とそのインデックス(4)を含むオブジェクトを返します。

上記のシナリオでは、Minimaxは、Xをボードの中央に移動すると最良の結果が得られると結論付けています。:)

終わり!

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.