Natural TB

[Evert]

So we should think of a tbwin,draw,loss as a lowerbound, exact score, upperbound... Is this theoretically correct?

I think so.
If you have perfect (DTM50) information, then the tablebase contains an exact score. If you have DTZ50 information and it indicates the position is a draw (cursed win, draw, blessed loss), you can treat this as an exact score, always.
Where it has incomplete information is for win/loss situations: you know the position is won (lost) taking into account the 50-move rule, but you don't know the fastest (DTM50) path to win. You do know a win though, which is a lower-bound to the actual score.

This has always been my understanding, but someone who has spent more time thinking about it than I have may be able to point to a subtlety I missed.

[Dirt]

As a secondary side effect I am trying hard to avoid DTZ probing because I think that if only WDL tables are present we can easily have 5-men in memory (374M for WDL against 922M for WDL+DTZ)

Is loading in one 5-piece DTZ table per game too much? I suppose if you are very short of time it might be, but that decision looks to be better made at the time.

[hgm]

So we should think of a tbwin,draw,loss as a lowerbound, exact score, upperbound... Is this theoretically correct?

If the WDL info says it is a win or loss, you could give it a 'mate-in-undetermined-number-of-moves' score. Which is lower than any mate in a determined number of moves, but higher than any heuristic eval score. This means the score is a lower bound; the true score will be a mate in some number of moves.

In general it does not pay to treat it as lower bound as you would for hash hits, however. So when the bound is not enough to give you a cutoff, you would not bother to resolve it by search, and use the bound like it was an exact score. That means the engine would prefer a determined mate over any undetermined mate, even though the latter could in theory still be faster.

You could elaborate on that by remembering for each material combination what the largest DTM is of any won position in it, and use that as the lower bound. Then the engine would prefer conversions that in general would be faster to win. That should make it shy away from throwing away material for nothing. When you cut at the conversion point, this would still make it overlook mates through a sacrifice. Plus that any capture of pieces would seem good, even if the piece was protected, as the recapture is masked by the probe. So KQBNKP would likely still lead to a Q for P sac. This suggests that it would be best to not cut the search in a non-quiet situation. I.e. if the probe says 'win', you would run a QS (which probed in its leaves) to see if the opponent could improve its score (by now probing a more favorable EGT). Then Q-for-P sacs in KQBNKP would get the score for conversion to KBNK, and not those of the far faster KQBNK.

[lucasart]

Marco,

I ran a test with natural_tb:

Code: Select all

$ ./natural_tb 
Stockfish 310516 64 BMI2 by T. Romstad, M. Costalba, J. Kiiski, G. Linscott
uci
id name Stockfish 310516 64 BMI2
id author T. Romstad, M. Costalba, J. Kiiski, G. Linscott

option name Write Debug Log type check default false
option name Contempt type spin default 0 min -100 max 100
option name Threads type spin default 1 min 1 max 128
option name Hash type spin default 16 min 1 max 1048576
option name Clear Hash type button
option name Ponder type check default false
option name MultiPV type spin default 1 min 1 max 500
option name Skill Level type spin default 20 min 0 max 20
option name Move Overhead type spin default 30 min 0 max 5000
option name Minimum Thinking Time type spin default 20 min 0 max 5000
option name Slow Mover type spin default 89 min 10 max 1000
option name nodestime type spin default 0 min 0 max 10000
option name UCI_Chess960 type check default false
option name SyzygyPath type string default <empty>
option name SyzygyProbeDepth type spin default 1 min 1 max 100
option name Syzygy50MoveRule type check default true
option name SyzygyProbeLimit type spin default 6 min 0 max 6
uciok
setoption name SyzygyPath value ../syzygy
info string Found 145 tablebases
isready
readyok
ucinewgame
info string Found 145 tablebases
position fen kbb5/8/8/8/8/8/KN6/8 b - - 0 1
d

 +---+---+---+---+---+---+---+---+
 | k | b | b |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 | K | N |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+

