Friday, November 1, 2013

Knight vs two pawns endgame

In a recent chess tournament where the best Italian engines played against an international selection my iCE engine managed to get into the quarter finals. It was paired against Booot, a very strong chess program rated more than 200 ELO higher than iCE in the rating lists.

It was a 6 round match and iCE scored 2 out of 5 points in the first 5 games. It needed a win in the last round playing White to get into the tie break. It looked promising but at the end it only got a Draw and was out.

In this last game iCE exchanged into an endgame where it plays with two pawns against a lonely knight. iCE wasn't able to see that its pawns won't be able to queen until it was to late.

iCE played 1. Kxf2 Ne4+ 2. Ke3 Nxd6 with a very good score

It had to search 29 half moves (plies) deep to understand the position.

info depth 29 seldepth 53 nodes 1388226533 pv g1f2 f6e4 f2e3 e4d6 e3d4 d6b7 d4e5 h7g6 e5e6 g6g5 e6d7 b7a5 score cp 0

Most humans will see the draw without problems. One pawn is stopped by the knight and the other be the king. So not realizing this is a clear defect.

So I decided to put some effort in coding a few rules for a KPPKN endgame just for fun.

In a KPPKN endgame there are 855.071.008 legal positions and 439.033.368 can be won (usually but not always for the side with the pawns of course). This means almost half of the possible positions are draws. Nevertheless it is really difficult to find some patterns that spot the draws.

I was able to find rules that detect 30.371.460 draws, so less than 10%. This is not to impressive, luckily combined with search it already helps a lot.

The new iCE performs much better in the above position

position fen 8/7k/1P1R1n2/8/6P1/8/5r2/6K1 w - - 2 68
go depth 10
info depth 1 seldepth 0 time 0 nodes 23 pv g1f2 f6g4 f2f3 nps 22999 score cp 1086 

info depth 2 seldepth 3 time 16 nodes 142 pv g1f2 f6e4 f2e3 e4d6 nps 8874 score cp 521 
info depth 3 seldepth 4 time 0 nodes 200 pv g1f2 f6e4 f2e3 e4d6 nps 199999 score cp 521
info depth 4 seldepth 5 time 0 nodes 181 pv g1f2 f6e4 f2e3 e4d6 nps 180999 score cp 521
info depth 5 seldepth 7 time 0 nodes 281 pv g1f2 f6e4 f2e3 e4d6 e3d4 nps 280999 score cp 567 
info depth 6 seldepth 11 time 15 nodes 12448 pv d6e6 f6g4 b6b7 f2b2 e6e7 h7g6 g1f1 nps 829866 score cp 251
info depth 7 seldepth 11 time 15 nodes 17080 pv g4g5 f6e4 g5g6 h7g7 d6d7 g7g6 b6b7 f2b2 nps 1138666 score cp 218 
info depth 8 seldepth 14 time 0 nodes 12371 pv g4g5 f6e4 d6h6 h7g7 h6h2 f2f7 h2b2 f7b7 nps 12370999 score cp 153 
info depth 9 seldepth 16 time 16 nodes 26088 pv g4g5 f6g4 b6b7 f2b2 g5g6 h7g7 d6d7 g7g6 nps 1630499 score cp 53 
info depth 10 seldepth 18 time 31 nodes 55953 pv g4g5 f6e4 d6e6 f2b2 g5g6 h7g7 e6e4 nps 1804935 score cp 0 
bestmove g4g5 ponder f6e4
info time 172 nodes 124767 nps 725389

Already at depth 6 iCE realizes that Kxf2 will only draw and at depth 10 it realizes that the alternatives are no better.