HTML games programming from the ground up: Improving the AI player

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: Creating a simple AI player

In the previous post, I identified that the simple AI player I built had some deficiencies in that, even at its strongest, it could be easily beaten. I decided that the best approach to improving the AI player was to combine elements of what I had with a tried and tested approach. For this, I selected the popular Minimax algorithm.

More on that in a moment. Before adding in a chunk of new code, I wanted to make the existing code more organised so it would be easier to add the new algorithm. To that end I refactored everything to follow an object oriented approach.

JavaScript has never had support for a strict OO approach and still doesn’t (because, while it supports encapsulation to a certain extent the ability to implement information hiding is limited), but the introduction of classes in ES6 has certainly improved things.

I identified 6 objects to implement:

• Player – an abstract class that represents a generic player in the game
• AiPlayer – a subclass of Player that adds further functionality for AI players
• Board – Represents the board (or bit of paper) on which the game is played
• Game – Represents a single game of Tic Tac Toe
• Ui – Manages the visual representation of the game and the user interface

Each of these classes sits in a JavaScript module. Here’s the Board class:

// Board class
// Represents the Tic Tac Toe board

class Board {
  // 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]
  ];

  constructor() {
    this.board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '];
  }

  // Get number of winning lines
  getNumLines() {
    return this.#lines.length;
  }

  // Returns the mark at index
  getMarkAt(index) {
    return this.board[index];
  }

  // Sets mark at index
  setMarkAt(index, mark) {
    this.board[index] = mark;
  }

  // Gets a copy of the entire current board state
  getBoard() {
    return [...this.board];
  }

  // Sets the board state from an external array
  setBoard(board) {
    this.board = [...board];
  }

  // Returns true if the cell is empty
  cellIsEmpty(index) {
    return this.board[index] == ' ';
  }

  // Checks if mark occurs 3 times in any line
  checkForWin(mark) {
    for (let i = 0; i < this.#lines.length; i++) {
      if (this.countMarks(mark, i) == 3 ) {
        return true;
      }
    }
    return false;
  }

  // Checks for a complete game (all positions filled)
  checkForComplete() {
    for (let i = 0; i < this.board.length; i++) {
      if (this.board[i] == ' ') {
        return false;
      }
    }

    return true;
  }

  // Counts the number of times mark occurs in the given win line
  countMarks(mark, line) {
    let count = 0;
    for (let i = 0; i < this.#lines[line].length; i++) {
      if (this.board[this.#lines[line][i]] == mark) {
        count++;
      }
    }
    return count;
  }
}

export { Board };

Some of this will be familiar from the previous version of the game, e.g. using a single dimension array to represent the board and the #lines array that represents the possible winning lines.

You can see the Board class now takes care of all the functionality related to the state of the board at any moment in time, such as getting and setting marks at particular locations and checking for win and draw conditions.

Note the use of the # character to prefix the name of the lines property. As I mentioned earlier in this post, JavaScript lacks some features commonly associated with OO programming, such as information hiding. There is no concept of public, private or protected methods and properties in JavaScript. Instead there is a convention that methods and properties that begin with a # character are intended to be private. It’s not enforceable, but it does at least give the programmer an indication of intended use.

The simplest of the new classes is the Player class:

// Player class
// Represents a tictactoe player

class Player {
  constructor(mark) {
    this.mark = mark;
  }

  getMark() {
    return this.mark;
  }
}

export { Player };

This class contains just one property, the mark made by this player (‘O’ or ‘X’), which is set by the constructor when a new object is instantiated, and one method, which is a getter for that property. This class is all we need to represent a human player.

For AI players, things get a lot more complex, so we need to extend this base class:

// AiPlayer class
// A subclass of Player that represents an AI player

import { Player } from './player.js';
import { Board } from './board.js';

class AiPlayer extends Player {
  #strength = 0;
  #maxDepths = [0, 2, 4, 6, 10];  // Holds the maximum search depths for the different AI strengths
  #scoreThresholds = [101, 100, 6, 3, 0]; // Holds the score threshold for the different AI strengths

  constructor (mark, strength) {
    super(mark);
    this.#strength = strength; // Holds the AI strength for this AI player
  }

