I've always been intrigued by the idea and challenge of creating a Chess AI. I've recently done it and have published the game online on this website for you to play. I've tested the AI against bots on chess.com; it can beat bots rated 1600 but loses against bots rated 2200 so its skill level probably resides within there. I've made some optimizations since then so it may or may not have improved in capability. In this article, I'll outline how I was able to implement the game engine and AI.
I've publicly released the source code for the Chess engine and AI in my Github repo ts-chess. You are free to use it if you'd like to create your own AIs and chess engines. I created this using TypeScript with the intention of having the full game and Chess AI run right in the web browser.
This is also available on NPM. To get started now: you can directly install via command line:
Implementing the Chess Engine
The chess engine is responsible for everything except the chess AI. It encapsulates piece movements, handling end of game scenarios, validating moves, and everything else pertaining to gameplay. When I began working on the project, I considered the various aspects and had to ask myself about:
- Board Position: how can we represent each position / cell on the board in an efficient manner?
- Chess Pieces: what is the best way to encapsulate logic specific to Chess pieces?
- Chess Piece Moves: what is the best way to encapsulate a potential move and the actual action of moving a chess piece?
- Algebraic Notation: how will the system handle inputs and outputs for algebraic notation?
- Board State: what is the move efficient way to represent the current state of a board and perform operations on it?
- Game State: what is the most efficient manner of determining if a player is in check, checkmate, or stalemate?
At a high level, I've chosen to implement the chess board state as a list of entries corresponding to cells on the board. Each entry is either a reference to a chess piece or null. The chess piece object stores its current position and which player it belongs to and is responsible for calculating which possible moves it can make. There is one class per each chess piece type, all of which extend a base class which handles common functionality. When calculating possible moves, the chess piece object is provided with a reference to the current board state. Initially, I was unsure if this was a wise approach, as this potentially could violate object oriented programming best practices, but I decided to proceed in this manner both because it would be slightly more efficient than filtering moves afterwords and because it makes a certain degree of sense if we consider that a "real life chess piece" would make moves based on its own perspective.
Here's an example Chess piece implementation:
To handle algebraic notation, the system considers which moves are available based on the current board state. The rules for algebraic notation indicate that the moving piece letter, column letter, and row number need to appear or not appear based on certain logic, with the apparent goal of being as specific as possible while using the least amount of characters required within the notation.
Generating the List of Possible Moves
Each chess piece class uses the current board state to determine which moves it has available. It runs through each possible move, filtering out moves which would take it outside the board or moves which are blocked by other pieces. It does not filter out moves which would put the player in an invalid state of check, that validation is not done unless the move is actually attempted. When move calculation begins, the piece will start at its current position and branch out in all valid directions, continuing until it has found all possible moves given its normal move abilities. Rooks will look to the left, right, up, and down. Bishops look across the diagonals. The queen re-uses both of those algorithms to find its moves. The pawn looks forward and at possible pieces it can capture, including en passant, and it includes fields for promotion if applicable. The king branches out similar to the queen and also includes castling. Each possible move is encapsulated within the same object as real moves themselves.
Caching Possible Moves
It is relatively cheap to calculate what moves are available to a single piece one time. However, when repeating this process thousands of times, the expenditure adds up. When an AI moves through its own possible moves as it looks at future moves, if it needs to re-calculate all possible moves each time, the system will need to calculate those moves as efficiently as possible or the AI will be too slow to be useable. To increase its efficienty, we can cache moves. At the beginning of the game, the system calculates the possible moves for each player. When a single piece is moved, it's likely that most other pieces will have the same exact moves available to it as before, and thus its moves do not need to be recalculated. The board state object caches moves by making a mapping between chess board cells and pieces which can move to it. Each time a piece is moved in the board, the system will figure out which available moves are affected by the change in position for both the previous position and the new position, and for each piece affected, will recalculate its possible moves while leaving other previous calculations unaffected.
Here's an example implementation:
Creating the AI
At a high level, this AI works by:
- Looking at all of its possible moves.
- For each move, looking at its opponent's responses.
- Continuing down a few more moves.
- Evaluate a score of the board at its state after those hypothetical moves have taken place.
This AI does not use machine learning. It relies mainly on its ability to efficiently look at all possible moves up to a certain point, then intelligently evaluate the state of that board. It will pick the best of those states, considering moves its opponent would make, and select that. This is esentially the minimax algorithm which I'll outline in sections below.
Creating the Heuristic Function
The herustic function is a function which takes the state of the board and outputs a value. In my implementation, the value will fall between -1 and 1, where -1 indicates a winning position for black and +1 indicates a winning position for white. If the game ends in checkmate once a certain position is reached, we can assign -Infinity or +Infinity for that position. The better the heuristic function, the better the AI will perform. I've created a heuristic which considers the following data points:
- The sum score of the pieces: chess pieces have predefined scores and this heuristics combines the scores and assigns a weight to it. Note that white pieces have a positive score and black pieces have a negative score. This carries through to the other data points as well.
- Pins and skewers on the board: if a player has a piece pinned or skewered, it will affect the score based on the points values of the pieces involved.
- Threat scores: f pieces are threatening other pieces, the score will reflect this.
- Activation score: in the beginning of the game, it's important to activate pieces; the score encourages this activation.
- Control of center score: it's good to have control of the center of the board.
- Mobility score: it's generally favorable to exert control of the board by positioning your pieces to access more, rather than less, squares
- Stacked pawn score: stacked pawns (two or more pawns in the same column) can cause issues, so it's generally good to avoid them.
The weight of each data point is assigned at the creation of the heuristic object. I started with my best guess as to which weights would lead to the best performing AI, then used a genetic algorithm to try and find other weights. I'll cover that process later on.
Here's an example implementation:
Minimax and Negamax
The minimax algorithm is an algorithm which recursively searches through possible moves that each player can make in an attempt to find the best possible move. The AI player will branch out for each possible move it can make. For each move, it will then repeat that process from the opponent's perspective given its new available moves, then for each of those moves, return back to itself and consider moves, etc., until a certain depth has been reached, such as 4 moves. Once that depth has been reached, it will take that final board position after those moves would have been made and runs the heuristic function on it. In the diagram here, the AI player has even numbered depths 0, 2, and 4, while the opponent has odd numbered depths 1 and 3. At each even depth, the AI favors the highest scores, and at each odd depth, it knows the opponent will favor the lowest scores, leading to a path which we can consider to be balanced between the two players.
For each node on each depth, we need to calculate the possible moves which are available to the player at the given depth. If we say there are 30 possible moves for each depth, the number of nodes after looking at 5 moves is 25,137,931. This means we need to evaluate the possible moves for 837,931 board positions and run the heuristic function for the other 24,300,000 board positions. This is why it is imperative that both the calculation of possible moves and the heuristic function are as optimized as possible. There are other optimizations we can put in place to eliminate nodes from the search space which I'll cover below.
The negamax algorithm is a variation of the minimax algorithm. Chess is a zero-sum game, meaning that one player's gain is equally and oppositely equivalent to the other player's loss. There is no sense of cooperation or mutual benefit if the players work together. This allows us to slightly simplify our implementation of the minimax algorithm by negating the heuristic score at each point instead of writing code from the perspective of each player.
Implementing the Alpha Beta Pruning Optimization
Alpha-beta pruning is a process which reduces the search space of the minimax algorithm by ignoring moves which the opposing player would certainly not make if it were playing as efficiently as possible. The algorithm keeps track of two additional variables alpha and beta. Alpha represents the max score found so far at any given point in the search and beta represents the min score found so far at any given point in the search. If the current player in the search is white and it finds a value greater than or equal to beta in a child node, it will stop searching subtrees since it knows black would never move through this branch. If the current player is black and it finds a value less than or equal to alpha, it will similarly stop searching. This optimization greatly reduces the number of nodes the AI needs to search through.
Optimizing by Sorting Possible Moves Ahead of Time
With alpha beta pruning in place, we can attempt to sort the available moves ahead of time to try to prune as many subtrees as possible. My implementation uses the heuristic function to sort moves ahead of time. These scores are not as valuable as scores determined after exploring future moves, but serves as a good start for pre-sorting moves. Running this heuristic over all of those nodes does add additional computation, so I've created a lightweight sort heuristic which only performs a portion of the analysis of the main heuristic.
Implementing the Transposition Table Optimization
In Chess, it is possible to reach a board state using many different combinations of moves. We can further eliminate nodes in our search space by storing previously evaluated positions. If a position has been previously encountered, and the depth in which it was encountered is lesser than the current depth, we can use that score instead of recalculating it for ourselves. It's important to keep the depth in mind because we don't want to trust a previous heuristic evaluation if it looked less moves ahead than we are about to. This would lead to less reliable heuristic scores and lower the quality of move selection. This adds space overhead but is generally worth the savings in execution time.
Implementing Iterative Deepening
Iterative deepening is a process where the depth first search starts with a depth of 1, then iteratively performs searches for depths 2, 3, etc., either until we reach a max depth or until a time limit has been reached. There is some redundant computation of possible moves (which I plan to address if I can), but we are compensated by the fact that the best move might be found in lower depths plus the fact that the transposition table keeps track of previous scores, thus become more effective as we move into lower depths. If the time limit is reached while a certain depth is still being processed, we'll only use the best move found so far from that depth if it is better than the one we already have from the last fully completed depth.
Creating a Genetic Algorithm to Find Heuristic Weights
In an attempt to find the optimal weights for my heuristic function, I created a genetic algorithm to try and find the best possible weights. The algorithm created many instances of the heuristic function, each with its own randomly assigned weights plus one I created by hand, then had them compete in a multi-round tournament to find the winners. Low performing heuristics would be pruned. High performing heuristics would make it to future rounds and would "reproduce" to create new heuristics which attempt to combine the best elements of the winners. Randomly generated heuristics would be created to fill in the remaining empty spots. At the end, I took a few of the winners and included them in the engine. The genetic algorithm is not used by the minimax AI itself, it is a separate script I've run manually to try and find values. Since it was playing real games of chess, it took days for the entire tournament to complete.
Here's an example implementation of a population which reproduces based on AI game wins/losses:
Creating the UI
I've not included the UI portion in the Github repo linked above. It is a simple board representation which I've created in Angular in the same repository as my frontend website itself. I created three modes:
- Board and Moves: view both the board and the list of moves which each player has made. This is the typical experience on chess programs.
- Board Only: view the board without the list of moves.
- Moves Only: this is an interesting mode which shows the list of moves without the board. You enter moves you'd like to make in algebraic notation. I've created this mode for anyone who is interested in trying to play Chess purely mentally by visualizing the board.
The Chess pieces are not images, they are actually typeable text characters.