Thursday, September 6, 2012

Mastering the King a Rook vs King and Pawn endgame

In iCE 0.3 I added a lot of endgame knowledge especially for drawish pawn less endgames with material in-balance (like KRNKR). However a few fundamental ones are still missing. One of them is King and Rook vs. King and Pawn which is really tricky to evaluate nevertheless very important.

Consider the following position with white to move

1. Rc8 is very tempting but only draws, after

1. ... Ra7 2. Ke8 Rxd7 3. Kxd7 we reach the following KRKP endgame, which is a draw

iCE did not know that. In fact iCE selected the move 1. Rd1+, but this is also only a draw after 1. ... Ke4. So while the endgame is not even on the board the lack of knowledge let play iCE the wrong move. I run a search for several hours, iCE was still happy with 1. Rd1+.  And of course it makes no sense to optimize towards a single position, the underlying knowledge problem must be solved.

There are a lot of winning positions for the pawn side if the pawn is already on the 6th or 7th rank. Here the rook is not able to stop the pawn from promoting and where the pawn side then wins the Queen vs Rook endgame.  But sometimes the pawn safely promotes but the rook side  is able to force a stalemate or give permanent checks. So finding out the pawn will promote is not enough for classifying it as a win.

If the pawn is not advanced the rook side might not be able to stop it without sacrificing the rook which leads to a draw.

In general one can state for this endgame
  • Usually the rook side is able to stop the pawn
  • If the attacker king is in front of the pawn the attacker will win
  • If the pawn gets support from its own king and the attacker king is away and behind the pawn the pawn side might be able to draw.
  • If the pawn is already on the 7th and sometimes on the 6th (with the pawn side to move) it might be able to promote and win 
  • There are hard to spot exceptions for both sides.
Those exceptions make it very hard to assemble a rule set to classify a position correctly. After several tries I decided on the following implementation for my KRKP module.

First I implemented a method to detect the wins for the pawn side. This method detects the trivial cases where the rook is immediately captured and the resulting KPK endgame is won, but also the non trivial ones where the pawn is able to promote and the queen survives (without stalemating the other king). The detector must handle the 3 non trivial cases
  • the pawn is on the 7th and the pawn side moves
  • the pawn is on the 7th and the rook side moves
  • the pawn is on the 6th and the pawn side moves
In all other non trivial positions the pawn side will not win. Most won positions obviously are found in the first case. I came up with a very complex rule that detects 99% of the wins in that situation. To detect the remaining 1% (about 1300 positions) I decided to just store them explicitly.

Only about 6000 positions make up the 2nd case. I tried hard to assemble some rules for that but at the end I gave up and also store them explicitly. The 3rd case is easy then. To win the pawn must move and we can look whether we have stored the resulting position for case number 2.

So this method detects 100% the pawn wins with a small internal database and a few complex rules.

Next I require a 2nd method that detects the drawn positions which is called only if we see that the position is not a win for the pawn obviously.

Theory states to count the tempi for the pawn side to promote with king support and the rook side to control the promotion square with both rook and king. If the pawn side requires less tempi than the rook side it is a draw. This is maybe a good rule of thumb for a human but it is not a correct rule for a computer. It will announce a lot of false draws. So I tried another approach.

Whether a position is drawn depends mainly on the pawn and king positions and less on the position of the rook. I assembled a small internal database of about 2600 records (each 2 byte) that contain those king and pawn positions that are drawn no matter where the rook stands or whose side to move it is. With those 2600 records I'm able to detect 700k out of 1.2M drawn positions.

I decided to stop here, this is good enough.

So after all that efforts I wanted to see whether it helped iCE to find a better move in the above position and voila it actually did. It sticks to the winning move realizing that the alternatives will draw. It is even able to announce the correct distance to mate.

depth move score  nodes
move score  nodes
1 d8=Q 379 56
d8=Q 277 72
2 d8=Q 379 275
d8=Q 277 234
3 d8=Q 379 386
d8=Q 267 336
4 d8=Q 367 1648
d8=Q 267 1220
5 d8=Q 344 2367
d8=Q 277 1993
6 d8=Q 356 6264
d8=Q 307 11897
7 Rc2 356 22k
d8=Q 317 20k
8 Ra1 341 123k
d8=Q 327 50k
9 Ra1 341 142k
d8=Q 327 57k
10 Rc8 356 5948k
d8=Q 327 285k
11 Rd1+ 341 2337k
d8=Q 367 363k
12 Rd1+ 341 805k
d8=Q 317 9M
13 Rd1+ 341 20M
d8=Q 317 14M
14 Rd1+ 336 8M d8=Q 367 3M
15 Rd1+ 341 13M d8=Q 417 8M
16 Rd1+ 338 54M d8=Q Mate 25 34M
17 Rd1+ 341 94M d8=Q Mate 24 73M

I like it when something works !