  // Calculate the AI player's move
  AIMove(board, mark) {
    let bestScore = -101;
    let scores = [];

    // Cycle through all the positions on the board
    for (let i = 0; i < 9; i++) {
      // If a cell is currently empty...
      if (board.cellIsEmpty(i)) {

        // Default to a score of -101 (this will be applied only if minimax
        // is not used because the AI player is weak)
        scores[i] = -101;

        // If the AI player is strong enough to warrant the minimax algorithm...
        if (this.#maxDepths[this.#strength] > 0) {
          // Play to the current position
          board.setMarkAt(i, mark);
          // Get a score using the minimax algorithm
          let score = this.#minimax(board, (mark == 'O' ? 'X' : 'O'), false, 1);
          scores[i] = score;
          board.setMarkAt(i, ' ');  // Remove mark from current position
          // If score is better then current best score then update this
          bestScore = Math.max(bestScore, score);
        }

      } else {
        // The position is not empty so apply a large negative score to ensure
        // this position will never be selected
        scores[i] = -1000;
      }
    }

    // Collect all the locations that have the maximum score
    let possibleMoves = [];

    for (let i = 0; i < scores.length; i++) {
      if (scores[i] == bestScore) {
        possibleMoves.push(i);
      }
    }

    // Return a move at random from all those delivering the best result
    return possibleMoves[Math.floor(Math.random() * possibleMoves.length)];
  }

  // Apply the minimax algorithm to determine the best score achievable from the given position
  #minimax(board, mark, isMax, depth) {
    // Evaluate the current board to check for wins for either player
    let score = this.#adjustScore(this.#evalBoard(board, isMax ? mark : (mark == 'O' ? 'X' : 'O')), depth);

    // If score is 0 there has been no win, so check for a draw ...
    if (score != 0 || board.checkForComplete()) {
      // if it's a draw, it scores 0, so just return this
      return score;
    }

    // Set an initial value for best score based on whether this is a
    // maximising or minimising player
    let bestScore = isMax ? -101 : 101;

    // If we haven't yet reached the maximum depth for this AI player...
    if (depth < this.#maxDepths[this.#strength]) {
      // Cycle through all the positions on the board
      for (let i = 0; i < 9; i++) {
        // If the position is currently empty...
        if (board.cellIsEmpty(i)) {
          board.setMarkAt(i, mark); // Play to that position
          // Recursively apply the minimax algorithm to get the best score
          // achievable for that position
          let score = this.#minimax(board, mark == 'O' ? 'X' : 'O', !isMax, depth + 1);
          // For a maximising player, chose the highest score. For a minimising
          // player, choose the lowest score
          bestScore = isMax ? Math.max(bestScore, score) : Math.min(bestScore, score);
          board.setMarkAt(i, ' ');  // Remove mark from current position
        }
      }
    } else {
      // We've reached the maximum depth for this AI so evaluate the
      //non-terminal board configuration to generate a score
      bestScore = this.#evalNonTerminalBoard(board, mark, isMax);
    }

    return bestScore;
  }

  // Evaluate the board to check for a win and apply appropriate score
  #evalBoard(board, playerMark) {
        // If the current AI player has won ...
       if (board.checkForWin(playerMark)) {
         return 100;  // Score 100
       } else if (board.checkForWin(playerMark == 'O' ? 'X' : 'O')) {
         // Or -100 if the opposing player has won
         return -100;
       }
       // Neither player has won so score 9
       return 0;
  }

  // Adjusts a score based on the search depth
  #adjustScore(score, depth) {
    return score * (1 - .05 * depth);
  }

  // Evaluate the value of the given non-terminal board configuration for the given player
  #evalNonTerminalBoard(board, mark, isMax) {
    let score = 0;
    for (let i = 0; i < board.getNumLines(); i++) {
      // The threshold determines which conditions are ignored
      // based on AI strength
      let threshold = this.#scoreThresholds[this.#strength];
      let count = board.countMarks(mark, i) * 10;
      count += board.countMarks(mark == 'O' ? 'X' : 'O', i);

      switch (count) {
        case 1:
          // Zero marks for player, 1 for opponent
          score -= threshold <= 3 ? (isMax ? -3 : 3) : 0;
          break;
        case 2:
          // Zero marks for player, 2 for opponent
          score -= threshold <= 6 ? (isMax ? -6 : 6) : 0;
          break;
        case 10:
          // One mark for player, 0 for opponent
          score += threshold <= 3 ? (isMax ? 3 : -3) : 0;
          break;
        case 20:
            // Two marks for player, 0 for opponent
            score += threshold <= 6 ? (isMax ? 6 : -6) : 0;
            break;
        case 11:
        case 12:
        case 21:
          score += threshold <= 1 ? -1 : 0;
          break;
      }
    }
    return score;
  }

}

