Building a Simple Chess AI

I’ve been wanting to build a chess AI for a few years now. I was excited by the idea of building a program that could its own decisions and learn from those decisions. I was finally able to build my own chess AI. You can play it here: https://zm2231.github.io/coding/2019/05/10/game.html or by going to the home screen and navigating to the page called Chess AI Game

Want To See How It’s Built? In the rest of this article, I’ll walk you through the different skill levels of the program, and how I implemented them, so you can make your own AI. I have included links where you can understand some of the theories/programs I discuss in here. Each iteration has increasing “intelligence”, which allows it to make better moves which is due to the different methods and how many moves ahead the program is thinking.. I’ve included all iterations as functions within my code. If you’d like to see the full code, you can view it here: https://www.github.com/zm2231/ChessNeuralNet The file which contains the code for calculating moves it located here: https://www.github.com/zm2231/ChessNeuralNet/blob/master/public/js/movecalc.js

Quick Explanation of Programs Used

The main program used here is Minimax. The word derives from the game theory of minimizing your loses and maximizes your wins. To explain this in a game, such as tic tac toe, the minimax algorithm will choose the best move through weights and the algorithm along with evaluating all possible outcomes for each move. It then choses the move that has the most opportunities to win.

Negamax is a slight simplification of minimax, and its code implementation is based on the principle that an opponent who is using a perfect strategy will be looking to make the inverse of a minimax move, thus their move will be the NEGAtive of your MAXimum move. Alpha-beta pruning is a variant of minimax that runs slightly more efficiently because instead of evaluating every single POSSIBLE move, it stops evaluating all subsequent moves after it has been found that a move is worse than a previous move. This will all make sense later.

Setup

The goal of this project is to build the chess AI, but I still needed to make a board, visuals and make sure the program knows the rules of chess. So, I created two different programs files that help with this. I have done something like this before, so I used the same chess.js that I made for a friend a while ago. chessboard.js handles creating the visuals (the chess board and pieces), as well as the interface for when a user makes a move (dragging pieces to a square). chess.js is a library which is used for chess move generation/validation, piece placement/movement, and check/checkmate/stalemate detection – basically all of the rules of chess. I also created 3 JavaScript files which handle different aspects of the chess AI:

  1. boardconfig.js – sets configuration for chessboard.js, and creates an instance of the board and chess game
  2. movecalc.js – contains the functions which calculate the move to make
  3. main.js – contains functions for initiating the computer to move Now, let’s discuss the move calculation functions. I’ll discuss each iteration that I built.

Iteration 1: Random Moves

Making random moves This first iteration has no real experience in playing chess, but it was quick to make. The AI simply finds all possible moves and randomly picks one. The main point of this iteration was to check to see if my board configuration file and rules in chess.js file works.

Iteration 2: Choose Best Move, Looking One Move Ahead

