Take a look below the game to read more about how it was created, find out what I was able to accomplish in my one week timeframe, and see a video of me losing to the engine that I created.
Try to beat the Crooked Rook at his own game but be careful ... he cheats!
The general idea of a Chess engine is for the AI to "look ahead" a certain number of moves in order to find the action that maximizes it's own position or strength. The complexity comes into play when accounting for how the enemy, the human player, will try to minimize the AI's position.
Position is determined by two factors, the first being that each piece has an assigned value. The pawns for example are valued at 100 while each king is valued at 20,000. In addition to these static values, each piece has a seperate piece-square table that promotes specific places on the board by adding or subtracting value. For example, the king is encouraged to stay in a defensive position while the knights are encouraged to maximize their movement options.
Taking the position evaluation functions into account, when it becomes the AI's turn, it loops through each available move, attempting to maximize it's position by moving pieces to better squares or by capturing. If the desired depth of evaluation is greater than zero, then for every move the AI can make, it will also loop through each available move for the human player. If the depth permits, then the next stage is to evaluate each of the possible moves the AI could make in response.
The more moves ahead the AI can look, the stronger it will be. Unfortunately, there are just too many moves in the game of Chess for each possible scenario to be evaluated all the way to the end of the game. Luckily, a pruning system is in place to limit the number of moves that are evaluated. The idea is to compare current positions against previously evaluated branches in order to determine if they're even worth pursuing.
If you'd like to learn more about the code that make all this possible, check out the source code for the Crooked Rook here. For anyone looking to create their own Chess engine, I received enormous benefit from the Chess programming wiki found here.
With the correct implementation of Alpha-Beta pruning and some unique check avoidance, I enabled the engine to comfortably play up to a depth of five. The number of positions evaluated at different stages of the game is still unbelievable. For example, by about six moves into my most recent game with the Crooked Rook, it evaluated 2,023,878 positions in just under 8 seconds before moving a piece.
I started the project by creating a simple grid system that would allow me to move pieces based on the rules of Chess. I was excited to get something working quickly, but later on in the process I became inhibited by my earlier design. For example, I failed to add the fundamental capability of castling kings. Based on my structure for determining valid moves, it would have taken me at least two days of working time in order to add the ability. I do think my system works very well for what it is, but I would like to try a different way in the future.
Ideally I would alter the evaluation functions throughout different stages of the game. Right now the positions are all based around early game without additional piece-square tables to transition to.
There are countless improvements I could make to the AI itself, and many of them I plan on incorporating into the next version. The most important thing with a Chess engine is to increase the depth of evaluation it is capable of reaching. An example of an improvement that would help is sorting the moves evaluated instead of looking at each piece arbitrarily.
Credit for the pieces I used can be found here.