Chess AI

In the month of May, I was stuck inside due to the coronavirus restrictions, during which time I decided to learn python. It was a language I wanted to learn for a while at this point and with my newfound free time, I was able to do it. Since I now have a new language under my belt, and some experience in creating applications, I wanted to try my hand at something slightly more complicated. The game of chess is something I have been interested in since childhood, I started playing around age 5, and even took classes in school to learn more. As I grew up, I turned to the usage of engines and other such software to hone my skills and learn more about the game. When I became more interested in programming, I always had in the back of my mind that I would like to create a chess engine one day, and eventually I was skilled enough to take on the venture.

Before any engine could be created, I first had to create the graphical user interface on which the game can be played. I did some research on graphics libraries in python and decided to use the Tkinter library to create the board. Above is an image of the code segment used to create the board. The tag_bind function shown on the last line is used to bind each square to a function call that takes the square's coordinates as its parameters. This is done to create a "on click" mechanism that can be used to perform actions on the board when a specific square is clicked. After the board was created, the next step was place the images of pieces onto the board; I downloaded free piece images and put them into their own file. An example of piece placement can be found below.

This specific example only shows the placement of the white and black pawns. As can be seen in the last two lines, the images must be re-bound since the image is placed over the graphical square rather than laying on top of it; with that the GUI was finished. The image of the board is shown below.

Once all the pieces are placed, I decided that I should create a piece class that can store the location, name, colour and piece value; this was made to work with the binding function. Since each square is bound to the click function along with its location, the object that exists on that square can be identified. The class describing the pieces can be found below.

An example of what happens when a square is clicked is shown below. The bottom left corner of the starting board contains a rook and the system internally corresponds to the item as the square is clicked. With this development, the rules of the game can now be implemented, since the system now understands the position of the pieces.

The next step was to create a method in which moves can be made. My solution to this was to use the click function along with a global boolean variable. On the first click, the move is engaged by storing the item to be moved, this makes the move variable true, which allows the piece to be moved to the destination square upon the second click. The problem with this is that the piece can be moved to any square, including the square on your own piece resides. To prevent this, the legality of moves must be checked in order to only allow moves that are legal. The code segment that checks for legality can be shown below.

The above image shows the calling of the isLegalMove function which calls the individual functions for each piece to check if it is legal. These checks include moves such as en pasent, and castling. The function returns whether or not the move is legal and also if the move was a capture. The function also returns the image of the piece, since it must be placed again over the graphically drawn square. The final piece was to create a way in which to find checks, and not allow for moves to be made given that the player is in check, or that the move will put them in check. This is done by creating a function that takes a piece and a secondary square and returns whether or not the square is attacked by that piece. This logic was applied to check if any piece is attacking the opposing sides' king. If so, the player is in check, and their king will be replaced with a king on a red square, indicating check. With this, the pieces can now be moved legally to allow for a two player game. An example can be found below.

The next step was to create the engine portion of the software. To do this, I decided to use the minimax algorithm to create a search tree of moves. The algorithm works by maximizing the benefit to oneself by minimizing the maximum possible damage that can occur when a move is made. All possible moves are made internally, and checked using this algorithm to find the move that gives the most benefit. This can be implemented by creating two functions, a maximizer and a minimizer which call each other recursively; one function makes a move internally, then evaluates the board to find a value higher than the recorded highest value. When such a move is found, the other function will be called to make a move to find the lowest value. This function calls the first function again until the given depth is reached. This way, the game is played internally by the engine to check for the best possible move. The engine function can be found below.

Originally, the evaluation was based only on piece value defined by the piece object. The issue with this is that chess is not played based upon the value of pieces alone. There are many strategies to the game including control of the center, or pawn structure. To create a more comprehensive evaluation function, I added multiple heuristics to the function; these include heat maps to determine superior placement, as well as superior positioning for square control. Square control implemented the same function used to find checks. Rather than passing the king as the defending piece, any square, empty or not can be used to see if it is attacked by another piece. This allows for the engine to play in order to control squares as well as win pieces. The evaluation function can be found below.

