Material signatures and std::map

iCE uses material signatures to classify material combination where it has special knowledge for. It uses a simple enumeration as id for certain material combinations

// ENDGAME IDENTIFIER FOR KNOWN ENDGAMES WITH SPECIAL MODULES
enum EEndGameId { EG_UNKNOWN, EG_KK,
                  EG_KNK, EG_KBK, EG_KRK, EG_KQK, EG_KPK, ...,  EG_MAXCOUNT };

Simple stuff so far. The interesting part is the code that assigns the correct id to a position. So far iCE was using the trivial approach. It just performed a long list of comparisons.

switch (bb.pcsCount)
{
case 2:    return EG_KK; break;
case 3: 
if (bb.pcsTypeCnt[W_KNIGHT] == 1 || bb.pcsTypeCnt[B_KNIGHT] == 1)  return EG_KNK;
if (bb.pcsTypeCnt[W_BISHOP] == 1 || bb.pcsTypeCnt[B_BISHOP] == 1)  return EG_KBK;
if (bb.pcsTypeCnt[W_ROOK] == 1   || bb.pcsTypeCnt[B_ROOK] == 1)    return EG_KRK;
if (bb.pcsTypeCnt[W_QUEEN] == 1  || bb.pcsTypeCnt[B_QUEEN] == 1)   return EG_KQK;
if (bb.pcsTypeCnt[W_PAWN] == 1   || bb.pcsTypeCnt[B_PAWN] == 1)    return EG_KPK;
break;  


This was ok as long as the number of modules was rather small, but over time I added more and more knowledge to iCE and this list grew. Currently iCE has special code for 40 endgames. So the above list was already rather long. It was not really a performance problem. The code is executed only when the material on the board changes and often it just stays as it is. But such a long list is not really elegant.

I considered three alternatives.

1.)
Using a table where I store the endgame ids which is indexed by the lower part of the material hash key. This should be very fast as it is just a look-up. I determined that for my kind of material hash keys I need a table of 8192 slots to allow a collision free perfect hash as long as I restrict the signatures  to 5 men or less positions.  This is currently the case but might change in the future. When adding 6 men positions the size of the required table for a perfect hash will be much bigger.

2.)
Storing the material hash keys of the interesting positions along with the id in a sorted list and then do a binary search in the list. This is a very compact data structure, search will take a bit longer.

3.)
Use the material hash key directly as underlying value in the enumeration. But this is ugly.

The implementation for 1 is straight forward. For the the second I used a std::map container. This is pretty cool. You just store pairs and the map gives you easy access to your values. It is a bit more expensive than the lookup table but should not make a practical difference. If it turns out to be a problem in profiling later I can still change it but I doubt it.

At program start I calculate the material hashes of the combinations that I'm interested in and store them in the map. During search whenever the material on the board changes I have a look there

EEndGameId TBoard::calculateEndGameId()
{
    if (bb.pcsCount > 5 || endgames.count(getMaterialHash()) == 0) return EG_UNKNOWN;
    return endgames[getMaterialHash()];
}

Very elegant and I was able to get rid of an ugly module.

1659

The Battle of the Lines of Elvas was fought on 14 January 1659, in Elvas, between Portugal and Spain. It ended in a decisive Portuguese victory.

By coincidence 1659 is the exact lines of code that I removed from the iCE source code while reworking its move generators. The move generation code belongs to the oldest modules in iCE. It was created for version 0.1 several years ago. I was not slow or buggy but my coding style changed over time and it did not fit really in anymore. 

iCE has several move generators for quiet moves, tactical moves and check evasions. The all followed the scheme

if (sideToMove == WHITE)
{
    // generate white moves
} else
{
    // do something similar for black
}

This is not really elegant.

Fortunately C++ provides function templates that solve that really nice. It required some code rework including the definition of some new data types. But overall the code now looks much nicer.

As far as I could measure there was no impact on speed and of course the new move generators pass the perft unit test again.

iCE 2.0 v1352 x32 [2014.1.5]
perft        Nodes    Time
  1             20    0 sec
  2            400    0 sec
  3          8.902    0 sec
  4        197.281    0.015 sec
  5      4.865.609    0.109 sec
  6    119.060.324    2.699 sec
 
Perft 1 - 6 executed in 2.823 sec  (43.96 Mnps)

position fen 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -
perft        Nodes    Time
  1             14    0 sec
  2            191    0 sec
  3          2.812    0.015 sec
  4         43.238    0 sec
  5        674.624    0.047 sec
  6     11.030.083    0.312 sec
  7    178.633.661    4.867 sec

Perft 1 - 7 executed in 5.241 sec  (36.32 Mnps)

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.