Incorporating Endgame tablebases

[universecoder]

How would I go about adding an endgame tablebase to a chess engine? What would be the steps to do so?

At one point, do I just stop the search and switch to the tablebase?

[Dann Corbit]

When a position on the search has a piece signature that matches one of your tablebase files you can do a lookup.

A search of the archives will show examples. It's a pretty popular question.

[hgm]

The engine should keep track of the material composition, from which it can easily recognize which end-game it is in. An advanced engine would have this anyway, and use it to decide which special evaluation routine to call for the various end-games, or which drawishness factor to apply to the normal evaluation.

Special end-game evaluation routines can come in two kinds: those whose evaluation is final, which should abort further searching (e.g. KNK), or those whose evaluation could benefit from deeper search.

You then only have to replace these special evaluation routines for the compositions you have EGT for by one that probes the applicable EGT, and converts the DTM found in it to a mate score, and returns that as evaluation, indicating it is 'final'. In case the EGT says draw, you could consider to just apply a large reduction factor to the normal evaluation, and allow the search to go on, in the hope you can swindle the opponent.

[Sven]

The idea of replacing special endgame evaluation by EGT probing is fine. However, in the implementation I would still see EGT probing in the context of search, not evaluation. (You probably did not intend to imply anything else, of course.) Otherwise you would indeed have to always provide the information about an evaluation score being "final" together with the score itself which increases complexity.

Furthermore, to simplify the implementation I would avoid probing the EGT at the root node, for obvious reasons (you need to play a move anyway but the EGT only provides a score). As a further (minor) optimization one could avoid to check the material signature at all if we are at least two plies below the root and the previous move was not a capture or promotion.

[hgm]

The idea of replacing special endgame evaluation by EGT probing is fine. However, in the implementation I would still see EGT probing in the context of search, not evaluation. (You probably did not intend to imply anything else, of course.) Otherwise you would indeed have to always provide the information about an evaluation score being "final" together with the score itself which increases complexity.

But some non-EGT-based special evaluation already requires that too. Especially when you detect a draw, deeper search can be completely pointless. I already mentioned KNK. Returning whether an evaluation is final or not is always a standard feature for me, in the handling of the special evaluation.

Furthermore, to simplify the implementation I would avoid probing the EGT at the root node, for obvious reasons (you need to play a move anyway but the EGT only provides a score). As a further (minor) optimization one could avoid to check the material signature at all if we are at least two plies below the root and the previous move was not a capture or promotion.

Indeed, in HaQiKi D I suppress probing in the few ply, to make sure the moves that are actually played will be subject to repetition detection. (Which the EGT does not take into account.) Otherwise you can easily get stuck in a loop that repeats when you are in a drawn end-game, even causing the engine to lose if this happens to be a perpetual check or chase.

[Sven]

The idea of replacing special endgame evaluation by EGT probing is fine. However, in the implementation I would still see EGT probing in the context of search, not evaluation. (You probably did not intend to imply anything else, of course.) Otherwise you would indeed have to always provide the information about an evaluation score being "final" together with the score itself which increases complexity.

But some non-EGT-based special evaluation already requires that too. Especially when you detect a draw, deeper search can be completely pointless. I already mentioned KNK. Returning whether an evaluation is final or not is always a standard feature for me, in the handling of the special evaluation.

Furthermore, to simplify the implementation I would avoid probing the EGT at the root node, for obvious reasons (you need to play a move anyway but the EGT only provides a score). As a further (minor) optimization one could avoid to check the material signature at all if we are at least two plies below the root and the previous move was not a capture or promotion.

Indeed, in HaQiKi D I suppress probing in the few ply, to make sure the moves that are actually played will be subject to repetition detection. (Which the EGT does not take into account.) Otherwise you can easily get stuck in a loop that repeats when you are in a drawn end-game, even causing the engine to lose if this happens to be a perpetual check or chase.

If I want to probe EGT at the top of each node then I would have to call the evaluation function at that point if I would follow your system. That is not what I would ever want to do. For me the static evaluation function has a totally different task, it is not meant to determine exact scores. Also the fact that it would return mate scores would break the assumption that the score returned by static eval is within the range [-MAX_EVAL_SCORE .. +MAX_EVAL_SCORE]. It would simply complicate everything.

Probing EGT within the search is much simpler, and it keeps the usual semantics of the static evaluation function. Checking whether the current position is a terminal node (and possibly returning a mate score) can be done with a separate function that is not related to static eval.

[hgm]

I always call the evaluation in every node anyway. For instance to determine if it makes sense to try a null move.

I am not sure what point you want to make anyway. Search has to call evaluation. So evaluation takes place in the search. How you divide up what has to be done over functions is a matter of convenience and/or efficiency.

I don't see why you would need the assumption that eval is between mate / mated scores. If I need the score just for returning it, who cares what it is? Mate scores can be returned just as easily as any other score.

The design I consider simplest and cleanest is to have a 'master evaluation', which decides what specific evaluation method to use depending on the material composition (general eval, scaled general eval, offsetted general eval, dedicated eval). The dedicated evaluations can request a cutoff. You could make them set a flag for that, but I usually use a the kludge of adding 1G to the intended score to label it as 'final'.

Code: Select all

#define E_FINAL &#40;1<<29&#41;

#define M_SCALED 200
#define M_SPECIAL 220

int
Evaluate&#40;)
&#123;
  unsigned char materialCode = ProbeMaterialHash&#40;);
  if&#40;materialCode > M_SPECIAL&#41;
    return (*evalFunctions&#91;materialCode - M_SPECIAL&#93;)();
  int eval = NaiveEval&#40;);
  if&#40;materialCode > M_SCALED&#41;
    return &#40;WhiteIsAhed&#40;eval&#41; ? whiteFactor&#91;materialCode - M_SCALED&#93; &#58; blackFactor&#91;materialCode - M_SCALED&#93;) * eval;
  return materialCode - M_SCALED/2 + eval;
&#125;

int
Search&#40;)
&#123;
  int curEval = Evaluate&#40;);
  if&#40;curEval > E_FINAL&#41; return curEval - 2*E_FINAL; // eval requested cutoff
  ...
&#125;

It seems hard to do it otherwise without duplicating code for testing what material composition you have.

[Sven]

Search has to call evaluation. So evaluation takes place in the search. How you divide up what has to be done over functions is a matter of convenience and/or efficiency.

This is a statement that I can agree upon. So let's say: you do it your way and I do it my way, and everything's fine

[Dann Corbit]

I think we can envision it either way.

A tablebase lookup is either a perfect evaluation or a perfect search.
The information returned is "utterly correct" and can be fully trusted with no further effort (assuming that the tablebase file is correct and we have probed correctly).

Caveat:
Depending on the tablebase file type, we may need further searching, especially if an optimal path is desired. The most popular types like Syzygy and bitbase files do not have minimal distance to mate stored.

But the information returned will be "utterly correct", at any rate.

[hgm]

So let's say: you do it your way and I do it my way, and everything's fine

Sure, I wasn't planning to change.

But it would be helpful to the OP to see the pseudo-code of how you do it, so that everyone can judge for himself if and how that simplifies things.