export { AiPlayer };

This adds a second property to the constructor, which is the strength of the AI player.

The key new feature here is the addition of the Minimax algorithm. Minimax is a recursive algorithm used to determine the best move for a particular player in a two-player game. It’s based on the principle of scoring each of the free positions on the board and then selecting the position with the best score. In Minimax, the AI player is classed as a “maximising” player, in that they are trying to maximise their score and the opponent is classed as a “minimising” player, in that they are trying to “minimise” the AI player’s score.

Here’s an example of how it works in Tic Tac Toe. Let’s assume the game has progressed to the point where the board looks like this and it is O’s turn to play next:

The Minimax algorithm starts by examining each position on the board to find those that are empty. When it finds one, top-centre for example, it experimentally plays a piece to that position to see what the outcome would be:

It now checks the board in its revised state to see whether a terminal state has been reached (i.e. a win or a draw). In this case it’s a win for ‘O’ so it returns a score that represents that win. The value of the score is arbitrary, other than wins for the player should be a high/positive value and wins for the opponent should be a low or negative value. In my case a win for the player scores 100. So the algorithm removes the piece from that position and assigns a score of 100 to that position and moves on to try the next empty position, if there is one.

In this case the move does not result in a terminal state. Neither side has won and there are still moves to be made. This is where the recursive nature of the algorithm kicks in. The algorithm is applied again, but this time for the minimising player, ‘X’.

Once again the algorithm iterates through each free space on the board, so it will start with the empty space at top-centre. This also results in a non-terminal condition, so the algorithm is again applied for the maximising player ‘O’, which results in a win for ‘O’ again scoring 100:

As ‘O’ is the maximising player, it will chose the highest value (although in this case, there is only one value to choose), so that’s what it returns to the previous level of the algorithm. ‘X’ records this score against the position it tried and moves on the next position, bottom-left, which also results in a win for O when it plays to top-centre. This leaves ‘X’ with the following scores:

The final set of scores for X show that, whichever of the two positions it plays to will result in a win for ‘O’. As it is the minimising player, it will chose the minimum value, but in this case, that is 100. So that’s what’s returned to the calling iteration, and what will be recorded against the position that ‘O’ played to. The algorithm now tries the third and final position for ‘O’:

Again, this is a non-terminal outcome, so the algorithm runs again for ‘X’, and is applied to the two available positions resulting in these outcomes:

In this case, the first of these positions (top-row) is non-terminal, but on the next move ‘O’ will win, resulting in a score of 100. The second position immediately results in a win for ‘X’, scoring -100. As ‘X’ is the minimising player, it will return the lowest possible score, which is -100. This leaves ‘O’ with the following scores for its possible moves:

Because ‘O’ is the maximising player, the algorithm will choose the maximum score, which is 100. This applies to more than one board position, so my algorithm will choose one of these positions at random to play to.

You can envisage this whole sequence as a tree showing the moves made and the scores returned:

One small issue with the raw algorithm is that it gives equal weight to the two winning moves even though the top-centre position results in an instant win, while the middle-right position results in a win after two further moves. The solution to this is to apply a weighting based on search depth. My version of the algorithm does this with the following formula in the #adjustScore method:

score = score * (1 – 0.05 * depth)

In other words, it reduces the score by 5% for each level of search depth. So the top-centre position, which results in a win at search depth 1, would generate a score of 95, while the middle-right position, which results in a win at search depth 3, would generate a score of 85. Therefore the position that results in a quicker win would be favoured.

The next challenge to solve is that if the Minimax algorithm is allowed to run its course to the maximum recursion depth on each move, this will result in the strongest possible player the algorithm can deliver. However, my previous algorithm offered five different AI strengths to play against.

