Thursday, November 10, 2011

More trivial endgame knowledge

I'm moving forward in enabling iCE to distinguish between drawn and winnable endgames. And here sometimes the stuff that the chess theory considers as trivial is nevertheless an important case for a chess engine to know.

Pawnless endgames with 2 minors vs a rook, like white playing with both bishops and black playing with a rook, are such a case. Theory says "trivial" and "unimportant" because the rook sacrifices for a minor and it's a draw then. For humans this rule is ok, for chess engine it is not, because in the above example about 10% of positions are winnable. If the engine does not know which positions might be winnable it will carelessly enter such a position as defending side and lose. In all variations of KmmKR (even in the king and two knights vs king and rook endgame) for both sides positions exists that can be won.

 KmmKR - whoever moves first wins

So making the evaluation smart enough to handle those games correctly you do two things
  1. Try to detect that the position is dead draw
  2. If it is not a draw try to give it a score that allows the engine to make progress (like a king at the edge is bad, so the winning side will make moves that force the defending side to the edge)
Step 1 is pretty tough, because to recognize a position as draw just by statically looking at the location of the pieces and the side to move, is not trivial. Without a bitbase it is nearly impossible to define a perfect draw recognizer or it would be so complex that it would also be very slow. So the draw recognizer uses heuristics that detect patterns that indicate winning potential and then plays safe and outputs "No draw".

An simple example is the pattern "king in the corner". There are a lot of winning positions when 1 side has the king in the corner, so it is safer to say "No draw". Then you don't make an error but you miss of course all draws in positions with a cornered king.

So you refine the pattern, e.g. only if the king is in the corner and the opponent king is also near the same corner then we say "No draw". This misses less draws but the pattern is more complex. So at the end it is a tradeoff between the complexity of the patterns and the draws that you miss.

Step 2 is then pretty simply, because the things that define the quality of a position are pretty easy, basically it is king distance from each other, king distance from edge or the corner the bishop controls.

So for now I have this type of endgame knowledge added. the recognizers are not perfect (as explained above) but hopefully good enough.

This is the performance of the recognizers, especially the wins (mostly for the side with the rook) with 2 knights are difficult to detect.

Incorrect Draws : 0
Spotted   Draws : 416.158.800

Missed    Draws : 730.608.536
Spotted   Wins  : 119.989.080

Incorrect Draws :           0
Spotted   Draws : 425.127.870

Missed    Draws : 675.820.802
Spotted   Wins  : 206.160.824

Incorrect Draws :           0
Spotted   Draws : 326.444.616

Missed    Draws : 972.419.472
Spotted   Wins  :  43.430.424