Looking one move ahead This next iteration starts adding some decision making to the chess AI. It looks at all possible moves it can make this turn and evaluates it’s position after each move and then makes the best move it can see. To implement this iteration, two functions are required:

  1. A function that evaluated the position
  2. Function to evaluate the outcome of each possible move Position Evaluation Function In chess, you can evaluate a current position to see which player is ahead. This will then allow the AI to basically say, “Move A leads to a position of -25, but move B leads to a position of 75. So, I’ll choose move B because I get more points. ” This is through weights that each piece is assigned. There are many ways to calculate this, but for this chess AI, we’ll use a relatively simple function to figure this out: So, having pieces will add to your score but the opponents score will subtract from the score. So, the return value will be the player’s position relative to its opponents. What about the value for each piece? There are several you can assign these values (https://en.wikipedia.org/wiki/Chess_piece_relative_value), but I decided to go with Larry Kaufman’s suggested values for the middle game, multiplied by 100, so there are no floating numbers to deal with: • pawn = 100 • knight = 350 • bishop = 350 • rook = 525 • q = 1000 • king = 10000 The function, shown below, takes the array that is returned by chess.js’s function chess.board(). The function then goes through each piece and adds the piece if its color matches with your color or subtracts from the. However, this board evaluation still has multiple flaws. For example, it evaluates an activated bishop the same as it evaluates a bishop in the starting position. For now, though, it should do the trick.

Evaluate All Possible Moves This function works by taking the position evaluation to see every possible move. I’ll build upon the random move function from the previous iteration. Instead of randomly choosing the move from the list of possible moves, the program will, in its head, go through every move and evaluate the position while evaluating the score. At the end, the function, which has been tracking the best possible move, will make that move. You’ll notice that I randomized the order of the possible moves. Without randomization the AI will choose the first move in the list. This leads to the knight moving, then the rook moving back and forth until a piece comes close enough to capture or the game is drawn by the opponent.

Iteration 3: Looking Multiple Moves Ahead

While the last iteration now forces the computer to capture pieces, it is still not up to par. Because the chess AI is only looking one move ahead, it can’t see ahead that far on what their opponent is planning. So, when it moves a piece, it can’t tell if that piece might be taken seconds later. So, in this third iteration, we’ll give the AI the ability to look more than one move ahead. To implement this, we’ll use an algorithm called Minimax. I’ll explain what Minimax is, and then show my implementation. Minimax Here is a quick Wikipedia of what minimax is: https://en.wikipedia.org/wiki/Minimax. You’ll even find a pseudocode example there. Basically, minimax is an algorithm that evaluates all possible moves and follows that move to see what your opponent will do. However, you can make it so the program evaluates however many moves ahead you want to. To further understand this concept, it helps to create a tree. In this instance, we are starting with the maximizing player, and looking 2 moves ahead:

Each square is a node when the maximizing player chooses a move, and a circle is a node when the minimizing player chooses a move. We can follow the tree and see the outcomes for each possible move lead to these positions: 100, -100, 0, and 10. The player will, naturally, try to achieve an outcome of 100 which will get the opponent a negative -100. So, if the player plays a move that is 0 points, the opponent has to play a move that leads to 0 to effectively counter the opponents move.

Implementing Minimax

Just as we did with the iteration looking one move ahead, we’ll still loop through all possible moves, but the value will be the final board position. For this, we’ll need to use recursion. Each recursive call, we decrease our depth by 1, until we get to a depth of 0, at which point we evaluate the position. These values trickle up and allows the AI to pick a move that leads to the best position. One thing to remember: we are evaluating from the viewpoint of one player. So, when we enter a recursive call and are evaluating as the opponent. The opponent is choosing a move that leads to the MINIMUM value. Hence the if/else statement.

Iteration 4: Minimax with Alpha Beta Pruning

At this point, the AI can make relatively good moves, protect its own pieces, and look far ahead to make a strategy. The only problem is the algorithm takes a very long time. That’s because of the number of branches it needs to evaluate. In order to remove the time it takes to go through possibilities, I’ll use alpha beta pruning. What Is Alpha Beta Pruning? When I was researching alpha beta pruning, I found these notes to be the best resource possible: http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html If you want to see how alpha beta pruning works, there are some great notes at the link above. But on a very high level, the idea is that we can eliminate branches when searching through the tree of moves, which makes our evaluating much faster. Take this tree as an example:

We start on the first branch, and come up with a 3, so that trickles up. We then go down the second branch, and the first move the min player comes across is a 2. But we run into a problem. The max player already found a branch with a 3. So unless there is a value in the other branch greater than 3, the max player won’t choose it. So we need to find a value greater than 3. But because the min player is choosing and already found a 2, they only want to find a value less than 2. So we are looking for: x < 2 and x > 3 That doesn’t exist, so there is no point evaluating further down this branch. In this example, there’s only 1 other branch, but in our chess game, this could be many more branches as we trickle down each move. Alpha beta pruning saves a lot of time! Implementing Alpha Beta Pruning This is just an extension of our Minimax implementation. We simply add in variables to track alpha and beta. We start with default alpha and beta values, but within each recursive call, we pass the alpha and beta values as they currently are. And as these values trickle up, we use min and max functions to compare them to the values and change the alpha/beta values. Finally, if we find we are on a branch when alpha is greater than beta, we know we are on a branch that isn’t a candidate and prune it.

Final Thoughts and Way To Improve

The final iteration here is actually a pretty good chess player. But it still has many limitations. The biggest: it is still very slow. Having the computer look 4 or more moves ahead is still really slow. The AI could be much better if it could look more moves ahead, but it would take an ungodly amount of time. One way I’ve considered to improve speed is to organize the possible moves. Right now, they are randomly organized before evaluating. But if they were organized with the best potential moves first (such as ones that capture pieces), alpha beta pruning would be able to eliminate more branches. But the sort function may take more time than is saved. Another issue is the position evaluation function. Currently, it is based on how many pieces are remaining on the board. But it does not take the piece position into consideration. Going forward, there are other algorithms I’d like to try to solve these issues, as well as attempt to incorporate some form of machine learning.