Thursday, January 2, 2014

A bit of New Years cleanup

I'm planning to do spend some time on my move ordering schema, again. So far iCE is not using  a history heuristic scheme. It only relies on the hash table move and the killer moves.

For this I have to change my internal move representation a bit so I get a few more bits to store the history score. So far I have 7 bits to hold a move ordering score, which allows values from 0 to 127.

My TMove looks like this

*  A Move is stored as a compact 32bit integer
*     off    bits   name           description
*      0      4     movedPiece     the id of the moved Piece
*      4      6     fromSq         the start square of the move   
*     10      6     toSq           the target square of the move
*     16      4     capturedPiece  which piece is captured
*     20      4     promoteTo      which piece do we promote To
*     24      1     enPassent      this move is an en Passent Capture
*                                  this influences the square where the
*                                  piece is captured
*     25      7     order          an ordering score for move ordering
*                                  range 0 .. 127

This includes some redundancy. The piece we promote to is stored in 4 bits because the actual piece type is directly stored here. In reality I can only promote to a knight, bishop, rook or queen. The color of the promoted piece is the same a from the moved pawn.  So I only need to code 4 states which require 2 bits

This means with some conversion work I can save 2 bits here, which I can reassign to the ordering value.

I changed and debugged my code and now I'm ready for some more move ordering exercises.