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.
I already spoke about this briefly in this post. Currently my chess engine will make all possible moves for a position ahead of time and evaluate each resulting chess board before entering Alpha Beta. Although this gives me an almost perfect sorting algorithm (just sort the fully evaluated positions), on a whole this design is not very efficient. The problem lies in the fact that often the algorithm will be evaluating moves that I will never explore due to an Alpha Beta cut-off. Imagine having 30 possible moves, making each move, and evaluating the score of the resulting position, just to later find out there is a cut off in the 5th position. This means that I have just evaluated 25 unnecessary positions.
The new design makes one move at a time and generates the next move only after the Alpha Beta call. This means that I need a separate algorithm for sorting, choosing which moves to make first to give me the best chance for a cut-off. This sorting is done by a tested algorithm called:
MVV/LVA Most Valuable Victim, Least Valuable Attacker. This works exactly as it reads, a move where a pawn attacks a queen would be sorted first, king attacking pawn would be sorted last.
I have already implemented this new Alpha Beta and noticed a significant performance improvement over the previous version. The current version with the new algorithm of Chess Bin Chess now searches to ply 6 (from 5) on Medium Setting and Ply 7 on Hard setting. Although previously the Hard setting was already searching to ply 7 it was painfully slow. On ply 7 I can now easily do one move per 30 seconds average.
I will be updating all of the posts with the newest version of the source code over the next few weeks.
Update January 19th 2010 – Well it took longer than I thought but all the posts are now updated to the new faster source code. It took so much longer to debug all the code then expected. I found so many mistakes, however I think now I have a fairly stable and bug free version.
Want to skip to the end, download the full chess engine source code on GitHub