Making An AI Chess Game

One night, my friend (also a software engineer) gave me a challenge of making a chess game. Given my interest in AI, I decided to make an AI powered one. Perhaps due to my masochistic tendencies, I decided to make it with only two dependencies: Lit and chess.js (a library for move validation). First, I will outline the algorithm used, and then explain the implementation and my development choices.

The Minimax Algorithm

Overview

Chess is a zero-sum game, meaning that one player's gain is another player's loss. The Minimax algorithm is a decision-making algorithm used in two-player games like chess. It works by simulating all possible moves and their outcomes, and then choosing the move that maximises the player's chances of winning whilst minimising the opponent's chances.

The Minimax algorithm works by recursively exploring the game tree, which is a tree-like structure that represents all possible moves and their outcomes. The maximiser aims to maximise their score, while the minimiser aims to minimise the maximiser's score. This occurs at each node in the tree, with maximising or minimising of scores occuring depending on whose turn it is. The algorithm assigns a score to each leaf node in the tree, based on an evaluation algorithm. See the diagram below for an overview.

Alpha Beta Pruning

It is possible to improve the efficiency of the Minimax algorithm by using a technique called alpha-beta pruning. This technique allows the algorithm to ignore branches of the tree that are not relevant to the final decision, thus reducing the number of nodes that need to be evaluated. Look again at the example diagram. Taking the branch on the left (6 => 3 => 5 => 5 || 4), we know before the final 5 (with red lines) is calculated that the current minimum value is 4 at the second most deep level of the tree. As the minimiser will choose the 4 over the 5, the maximiser at the next level above will not choose the branch with the 4, regardless of the final value calculated (the 5 with red lines). Therefore, we can prune the rightmost branch, reducing computational complexity.

Evaluation Algorithm

In order to determine preferable game states for each player, an evaluation algorithm is required. There are various methods of performing this, but I initially tried to determine game state based simply on the number of pieces each player owned (and their associated values), whilst considering if either player had won. With a high depth of search (number of moves to simulate), this was sufficient to determine the best move. However, recursively searching the game tree is computationally expensive, and I found that the AI would take a long time to make a move. Therefore, a different approach was needed.

After some research, I stumbled upon piece square tables. These take the assumption that different pieces have varying values depending on their position on the board. For example, knights are more valuable in the centre of the board than on the edges, and pawns are more valuable when they are closer to the opponent's back rank. I used this in addition to my previous strategy. This resulted in a far more performant algorithm, with a corresponding decrease in search depth able to be made.

Implementation of the Minimax Algorithm

Creating the algorithm proved to be an excellent exercise in debugging. I had seen various sources recommending writing a Negamax algorithm instead of Minimax, as it is easier to implement. However, never one to give up, I continued with the Minimax algorithm. Here is my implementation:

let positionsEvaluated = 0;

function minimax(
  game: Chess,
  depth: number,
  isMaximizingPlayer: boolean,
  alpha: number,
  beta: number,
): [number, string] {
  positionsEvaluated++;

  if (depth === 0 || game.isGameOver()) {
    if (game.isCheckmate()) {
      return [isMaximizingPlayer ? -100000 : 100000, ''];
    }
    if (game.isDraw()) {
      return [0, ''];
    }
    return [evaluateBoard(game), ''];
  }

  let bestMove = '';
  if (isMaximizingPlayer) {
    let bestScore = -Infinity;
    const moves = game.moves();

    for (const move of moves) {
      game.move(move);
      const [score] = minimax(game, depth - 1, false, alpha, beta);
      game.undo();

      if (score > bestScore) {
        bestScore = score;
        bestMove = move;
      }
      /* eslint-disable-next-line no-param-reassign */
      alpha = Math.max(alpha, bestScore);
      if (beta <= alpha) {
        break;
      }
    }
    return [bestScore, bestMove];
  }
  let bestScore = Infinity;
  const moves = game.moves();

  for (const move of moves) {
    game.move(move);
    const [score] = minimax(game, depth - 1, true, alpha, beta);
    game.undo();

    if (score < bestScore) {
      bestScore = score;
      bestMove = move;
    }
    /* eslint-disable-next-line no-param-reassign */
    beta = Math.min(beta, bestScore);
    if (beta <= alpha) {
      break;
    }
  }
  return [bestScore, bestMove];
}

