You can find the full source code for this tutorial in my GitHub repository.
The final product is playable at https://zeyu2001.github.io/chess-ai/.
You should know basic programming and the general concept of a tree data structure. Everything else will be covered as part of this tutorial.
The two main algorithms involved are the minimax algorithm and alpha-beta pruning. These will be explained in-depth later on, and should be relatively simple to grasp if you have experience in programming.
Getting the GUI and game mechanics out of the way. This allows us to direct our focus towards only the most fascinating aspect of the application: the decision-making (AI) part! For this, we will be using external libraries:
chessboard.js handles the graphical interface, i.e. the chess board itself.
chess.js handles the game mechanics, such as move generation / validation.
With these libraries, you should be able to create a working chess game by following the examples (5000 through 5005 in particular) on the chessboard.js website.
Great! We have a functioning chessboard. But how do we implement an AI that plays (reasonably) good chess? Well, we’re going to need an evaluation function. Basically, we want to assign a ‘score’ to each chessboard instance (i.e. each set of positions of pieces on the board) so that our AI can make decisions on which positions are more favourable than other positions.
Chess is a zero-sum game. Any advantages gained by Player A implies disadvantages for Player B. Advantages can come in the form of capturing opponent pieces, or having pieces in favourable positions. Therefore, when assigning a score from our AI’s perspective, a positive score implies an overall advantage for our AI and disadvantage for its opponent, while a negative score implies an overall disadvantage for our AI and advantage for its opponent.
For instance, the score for the starting position is 0, indicating that neither side has an advantage yet. Later on into the game, we are faced with a decision between two moves: Move A and Move B. Let’s say Move A captures a queen, putting our score at 900, while Move B captures a pawn, putting our score at 100.
The AI will be able to compare between the two potential scenarios, and decide that Move A is the better move. Of course, this does not consider future ramifications — what if Move A gives our opponent the opportunity to attack? We will overcome this hurdle in the following sections by performing lookahead to anticipate subsequent moves.
The first aspect of our evaluation involves assigning weights to each piece type. If our AI plays from black’s perspective, any black pieces will add to our score, while any white pieces will subtract from our score, according to the following weights:
We now have a score based on which pieces exist on the board, but some positions are more favourable than others. For instance, positions that grant higher mobility should be more favourable. For this, we use *piece square tables *(PSTs), which assign an additional score delta to each piece based on its position on the board.
For instance, the PST for knights encourages moving to the center:
This is from white’s perspective, so it would have to be reflected for black.
I certainly am not a chess expert, so the piece weights and PST values are adapted from Sunfish.py. The following is my implementation of the evaluation function. Note that instead of iterating over 64 squares for each evaluation, we simply start from 0 and add or subtract from the score according to the latest move, keeping track of the previous score.
Now that we have an evaluation algorithm, we can start making intelligent decisions! We will use the minimax algorithm for this, and I highly recommend reading up on the Wikipedia article to better understand this decision strategy.
We can represent chessboard positions as nodes in a *game tree. *Each node is a chessboard instance, and has children corresponding to the possible moves that can be taken from the parent node.
Essentially, minimax aims to minimize the possible losses, assuming both players are rational decision makers. We can represent the possible moves as a game tree, where each layer alternates between the maximizing and minimizing player. We are the maximizing player, attempting to maximize our score, while the opponent is the minimizing player, attempting to minimize our score.
At the leaf nodes, the evaluated score is backtracked. Positive and negative infinity are wins and losses respectively. At each recursive layer, the maximizing and minimizing roles are alternated. Layer 0 is the current game state, and the goal is to maximize our score.
The question our AI has to answer is: “Out of all the possible moves at Layer 0, which guarantees the maximum score?”
This is the same as asking, “Assuming my opponent is always making the most optimal decisions, which move leads to the possibility of attaining the best possible score?”
If we want our AI to be any decent at chess, we would have to perform a lookahead to anticipate our opponent’s subsequent moves. Of course, we can only anticipate a couple turns in advance — it’s not computationally feasible to look ahead as far as the final winning or losing states. We will have to introduce a depth limit that corresponds to the number of turns we are willing to look ahead, and use our evaluation function to determine the favorability of game states once we reach the depth limit.
This is a fun recursion problem, and I recommend trying to implement it yourself, although my implementation can be found below. If you're stuck, here’s the general idea:
We decide on a predetermined depth limit, k.
At Layer 0, we consider each of our possible moves, i.e. child nodes.
For each child node, we consider the minimum score that our opponent can force us to receive. Then, we choose the maximum node.
But to know the minimum score that our opponent can force us to receive, we must go to Layer 1. For each node in Layer 1, we consider their child nodes.
For each child node (possible move by our opponent), we consider the maximum score that we can achieve subsequently. Then, the minimum score that our opponent can force us to receive is the minimum node.
But to know the maximum score that we can achieve subsequently, we must go to Layer 2.
And so on…
At Layer k, the final board state is evaluated and backtracked to Layer k - 1, and this continues until we reach Layer 0, at which point we can finally answer: “What is the optimal move at this point?”
Here’s my implementation. Note that I used a slightly modified version of chess.js, which allows me to use
game.ugly_move() to generate and make moves without converting them to a human-readable format, improving the efficiency of the algorithm. The modified version can be found here, but using the normal
game.move() will work just fine too.
Our AI should now be able to make reasonably good decisions. The higher the search depth, the better it will play. However, increasing the search depth drastically increases the execution time. Alpha-beta pruning helps to improve the algorithm’s efficiency by ‘pruning’ branches that we don’t need to evaluate. An additional reading resource can be found here.
The core idea of alpha-beta pruning is that we can stop evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move.
Suppose that the game tree is as follows:
For brevity, let’s consider the following subtree:
The maximizing player first considers the left child, and determines that it has a value of 5. Other paths will only be chosen if their value is
x > 5.
Next, the right child is considered. The minimizing player, at the right child, has found the values 7 and 4 so far. But then this means that regardless of what the remaining value is, the minimizing player would end up with a minimum value of at most 4. We know the final value of this subtree would be
x <= 4, regardless of the remaining value.
In order for this path to be relevant,
x > 5. But we know that
x <= 4. This is a contradiction, so the maximizing player wouldn’t choose this path and there is no point evaluating this path further.
The same idea can then be extended to the rest of the game tree. We use two variables, alpha and beta, to keep track of the maximizing and minimizing values (5 and 4 in the previous example) respectively. This only requires minor modifications to the previous minimax function — see if you can implement it yourself!
Here’s my implementation:
That’s all! I hope you have enjoyed reading this article as much as I have enjoyed writing it. I’ve explained how I implemented my AI, and hopefully introduced several new and interesting concepts to you.