Sunday, November 7, 2010

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.