You can see an index of all the posts in this series: go to index.
If you want to view my progress to date, you can find the files from the end of the previous post here: Starting the Tic Tac Toe game
In the previous post, I set up the basic framework for a game of Tic Tac Toe. This framework had a rough and ready user interface that will eventually be replaced with a more refined interface. This version of the game enables one or more games to be played by two human players taking turns to move.
In this post, I will add a simple AI player. There is no single correct approach to creating AI players. For this game I wanted to create a simple AI player that was flexible enough to provide a range of playing strengths. At the lower end it should play within the rules of the game but provide very little challenge so that young players just learning the game can get the satisfactions of a few easy wins. At the top end it should be strong enough to at least force more experienced players into a draw.
The most sophisticated board game AI algorithms use some form of look ahead algorithm that will analyse a tree of possible moves from the current position to ascertain a move that will maximise the AI player’s advantage and minimise the other player’s advantage. The intial AI for this game will be simpler than that as it will only consider the current state of the game board rather than looking ahead. I will improve upon it in a future post.
The algorithm is based on creating a score for each position. The score is based on the current state of every win line that intersects that position on the board. The diagram below shows the possible win lines:
The numbers show how many win lines must be processed for each position in the board: four for the centre cell, three for corner cells, and two for side cells. A set of nine scores is created representing each of the nine positions on the board. Initially the score for each position is set to zero.
The board is then analysed by looping through each board position. If a cell is currently occupied by either player it is given a score of -1. If a cell is unoccupied it is scored as follows. For each winning line that intersects the cell:
Number of own marks in line | Number of opponent's marks in line | Score adjustment |
0 | 0 | +1 |
0 | 1 | +1 |
0 | 2 | +10 |
1 | 0 | +2 |
1 | 1 | No adjustment |
2 | 0 | +20 |
You can see that significantly more weight is given to winning moves (i.e. where the AI player already has two marks in that line and can win on this move) and to moves that block an opponent win (i.e. where the opponent already has two marks in that line and will win on their next move). Other score adjustments are incremental based on whether they can advantage the AI player / disadvantage the opponent.
As the scores are being created, the AI routine keeps track of the maximum score. Once the scores are calculated the AI will choose one of the cells that has the maximum score at random. The following board state shows an example. It is X’s turn to play next and X is an AI player.
These are the scores calculated for each position:
-1 | 1 + 2 = 3 | 1 + 1 + 2 = 4 |
1 + 2 = 3 | -1 | 1 + 2 = 3 |
1 + 1 + 2 = 4 | 1 + 2 = 3 | -1 |
You can see that the three cells that are currently occupied have been given a score of -1. This ensures they will always be a lower value than any unoccupied cells and can never be selected.
The cells on each side in the centre are intersected by two lines, one with a single own mark, which accrues 2 points, and one with a single opponent mark, which accrues 1 point. This gives a total of 3 points for each of these cells. The cells in two remaining corners are intersected by three lines. Two of these have a single opponent mark, which adds 1 point, but one has a single own mark, which accrues 2 points, giving a total of 4 points.
This means there are two cells that share the maximum score of 4 points and the AI player will choose one of those cells at random.
I deliberately chose this board configuration because it highlights the inherent weakness of any AI that doesn’t have a look ahead capability. Anybody who is very familiar with Tic Tac Toe will recognise this board configuration as a trick that more experienced players can lure beginning players into. O plays first into a corner. An analysis of the strength of various positions based solely on the opportunities they present at the current time will yield the centre cell as the most advantageous position to play next. This is what the AI player (X) has done here. Next O plays to the opposite corner. Again, based purely on which cells give the best positional advantage for the next move, the AI player identifies one of the two remaining corners as being the best next play. However, at this point the game is lost. O can play to the remaining corner, opening up two possible lines for a win on the next move. Since X cannot block both, O must win the game.
For a truly worthy AI player, I will have to fix this at some point. But for now, I’ll stick to the current algorithm and deal with the question of difficulty levels. This is achieved by creating a set of score thresholds. After the AI player has completed its board analysis, it will filter out any positive scores that are below a threshold by setting those scores to zero.
The thresholds I’ve used are shown below, along with the effect they have:
AI Strength | Threshold | Effect |
Very weak | 100 | Select at random from all available cells |
Weak | 50 | Only favour win on next move opportunities |
Average | 10 | Only favour win on next move and block enemy from winning on next move opportunities |
Strong | 3 | Favour everything except cells offering only a weak advantage |
Very Strong | 0 | Apply the full algorithm |
Before I can add the code to implement this initial simple AI player, I need to update the rough and ready user interface to allow the player to select whether each player is to be a human or AI player and what the AI strength should be. Here’s the revised HTML (the changed parts are highlighted):
<!DOCTYPE html>
<html lang="en" dir="ltr">
<head>
<meta charset="utf-8">
<title>Tic Tac Toe</title>
<link href="css/tictactoe.css" rel="stylesheet">
<script src="js/tictactoe.js"></script>
</head>
<body>
<div class="game_layer">
<!-- board -->
<div class="board">
<div class="cell_container"><div class="cell_id">1</div><div class="cell_content" id="cell0"></div></div>
<div class="cell_container centre"><div class="cell_id">2</div><div class="cell_content" id="cell1"></div></div>
<div class="cell_container"><div class="cell_id">3</div><div class="cell_content" id="cell2"></div></div>
<div class="cell_container middle"><div class="cell_id">4</div><div class="cell_content" id="cell3"></div></div>
<div class="cell_container middle centre"><div class="cell_id">5</div><div class="cell_content" id="cell4"></div></div>
<div class="cell_container middle"><div class="cell_id">6</div><div class="cell_content" id="cell5"></div></div>
<div class="cell_container"><div class="cell_id">7</div><div class="cell_content" id="cell6"></div></div>
<div class="cell_container centre"><div class="cell_id">8</div><div class="cell_content" id="cell7"></div></div>
<div class="cell_container"><div class="cell_id">9</div><div class="cell_content" id="cell8"></div></div>
</div>
<!-- game status -->
<div id="inPlayControls" class="hidden">
<p>It's <span id="turn"></span>'s turn to play.</p>
<!-- user input -->
<input id="selectedCell" type="number">
<button id="play" disabled>Play</button>
<button id="quit">Resign</button>
<p id="valWarning" class="warning hidden">Please enter a cell number between 1 and 9!</p>
<p id="posWarning" class="warning hidden">Please enter a number for a cell that is empty!</p>
</div>
<!-- end of game info and controls -->
<div id="resultMsg" class="hidden">
<p id="winMsg"><span id="winner"></span> wins!</p>
<p id="drawMsg">The game is drawn!</p>
</div>
<div id="newGameControls">
<h1>New Game</h1>
<div id="playerSetup">
<div>
<p>Player O (goes first)</p>
<label for="playerOHuman">Human</label><input type="radio" name="playerO" id="playerOHuman" checked>
<label for="playerOComputer">Computer</label><input type="radio" name="playerO" id="playerOComputer">
<label for="compStrengthO">Computer strength</label>
<select id="compStrengthO">
<option value="0">Very weak</option>
<option value="1">Weak</option>
<option value="2">Average</option>
<option value="3">Strong</option>
<option value="4">Very strong</option>
</select>
</div>
<div>
<p>Player X</p>
<label for="playerXHuman">Human</label><input type="radio" name="playerX" id="playerXHuman" checked>
<label for="playerXComputer">Computer</label><input type="radio" name="playerX" id="playerXComputer">
<label for="compStrengthX">Computer strength</label>
<select id="compStrengthX">
<option value="0">Very weak</option>
<option value="1">Weak</option>
<option value="2">Average</option>
<option value="3">Strong</option>
<option value="4">Very strong</option>
</select>
</div>
<button id="new">Start New Game</button>
</div>
</div>
</div>
<!-- script to boot game once DOM loaded -->
<script>
document.addEventListener('DOMContentLoaded', function() {
tictactoe.initialiseGame();
});
</script>
</body>
</html>
You can see that the controls for starting a new game have been expanded to include player selection and AI strength selection. Here’s how this looks:
Again this unstyled version is pretty ugly, but it’s functional enough to allow me to test the AI code I’m about to add.
The additions to the JavaScript are more extensive:
// Javascript file for Tic Tac Toe
var tictactoe = {
board: [], // Holds array representing board (set in resetGame function)
// Lines is an array with the board positions representing the possible win lines
lines: [
[0, 1, 2],
[0, 4, 8],
[0, 3, 6],
[1, 4, 7],
[2, 4, 6],
[2, 5, 8],
[3, 4, 5],
[6, 7, 8]
],
AIThresholds: [100, 50, 10, 3, 0],
playerChars: ['O', 'X'], // The characters representing the two players
turn: 0, // A character representing the current player
moves: 0, // Number of moves made in the game
players: ['H', 'H'], // Holds the player for O and X respectively ('H' = human, 'C' = computer)
AIStrengths: [0, 0], // Holds the AI strengths for O and X respectively
// Initialise the game on start up (set up UI handlers and begin new game)
initialiseGame: function() {
document.querySelector('#quit').addEventListener('click', () => {
tictactoe.quit(true);
});
document.querySelector('#new').addEventListener('click', this.resetGame);
document.querySelector('#play').addEventListener('click', this.play);
},
// Draw the current board based on the contents of the board array
drawBoard: function() {
for(let i = 0; i < 9; i++) {
document.querySelector('#cell' + i).innerHTML = this.board[i];
}
document.querySelector('#turn').innerHTML = this.playerChars[this.turn];
},
// Gets the next move from a computer or human player
getMove: function() {
// If the current player is a computer player, make the next move
if (this.players[this.turn] == 'C') {
this.AIMove();
} else {
// Otherwise, enable the input controls for a human player
document.querySelector('#play').disabled = false;
document.querySelector('#quit').disabled = false;
}
},
// Calculate the AI player's move
AIMove: function() {
// Create empty array for scores
let scores = [];
// Set the maximum score to 0
let maxScore = 0;
// Loop through the locations and generate a score for each
for (let i = 0; i < 9; i++) {
// If this space on the board is occupied ...
if (this.board[i] != ' ') {
// Give it a negative score
scores[i] = -1;
} else {
// Calculate a score for this location
// Set initial value to 0
scores[i] = 0;
// Find each line that contains the current position
for (let j = 0; j < this.lines.length; j++) {
if (this.lines[j].includes(i)) {
// Count number of marks in line made by AI player and other player
let ownMarks = this.countMarks(this.turn, j);
let opponentMarks = this.countMarks(this.otherPlayer(), j);
if (ownMarks == 0) {
if (opponentMarks == 0) {
scores[i]++;
} else {
scores[i] += opponentMarks == 2 ? 10 : 1;
}
} else if (opponentMarks == 0) {
scores[i] += ownMarks == 2 ? 20 : 2;
}
}
}
// Adjust value based on AI threshold (strength)
if (scores [i] <= this.AIThresholds[this.AIStrengths[this.turn]]) {
scores[i] = 0;
}
// Update max score if necessary
maxScore = Math.max(maxScore, scores[i]);
}
}
// Collect all the locations that have the maximum score
let possibleMoves = [];
for (let i = 0; i < scores.length; i++) {
if (scores[i] == maxScore) {
possibleMoves.push(i);
}
}
// Select a move at random from those available
this.processMove(possibleMoves[Math.floor(Math.random() * possibleMoves.length)]);
},
// Called when a player inputs a move. Validates the move, then updates and
// redraws the board
play: function() {
let valWarning = document.querySelector('#valWarning');
let posWarning = document.querySelector('#posWarning')
let cellInput = document.querySelector('#selectedCell')
valWarning.classList.add('hidden');
posWarning.classList.add('hidden');
document.querySelector('#play').disabled = true;
document.querySelector('#quit').disabled = true;
let selectedCell = parseInt(cellInput.value);
// Check player entered a valid cell number
if (isNaN(selectedCell) || selectedCell < 1 || selectedCell > 9) {
valWarning.classList.remove('hidden');
} else {
selectedCell--;
// Check entered cell is empty
if (tictactoe.board[selectedCell] != ' ') {
posWarning.classList.remove('hidden');
} else {
// if valid cell has been entered, process the move
cellInput.value = '';
tictactoe.processMove(selectedCell);
}
}
},
// Checks if either player has achieved a line of three marks
checkForWin: function() {
for (let i = 0; i < this.lines.length; i++) {
if (this.countMarks(0, i) == 3 || this.countMarks(1, i) == 3) {
return true;
}
}
return false;
},
// Counts the marks for the given player in the given win line
countMarks: function(piece, line) {
let count = 0;
for (let i = 0; i < this.lines[line].length; i++) {
if (this.board[this.lines[line][i]] == this.playerChars[piece]) {
count++;
}
}
return count;
},
// Process a move for the current player
processMove: function(selectedCell) {
this.board[selectedCell] = tictactoe.playerChars[tictactoe.turn];
this.turn = tictactoe.otherPlayer();
this.drawBoard();
// Check for a won game, then for a draw
if (this.checkForWin()) {
this.quit(true);
} else if (++this.moves == 9) {
this.quit(false);
} else {
// If neither, get next move
this.getMove();
}
},
// Called when the game ends. Displays the winner or a draw message and the
// controls to start a new game
quit: function(gameIsWon) {
let winMsg = document.querySelector('#winMsg');
let drawMsg = document.querySelector('#drawMsg');
winMsg.classList.add('hidden');
drawMsg.classList.add('hidden');
if(gameIsWon) {
document.querySelector('#winner').innerHTML = this.playerChars[this.otherPlayer()];
winMsg.classList.remove('hidden');
} else {
drawMsg.classList.remove('hidden');
}
document.querySelector('#inPlayControls').classList.add('hidden');
document.querySelector('#resultMsg').classList.remove('hidden');
document.querySelector('#newGameControls').classList.remove('hidden');
},
// Starts a new game, clearing the board, setting the first player to 'O' and
// showing the UI for entering moves
resetGame: function() {
tictactoe.board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '];
tictactoe.turn = 0;
tictactoe.moves = 0;
tictactoe.players[0] = document.querySelector('#playerOComputer').checked ? 'C' : 'H';
tictactoe.players[1] = document.querySelector('#playerXComputer').checked ? 'C' : 'H';
tictactoe.AIStrengths[0] = parseInt(document.querySelector('#compStrengthO').value);
tictactoe.AIStrengths[1] = parseInt(document.querySelector('#compStrengthX').value);
document.querySelector('#inPlayControls').classList.remove('hidden');
document.querySelector('#resultMsg').classList.add('hidden');
document.querySelector('#newGameControls').classList.add('hidden');
tictactoe.drawBoard();
tictactoe.getMove();
},
// Returns the index number of the player not currently in play
otherPlayer: function() {
return 1 - tictactoe.turn;
}
}
The first change to note here is that the resetGame function now collects some additional information about the players and AI strengths from the DOM and stores these in variables in the TicTacToe object.
Whereas the previous version of the game stored the current player as either ‘O’ or ‘X’, this is now stored as a number, 0 or1 respectively. This makes it easier to look up the player and AI strength information for each player (note that a game between two AI players of different strengths is supported). If the current player needs to be converted into a character, for example when showing whose turn it is in the UI, this is now done using the two-element array playerChars.
The code that updates the board and checks for end game conditions has now been moved out of the play function and into it’s own function processMove. This function can then be called both by the play function to process a player move and by the AIMove function to process an AI move.
The AIMove function executes the algorithm described earlier in this post. Note that it makes use of the countMarks function which was developed for the win detection code.
There is also a new getMove function which either invokes the AIMove function or enables the UI so a human player can make a move, depending on whose turn it is and what type of player is playing next.
In the next post in this series, I’ll make some improvements to the AI code to include look-ahead functionality.
Be First to Comment