evaluating tablebases draws

[Uri Blass]

I think that the problem with probing tablebases is discontinuous evaluation function that does not know which position is better.

It may be better to have +2 evaluation for a draw(KR vs KPP) and +1 evaluation for a loss(KR vs KPPP) without tablebases because you prefer the draw and not
to have correct 0 evaluation for the draw(KRKPP) thanks to tablebases so you prefer the KR vs KPPP loss.

In order to fight against this problem I suggest the following idea after you probed tablebases and found a draw.

suppose that your program has static evaluation e for some quiet tablebase drawn position.

My idea is to calculate E(e,d) based on many searches without tablebases and get some average for expected result by searching to depth d.

Later change the tablebases code from returning a draw when you get draw from tablebases to returning E(e,d) when e is the static evaluation and d is the remaining depth.

The question is if this idea is going to perform better relative to returning 0.

I wonder if people tested it in games.

[Daniel Shawul]

This is not necessarily a problem of tablebases but that comparing scores of positions searched to different depths, one with a terminal WDL score (meaning searched to maximum depth) and the other with a heuristic score at some depth, could lead you to choose sub-optimal moves. Pathological cases where searching deeper leads to sub-optimal play are well known (Nau), and ofcourse the Chinook guys had serious problems with their tablebases because it assumes the opponent is as strong as itself and does not try to win a positon where the TB says is DRAW. In your example, I think you are assuming KRvkpp is in bitbases (5-men) while KRvkppp (6-men) is not, otherwise I don't see a problem as first pos is a DRAW and the second a LOSS. You can ofcourse construct the same example for N and N+1 TBs

[bob]

This is not necessarily a problem of tablebases but that comparing scores of positions searched to different depths, one with a terminal WDL score (meaning searched to maximum depth) and the other with a heuristic score at some depth, could lead you to choose sub-optimal moves. Pathological cases where searching deeper leads to sub-optimal play are well known (Nau), and ofcourse the Chinook guys had serious problems with their tablebases because it assumes the opponent is as strong as itself and does not try to win a positon where the TB says is DRAW. In your example, I think you are assuming KRvkpp is in bitbases (5-men) while KRvkppp (6-men) is not, otherwise I don't see a problem as first pos is a DRAW and the second a LOSS. You can ofcourse construct the same example for N and N+1 TBs

I took his comments as the normal draw != draw to a logical player. For example, KRP vs KR, table base may say draw. If so, it will ALSO say draw for any resulting KRKR position. And in years gone by, a program might pick either equally. There are known solutions to this, from simple to complex...

[Cardoso]

This is not necessarily a problem of tablebases but that comparing scores of positions searched to different depths, one with a terminal WDL score (meaning searched to maximum depth) and the other with a heuristic score at some depth, could lead you to choose sub-optimal moves. Pathological cases where searching deeper leads to sub-optimal play are well known (Nau), and ofcourse the Chinook guys had serious problems with their tablebases because it assumes the opponent is as strong as itself and does not try to win a positon where the TB says is DRAW. In your example, I think you are assuming KRvkpp is in bitbases (5-men) while KRvkppp (6-men) is not, otherwise I don't see a problem as first pos is a DRAW and the second a LOSS. You can ofcourse construct the same example for N and N+1 TBs

I took his comments as the normal draw != draw to a logical player. For example, KRP vs KR, table base may say draw. If so, it will ALSO say draw for any resulting KRKR position. And in years gone by, a program might pick either equally. There are known solutions to this, from simple to complex...