Fen&#58; kbb5/8/8/8/8/8/KN6/8 b - - 0 1
Key&#58; DB63D155EAD389AF
Checkers&#58; 
Tablebases WDL&#58;  Win &#40;Success&#41;
Tablebases DTZ&#58;   99 &#40;Success&#41;
go depth 10
info depth 1 seldepth 2 multipv 1 score cp 389 nodes 15 nps 7500 tbhits 0 time 2 pv c8e6 a2b1
info depth 2 seldepth 4 multipv 1 score cp 422 nodes 54 nps 18000 tbhits 7 time 3 pv c8e6 a2b1 b8e5
info depth 3 seldepth 6 multipv 1 score cp 425 nodes 206 nps 68666 tbhits 48 time 3 pv a8b7 a2b1 c8f5 b1a2
info depth 4 seldepth 6 multipv 1 score cp 458 nodes 413 nps 103250 tbhits 98 time 4 pv a8b7 a2b1 c8f5 b1a2 b8e5
info depth 5 seldepth 8 multipv 1 score cp 458 nodes 779 nps 194750 tbhits 173 time 4 pv a8b7 a2b1 c8f5 b1a2 f5e6 a2b1 b8e5
info depth 6 seldepth 9 multipv 1 score cp 477 nodes 2946 nps 368250 tbhits 854 time 8 pv a8b7 a2b1 c8f5 b1a2 b8e5 b2c4 f5e6
info depth 7 seldepth 10 multipv 1 score cp 494 nodes 11546 nps 679176 tbhits 4319 time 17 pv c8e6 a2b1 b8e5 b1a1 a8b7 a1b1 e6f5 b1a2 b7c6
info depth 8 seldepth 16 multipv 1 score cp 496 nodes 16941 nps 651576 tbhits 5694 time 26 pv a8b7 a2b1 c8f5 b1a2 f5e6 a2b1 b8d6 b1c2 e6f5 c2d1 b7c6
info depth 9 seldepth 16 multipv 1 score cp 3401 nodes 20982 nps 676838 tbhits 6718 time 31 pv a8b7 a2b1 c8f5 b1a2 b8e5 a2b3 f5e6 b3c2 b7b6 c2b1 e6f5 b1a1 b6c6 a1a2
info depth 10 seldepth 20 multipv 1 score cp 2889 nodes 28631 nps 715775 tbhits 8811 time 40 pv a8b7 a2b1 c8f5 b1a2 b8d6 a2a1 f5d7 a1b1 d7e6 b1c2 e6f5 c2d1 d6f4 b2c4 f5e6
bestmove a8b7 ponder a2b1
position fen kbb5/8/8/8/8/8/KN6/8 b - - 0 1 moves a8b7
d

 +---+---+---+---+---+---+---+---+
 |   | b | b |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   | k |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 | K | N |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+

Fen&#58; 1bb5/1k6/8/8/8/8/KN6/8 w - - 1 2
Key&#58; C51967FC9B106625
Checkers&#58; 
Tablebases WDL&#58; Loss &#40;Success&#41;
Tablebases DTZ&#58;  -98 &#40;Success&#41;
go depth 10  
info depth 1 seldepth 1 multipv 1 score cp -2889 nodes 17 nps 17000 tbhits 0 time 1 pv a2b1
info depth 2 seldepth 3 multipv 1 score cp -2889 nodes 36 nps 36000 tbhits 0 time 1 pv a2b1 c8f5 b1a2
info depth 3 seldepth 4 multipv 1 score cp -2889 nodes 57 nps 57000 tbhits 0 time 1 pv a2b1 c8f5 b1a2 b8d6
info depth 4 seldepth 5 multipv 1 score cp -2889 nodes 81 nps 81000 tbhits 0 time 1 pv a2b1 c8f5 b1a2 b8d6 a2a1
info depth 5 seldepth 6 multipv 1 score cp -2889 nodes 107 nps 107000 tbhits 0 time 1 pv a2b1 c8f5 b1a2 b8d6 a2a1 f5d7
info depth 6 seldepth 7 multipv 1 score cp -2889 nodes 138 nps 138000 tbhits 0 time 1 pv a2b1 c8f5 b1a2 b8d6 a2a1 f5d7 a1b1
info depth 7 seldepth 8 multipv 1 score cp -2889 nodes 171 nps 171000 tbhits 0 time 1 pv a2b1 c8f5 b1a2 b8d6 a2a1 f5d7 a1b1 d7e6
info depth 8 seldepth 9 multipv 1 score cp -2889 nodes 213 nps 106500 tbhits 0 time 2 pv a2b1 c8f5 b1a2 b8d6 a2a1 f5d7 a1b1 d7e6 b1c2
info depth 9 seldepth 12 multipv 1 score cp -2889 nodes 276 nps 138000 tbhits 0 time 2 pv a2b1 c8f5 b1a2 b8d6 a2a1 f5d7 a1b1 d7e6 b1c2 e6f5 c2d1 d6f4
info depth 10 seldepth 14 multipv 1 score cp -2889 nodes 410 nps 205000 tbhits 15 time 2 pv a2b1 c8f5 b1a2 b8d6 a2a1 f5d7 a1b1 d7e6 b1c2 e6f5 c2d1 d6f4 b2c4 f5e6
bestmove a2b1 ponder c8f5
position fen 1bb5/1k6/8/8/8/8/KN6/8 w - - 1 2 moves a2b1
d

 +---+---+---+---+---+---+---+---+
 |   | b | b |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   | k |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   | N |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   | K |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+