The problem with this approach is that although it is theoretically invincible, it is not the most practical approach. This is because realistically, a depth of three is the only depth that can be played without taking unreasonable amounts of time. This sounds good for the start of the game, however the engine begins to miss easy strategies that can obviously be seen to someone, such as multiple captures. However, this type of play would not be seen by the engine since it can only see three moves ahead. Even more dangerous would be an advanced strategy that the engine also could not see due to the limited depth. My solution to this was to apply artificial intelligence to the engine. Personally, I was inspired by Google's Deepmind, and their creation of AlphaZero, a chess engine that was created using neural networks. AlphaZero trained for four hours and was able to become arguably one of the most powerful chess playing entities in history, even beating the current computer chess champion Stockfish in a match of 100 games. Stockfish is a traditional engine that uses heuristics based upon tree searches. This is much more advanced compared to my minimax version, and was quite frankly, out of my expertise. Stockfish is highly precise, and requires hours of adjustment in order to obtain the perfect move. I personally was much more interested in the neural network approach, since it was not only a concept I wished to learn, but also less demanding from a work sense. This is because a traditional engine requires many hours and many small changes in order to get the best engine, a neural network on the other end can be trained without my personal assistance. With this I began researching neural networks and how to apply them. I came across the library Tensorflow, Google's own library for deep learning. A neural network is a mathematical representation of how the brain learns. The structure contains layers of "neurons", which in this case are nodes with specific multipliers. A matrix is passed through to the input layer, which is manipulated by each node and passed to the next, eventually there is an output corresponding to the output function. Such a system is trained by having the network randomly assign node values, and checking against the real answer. The system then back propogates in order to adjust each node so as to create a one size fits all combination of nodes. I began by using keras from Tensorflow in order to predict the function x^3.

As can be seen, the prediction is not perfect, but it is close enough for my own satisfaction. With this, I was able to move onto the next stage and train a neural network to play the game of chess. I decided that I could not develop this engine on my computer at the time, since it was very slow, and could not support the training of such a model. I discovered that Google Colaboratory allows for users to run python programs on their own servers, and would therefore not burden my local machine. I began creating the software to train the model on Colab; below is an image of the code segment showing the creation of the neural network layers.

I began by converting the internal board into an ascii array; this is what would be inputted into neural network and at first I decided that such an array would be outputted as the networks prediction. The issue with this was that the output was way off most of the time in that it would either misplace characters or even use other invalid characters. I needed to think of a manner in which the network could output the move that it wished to make. To fix this, instead of using a relu activation function to output an ascii array, I came up with a solution to use the softmax function to display its confidence in making all possible board movements. This is to say that there are 64 squares on which pieces can be, and 63 places that the piece could be moved to. Although most moves aren't legal, I decided that I could use modulus and division in tandem to decode a singular number into four coordinates. The logic is very simple; the number one corresponds to moving the piece on the bottom left to the bottom left. This seems pointless, however without including the same place movements, there is no way to keep track of the relative movements. The number two corresponds to moving the bottom left piece up one, and so on. When the bottom left piece is to be moved to the top right, the number is 64, which afterwards goes all the way back to the second piece on a2. Now moving a2 to the bottom left would be the number 65, since it represents over a full lap of the first pieces' movements. This method is continued until the number 4096 (64*64), which corresponds to moving the top right corner to itself. This method allowed me to have 4096 output nodes, which when used with the softmax function represents how confident the engine is in that move. The move the network is most confident with can then be moved; the code segment showing the reversing of coordinates into a single number.

The model was trained using data from an online database. The games I found consisted of games played by high level engines and grandmasters; this would ensure that the moves that the network trains with are highly accurate. The implementation of this model was relatively simple. Simply take the network's prediction on the current board state, and filter out moves that are not legal. After this, find the move for which the network has the greatest confidence in, and play the move. A code segment of this can be found below.

The issue with this approach is that chess is an extremely complex game. In the opening, the network is textbook. This is because opening theory is very precise and has not changed for a very long time. This makes it so that the network has learned how to play an opening with exact precision. The problem occurs once the game leaves the opening. It is predicted that there are more games of chess than there are atoms in the universe. This makes it so that every single game of chess played is a unique game that has never been played and most likely will never be played again. This makes it so that once the game advances, the network begins to make very bad moves. My solution to this issue was to combine both the minimax version as well as the neural network approach to create a MCTS version. The Monte Carlo tree search method creates a search tree that is weighted based upon a prediction from a neural network. The advantage of this method is that instead of searching all possible moves, the neural network can pick out its five best moves to search through in order to allow for higher search depths. This was implemented with similar logic; the networks moves are filtered for legality, and instead of looping through all possible moves in the minimax algorithm, it loops through the five best moves. With this final MCTS version, the chess AI project has come to an end. I learned a lot about search trees and especially about deep learning, More importantly, I was able to apply my new found python skills by using graphics, object oriented concepts, and artificial intelligence concepts.