The most obvious way to implement that with Minimax is to limit the search depth for the various strengths. This is set in the #maxDepths property. Note that the weakest player has a maximum search depth of 0, which means the Minimax algorithm is never entered and this player chooses entirely at random from the available moves. By contrast, the strongest player has a maximum search depth of 10. Since the longest possible game has only 9 moves, this guarantees that it will always explore the game tree to the maximum possible depth.

Setting a maximum search depth does mean that there will be circumstances in which Minimax must return from a non-terminal state, i.e. an incomplete game. You’ve seen that complete games are scored 100 if the AI player wins and -100 if the opposing player wins. Draws are scored as 0 by the way since they favour neither player. But how do I score a non-terminal state?

This is where my previous AI logic comes back into the mix. This is now in a slightly different form in the #evalNonTerminalBoard method. It works by examining each possible winning line in turn and counting the number of player marks and opponents marks in each line. The lines are then scored as follows:

So you can see here that lines that are completely empty score 0, because they could go either way. Lines that can’t be won by either player, attract a small negative score, because ideally we want to favour positions that maximise the AI’s opportunities for winning. Lines that are potential wins for the AI score 3 or 6 points depending on whether there are 1 or 2 marks in the line. Correspondingly, lines that are potential wins for the opponent, score -3 or -6 points depending on whether there are 1 or 2 opponent marks in the line.

There are 8 possible winning lines, so in theory the maximum score you could accumulate for a board is 6×8 or 48 which is less than the score awarded to a win at maximum depth (55). However, in practice you can’t get a configuration that scores this highly because it would require every line to have two player marks and no opponent marks. So. we can always be sure that a win will be favoured over a non-terminal board configuration. The non-terminal scoring will come into play with the weaker AI players early in the game, where they are effectively comparing non-terminal states to decide which offers the greatest opportunity and least threat.

The user interface is managed by the Ui class.

// UI class
// Encapsulates the user interface for Tic Tac Toe

import { Game} from './game.js';

class Ui {
  #controls = null;

