Sunday, May 8, 2011

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


  1. hello Thomas, when the lookup on tablebase is done? within alphabeta or in iterative deeping?

    1. Hi,

      it is actually not a table base (which is just a database of all possible positions). It is a position recognizer. Those drawish endgames get a DRAW score unless some patterns in the position are present that are dangerous. An easy example for a pattern would be (rook is able to capture the unprotected knight).

      Those recognizer are called in alpha-beta whenever the material signature of the position indicates that a suitable recognizer is available. So when I enter a node in alpha-beta where the current board has 5 pieces or less I call the recognizer for that material signature (if I have one). If it returns "DRAW" I'm done with this node and return a draw score (no move generation etc. is done). If the recognizer says "DON'T KNOW" the node is processed normally (hash lookup, move generation, make move, alpha-beta, unmake move).


    2. Ok, I've implemented this with Gaviota tb but the gain is low, I think the lookup of tablebase need not always be called, but only in some cases, such as when depth> (8 - n_pieces) and npieces <6. what solution did you find?

    3. Overall the gain of tb is low, I guess most of the experienced gains come from the KRPKR endgame, which is common and difficult to play. A table base only helps if it corrects an evaluation that would otherwise be very wrong. A decent engine should not have such a problem so a tb cannot improve the situation very much. Gaviota is very strong and mature, even without a table base it will play excellent endgames. So there is not much to gain. If you do this with a weak engine it might be different (although weak engines often don't survive until the endgame).

      Gaviota tbs have a probe hard and probe soft mode, probe hard reads from disk and is slow but always returns a result (should be done in nodes of higher depths). Probe soft looks the position up in a endgame ram cache which is fast but might not return something if the position is not yet in.

      I haven't experienced with different settings of this as I only use the gaviota tb for verifying my recognizers and here I have a always probe hard mode while looping through all possible positions.

      Maybe in a future version of iCE I implement a tb lookup in the root node, because it is very annoying seeing iCE struggle to win a won endgame against an engine that gets the best defense from a table base.