TableBase Generation on the fly

8/1k6/8/8/8/8/1K4P1/8 w - - 0 1

Most chess engines access external table bases for a perfect play in the endgame with 6 or less pieces. It also helps them to decide whether the should exchange into such an endgame or not.

I'm not a huge fan of those databases. It eliminates an important part of knowledge that an chess engine should possess and replaces it with a database access call. However most engines do it and maybe in a future version I will also turn my chess engine into a database client, but not yet.

Also that iCE is not using table bases is not fully true, since the very early versions iCE has some tables directly built into its binaries that tell it the score of all positions with 3 pieces or less (like a 3 men table base).

I calculated the values for those table myself, so its at least my own contribution. I had my own little table base generator. It was awfully slow as I was using a lot of code that I already had for move generation, board setup and stuff. It was not optimized towards a TB generator and it took several seconds to generate a single 3 men table. But this was Ok, as I was just using its output and was not executing the generation itself my engine.

As an intellectual challenge I thought it is now time to come back to that. To write a table base generator some real mind bending thinking is required. This is a nice change from the usual "change 1 value in the program and wait for a day to see whether it worked." If I get the generator fast enough I might be able to throw out the ugly large internal tables from the source code and generate them on the fly when the program starts. 

Table Base look up for 8/1k6/8/8/8/8/1K4P1/8 w - - 0 1

So 1st priority are the 3 men tables (1 piece in addition to both kings.) I introduced a new board data type where the whole board is represented
as a single packed integer. A move is also  represented as integer. It is the resulting board. A move execution is then just replacing the current board int with the move int. This enables some really fast board operations now.

Then I went to the actual TB generator code. This was really tricky to get it right. I experienced inflated Mate scores. So in the King, Queen against King endgame the longest Mate is a "Mate in 10" but I saw a lot of funny "Mate in 30"s generated.

The reason for that is retrograde generation of the data. A predecessor of a Mated in 1 position is not necessarily a Mate in 2 position it can also be a Mate in 1 position. But finally I was able to correct those scores into a consistent data set.

For a verification run I compared my new generated data against the old internal values from iCE and to my surprise 0,6% of the KPK positions deviated from each other. A quick check revealed that iCE currently has some errors in its table and my new set is the correct one. The errors were not fatal. A Win was a Win, the Mate distance was just off by 1 and sometimes even 2 moves. Probably no one would have ever noticed that. But for me the whole exercise already has a benefit.

Whether I really include the on the fly generation code in iCE I have not yet decided. It depends on how fast I can get it with some profiling or improvements in the algorithms. Currently I'm not fully happy with the speed yet.

Here is the data for my KPK set, run as a 32 bit binary on an older machine (which somewhat marks the lower limit of the hardware spectrum I target). The set already exploits board symmetries to reduce the positions it has to process and store.  

TableBase: KPK   Generation Time:  0.172 sec   Iterations: 20/8

STM           WHITE     BLACK                    WHITE     BLACK
----------------------------------------------------------------
ILLEGAL      49.279    32.944      UNKNOWN           0         0
MATED             0        42      DRAWS        19.184    36.206

Balanced endgames

Is the position balanced ?

Almost all evaluation terms have a endgame component, some evaluation terms only exist for the endgame. In order to tune them it is very helpful not to start games from the starting position. 

A lot of games might be decided without even reaching the endgame, so the outcome of the game does tell very little whether the evaluation values of the winner were good or bad. So it is better to start games from a late midgame position. But here starts the challenge. 

What are good starting positions ?

If the position is to drawish and always leads to a draw it does not help. If it favors one side to much it is also rather useless. To find good starting positions is rather tricky.

I searched the web and some helpful fellows posted positions that they thought were balanced. They searched them with an engine and if the score was within a range around 0 they used it. 

I used those as a starting point and ran a 16000 games tournament between Stockfish and Komodo using 248 of those positions. I then analyzed the resulting games file and got mixed results. Some of those "balanced" were not balanced at all, some of those positions were dead drawn. I then assigned points for usefulness to them. Those below are the ones from the tested 248 positions which seem the most useful. 

Maybe they are of some help to others. The numbers to the right mark the number of games played with this position, the wins by white and black and the number of draws.

PS.: The above posted position is not balanced. White scores about 80% (41 - 2 - 23).

  
  #  FEN                                                     Gm   W    B    D
