After creating tic tac toe in JavaScript in my previous article I decided to add a second player in the form of a computer opponent. One player would still place their tokens in the same way, but the other player would use an algorithm to determine the best play against you.
There are a few ways in which we can create the algorithm for computer player. The game of tic tac toe is known as a "solved" game, which means that the best play to make for any given move has already been worked out. We could, therefore, build an algorithm that matches the game current game board with the known state of play and then just place the computer piece in the most optimal place.
The downside of that approach, however, is that we need to enter in all of the different conditions of the board before hand. This means that if we want to change the rules or alter the size of the board we would need to enter in a completely different set of game conditions.
A much better way to determine the best move to make is to use an algorithm and calculate the best move based on a score.
In this article I will go through the algorithm used to calculate the best move in tic tac toe and then look at the code that implements this algorithm. This article will build upon the work done in the last article on creating tic tac toe in JavaScript so not all of the code will be present here.
Winning Tic Tac Toe
In order to win a game of tic tac toe we need to determine what the best move would be. The "best" move is the move that gives us the best chance of winning the game.
One of the best ways in which to calculate the computer move is to use an algorithm called Minimax or MinMax. This is an algorithm that will calculate the best move by playing the game to its conclusion and giving each move a score. The best score calculated during this process is then used to play the game.
As an example, let's take a game board in tic tac toe that is half way complete. Showing the game towards the end is a much simpler way to show how the game is played as there are few outcomes to the state of the game board. If we start at the beginning of the game we would need to factor into account many different scenarios of play.
In this game the X player has just entered their counter and it is now the computers go to put the O counter. This is what the game board looks like.
X|O|X
O|O|X
X|-|-
In order to determine the best play for the computer we the current state of the game board and play it through to conclusion. There are 3 possible states that we can give the outcome of the game, each of which has a score.
- +10 means that the play we make leads to the game being won.
- 0 means that the play we make leads to a draw.
- -10 means that the play we make leads to a loss.
The idea behind the minimax algorithm is that we work through the game and give the different scenarios one of these scores.
We begin by placing our counter in the first free square, which is the middle bottom square.
X|O|X
O|O|X
X|-|O
We can see here that the computer has won straight away, so this board gets a +10 score in out move outcomes.
Despite this being a win, this might not be the best move to win the game, so we check the other moves available to make sure this is the optimal path. The other possible move we can make is to put the counter in the bottom right hand square.
X|O|X
O|O|X
X|O|-
The game is still in a playable state and so we mimic the game that the other player would perform and place the last counter (in this case X) in the middle bottom square.
X|O|X
O|O|X
X|X|O
This results in a draw situation, which means that we give this outcomes a 0 score. If the "X"
After running through the above we can see that the best move is to put the counter in the bottom middle position, since that gives the computer player a certain win result.
This is exactly the same algorithm that will be run on any move during the game. The more empty spaces there are available on the game board means the more we need to play the game to determine the best outcome. In the above example we only needed to make 3 plays, if the game board was empty we would need to make at least 255,168 moves to determine the best approach (see this page for a reference of this number).
Code To Determine The Best Move
To add the minimax algorithm to the game we first need to have a way of using the result. What we need to do is create a function that will look for empty spaces in the game board and play the game using that space as a starting point. We then compare the score returned with the current best score and update the current move set (i.e. the coordinates of the empty square) if the score is better.
When we have finished looking at all of the empty squares in the game board we will have a set of coordinates that points to the optimal empty square to move to. The only thing left to do is make the move (by putting the player token into the game board), redrawing the board and swapping the current player.
This is the function that takes care of the computer player, it's called aiPlay(). I have added comments within the code to show what steps are being undertaken.
function aiPlay() {
// Define the lowest possible state for the best score.
let bestScore = -Infinity;
// Set the variable for our "best" move.
let move;
// Loop through all of the squares in the game board.
for (let i = 0; i < state.length; i++) {
for (let j = 0; j < state[i].length; j++) {
if (state[i][j] == "") {
// This is an empty square, so we can start the play at this point.
state[i][j] = player2;
let score = minimax(state, false);
state[i][j] = "";
if (score > bestScore) {
// This is the best score we have had so far, so we store it.
bestScore = score;
move = { i, j };
}
}
}
}
// Make the move and draw the result.
state[move.i][move.j] = currentPlayer;
drawState();
// Swap the player.
if (currentPlayer == player1) {
currentPlayer = player2;
} else {
currentPlayer = player1;
}
}
To determine the score of the move we use the minimax() function, which will run the minimax algorithm for the current state of the board, let's look at this function.
The Minimax Function
We use the minimax() function to determine if the score of the game from the current state of the game board. This is the game board after we have added a single move. Here is the code in full.
function minimax(state, isMaximising) {
var winner = isWin();
if (winner === player2) {
return 10;
} else if (winner === player1) {
return -10;
} else if (winner === "draw") {
return 0;
}
if (isMaximising) {
var bestScore = -Infinity;
for (let i = 0; i < state.length; i++) {
for (let j = 0; j < state[i].length; j++) {
if (state[i][j] == "") {
state[i][j] = player2;
let score = minimax(state, false);
state[i][j] = "";
bestScore = Math.max(bestScore, score);
}
}
}
} else {
var bestScore = Infinity;
for (let i = 0; i < state.length; i++) {
for (let j = 0; j < state[i].length; j++) {
if (state[i][j] == "") {
state[i][j] = player1;
let score = minimax(state, true);
state[i][j] = "";
bestScore = Math.min(bestScore, score);
}
}
}
}
return bestScore;
}
The function works by looking through the game board for any blank spaces and then making a play in that space, we then call the function recursively until the game is in a won state.
As we enter the function for the first time we will have already made the move that the computer would make, so by setting the isMaximizing parameter to "true" we then play the game as the other player. We then call the function again and pass the value of "false" to the isMaximising parameter, which causes the computer player to have a go. The function essentially flip-flops back and forwards from one player to another, each time playing a counter and detecting if the game has been won.
One important thing to note in all of this is that when we have determined the score of the play we reset the game board back to it's original value. This preserves the current state of the game without having to make lots of copies of the game board to calculate the result.
The result of this function is either a +10 for a win, a -10 for a loss and a 0 for a draw, which we then pass upstream to the aiPlay() function. Using this information we are then able to determine the best move to make based on the score of the function.
All we need to do now is incorporate this second player into the tic tac toe game so that the computer can play too.
Adding The Second Player
In the original game we had a function called canvasClick(), which was used to record the click event and so the play of each player. To incorporate the computer player into the game we just need to expand this function to include the aiPlay() function. Once the computer player has played we perform a second check to see if the game has been won or not.
function canvasClick(event) {
const rect = canvas.getBoundingClientRect();
var x = event.clientX - rect.left,
y = event.clientY - rect.top;
// Collision detection between clicked offset and element.
boxes.forEach(function (element) {
if (
y > element.y &&
y < element.y + element.height &&
x > element.x &&
x < element.x + element.width
) {
if (state[element.row][element.column] !== "") {
return;
}
play(element.row, element.column);
// See if there is a winner.
let winner = isWin();
if (winner === "draw") {
document.getElementById("win").innerHTML = "draw!";
} else if (winner === player1 || winner === player2) {
document.getElementById("win").innerHTML = winner;
}
if (winner !== false) {
canvas.removeEventListener("click", canvasClick);
return;
}
aiPlay();
// See if there is a winner.
winner = isWin();
if (winner === "draw") {
document.getElementById("win").innerHTML = "draw!";
} else if (winner === player1 || winner === player2) {
document.getElementById("win").innerHTML = winner;
}
if (winner !== false) {
canvas.removeEventListener("click", canvasClick);
return;
}
}
});
}
This is all we need to do to initiate the minimax algorithm and perform the best move possible against the human player. Once this function has run it is then the human players turn again and the cycle will repeat until the game is won.
Conclusion
With these changes to the tic tac toe game it actually becomes very difficult to beat the computer. Every move you make causes the computer to run through every permutation of the game board to find the best possible score to play against you, which results in an AI player that appears to be highly skilled. In reality, the AI player is just predicting the plays made to the game board and knows the best move to make in any given situation.
I have tried to keep things as simple as possible here, so the minimax function in this article is a simple implementation of the algorithm. This can be improved further using alpha-beta pruning to prevent game scores from similar games being calculated multiple times. For example, if we know that placing a counter in a particular spot will eventually lead to a loss then don't need to go all the way to the end of the recursion to figure this out for every part of the analysis. We could look for game boards that are the same from different routes in the game play and so we wouldn't need to traverse all the way down the path just to have the same outcome. By doing this we can improve the performance of the algorithm as we can reduce the number of moves that we would need to perform.
The minimax function could also be altered to have a depth parameter. This can be used to stop the recursion at a particular level, which essentially creates a difficulty level for the AI player. For example, let's say we changed the minimax code so that if we hit a depth of 3 the function would return the current score at that level (even if the game had not been won). This small change would effectively prevent the minimax algorithm from knowing the final destination of a play, which means that it might not know if placing a counter in a square would actually lead to a win. Without this knowledge of the final outcome of the game the algorithm could therefore make a mistake without knowing it.
As an experiment I tried to increase the game board to a larger size, which is possible due to the way in which we are drawing the board. The result was that the minimax function took significantly longer to find a solution than it did previously. In fact, by just increasing the game board to a 6x6 grid the minimax function took upwards of 10 seconds to run to completion. You can see why using alpha-beta pruning and depth limits would be be beneficial in this case.
If you want to see all of the code working in this article then I have created a CodePen that shows JavaScript tic tac toe running with the minimax engine. If you just want to have a game then I have also created a page on this website that shows the game in action. Let me know if you are able to beat it as I am yet to get anything better than a draw.
If you want to know more about the minimax algorithm in tic tac toe then take a look at The Coding Train's tutorial and code on this. Daniel Shiffman does a really good job of showing how the minimax algorithm tree is created and used to determine the best course of action.
Add new comment