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 !