---+--------------------------------------------------------+-----------------   
  1. 5rk1/N4p1p/1p6/2p2p2/4p3/P4bP1/1PP2P1P/2K1R3 b - -      64   21 - 27 - 16
  2. 5k2/p1p2pp1/2p4p/2N5/1P2R2P/P1P5/5PPK/3r1b2 b - -       64   24 - 19 - 21
  3. 1B4k1/p3r1p1/1n3p1p/4p3/1Rp5/P1P2P2/2P2P1P/5K2 w - -    64   16 - 25 - 23
  4. 2k1r3/2p4p/pp6/2p1p3/b3P2B/P1R2P2/P5PP/6K1 w - -        66   23 - 14 - 29
  5. r4b2/1R6/4k1pp/2ppp3/Pp6/1P3P1P/1BP1K1P1/8 b - -        66   21 - 14 - 31
  6. 2kr4/1p2R1p1/2p4p/Pp6/3b1P1P/6P1/2P3K1/4B3 w - -        64   16 - 16 - 32
  7. 3k4/p1p2p1R/1p2p1p1/3bn3/8/PP4P1/2P3P1/2K2B2 b - -      64   22 - 13 - 29
  8. 3r1b2/5k2/pp3p2/4pp1p/P7/2P2PP1/1PKN3P/4R3 b - -        66   28 - 11 - 27
  9. r2k4/p1p2pN1/1p5p/2p1P1bP/8/1P4P1/PBP2P2/6K1 w - -      64   31 - 11 - 22
 10. 5r2/p3k2p/3pn3/3B1p2/PPPp4/6PP/2P4K/B7 w - -            66   15 - 15 - 36
 11. 3B1b2/p2n1p2/5P2/1k6/1p6/6P1/1p3P1P/1R4K1 b - -         64   10 - 33 - 21
 12. 5nk1/pp3ppp/4p1b1/3pP3/P2P4/3B4/1P3PPP/2B3K1 w - -      64   17 - 13 - 34
 13. 4b1k1/2p1r1p1/1p1p3p/p2P3P/3PP1P1/5K2/P2N4/6R1 b - -    64   15 - 13 - 36
 14. 2k5/2p2p2/p1p2rp1/3n3p/1P2KB1P/P5P1/1P3P2/3R4 w - -     64   17 - 12 - 35
 15. 2k2b1r/3n4/5P2/8/1pp5/4B1P1/1P3P1P/5RK1 w - -           64    9 - 31 - 24
 16. 3r2k1/p4ppp/1p2pn2/8/P2N4/2P3P1/1P3PP1/4R1K1 b - -      64   16 - 12 - 36
 17. 1B4k1/1p4pp/p3pb2/5p2/3P1P2/4PP2/P3K2P/1n1N4 w - -      64   18 - 11 - 35
 18. r7/pp3pkp/1n1p2p1/3P4/5PN1/1P6/P5PP/4R1K1 w - -         64   15 - 12 - 37
 19. r7/5p2/2p2k1p/ppNp1b2/3R4/1PP2P2/1P4PP/4K3 w - -        66   19 - 10 - 37
 20. 4kr2/1pp3pp/p1p5/4b3/4P3/3PB3/PP3P1P/R5K1 w - -         66   16 - 11 - 39
 21. 2r3k1/3b1pp1/4p3/1p2P1p1/1N6/P1R5/1PP4P/2K5 w - -       64   12 - 14 - 38
 22. r3k1B1/1p1b4/p6p/5p2/3p1p2/5P1P/PPP2P2/2K4R b q -       64   23 -  9 - 32
 23. 2n2k2/n4pp1/pp2p2p/3pP3/1P1P2PP/P2KB3/5P2/4N3 w - -     64   18 - 10 - 36
 24. 2r3k1/3b4/p2p2pp/3P1p2/1PpN4/P3P2P/5KP1/2R5 w - -       64   18 - 10 - 36
 25. r7/p4pk1/1p6/4n1p1/4PpP1/P7/1P2B1PP/3K3R b - -          64   13 - 12 - 39
 26. 3kb3/pp2p2p/3p2p1/4n1P1/4PK1P/1PP5/P1N1B3/8 b - -       64   13 - 12 - 39
 27. 2nr1k2/p4p2/4pp1p/2p5/2P3P1/P3P3/2K1BP1P/1R6 w - -      66   25 -  8 - 33
 28. 3k3r/1p2b2p/p3pp2/2p5/P4P2/2NKP3/1P4PP/7R b - -         66   10 - 16 - 40
 29. 2rk4/p4ppp/1pn5/2p5/4B3/P1P3P1/4PP1P/1R4K1 w - -        64   25 -  8 - 31
 30. 3b4/3k2p1/3p4/pp3p2/4bP2/4N1PP/P3K3/3R4 b - -           64   24 -  8 - 32
 31. r5k1/p7/2p3p1/4R2p/7P/2P2P1N/PP4n1/3K4 b - -            64   13 - 11 - 40
 32. 1r4k1/4b2p/2np4/8/1p2R3/1P1R4/P5PP/1K6 b - -            64   15 - 10 - 39
 33. 8/2pk3p/1p4p1/p5P1/2bPnB1P/P7/6K1/1R6 b - -             64   15 - 10 - 39
 34. 3r2k1/pp2p2p/4pnp1/4R3/8/7P/PPP2PP1/3N2K1 w - -         64   21 -  8 - 35
 35. 2r5/4k1p1/p3p1P1/6b1/2p5/7B/PPP5/1K1R4 w - -            64   21 -  8 - 35
 36. 3r1k2/3b1pp1/7p/1p1PpP2/2p1P3/7P/1PB3P1/R5K1 b - -      64   12 - 11 - 41

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.  