  constructor(quitHandler, newGameHandler, makeMoveHandler) {
    this.#controls = {
      'compStrengthO': document.querySelector('#compStrengthO'),
      'compStrengthX': document.querySelector('#compStrengthX'),
      'drawMsg': document.querySelector('#drawMsg'),
      'inPlayControls': document.querySelector('#inPlayControls'),
      'new': document.querySelector('#new'),
      'newGameControls': document.querySelector('#newGameControls'),
      'play': document.querySelector('#play'),
      'playerOComputer': document.querySelector('#playerOComputer'),
      'playerXComputer': document.querySelector('#playerXComputer'),
      'posWarning': document.querySelector('#posWarning'),
      'quit': document.querySelector('#quit'),
      'resultMsg': document.querySelector('#resultMsg'),
      'selectedCell': document.querySelector('#selectedCell'),
      'turn': document.querySelector('#turn'),
      'valWarning': document.querySelector('#valWarning'),
      'winMsg': document.querySelector('#winMsg'),
      'winner': document.querySelector('#winner')
    }
    this.#controls['quit'].addEventListener('click', quitHandler);
    this.#controls['new'].addEventListener('click', newGameHandler);
    this.#controls['play'].addEventListener('click', makeMoveHandler);
  }

  // Draws the board
  drawBoard(board) {
    for(let i = 0; i < board.length; i++) {
      document.querySelector('#cell' + i).innerHTML = board[i];
    }
  }

  // Displays the mark of the player whose turn it is to play
  displayTurn(mark) {
      this.#controls['turn'].innerHTML = mark;
  }

  // Displays the winner as the given mark
  displayWinner(mark) {
    this.#controls['winner'].innerHTML = mark;
    this.#showControl(this.#controls['winMsg']);
  }

  // Enables buttons so that a human player can make a move
  requestMove() {
    document.querySelector('#play').disabled = false;
    document.querySelector('#quit').disabled = false;
  }

  // Shows the listed controls
  showControls(controls) {
    this.applyControlFunction(controls, this.#showControl);
  }

  // Show control
  #showControl(control) {
    control.classList.remove('hidden');
  }

  // Hide the listed controls
  hideControls(controls) {
    this.applyControlFunction(controls, this.#hideControl);
  }

  // Hide control
  #hideControl(control) {
    control.classList.add('hidden');
  }

  // Disable the listed controls
  disableControls(controls) {
    this.applyControlFunction(controls, this.disableControl);
  }

  // Disable control
  disableControl(control) {
    control.disabled = true;
  }

  // Clear controls
  clearControls(controls) {
    this.applyControlFunction(controls, this.clearControl);
  }

  // Clear control
  clearControl(control) {
      control.value = '';
  }

  // Apply function to controls
  applyControlFunction(controls, funcToApply) {
    for (let i = 0; i < controls.length; i++) {
      funcToApply(this.#controls[controls[i]]);
    }
  }

  // Validate numeric input
  isValidNumber(control, min, max) {
    let value = this.getNumericValue(control);
    return (!(isNaN(value) || value < min || value > max));
  }

  // Gets a numeric value for a control
  getNumericValue(control) {
    return parseInt(this.#controls[control].value);
  }

  // Returns true if the indicated control is checked
  isChecked(control) {
    return this.#controls[control].checked;
  }
}

export { Ui };

The constructor for this class finds all of the required controls and displays and stores them in an object referenced by relevant names. This is stored in the #controls property; The names are used by client functions to specify the elements of the user interface they need to access. For example, the hideControls method expects to receive an array of names of controls that the client function wants hidden.

Abstracting things this way means that, when I improve the look of the game and change the way that controls and displays are represented, I only have to update the code in this class – client requests can work in the same way.

The final class is the Game class that, believe it or not, represents a game:

// Game class
// Represents a game

import { Ui } from './ui.js';
import { Board } from './board.js';
import { Player } from './player.js';
import { AiPlayer } from './aiPlayer.js';

class Game {
  #board = null;  // The board object for the game
  #players = [];  // Holds the player objects for O and X respectively
  #turn = 0;      // The index number for the current player

  // Constructor expects a player type for each player - 'A' for AI or 'H' for
  // human and a playing strength from 0 to 4 (this will be ignored for human)
  // players
  constructor(type1, strength1, type2, strength2) {
    this.#board = new Board();

    // Set up players
    this.#players[0] = type1 == 'A' ? new AiPlayer('O', strength1) : new Player('O');
    this.#players[1] = type2 == 'A' ? new AiPlayer('X', strength2) : new Player('X');
  }

  // Returns the mark at index
  getMarkAt(index) {
    return this.#board.getMarkAt(index);
  }

  // Returns the mark for the current player
  getMarkForCurrentPlayer() {
    return this.#players[this.#turn].getMark();
  }

  // Gets the next move from a computer or human player
  getMove() {
    // If the current player is a computer player, make the next move and
    // indicate move is complete
    let currentPlayer = this.#players[this.#turn];
    if (currentPlayer instanceof AiPlayer) {
      return this.processMove(currentPlayer.AIMove(this.#board, currentPlayer.getMark()));
    } else {
      // Otherwise, indicate the current move needs human input to complete
      return [this.#board.getBoard(), 'P', ' '];
    }
  }

  // Checks if a move is valid (i.e. into an empty cell)
  isValidMove(selectedCell) {
    return this.#board.cellIsEmpty(selectedCell);
  }

  // Process a move for the current player (human or AI)
  processMove(selectedCell) {
    let currentPlayerMark = this.#players[this.#turn].getMark();
    this.#board.setMarkAt(selectedCell, currentPlayerMark);
    this.#turn = this.#otherPlayer(this.#turn);
    let outcome = [this.#board.getBoard()];

    // Check for a won game, then for a draw
    if (this.#board.checkForWin(currentPlayerMark)) {
      //quit(true);
      outcome = outcome.concat(['W', currentPlayerMark]);
    } else if (this.#board.checkForComplete()) {
      // quit(false);
      outcome = outcome.concat(['D', ' ']);
    } else {
      // If neither, get next move
      //getMove();
      outcome = outcome.concat(['C', this.#players[this.#turn].getMark()]);
    }

    return outcome;
  }

  // Returns the index number of the opponent to player
  #otherPlayer(player) {
    return 1 - player;
  }
}

export { Game };

When an object of this class is instantiated, it creates a new Board and two new players (either human or AI). It’s then responsible for getting and processing each move (handled by the getMove and processMove methods respectively) and returning an outcome after each move. The outcome is an array with three elements. The first element is a copy of the current state of the board. The second element is a character representing the outcome. This can be:

The final module, tictactoe.js, is not a class but rather the code that glues everything else together and runs the game.

// Javascript file for Tic Tac Toe

import { Ui } from './ui.js';
import { Game } from './game.js';

let ui = null;    // Object encapsulating the UI for the game
let game = null;  // Object representing the game state

// Initialise the game on start up (set up UI handlers and begin new game)
function initialiseGame() {
  ui = new Ui(() => {
    quit(game.getMarkForCurrentPlayer() == 'O' ? 'X' : 'O');
  }, resetGame, play);
}

  // Gets the next move from a computer or human player
  function getMove() {
    processOutcome(game.getMove());
  }

  function processOutcome(outcome) {
    ui.drawBoard(outcome[0]);

    switch (outcome[1]) {
      case 'P':
        // If the game can't complete the current move (because it's a human
        // player's turn to play, then request move input from the UI)
        ui.requestMove();
        break;
      case 'W':
      case 'D':
        //  Game was won or drawn
        quit(outcome[2]);
        break;
      default:
        // Game is still in play
        ui.displayTurn(outcome[2]);
        getMove();
        break;
    }
  }

  // Called when a player inputs a move. Validates the move, then send the
  // move to the game to process if valid
  function play() {
    let valid = true;
    let selectedCell;
    ui.hideControls(['valWarning', 'posWarning']);

    // Check player entered a valid cell number
    if (ui.isValidNumber('selectedCell', 1, 9)) {
      selectedCell = ui.getNumericValue('selectedCell') - 1;

      // Check entered cell is empty
      if (!game.isValidMove(selectedCell)) {
        ui.showControls(['posWarning']);
        valid = false;
      }
    } else {
      ui.showControls(['valWarning']);
      valid = false;
    }

    // if valid cell has been entered, pass the move to the game for processing
    if (valid) {
      ui.disableControls(['play', 'quit']);
      ui.clearControls(['selectedCell']);
      processOutcome(game.processMove(selectedCell));
    }
  }

  // Called when the game ends. Displays the winner or a draw message and the
  // controls to start a new game
  function quit(outcome) {
    ui.hideControls(['winMsg', 'drawMsg']);

    if(outcome == 'O' || outcome == 'X') {
      ui.displayWinner(outcome);
    } else {
      ui.showControls(['drawMsg']);
    }

    ui.hideControls(['inPlayControls']);
    ui.showControls(['resultMsg', 'newGameControls']);
  }

  // Starts a new game, clearing the board, setting the first player to 'O' and
  // showing the UI for entering moves
  function resetGame() {
    let type1 = ui.isChecked('playerOComputer') ? 'A' : 'H';
    let type2 = ui.isChecked('playerXComputer') ? 'A' : 'H';
    let strength1 = ui.getNumericValue('compStrengthO');
    let strength2 = ui.getNumericValue('compStrengthX');
    game = new Game(type1, strength1, type2, strength2);

    // Hide new game dialog and show in game controls
    ui.hideControls(['resultMsg', 'newGameControls']);
    ui.clearControls(['selectedCell']);
    ui.showControls(['inPlayControls']);

    // Drawe the initial board and display the turn and get first move
    ui.drawBoard(game);
    ui.displayTurn(game.getMarkForCurrentPlayer());
    getMove();
  }

export { initialiseGame };

This exposes a function, initialiseGame, that creates a new Ui instance, and then sets up a new game and begins play. The other functions here are fairly self explanatory. Note how they use the control names mentioned earlier to send commands to the Ui object.

The index.html file remains largely the same as the previous version of the game other than a small update to the code that calls the initialiseGame method:

    <!-- script to boot game once DOM loaded -->
    <script type="module">
      import { initialiseGame } from './js/tictactoe.js';
      document.addEventListener('DOMContentLoaded', function() {
        initialiseGame();
      });
    </script>

Now that I have the functionality and structure I want, it’s time to turn my attention to that ugly user interface and give it a makeover. I’ll pick up that task in the next post.