Sunday, February 9, 2014

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


Saturday, February 1, 2014

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