function getBestMove(pgn: string, depth: number = 3): [string | null, number] {
  positionsEvaluated = 0;
  const game = new Chess();
  game.loadPgn(pgn);
  const isMaximizingPlayer = game.turn() === 'b';
  const [, bestMove] = minimax(
    game,
    depth,
    isMaximizingPlayer,
    -Infinity,
    Infinity,
  );
  return [bestMove, positionsEvaluated];
}

We can see that the terms alpha and beta are passed to the function. These are the best scores that the maximiser and minimiser can guarantee at that level of the tree, and informs the next level of the tree whether to prune or not. The function returns the best move and the number of positions evaluated.

Multithreaded processing

Due to the idioscyncracies of Lit's lifecycle updating, I found that the AI would often freeze the UI when it was calculating its move. This was because the Minimax algorithm is computationally expensive, blocking the event loop. Thus, I decided to offload the calculations to a Worker. This allows the calculations to be performed in a separate thread, preventing the UI from freezing. If you have a keen eye, you may have noticed that a new Chess object (from Chess.js) is instantiated at each call of getBestMove. This is due to the data passed to a worker using the structured clone algorithm, which does not duplicate class private properties.

At first, I opted to initialise the Chess object with a fen string, which is a string representation of the game state. Upon later debugging, I found that without the history of moves, at later stages of the game, the algorithm was recommending moves that resulted in a draw due to threefold repetition. Clearly, the algorithm needed access to the same game history as the custom game controller had access to in the main thread. As a result, I sent the pgn string to the Worker, which is a string representation of the game state including the history of moves.

Implementation of the UI

Chess Pieces and Board

The first task was to create the pieces. I created an abstract base piece icon, allowing each piece icon to inherit a consistent set of properties. I then created a piece icon factory, providing a single method with which pieces could be instantiated. Finally, I created a chess piece, which rendered the correct icon and provided drag and drop functionality.

For the board, I first created the chess squares. These conditionally render a chess piece if required, and dispatch events upon hover to provide for available move highlighting. The chess board is responsible for setting properties on the chess squares, such as their colour and if they should be highlighted. It also implemented drag and drop functionality for the pieces.

Game Controller

Lit provides an interface called ReactiveController, which is an object able to hook into the host element's lifecycle. I created a custom game controller, wrapping around the Chess object and providing a consistent interface with which the UI can interact. Due to its ability to call updates on the host, the game controller can also update the UI when the game state changes. Unfortunately, the hostUpdated() method in the ReactiveController interface does not have access to the _changedProperties map when an update takes place. As a result, currently the host element (the ChessApp component) dictates when the controller should make an AI move if AI vs AI mode is not enabled, with the controller dictating this in AI vs AI mode. This sharing of responsibilities is not ideal, and would be addressed in a future version of the app. Despite this, there is generally a good separation of concerns between the game controller and the host element.

Dialog Controller

A key part of the application is the use of a dedicated DialogController. Implemented as a Lit reactive controller, this utility is responsible for managing the complete lifecycle of a dialog element. When a host component requires a dialog, it simply interacts with its DialogController instance, which handles the underlying mechanics: creating the <dialog-element>, appending it to the document body, rendering the specified content and styles, and managing the close event. The content is given by the use of a provider function, which is passed to the controller. This function is called when the dialog is opened, and returns a template literal containing the content to be rendered. This separation of concerns is particularly beneficial, as it keeps the host components significantly tidier by offloading the dialog management logic, whilst simultaneously promoting the reuse of the dialog functionality throughout the application.

ChessApp Class

This class acts as the main application container and orchestrator. It is responsible for rendering the UI components (ChessBoard, ChessPanel, buttons), handling user interactions (via events from the UI), managing the application-level state (like dark mode and the dialog message), and coordinating between the UI events and the ChessGameController. It decides when to call methods on the controller based on user actions or game state changes (like triggering the AI move after the player's turn or showing the dialog when the game is over).

Conclusion

Overall, this was a fun project to work on. I learnt a lot about the Minimax algorithm and how to implement it efficiently. For further improvements, I'd like to add an option to randomise the AI's moves, as well as a more sophisticated evaluation algorithm. Support for mobile devices would also be a nice addition, as would having an area to view the pieces already taken. Although making improvements is enticing, I'll be focussing my efforts on learning Java in the near future.