How texel probes endgame tablebases
Posted: Sat Jul 16, 2016 8:54 am
Texel uses endgame tablebases somewhat differently than other chess engines. Both syzygy and gaviota tablebases can be used simultaneously to complement each other. This post describes how the tablebase probing works.
Goals
- Emulate DTM50 tablebases using publicly available tablebase files.
A DTM50 tablebase contains information needed to force a mate in the fewest possible moves while taking the 50-move draw rule into account. This is what a typical chess engine is already trying to achieve in non-tablebase positions. Therefore I consider DTM50 to be the metric most consistent with the normal behavior of a chess engine.
- Correctly handle the 50-move draw rule.
Texel is designed to play according to the FIDE laws of chess and must not incorrectly think that it can win in a position where more than 50 reversible moves are required to force a mate. This goal also means that texel is not a good choice for analysis of correspondence games where the 50-move draw rule is not used.
- Always play game-theoretically optimal moves when the root position is a tablebase position, even if the half-move clock is non-zero.
In order to be a useful analysis tool texel should be able to find optimal moves (i.e. preserving a win or draw) in tablebase positions even if the half-move clock is larger than 0 and even if sub-optimal moves have been played in order to reach the current position.
- Consistent hash table scores.
Information stored in the transposition table must not have different score ranges depending on if the root position is a TB position or not. This makes it possible to move back and forth in analysis mode without clearing the hash table and without getting inconsistent results.
- Small probe overhead before a TB position is reached in a game.
Retrieving tablebase information during game play and during analysis should be as efficient as possible, both for single threaded and multi-threaded search. This implies that the algorithm should intelligently decide which tablebase type (WDL, DTZ, DTM) to probe.
- Swindle mode to improve practical chances against imperfect opponents.
"Reasonable" moves should be played in order for the engine to not look stupid to a human observer and to improve winning chances when playing against opponents that do not have tablebase information available. For example, in a drawn KRBKR endgame the side with the bishop should not give up its rook even if that preserves the draw. Swindle mode can also be effective against opponents that have imperfect tablebase information available, such as only gaviota or nalimov tablebases that ignore the 50-move draw rule.
Implementation
A tablebase probe can return an exact score or an upper or lower bound, depending on circumstances. The returned score is 0 for a draw, or a mate score for a won/lost position.
- For a gaviota DTM probe the mate score is directly available from the tablebase.
- For a gaviota WDL probe a mate score bound is obtained by looking up the longest possible mate for the given tablebase class in a table that is included in the texel source code.
- For a syzygy WDL probe a mate score bound is obtained by looking up the longest possible mate from a table indexed by the tablebase class and the maximum number of remaining pawn moves. This table is computed using a dynamic programming algorithm when the engine starts.
- For a syzygy DTZ probe a mate score bound is obtained by a look-up from the same table as in the syzygy WDL case, but the DTZ value is used for the current position instead of assuming the largest possible DTZ value for the given tablebase class.
A tablebase probe thus returns similar information as a transposition table probe, and similar logic is used to decide if the probe result can be used to cut off the search tree. The main difference is that tablebase probes behave as if the draft is infinite, because they contain absolute truths instead of being based on imperfect search. In the recursive search function tablebases are probed directly after probing the transposition table.
If a tablebase probe returns a mate bound, but the bound is not good enough to cause a cut off, the search continues to recursively explore this node, just like if a transposition table probe would produce a not good enough bound. It is likely that the recursive search is not able to find a mate score in this case. However, since the tablebase probe always returns absolute truths the tablebase bound can nevertheless be returned as the score for this node.
This post contains some examples of TB probe score bounds.
There are several other details that the implementation has to handle:
- DTZ values from syzygy tablebases can in some cases be off by 1. This is a deliberate design choice that improves compression of the tablebase files. This has to be taken into account to provide correct mate score bounds and to get correct results when a position is on the edge of being drawn by the 50-move rule. In some such positions the syzygy tablebase probe result can not be used. This happens for example in the following position:
[D]7q/3N2k1/8/8/8/7Q/8/1K6 w - - 70 1
- Gaviota tablebases ignore the 50-move draw rule. A probe result can still be useful in many cases.
If the probe returns draw the position is a draw regardless of the half-move clock.
If the probe result is mate in X and X and the half-move clock are small enough to ensure the 50-move rule is irrelevant, the position is mate in X.
If the probe result is mate in X, the value of the position is at least draw regardless of the half-move clock.
- In order to prevent hash grafting that would make the path length to a mate position longer than the 50-move draw rule allows, the half-move clock is factored into the hash signature for all positions having few enough pieces to be potential tablebase positions.
- The syzygy probing code has been modified to make DTZ probes thread safe in the same way WDL probes are already thread safe. This is needed in the texel implementation because all search threads can perform DTZ probes anywhere in the search tree. In the syzygy reference implementation this is not needed because DTZ tables are only probed at the root position before the search starts.
- The gaviota probing code uses a tablebase cache for decompressed data. The implementation of this cache has been changed from a linked list to a hash table to make it fast even if the cache is very large.
- The gaviota probing code has been changed so that LZMA decompression can be performed in parallel by different threads.
- When probing the tablebases for a position the code tries to obtain the required information by probing the "most promising" tablebase first. For example, if the alpha/beta bounds are not mate scores, there is no need to probe a DTZ or DTM table since a WDL probe will be good enough to cause a cut off. If the alpha/beta bounds are mate scores a WDL probe is tried first anyway, because such a probe is cheaper than a DTZ/DTM probe and it might be enough to cause a cut off, for example if the probe result is a draw.
- A tablebase draw probe returns a 0 score. Since the engine is in constant "tablebase swindle mode", this 0 is converted to a score close to 0 in a way that encourages "reasonable" moves to be played. A cursed win is converted to a score in the range 35 - 69 centipawns, where the score is higher the closer to a real win the cursed win is. A blessed loss is similarly converted to a score in the range -69 - -35. A drawn position that is not a cursed win or a blessed loss is mapped to a score in the range -34 - +34. This score is calculated by applying a logarithm-like function to the score returned by the normal texel evaluation function for the position.
- If a tablebase probe returns a draw score and the remaining search depth is >= 16, the search is continued recursively instead of returning the swindle score described above. The idea is that continued searching helps the engine to obtain a higher swindle score, for example by forcing the opponent king to the edge of the board in a drawn KRBKR position. The hope is that a higher swindle score will increase the probability that the opponent makes a mistake. The >= 16 condition is applied in order to not spend too much time on "swindle nodes" when other parts of the search tree do not involve tablebase positions.
- If the root position is a pawn-less 4 man position, no gaviota or syzygy tablebases are available, the available thinking time is large enough, and the transposition table is large enough, texel will automatically generate a tablebase for the position and store it in the main transposition table. This feature could be useful in circumstances where tablebases are often not available, such as smartphones.
Results
The combination of DTZ, DTM and search can in some non-trivial cases obtain the same result as a DTM50 tablebase probe. This post describes one such case.
There are however lots of positions where a very deep search would be needed to get the same result as a DTM50 tablebase. In such positions texel will not be able to find the fastest possible mate, but it will still be able to find a reasonably fast mate.
Future improvements
It could make sense to make the swindle scores asymmetric since texel has perfect tablebase information even though its opponent might not. Handling this would be similar to handling contempt, and would require a strategy to deal with transposition table data consistency when the engine switches side, and in analysis mode. The idea is that a tablebase -69 score (blessed loss on the edge of being a real loss) is a guaranteed draw if texel plays the defending side (assuming the implementation is bug free), so a -69 TB score would be preferable over a -30 non-TB score, since the non-TB score indicates a small disadvantage that could lead to a loss.
In a lost TB position it could make sense to maximize the DTZ value instead of maximizing the DTM50 value, because that would increase the probability for an opponent to make a mistake if the opponent does not have a tablebase implementation that is aware of the 50-move draw rule.
When analyzing endgame studies and correspondence games it would be useful to be able to disable the 50-move draw rule.
Goals
- Emulate DTM50 tablebases using publicly available tablebase files.
A DTM50 tablebase contains information needed to force a mate in the fewest possible moves while taking the 50-move draw rule into account. This is what a typical chess engine is already trying to achieve in non-tablebase positions. Therefore I consider DTM50 to be the metric most consistent with the normal behavior of a chess engine.
- Correctly handle the 50-move draw rule.
Texel is designed to play according to the FIDE laws of chess and must not incorrectly think that it can win in a position where more than 50 reversible moves are required to force a mate. This goal also means that texel is not a good choice for analysis of correspondence games where the 50-move draw rule is not used.
- Always play game-theoretically optimal moves when the root position is a tablebase position, even if the half-move clock is non-zero.
In order to be a useful analysis tool texel should be able to find optimal moves (i.e. preserving a win or draw) in tablebase positions even if the half-move clock is larger than 0 and even if sub-optimal moves have been played in order to reach the current position.
- Consistent hash table scores.
Information stored in the transposition table must not have different score ranges depending on if the root position is a TB position or not. This makes it possible to move back and forth in analysis mode without clearing the hash table and without getting inconsistent results.
- Small probe overhead before a TB position is reached in a game.
Retrieving tablebase information during game play and during analysis should be as efficient as possible, both for single threaded and multi-threaded search. This implies that the algorithm should intelligently decide which tablebase type (WDL, DTZ, DTM) to probe.
- Swindle mode to improve practical chances against imperfect opponents.
"Reasonable" moves should be played in order for the engine to not look stupid to a human observer and to improve winning chances when playing against opponents that do not have tablebase information available. For example, in a drawn KRBKR endgame the side with the bishop should not give up its rook even if that preserves the draw. Swindle mode can also be effective against opponents that have imperfect tablebase information available, such as only gaviota or nalimov tablebases that ignore the 50-move draw rule.
Implementation
A tablebase probe can return an exact score or an upper or lower bound, depending on circumstances. The returned score is 0 for a draw, or a mate score for a won/lost position.
- For a gaviota DTM probe the mate score is directly available from the tablebase.
- For a gaviota WDL probe a mate score bound is obtained by looking up the longest possible mate for the given tablebase class in a table that is included in the texel source code.
- For a syzygy WDL probe a mate score bound is obtained by looking up the longest possible mate from a table indexed by the tablebase class and the maximum number of remaining pawn moves. This table is computed using a dynamic programming algorithm when the engine starts.
- For a syzygy DTZ probe a mate score bound is obtained by a look-up from the same table as in the syzygy WDL case, but the DTZ value is used for the current position instead of assuming the largest possible DTZ value for the given tablebase class.
A tablebase probe thus returns similar information as a transposition table probe, and similar logic is used to decide if the probe result can be used to cut off the search tree. The main difference is that tablebase probes behave as if the draft is infinite, because they contain absolute truths instead of being based on imperfect search. In the recursive search function tablebases are probed directly after probing the transposition table.
If a tablebase probe returns a mate bound, but the bound is not good enough to cause a cut off, the search continues to recursively explore this node, just like if a transposition table probe would produce a not good enough bound. It is likely that the recursive search is not able to find a mate score in this case. However, since the tablebase probe always returns absolute truths the tablebase bound can nevertheless be returned as the score for this node.
This post contains some examples of TB probe score bounds.
There are several other details that the implementation has to handle:
- DTZ values from syzygy tablebases can in some cases be off by 1. This is a deliberate design choice that improves compression of the tablebase files. This has to be taken into account to provide correct mate score bounds and to get correct results when a position is on the edge of being drawn by the 50-move rule. In some such positions the syzygy tablebase probe result can not be used. This happens for example in the following position:
[D]7q/3N2k1/8/8/8/7Q/8/1K6 w - - 70 1
- Gaviota tablebases ignore the 50-move draw rule. A probe result can still be useful in many cases.
If the probe returns draw the position is a draw regardless of the half-move clock.
If the probe result is mate in X and X and the half-move clock are small enough to ensure the 50-move rule is irrelevant, the position is mate in X.
If the probe result is mate in X, the value of the position is at least draw regardless of the half-move clock.
- In order to prevent hash grafting that would make the path length to a mate position longer than the 50-move draw rule allows, the half-move clock is factored into the hash signature for all positions having few enough pieces to be potential tablebase positions.
- The syzygy probing code has been modified to make DTZ probes thread safe in the same way WDL probes are already thread safe. This is needed in the texel implementation because all search threads can perform DTZ probes anywhere in the search tree. In the syzygy reference implementation this is not needed because DTZ tables are only probed at the root position before the search starts.
- The gaviota probing code uses a tablebase cache for decompressed data. The implementation of this cache has been changed from a linked list to a hash table to make it fast even if the cache is very large.
- The gaviota probing code has been changed so that LZMA decompression can be performed in parallel by different threads.
- When probing the tablebases for a position the code tries to obtain the required information by probing the "most promising" tablebase first. For example, if the alpha/beta bounds are not mate scores, there is no need to probe a DTZ or DTM table since a WDL probe will be good enough to cause a cut off. If the alpha/beta bounds are mate scores a WDL probe is tried first anyway, because such a probe is cheaper than a DTZ/DTM probe and it might be enough to cause a cut off, for example if the probe result is a draw.
- A tablebase draw probe returns a 0 score. Since the engine is in constant "tablebase swindle mode", this 0 is converted to a score close to 0 in a way that encourages "reasonable" moves to be played. A cursed win is converted to a score in the range 35 - 69 centipawns, where the score is higher the closer to a real win the cursed win is. A blessed loss is similarly converted to a score in the range -69 - -35. A drawn position that is not a cursed win or a blessed loss is mapped to a score in the range -34 - +34. This score is calculated by applying a logarithm-like function to the score returned by the normal texel evaluation function for the position.
- If a tablebase probe returns a draw score and the remaining search depth is >= 16, the search is continued recursively instead of returning the swindle score described above. The idea is that continued searching helps the engine to obtain a higher swindle score, for example by forcing the opponent king to the edge of the board in a drawn KRBKR position. The hope is that a higher swindle score will increase the probability that the opponent makes a mistake. The >= 16 condition is applied in order to not spend too much time on "swindle nodes" when other parts of the search tree do not involve tablebase positions.
- If the root position is a pawn-less 4 man position, no gaviota or syzygy tablebases are available, the available thinking time is large enough, and the transposition table is large enough, texel will automatically generate a tablebase for the position and store it in the main transposition table. This feature could be useful in circumstances where tablebases are often not available, such as smartphones.
Results
The combination of DTZ, DTM and search can in some non-trivial cases obtain the same result as a DTM50 tablebase probe. This post describes one such case.
There are however lots of positions where a very deep search would be needed to get the same result as a DTM50 tablebase. In such positions texel will not be able to find the fastest possible mate, but it will still be able to find a reasonably fast mate.
Future improvements
It could make sense to make the swindle scores asymmetric since texel has perfect tablebase information even though its opponent might not. Handling this would be similar to handling contempt, and would require a strategy to deal with transposition table data consistency when the engine switches side, and in analysis mode. The idea is that a tablebase -69 score (blessed loss on the edge of being a real loss) is a guaranteed draw if texel plays the defending side (assuming the implementation is bug free), so a -69 TB score would be preferable over a -30 non-TB score, since the non-TB score indicates a small disadvantage that could lead to a loss.
In a lost TB position it could make sense to maximize the DTZ value instead of maximizing the DTM50 value, because that would increase the probability for an opponent to make a mistake if the opponent does not have a tablebase implementation that is aware of the 50-move draw rule.
When analyzing endgame studies and correspondence games it would be useful to be able to disable the 50-move draw rule.