Draw recognizer with pawns involved

I try to build a endgame draw recognizer for all 4 man endgame positions that are not easily evaluated. So I don't build one for king and 2 rooks against king as this make no sense. The engine will mate the enemy king and avoid stalemate traps without any additional help.

King and bishop vs king and pawn is more interesting. Usually it is a draw but there are quite a few winning positions for the side with the pawn and even a few for the side with the bishop.

I verify the recognizer by running all possible positions through it and verify its decision (draw / not draw) against a table base. This verification process takes much longer when pawns are involved as I have to test much mor positions. Without pawns I only test 10 squares for the white king, all other positions can be matched by mirroring or flipping to one of the 10 tested squares. With pawns that does not work, so I have to test 32 squares for the white king and so it takes three times as long.


So the whole recognizer implementation takes quite some time and I looking forward when it is done so I can move to more interesting stuff.

More on drawish endgames

After implementing a draw recognizer for the KRKR endgame I decided to implement a recognizer for the endgame of rook vs. knight and rook vs. bishop. I thought it is easier because only the side with the rook has winning chances but in fact it turned out to be much more difficult.

Even in the rook vs knight endgame there are a few positions where the side with knight wins.

 Black to move - Mate in 1

And in both endgames there are positions that look like a draw (you cannot easy see a forced win) but are in fact a forced win. In the knight vs. rook endgame some wins require up to 40 moves.

So at the end I implemented the draw recognizer but in order to not let them report false draws they rule out a lot of stuff and miss a lot of draw positions. The worst is knight vs. rook, bishop vs. rook works a bit better.

Anyway it helps the engine to play those endgames a lot

White moves and Mates in 29! (Ke1 !)

In this position it finds the winning move at ply 4 instantly. It sees the mate at ply 31 after 55 seconds.


position fen 8/8/8/8/8/2R5/8/3K1bk1 w - - 0 1
go depth 31
info depth 1 seldepth 2 time 0 nodes 37 pv d1d2  nps 36999 score cp 125 hashfull 0 tbhits 0
info depth 2 seldepth 3 time 0 nodes 95 pv d1d2 g1f2  nps 94999 score cp 110 hashfull 0 tbhits 1
info depth 3 seldepth 5 time 0 nodes 470 pv d1d2 g1f2 c3c7  nps 469999 score cp 110 hashfull 0 tbhits 15
info depth 4 seldepth 6 time 0 nodes 1141 pv d1e1 f1g2 c3g3 g1h2  nps 1140999 score cp 120 hashfull 0 tbhits 65
..
info depth 31 seldepth 47 time 11797 nodes 9152530 pv d1e1 g1g2 c3c2 g2g1 c2c6 f1b5 c6g6 g1h2 e1f2 h2h3 f2f3 h3h4 f3f4 h4h3 g6g3 h3h2 f4f3  nps 775835 score mate 29 hashfull 57 tbhits 77627

Improving the chess endgame knowledge

While monitoring games the engine plays I realized that often basically won games result in a draw because the engine does not understand when a endgame is a draw, e.g. exchanging the last pawn to a king and rook vs king and knight endgame is usually bad for the side ahead, as this endgame is likely a draw although one side being clearly ahead in material.

I was aware of that lack of knowledge but underestimated its impact in actual games. This issue is fixed when table bases are available and the engine is able to access them, because then it will recognize those positions are draw from the table base score, but I don't want to create a table base dependency for the engine that has a significant impact on playing strength.

So I decided to implement some more endgame knowledge in the engine to recognize also some non trivial positions as draw. I plan to use that knowledge not only in eval but also in search. This means when somewhere in the tree a position is recognized as DRAW search will stop evaluating this node even when not at the horizon.

For the moment I focus on positions with 4 pieces. 3 pieces are covered through internal table bases already. The easy stuff is when no site has enough mating material yet e.g. King and Bishop vs. King and Knight. Here we can just return a DRAW score.

The next thing is a King and Rook vs. King and Rook endgame. This endgame is perceived as DRAW but it is not possible just to return a DRAW score. There are positions that are forced wins or losses and if they are not handled properly this will introduce severe errors.

To take care of that I thought of implementing patterns that when they appear on the board indicate that this position is likely not a DRAW. One example of an easy pattern is where the side to move is able to capture the undefended enemy piece next turn. You can also think of more advanced pattern where the side to move is able to check the king where then the king is pinned to its piece. So I assembled the patterns I could think of and thought I have a good DRAW detection for the KRKR game.

I was wrong.

Not because I thought there is a problem with my patterns, more out of curiosity I implemented a validation routine that runs through all possible KRKP positions and calls my new isDraw() method for them. If isDraw() retruns true the score for that position is looked up in my KRKR table base and verified if it really is a DRAW. It was quite a disaster. I had errors over errors there.

There are non trivial forced wins in a KRKR game I did just not think of. Consider the next diagram, those patterns are likely to be missed

Black moves and Mates in 7!

So I reworked my patterns with the help of the table bases unless I did not falsely classify positions as draw anymore. In some cases the patterns indicate a possible win/loss which in fact is a DRAW but this is not so severe as search will just continue in that case and not introduce errors. 

