Endgame Tablebases

At the moment I take a bit of rest from working on the engine and play around with a different aspect of chess, the endgame.
My engine posses a bit of endgame knowledge, like

force the downside king to the edge
keep the upside king close to the downside king
occupy the key squares of your pawn with your own king

This is usually enough for the engine to determine a quick mating sequence through search, even if the mate is not within its search depth yet.

A slight enhancement for an engine would be the usage of a endgame database where it stores for a variety of positions its correct value, so if the engine encounters such a position it knows its value instantly without searching further. Obviously the number of possible positions growths very rapidly with the number of remaining pieces on the board. In a 3 piece endgame (2 kings and 1 additional piece) there are 2^18 possible positions per remaining piece type and side to move ( a good amount of it is illegal, but anyway a huge number).

If the remaining piece is a knight or a bishop the position is a draw (insufficient material), so the interesting combination are king and queen or rook or pawn vs king, with pawn being probably the most interesting as it is not as trivial to determine whether the position is a win or a draw as with rook or queen. But it is also more difficult as the pawn must promote first turning the board into a king and queen vs king endgame.

So I started with the creation of a database of a king and rook or queen vs king endgame. The algorithm works as follows.

1. Create all positions, evaluate them and mark those where the downside is mated as "Mated"
2. Look through all the positions marked as "Mate" and mark all those positions the upside can reach in 1 move as "Mate in 1"
3. Now generate all positions again and the moves in that position (it is downsides turn). Simulate the moves and look at the resulting positions. If all positions found are marked as "Mate in 1" the actual position gets "Mated in 1" score.
4. Now generate all positions again and generate the moves for the upside, simulate the move and if you encounter 1 position marked "Mated in 1" the actual position gets the score of "Mate in 2".
5. Go back to 3. but now look for positions where the downside cannot avoid a "Mate in 2" position. This position becomes "Mated in 2".
6. Alternate between upside and downside processing until you make no longer progress (finding at least one score of a previously unknown position). Then you're done.

Here is sample of how it look at the end. This position is number 5.202 of 262.144

Its score in the database was determined as 

• when it is upsides move = Mate in 2 (1. Rc2 Ka1 2. Rc1#)
• when its downsides turn = Mated in 1 (1. ... Ka1 2. Rc1#)
• and if the rook was not a rook but a queen, then it is a "Mate in 1" (1. Qe1#) or a Draw (Stalemate)

So far I have only played around with the basic stuff, but it is fun so I will now work on the king and pawn vs king table.

Again, I don't expect the engine to play stronger with that knowledge, but I think it is fun to enable the engine to announce deep mates, like "Mate in 16". However I have not decided how to make that knowledge available to the engine, at the moment it is just written to a file in the file system.