Fen&#58; 1bb5/1k6/8/8/8/8/1N6/1K6 b - - 2 2
Key&#58; FA7C404DC9AE47DB
Checkers&#58; 
Tablebases WDL&#58;  Win &#40;Success&#41;
Tablebases DTZ&#58;   91 &#40;Success&#41;

So:
* I took a very hard to win TB position (KBBKN): mate in 99 plies, just before the 50 move rule.
* A quick depth=10 search, and SF found a (the?) best move, reducing DTZ to 98: a8b7!
* After playing a8b7, it's now white's turn. White is lost, even with best play, but he should try to maximize DTZ to complicate Black's task at winning. SF does not find the correct move at depth=10 here, and instead finds an inferior that reduces DTZ to 91.

I try again, flush the TT, and search at depth=12, a bit deeper:

Code: Select all

ucinewgame
info string Found 145 tablebases
position fen 1bb5/1k6/8/8/8/8/KN6/8 w - - 1 2
go depth 12
info depth 1 seldepth 1 multipv 1 score cp -379 nodes 29 nps 14500 tbhits 0 time 2 pv b2c4
info depth 2 seldepth 2 multipv 1 score cp -375 nodes 77 nps 38500 tbhits 11 time 2 pv b2c4 b8f4
info depth 3 seldepth 4 multipv 1 score cp -429 nodes 310 nps 155000 tbhits 56 time 2 pv b2d1 b8e5 a2b1
info depth 4 seldepth 7 multipv 1 score cp -444 nodes 758 nps 252666 tbhits 185 time 3 pv b2d1 b7c6 d1f2 c8e6 a2b2
info depth 5 seldepth 8 multipv 1 score cp -465 nodes 2182 nps 436400 tbhits 673 time 5 pv b2d1 b7c6 d1f2 b8g3 f2d1 c8e6 a2b2
info depth 6 seldepth 9 multipv 1 score cp -466 nodes 3506 nps 500857 tbhits 1126 time 7 pv b2d1 c8e6 a2b2 e6f5 d1f2 b8e5 b2a2 b7c6
info depth 7 seldepth 11 multipv 1 score cp -509 nodes 9127 nps 608466 tbhits 3210 time 15 pv b2d1 b7c6 d1f2 b8g3 f2d1 g3e5 d1b2 c8e6 a2b1
info depth 8 seldepth 12 multipv 1 score cp -534 nodes 12954 nps 647700 tbhits 4439 time 20 pv b2d1 c8g4 d1f2 g4f5 a2b2 b8e5 b2a2 f5e6 a2b1 b7c6
info depth 9 seldepth 13 multipv 1 score cp -3614 nodes 37223 nps 907878 tbhits 14500 time 41 pv b2d1 b7c6 d1f2 c8f5 a2b2 b8e5 b2a3 f5e6 f2d1 e5d6 a3b2
info depth 10 seldepth 19 multipv 1 score cp -2960 nodes 56872 nps 888625 tbhits 19416 time 64 pv b2d1 b7c6 d1f2 c8f5 a2b2 b8e5 b2a3 f5e6 f2d1 e5f4 a3b2
info depth 11 seldepth 19 multipv 1 score cp -3353 nodes 64845 nps 913309 tbhits 21779 time 71 pv b2d1 b7c6 d1f2 c8f5 a2b2 b8e5 b2a3 f5e6 f2d1 e5d6 a3b2 d6f4 b2a3
info depth 12 seldepth 23 multipv 1 score cp -3837 nodes 101005 nps 1010050 tbhits 33925 time 100 pv b2d1 c8f5 a2b3 b7c6 b3a3 f5c2 d1e3 c2g6 a3a4 b8f4 e3c4 g6f7 a4b3
bestmove b2d1 ponder c8f5
position fen 1bb5/1k6/8/8/8/8/KN6/8 w - - 1 2 moves b2d1
d

 +---+---+---+---+---+---+---+---+
 |   | b | b |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   | k |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 | K |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   | N |   |   |   |   |
 +---+---+---+---+---+---+---+---+

Fen: 1bb5/1k6/8/8/8/8/K7/3N4 b - - 2 2
Key: EB5DE4100947FBAE
Checkers: 
Tablebases WDL:  Win (Success)
Tablebases DTZ:   93 (Success)

SF now finds a slightly better defense, bringing DTZ to 93, but still not the best.