At the end I came up with 11 patterns that together are able to recognize about 75% of all DRAW positions. For the moment this s good enough.

Incorrect Draws : 0
Spotted   Draws : 11.547.632
Missed    Draws : 3.590.432
Spotted   Wins/Loss  : 6.423.392

I was also surprised by the high number of positions with forced wins and losses. Quite high for an endgame that is perceived as DRAW.

Passed the tournament entry test

The ice has successfully passed the tournament entry test consisting of a test tournament between new engines. It completed all games without any bug, errors or warnings (e.g. loss on time).

Its playing strength still leaves much room for improvement.

 It finished 14th ot of 20 participants

Test at Dual Opteron 244 at 40/5, ponder=on
OPTERON-A, 2011.04.02 - 2011.04.05
                              Score     Ha Di Cu Fr Re Ph Al Ja If Be Fi Sj Do iC Ze Ca Ch Ja Ch Ch
----------------------------------------------------------------------------------------------------
1: Hannibal 1.0a           37.5 / 38   XX 1= 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
2: Dirty 23032011-x64      34.0 / 38   0= XX == 01 1= 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
3: CuckooChess 1.09-JA     31.5 / 38   00 == XX == 1= 01 =1 11 11 1= 11 11 11 11 11 11 11 11 11 11
4: FranMAD 0.18            30.0 / 38   00 10 == XX 01 01 10 01 11 11 11 11 11 11 11 11 11 11 11 11
5: RedQueen 0.9.5-JA       29.5 / 38   00 0= 0= 10 XX 10 01 =1 11 11 11 11 11 11 11 11 11 11 11 11
6: Phalanx Reborn          28.5 / 38   00 00 10 10 01 XX 11 1= 11 =1 11 1= 01 11 11 11 11 11 11 11
7: AliChess 4.25           26.0 / 38   00 00 =0 01 10 00 XX 11 11 11 10 =1 11 =1 11 1= 11 11 11 11
8: Jazz 4.4.4wb-x64-JA     21.5 / 38   00 00 00 10 =0 0= 00 XX 0= =1 01 0= 11 11 11 11 11 11 11 11
9: Ifrit j4.3-x64-JA       19.5 / 38   00 00 00 00 00 00 00 1= XX =1 1= 10 01 =1 11 11 1= 11 11 11
10: BetsabeII 1.0-ja        18.5 / 38   00 00 0= 00 00 =0 00 =0 =0 XX 10 11 11 0= 10 11 11 11 11 11
11: FireFly 2.59b1-x64      18.0 / 38   00 00 00 00 00 00 01 10 0= 01 XX 11 10 11 10 11 =1 10 11 11
12: Sjakk 1.1.7             15.5 / 38   00 00 00 00 00 0= =0 1= 01 00 00 XX 00 11 11 1= =1 01 11 11
13: Dolphin 1.04            15.0 / 38   00 00 00 00 00 10 00 00 10 00 01 11 XX 10 11 00 11 10 11 11
14: iCE 0.1-b1120           14.0 / 38   00 00 00 00 00 00 =0 00 =0 1= 00 00 01 XX 01 1= 11 11 11 11
15: ZetaDva 0.1.5.3-x64-JA  11.0 / 38   00 00 00 00 00 00 00 00 00 01 01 00 00 10 XX 1= 01 =1 11 11
16: Capivara LK 0.07s02     10.5 / 38   00 00 00 00 00 00 0= 00 00 00 00 0= 11 0= 0= XX 01 =1 11 11
17: ChessKISS 1.0            9.0 / 38   00 00 00 00 00 00 00 00 0= 00 =0 =0 00 00 10 10 XX 1= 11 11
18: JaksaH 1.11-x64          8.5 / 38   00 00 00 00 00 00 00 00 00 00 01 10 01 00 =0 =0 0= XX 11 11
19: ChessBunny 1.0_disk      1.0 / 38   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 XX ==
20: Chad'sChess 0.15         1.0 / 38   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 == XX
----------------------------------------------------------------------------------------------------
380 games: +175 =34 -171

Public tournament participation

The first release of the iCE engine went public. It took me about two years to develop it, or better say to evolve it. I had a chess playing program (not an engine) after a few weeks but this first version and the now released one have not much in common anymore. OK, both were Shannon Type A based somehow (not that I knew what Shannon Type A means, when I started). But that's about it.

So now its time to let go and I requested to participate with iCE in its first public tournament. I think it is still pretty weak and I hope it does not finish last or I'm really embarrassed. But at least I then have a baseline where I can develop from.

The 1st release of both engines is done

Today I published both engines (mACE and iCE) to my homepage, so whoever wants to give them I try can now do so.

I also started a little tutorial about chess programming there, so who is interested might have a look at
http://www.fam-petzke.de/chess_home_en.shtml.

About to release the 1st public version

After the last tournament where the ice engine did not so bad, I decided to take a little rest from the core engine programming. I plan to make the engine available for download via my private web site and have to do some preparation for that first. I will post the first public release of my engine as soon as this is finished.

Stay tuned !