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.

This is the second re-design I am doing on the ChessBin Chess Engine.  You can read all about the first one here, so you don’t make the same mistakes as me.  I guess that is what you get for re-inventing the wheel.  At least I am still having fun. 

This re-construction is related to how my chess engine stores the chess board.  Currently the chess board is described as a two dimensional array.  This way with a column and row you can locate any square on the board.  This is makes my chess engine easy to understand but slow. 

The new design will modify the chess board to be a single array of 64 squares.  This makes it necessary to refer to board positions via an index.  An index of 0 will locate the top left most square on the board and an index of 63 will locate the bottom right one.  This also allows me to drop the entire Position struct as it is no longer necessary to describe the position by two bytes. 

The new version of my ChessBin chess engine that I am currently testing is about 25% faster due to these changes.

I will be modifying each of the posts and the development kit over the next few weeks.  Stay tuned for updates.

Updated April 22nd 2009, I have finished updating all of the posts and the Chess Game Development Kit.

Over the last month I have been focusing on increasing the performance of the move generation code in my Chess Engine.  Based on my tests I believe I have gained about a 25% speed improvement in move generation.

The largest speed gain came from the removal of the Board Column and Board Row members from the Board Square class.  I came to a realization that I have been storing the same information about the position of the chess piece 2 times.  Once in the Board class via the 64 square array indexers and once in the Board Square class in the Board Column and Row variables.  Although having the Board Column and Row specifically in the Board Square class made it much easier to understand my code, at the end the performance loss was not worth it.

Unfortunately this means that I have to modify some of the code listings in previous entries so that the next sections will make sense.  I will eventually also modify the Chess Game Starter Kit to include the newer faster code.

Until then if you are waiting for the next sections of the chess engine, please be patient until I finish updating the previous entries.

2008-Dec-06 Performance Reconstruction is now complete (at least for now)