An Alpha Beta search will often have to consider the same position several times. This occurs due to the fact that in chess there are many ways to reach the same piece arrangement. For this reason most chess engines implement a Transposition Table that stores previously searched positions and evaluations.
It’s this time again. The time where I realize that I made a poor decision somewhere in my design and a small portion of my code has to be re-written.
Over the last year of development of my chess engine, much of the time has been spent optimizing my code to allow for better and faster move searching. Over that time I have learned a few tricks that I would like to share with you.
Now that we have all the necessary parts for keeping track of our chess pieces, generating valid moves and searching for the best computer move, we are ready to put it all together and complete our chess engine.
In this post I am going to discuss Forsyth-Edwards Notation (FEN) and its implementation in a chess engine. FEN is a standard way of describing a chess position, containing enough information to restart the chess game from that position. It is based on a notation developed by a Scottish journalist, David Forsyth in the 19th century.
Now that we have discussed the basics of Alpha Beta we can add some small modifications to increase the strength of our move searching and solve the problems of the Horizon Affect
Last time I discussed Min Max and the Alpha Beta algorithms. However you might have noticed that the algorithm I showed last time does not really tell you which of the available moves is the best, but rather which was the best score out of all the available moves. To figure out which resulting chess board is the best I have implemented another method called Alpha Beta Root.
Out of all of the computer chess programming concepts I discussed on this website I found move searching to be the most complicated for me to understand, and the most time consuming to write.
Before we can discus move searching and the Alpha Beta algorithm we need a way to check for check mates. This method will actually be located in our static Search class. This method will loop through all of the moves for all the chess pieces on the board and see if they actually have a valid move.
From what information I could gather on the internet, it seems that most experts agree that the evaluation function of a chess engine has the greatest capability to dictate the strength of your chess game