To sum up:
* Negative: We lose the "best defense" (defined as: maximize DTZ when you're losing). Sure it has no elo impact, especially if then opponent uses TBs, but it has an educational value for those studying endgames if SF can show the correct defense in TB positions.
* Positive: Symmetrically, we lose the "best attack" defined as minimizing DTZ. However, the real target is DTM not DTZ. More often than not, we see these unnatural sacrifices aiming at reducing DTZ instead of aiming at reducing DTM (for which it's best to let the search do its work). So I think we have a gain overall in this area.
* Positive: code simplification. And we don't need DTZ tables (reduce by half the size of the download for users).

So, I really think your patch has merit. However, I think the best course of action is to first merge the syzygy branch into master: no functional change, great code cleanup/documentation. And then do more testing on this natural_tb, before eventually mergine (unless we find real problems that are not trivial to resolve).

[Michel]

In general it does not pay to treat it as lower bound as you would for hash hits, however.

Why not? IMHO using TB hits in this way would precisely have the effect that it would continue to search for a mate, when it makes sense to do so (i.e. when the window contains mate scores).

If this idea is correct (I am not completely sure) then no hacks would be required to resolve the issue of mate blindness.

And no performance sacrifices either since we only continue searching if the root window has already been enlarged so much that it contains mate scores. This will only happen (in aspiration search) if the position has already been determined to be a win.

[mcostalba]

So, I really think your patch has merit. However, I think the best course of action is to first merge the syzygy branch into master: no functional change, great code cleanup/documentation. And then do more testing on this natural_tb, before eventually mergine (unless we find real problems that are not trivial to resolve).

Thanks for your quick test.

At the moment I have no urge to merge anything in SF. Indeed I think I will not merge any syzygy new version during my maintenance period.

I think we should instead systematically test and verify the "Natural TB": many real games end tests are needed to get a correct picture of this experiment.

And at one point a direct match with syzgy will be needed to measure any ELO loss from syzygy.

[kbhearn]

You're going to find it difficult to measure ELO loss from hacking away the DTZ tables. Not because it's not costing you ELO, but because the positions where it's important are relatively infrequent so it'll be impossible to measure with a general elo test, you'll be measuring noise.

You will however most likely be able to find some truly difficult example positions where without the dtz tables you stumble into a cursed win from an uncursed one if you don't use the tables. And seeing as using dtz tables only costs you once the root is already in tablebases, the cost is effectively nonexistent to do so except possibly under ultrabullet conditions if a single access per node is going to cause a flag...

[mcostalba]

You will however most likely be able to find some truly difficult example positions where without the dtz tables you stumble into a cursed win from an uncursed one if you don't use the tables.

This is not my target.

Usually I would not have replied to such a post but because I see many people are interested and this is a hot topic (definitely hotter than what it should be), I state again my targets with "Natural TB":

1) Lead to a game play that is ELO equivalent to current TB

2) Avoid current TB artifacts that sound unnatural (at least to me)

[petero2]

In general it does not pay to treat it as lower bound as you would for hash hits, however.

Why not? IMHO using TB hits in this way would precisely have the effect that it would continue to search for a mate, when it makes sense to do so (i.e. when the window contains mate scores).

If this idea is correct (I am not completely sure) then no hacks would be required to resolve the issue of mate blindness.

And no performance sacrifices either since we only continue searching if the root window has already been enlarged so much that it contains mate scores. This will only happen (in aspiration search) if the position has already been determined to be a win.

This is in fact what Texel's tablebase implementation already does. It works fine and in some cases produces impressive results, such as finding the mate in 70/72 in the positions I mentioned here.

[bob]

As a secondary side effect I am trying hard to avoid DTZ probing because I think that if only WDL tables are present we can easily have 5-men in memory (374M for WDL against 922M for WDL+DTZ)

Is loading in one 5-piece DTZ table per game too much? I suppose if you are very short of time it might be, but that decision looks to be better made at the time.

I am not sure why this discussion is even taking place. W/D/L tables have been around for 20 years now. And they have their place in the search, and they have their drawbacks (inability to make progress and the likelihood of running into unforced 50 move draws).

DTM tables have problems, as has been discussed here in the last year (the conversion of a real win into a cursed win and therefore a draw. They also lead to unnatural play (I remember a game vs a GM many years ago where Crafty sacrificed a queen for nothing, in order to translate into a KNNKP ending that was won.

DTZ's avoid the 50 move problem, but they lose the mate scores, and they also lead to unnatural playing style for the same reason as DTMs, namely converting to a won ending quickly is preferred to a mate that is a bit longer than the conversion.

In short, there are warts. And the warts are inescapable. Even DTM50 would be just as problematic. You'd get correct mate scores, but you would still get unnatural playing style with unnecessary sacrificial lines of play.

I'd have thought this was beat to death many times over by now. DTZ was done in the late 70's (Ken Thompson). DTM was done in the early 90's (Steven Edwards). Both have had their "warts" discussed many times by now. At least a few people went to the trouble of converting Edwards tables to W/D/L to play with that, and while it had advantages within the search (much smaller file sizes) it hid progress.