Saturday, November 12, 2011

You can't win with 2 knights, so it's a draw, isn't it ?

I just encountered an awkward bug in iCE. I had some simple rules in my evaluation that check whether there is still enough mating material on the board. One of those rules was

If the only material left on the board is 2 knights it is a draw.

This is in general correct, unfortunately not always and according Murphy's law things that can go wrong will go wrong.

I was still coding 5 man endgame knowledge and I was just working on a a very simple one. King and 2 knights vs King and 1 knight (KNNKN). This is also almost always a draw, but as the defender side still has a knight, it can now be mated where without the knight the move sequence would only lead to a stalemate. So some easy checks to recognize those positions and otherwise declare a draw.

I then checked whether it works correctly in the engine with that position

 White moves and mates in 4
A possible mate sequence is

1. Kc2  Nc5    2. Nb4+  Ka1    3. Nd4  Nb3     4. Nxb3#

Leading to this position
Mate !
So now Murphy's law hits and iCE was not recognizing this Mate, because it obeyed the 2 knights rule and announced a draw. iCE was therefore not able to solve this simple Mate in 4. Even if this probably never appears in a real game as problem it bothers me to know it's there. I modified the 2 knights draw rule slightly so that is does not announce a draw if the defender is in check and has nowhere to go. Knowing only 2 knights are on the board this is a simple mate check (much simpler than in a normal position). And now it solves this simple position correctly in no time.

iCE 0.3 build 491 [2011.11.12]
position fen 8/8/8/1N6/n7/3N4/k7/2K5 w - - 0 1
go depth 8
info depth 1 time 0 nodes 34 pv b5d6  nps 33999 score cp 22
info depth 2 time 0 nodes 116 pv c1c2 a4b2  nps 115999 score cp 22 
info depth 3 time 16 nodes 333 pv c1c2 a4b2 d3b4 a2a1 b5c7  nps 20812 score cp 23
info depth 4 time 0 nodes 606 pv c1c2 a4b2 d3b4 a2a1 b5c7 b2d1  nps 605999 score cp 23
info depth 5 time 15 nodes 1012 pv c1c2 a4b2 d3b4 a2a1 b5d4 b2d1 d4b3 nps 67466 score mate 4
info depth 6 time 16 nodes 1490 pv c1c2 a4b2 d3b4 a2a1 b5d4 b2d1 d4b3 nps 93124 score mate 4
info depth 7 time 15 nodes 1614 pv c1c2 a4b2 d3b4 a2a1 b5d4 b2d1 d4b3 nps 107600 score mate 4
bestmove c1c2 ponder a4b2


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

Tuesday, November 1, 2011

The KBBKB ruleset is done

So as announced in the previous post I was working on a rule set to recognize a draw in a king and 2 bishops vs bishop endgame. I verified the rule set against the Gaviota table base for that endgame and it is now correct. It was unfortunately much more complicated as I first thought.
For simplicity I always assume White is the side with the 2 bishops, so I have to check all cases where the white king is on one of the 10 core squares in a pawnless endgame (A1, B1, C1, D1, B2, C2, D2, C3, D3, D4). Due to symmetry reasons this is enough. For those 10 squares I now recognize

Incorrect Draws :           0
Spotted   Draws : 146.068.302
Missed    Draws :  44.341.638
Spotted   Wins  :  16.484.560

which is pretty good as in the missed draws also a lot of positions are contained where the attacker bishops travel on the same color, which I did not bother to recognize.

So another little piece of endgame knowledge added. If iCE 0.2 would have already possessed it, it would have won at least 1 more game :-)

Still a lot is missing, like King Rook and Minor vs King Rook which also did cost half a point already.