Wednesday, April 27, 2011

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.