Queen vs 3 Minors part 2

I did some more research in the case of a material imbalance of 3 minors vs a queen. In my previous post I determined the imbalance to be worth 0,82 pawns.

Unfortunately this seems to be too simple. The above imbalance figure includes the bonus for the bishop pair which the side with the minors usually enjoys. To remove this effect I repeated the test with positions where the 3 minors did not include the bishop pair.

An additional factor not covered so far is the effect coming from the number of rooks still on the board. In my previous test all starting positions included 2 rook pairs. The theory says that the bonus for the minors should be bigger if the rooks are still on the board. The bonus might be different if some rooks are removed. So I performed several tests to test this hypothesis. 

Here are my results

QRR vs RRBNN

In those positions all rooks were still on the board

Queen side scores 43,0% with equal number of pawns
Queen side scores 23,8% with Minors having an extra pawn

Value of Imbalance for Queen side: -0,37 pawns

QRvsRBNN

In those positions 1 rook for each side was removed

Queen side scores 50,5% with equal number of pawns
Queen side scores 28,9% with Minors having an extra pawn

Value of Imbalance for Queen side: +0,02 pawns

QvsBNN

 In those positions all rooks are removed

Queen side scores 70,8% with equal number of pawns
Queen side scores 44,5% with Minors having an extra pawn

Value of Imbalance for Queen side: +0,79 pawns






It seems the number of rooks has huge impact on the value of the imbalance. Its value changes by more than a pawn. 

 Probably the imbalances of queen and pawns vs a rook and two minors are to hard to be calculated or require a bigger effort. The missing pawns give the side with the minors some development compensation and also half open files, so the value of the imbalance gets polluted with other stuff. So this remains maybe as a future but not immediate exercise.

Queen vs 3 minors

Recently there was an interesting "Lonely queen" discussion at Talkchess where it was claimed that stockfish seems to have trouble to understand positions where a queen is exchanged vs 3 pieces.

iCE also does not have special code to handle this imbalance. I relied here on the mobility (3 pieces have more mobility than a queen, whose mobility in iCE is cut at 14 squares). This imbalance is difficult to tune as it appears in less than 1% of the games.






H.G. Muller suggested a cool method to not tune but to measure the value of the imbalance by playing games that enforce the imbalance and measure the winning chances for both sides. This is what I did.

I created a set of starting positions where the imbalance is present. To make it simpler to count I always gave the 3 minors to Black, but awarded the first move in halve of the starting positions to Black.

I then played a iCE vs iCE tournament. After 1000 games, Black scored 63,75%. So the imbalance has a significant influence. I now have to translate this winning percentage into centipawns as this is the score unit in iCE.

Here I removed for Black also the f7 pawn in the starting positions and played again. Black now scored 46,96%. This made the pawn worth 16,79%.


Now I could calculate the value of the imbalance as 13,75% / 16,79% * 1 pawn = 0,82 pawns.

At Talkchess the value of the imbalance was guessed to be 0,70 pawns. It seems this was an excellent guess.

Next step is to include a material imbalance term in the evaluation. It can go with the material signature and material hash, so it provides almost no additional computational costs. The impact on the playing strength will be tiny as it occurs so seldom.

But if your engine plays in 1% of its games really awkward people will notice. The stockfish case is a good example for that.

Next steps will be the measurement of some more imbalances that also involve a rook.