CHESS BOT
Status
Start Year
Duration
Development Platform
Technologies / Concepts
Complete
2022
2 Weeks
Native C++
C++, SDL2, Mini-Max, Alpha-Beta Pruning
OVERVIEW
This was my application piece to get into my Graduate program, and it was a great experience to dive into some AI concepts that I otherwise have not had the opportunity to.
While I have had plenty of chances to deal with other more common AI such as pathing/steering algorithms and decisions trees, turn-based AI is something I would definitely be interested in working on again in the future.
This piece in particular was made before I had a deep understanding of C++, and thus it is more closely resembling of C with classes with much of the true power of C++ being underutilized. Given more time to work on this project I would like to see how much better it could get with my current knowledge.
Chess Bot is playing Black, I am playing White
The base algorithm used for this AI was the mini-max algorithm. This algorithm is essentially a post-order traversal calculating moves forward to a certain depth.
At each node, the board position is analyzed to determine who’s position the board favors. Factors considered include number and value of pieces on the board as well as how optimally pieces are positioned (pawns near middle or opponent’s side, knights near center of board, etc.) and a value can then be determined to set the value of the position and which side it favors.
However, the game of Chess is not played by just what player, and thus moves need to predicted based on the best move available to the player that is actually the one making the move. For example, if there are two positions to choose from with one favoring White and the other Black, the board that would be considered is completely dependent on who’s turn it would be.
My Chess Bot sees a good move ahead
By first calculating the lowest level of the tree based on the desired depth, we can then determine which moves each player would choose going back upwards the tree.
Once the base algorithm is complete, my entire focus then shifted to optimization.
The first technique I implemented was Alpha-Beta pruning. This allowed certain position calculations to be skipped based on if a better option has already been discovered previously during the current iteration.
Given more time with the algorithm, I would have liked to implement other optimizations such as hashing and caching positions so that way converging moves would not be calculated more than once.
Additionally, I would also be interested in adding opening move prep. Since the engine cannot see that far ahead, much of the advantages and disadvantages with certain openings cannot be seen by it. I would like to give it a library of opening moves to give it a wider variety of tested opening options.
An uneven trade leaves me down a pawn
WHAT I LEARNED
This was one of the most enjoyable projects I have worked on to date, as taking a deep dive into this niche type of AI provided so many different avenues to learn.
Although I saw many different additions that could have been made to the algorithms themselves, looking back on the project I feel as though the most could be gained from instead applying my current knowledge of C++ to better utilize the language. There are plenty instances of inefficient copies and unused opportunities for better data management that I feel I would more so benefit the project than adding on to the algorithms themselves.
All that being said, my Chess Bot is good enough to beat me more times than not, with myself playing at around 1100 rating.