Performance Reconstruction Phase Three

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