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