Success with the KPKP endgame table

After fixing all known problems with the king queen vs king pawn table I regenerated also all the king and piece vs king pawn tables so they are at least consitent.

I now proceed to the king pawn vs king pawn table. This is in a way special compared to the king and piece tables as with two opposite pawns on the board they possibility of "en passent" arises. All previous combination of 4 pieces did not have that problem.

To demonstrate this look at the following board

With Black to move White will win in 17 moves, so the value of that position is Mated in 17. But if the last move of white was f2-f4 then black can play g4 x f3 and wins in 11 moves (Mate in 11).

Unfortunately the table base has no history information of played moves because it is generated backwards from Mate positions. A clean solution would be to evaluate this position twice, with and without en passent possibility, but then you have to store whether you captured "en passent" or not as in the next iteration of retro table analysis the move generator may in case of en passent may only generate a single move (f2-f4).

This is quite tricky to implement as the data model so far does not allow the storage of a en passent flag. So I decided to implement a little hack here.

Whenever the move generator generates a move that will allow en passent captures for the opponent next turn (pawn double step with end position next to the opponent pawn) this move is deleted from the list of available moves and not considered in the analysis.

The assumption behind this is that a move that allows the opponent to capture the pawn will never be the best move, it is at most as good as another move from the list (e.g. the single pawn step move). This in fact seems to work quite well. The generated table is consistent and as far as I can tell correct.

Still fighting the KQKP table

I fixed most of the issues with the KQKP table but there are still errors in it.

I find them when I consider symmetry properties of the board. When you have a position and flip the board vertical you end up with a mirrored position that should have the exact same value. Whenever the position and the mirrored position values are different you know there is a bug somewhere. This way I eliminated most of the bugs. The last I found is caused by not properly handling under promotions.

Consider the following position

If white promotes the pawn to a queen it is mated next move, moving with the king is slightly better as White then is "Mated in 2". The best move however is e7-e8 N. Then black must move out of check and white gains an additional move. So this positions value is "Mated in 3" but the table shows "Mated in 2" because it does not consider the under promotion to a knight.

A nice shot of the inconsistency of the table.

So this is the next thing to fix and then hopefully the KQKP is ready and I can finally progress to the KPKP table.

Further work on the 4 man end game tables

The work on the KPKP table base is quite challenging, because one has to consider the pawn promotions and also decide how to handle en passent positions. While working on the table it showed that there are some inconsistencies in the KQKP and other tables as well that popped up when handling the promotions. So I have to verify the base tables before I continue to work on the KPKP table. I hope to fix those issues pretty soon.

Chess endgame table base KRKB

The next on my list for endgame tables was the endgame of king and rook vs king and bishop. Theory says that games with rook vs bishop or knight are drawish as they contain mostly draws and a few easy to spot wins where the rook is able to capture the piece (e.g. by pinning it to the king).

The table proved the theory however there are a few positions where the side with the rook can force a win that is not that obvious. I find those positions and the paths to mate from them quite interesting. One example is the following board

From the first look this position seems to be a safe draw for black. White is not able to capture the bishop in the near future. But the final table shows that this position is a forced with for White in 29 moves. The only winning move is 1. Ke1. The bishop is captured in move 17. So it would require a rather deep calculation for an engine to see the win in that position.

Chess endgame table base KQKR

When I continued my work on the 4 man endgame table bases I started to work on a rather interesting 4 man combination. It is the King and Queen vs King and Rook end game. It is interesting because it is not trivial. All previous tables were mostly trivial as they contain easy forced wins (King and Queen vs King) or contain mostly draws (King and Queen vs King and Queen).


Consider the following position

Black threatens check mate with ... Rh4#. With white to move white can prevent the mate and win. But the table base shows that it requires at least 35 moves to do so. With regards to the 50 moves rule this requires accurate play and here the table base is quite helpful.

The generation of the table took quite some time on my computer also because I use board symmetries when storing the data but so far not in the calculation of the table. So I consider all 33.554.432 positions (2 * 2^24) and this took several hours.

4 man table bases

After the creation of the interesting 3 man table bases I move on to the 4 man stuff. The principle is the same but unfortunately they grow very heavily in size compared to the 3 man tables. At the 1st look they are 64 times bigger because a additional piece with 64 possible squares is included. This means uncompressed takes such a table 30 MB, which is quite a lot if you consider the fact that there are a lot of possible 4 man games and all of them require that space.

So I have to deal with board symmetry properties to contain the space required by the tables. I start with the games without pawns. Here the symmetries are the biggest and I need those tables for the games with the pawns anyway.

I'm starting to think of a conversion method that involves core squares like A1, B1, C1, D1, B2, C2, D2, C3, D3 and D4. Only positions with the white king on a core square are processed. If the white king is not on a core square the board is rotated or flipped and rotated until the white king is on a core square. This should save about 80% of space.

When the conversion is working I will explain it in more detail in a later post.

Creating a KPK endgame table base

After creating the KQK and KRK table bases I go to the more difficult stuff, which is a table base that involves pawns. I create a KPK (King and Pawn vs King) table base. There are 2 reasons that make this more difficult

1. There is no mate position with a King and Pawn vs King. So you cannot just use the plain creation method from KQK here. You must promote the pawn to a queen or a rook before you can mate the king.
2. White pawns and black pawns move in different directions. In a KQK endgame it makes no difference when you have a queen on b7 and it is the turn from the one with the queen, whether this is a black or a white queen. The distance to mate will be the same for both sides. In a KPK endgame a white pawn on b7 is very much different from a black pawn on b7.

This is the algorithm I used to construct the table base. There might be more efficient ways to to that and certainly there are more efficient ways to store the data (using board symmetries), but this makes it more difficult. The whole table fits in less than 1 MB, so I did not bother to save a few kb here by doing mind bending conversions.

First I initialize the table with the knowledge from the KQK table base. So on every promotion square I put a queen and score all possible positions with the score of that position from the KQK table base.

Here I encountered the first trap. Usually it is best to promote to a queen but not always.

Promoting the pawn to a queen will draw. The only winning move is under promoting the pawn to a rook. So when initializing the table make sure you consider rook promotions too when they score better than queen promotions.

After initializing the table I very much follow the method of generating positions further away from the known ones until all linked positions are generated and the table is no longer improved. The remaining unlinked unknown ones are draws. I ended up with a good table where the longest distance to mate was a "Mate in 28". But after verifying the content I found out that some positions were incorrectly scored.

This position was scored "Mate in 6". In fact it is a "Mate in 5". The reason is that I traced positions back from positions were the pawn was promoted and if in the position above the pawn moves to b8 and promotes to a queen it will in fact require 6 moves to mate (incl. the pawn move). However the move Kf5 will already "Mate in 5". But when this position was scored the position with the king on f5 was yet unknown and therefore the "Mate in 6" score was awarded to that position.

I tried several table generation methods that work around that issue (like only initializing with Mated in 0 scores) but all failed. The generated tables were worse than the one I already had. I finally accepted that the first pass will generated positions with paths to mates that are not necessarily the shortest ones.

I then tried a second pass on the filled table were I adjust the scores. I start with the Mated in 1 positions and verify them whether they are truly Mated in 1, I then verify the Mate in 2 positions whether shorter Mates are possible and so on until the "Mate in 28" positions are verified. The algorithm did quite some adjustments, much more than I expected, but the adjusted table now seems to be correct (My table access code does not distinguish between the promotions, it scores all promotions with the best score from a promotion, but this is just cosmetics, the only important thing is the correct score of each position).