What I do in drawn TB positions is to continue searching (with TBs on, contrary to some wich turn off TBs during draw searches) with a very slight (recursive) reduction (I use fractional plies since they provide softer and more fine grained reductions/extensions), this will provide a better score better than simply return 0 or (draw_score +-1).
The reduced search is not done if alpha has a winning exact TB score (for DTM TBs) or a KNOWN_WIN (for WDL TBs) since a draw search can't return a winning/loosing score.
Also if alpha has a -KNOWN_WIN score we can return immediately with current material score.
Although draw searches increase node count the hashtable will soften a bit this problem (don't forget in the hashtable to store the depth _before_ the reduction is done, otherwise if the search encounters the same drawn TB position again will search it again due to a slight insufficient draft).

my scoring range is from -32000 to +32000,
MATE=32000;
PLY=8;
KNOWN_WIN=15000; //for WDL TBs

best regards,
Alvaro




Surely it will increase node count, but it is better.

[syzygy]

What I do in drawn TB positions is to continue searching (with TBs on, contrary to some wich turn off TBs during draw searches) with a very slight (recursive) reduction (I use fractional plies since they provide softer and more fine grained reductions/extensions), this will provide a better score better than simply return 0 or (draw_score +-1).

It is important to distinguish between the case that the root position is a TB draw and the case that the root position is not yet in the TBs. I assume you are talking about the latter case?

I would be very surprised if not pruning the tree but only reducing the tree gains anything that could outweigh giving up some of the most important gain from TBs.

And I'm not sure what you are returning in the end. Not the draw score, apparently. Do you prefer a drawn KRPvKR to be evaluated as +1? In contrived cases this can help but in general surely not.

Or are you talking about the case that the root position is a known TB draw?

[Cardoso]

It is important to distinguish between the case that the root position is a TB draw and the case that the root position is not yet in the TBs. I assume you are talking about the latter case?

the latter, at the root I don't do TB probes at all.

I would be very surprised if not pruning the tree but only reducing the tree gains anything that could outweigh giving up some of the most important gain from TBs.

I understand it's very very tempting to always prune on a TB drawn position, since the search tree is much smaller, but I haven't found anything better so far. You see if I prune immediately returning a zero, my engine will give away pieces, if I return the position static evaluation my engine will switch to wood pusher mode .
Maybe we should invent a new TB with only draw scores, of course since the majority of TB positions are draws the compression would be very bad (using 2 bytes per position), and the time to compute them would require at the very least distributed computing, forget it .

And I'm not sure what you are returning in the end. Not the draw score, apparently. Do you prefer a drawn KRPvKR to be evaluated as +1? In contrived cases this can help but in general surely not.

Sorry Ronald, but my engine is a checkers engine, but I suppose some of these ideas can be applied to chess. But it seems to me you should avoid the temptation of (at least always) return +1 for a TB drawn KRPvKR position. Do at least a short search maybe with depth/2 or depth/4 remaining depth. Of course I don't have any experience in programming a chess engine. Also making some testing matches can give you some insight about my preference in continuing searching in tb drawn positions.

best regards,
Alvaro

[syzygy]

You see if I prune immediately returning a zero, my engine will give away pieces, if I return the position static evaluation my engine will switch to wood pusher mode .

What do you mean by giving away pieces?

If you mean giving away pieces when the root position is a TB draw, then we are talking about the case in which the root position is in the TBs. Again, it is very important to distinguish between these two cases:
1. root position is in the TBs.
2. root position is not in the TBs.

These two cases deserve a very different treatment.

Note that I'm not asking whether you probe at the root. I am asking if you're talking about case 1 or case 2.

[Cardoso]

You see if I prune immediately returning a zero, my engine will give away pieces, if I return the position static evaluation my engine will switch to wood pusher mode .

What do you mean by giving away pieces?

If you mean giving away pieces when the root position is a TB draw, then we are talking about the case in which the root position is in the TBs. Again, it is very important to distinguish between these two cases:
1. root position is in the TBs.
2. root position is not in the TBs.

These two cases deserve a very different treatment.

Note that I'm not asking whether you probe at the root. I am asking if you're talking about case 1 or case 2.

Ahh, sorry I missed we were talking about root positions only.
In this case please disregard my comments, they are of no use to you.

best regards,
Alvaro

[syzygy]

Ahh, sorry I missed we were talking about root positions only.
In this case please disregard my comments, they are of no use to you.

No, I am not talking about root positions only.

My point is that I use tablebases differently dependent on whether I am in case 1 or in case 2.

I can see that the problem of "giving away pieces" exists in case 1. If the root position is a TB draw, that does not mean the engine should play just any move that keeps the draw. Throwing away pieces for the only reason that the resulting position is still a draw is ugly and should be solved.

In case 2 the situation is very different. The game will usually not have been decided yet and you just want to know which endings are won, drawn or lost. It is only of minor importance to distinguish between draws deep in the tree. In my view this minor importance is greatly outweighed by the advantage of being able to cut whole branches with perftect knowledge.

So we are talking about probing in the tree, but I want to if we are talking about doing a search when the root position has a known TB result (case 1) or if we are talking about doing a search when the root position has not yet reached the TBs (case 2).

[Cardoso]

Ahh, sorry I missed we were talking about root positions only.
In this case please disregard my comments, they are of no use to you.

No, I am not talking about root positions only.

My point is that I use tablebases differently dependent on whether I am in case 1 or in case 2.

I can see that the problem of "giving away pieces" exists in case 1. If the root position is a TB draw, that does not mean the engine should play just any move that keeps the draw. Throwing away pieces for the only reason that the resulting position is still a draw is ugly and should be solved.

In case 2 the situation is very different. The game will usually not have been decided yet and you just want to know which endings are won, drawn or lost. It is only of minor importance to distinguish between draws deep in the tree. In my view this minor importance is greatly outweighed by the advantage of being able to cut whole branches with perftect knowledge.

So we are talking about probing in the tree, but I want to if we are talking about doing a search when the root position has a known TB result (case 1) or if we are talking about doing a search when the root position has not yet reached the TBs (case 2).

Since I don't do TB probes at the root the draw searches are also not done at the root. Draw searches are only done if the current position is in the TB and it is a TB draws[/u] , and of course if alpha is not an exact dtm win nor a wdl KNOWN_WIN.
My draw searches finds lines in witch every position is also a TB draw.
So what I do does not fit in your needs since you are asking the root case.
However at case 1 I suppose one could select only the moves with the best TB theoretical value (wdl TBs) and discard the rest. This way you prune worse branches completely and save time.
At case 2 I really don't know what to do except continue searching the usual way. But maybe you can add specific endgame heuristic knowledge, but since you have TBs with 5 or 6 pieces this means you must add heuristic knowledge to 7 piece endgames and up, and this is too complex.

best regards,
Alvaro