Sunday, January 1, 2012

Endgame King Bishop and Knight vs. King and Knight

All my latest efforts to improve the play of iCE went into mastering the endgame of King Knight and Bishop vs King and Knight. The theory does not say much about this endgame, obviously it is not interesting enough for human play and chess engine play it via table bases.

However I want to build some endgame knowledge into iCE directly so I tried to figure out some basic properties about it.

It seems overall it is drawish, so there are a lot of drawn positions. But there is also a significant amount positions that look drawish but are winnable by the stronger side. The line of play from those positions is sometimes not clear. So an engine without any knowledge of this endgame might easily move from a drawn into a lost position as it cannot tell the difference.

White moves and Mates in 101 !

Black moves and loses in 95 !

So it is very hard to tell whether a position is drawn or won. Some general principles for winnable positions are
  • the attacker king is actively placed
  • the distance between defender knight and defender king is big
  • the defender knight is restricted in its mobility
  • the attacker king is closer than the defender king to the defender knight
I then coded a module that detects dangerous patterns in a position. If a position does not contain any dangerous pattern it is a draw. A knight on the board makes patterns difficult and in this endgame 2 knights are on the board. So the pattern module is now a very comprehensive chunk of code, it took a lot of time to build it and it is far from perfect. It never announces a won/lost position as draw but does miss a lot of drawn positions.

Incorrect Draws : 0
Spotted   Draws : 64.403.306
Missed    Draws : 117.746.021
Spotted   Wins  : 37.532.061

So about a third of the drawn positions are recognized, two thirds are missed but this is as good as I could make it. The effort is still worth it in my opinion because if a draw is recognized search stops at this node cutting of potential huge sub trees that otherwise would have been searched. So there is still a significant savings potential.

I now have a neat little number of special endgame modules for different kinds of endgames. The code that forks the evaluation into one of this modules is a bit messy. I will clean that up and then I have to do some extensive testing whether those modules integrate correctly into search and evaluation.

More fun to come...