Natural TB

[syzygy]

This is perhaps even more controversial than the assumption above, but IMO TB are useful to make the engine stronger in the middle-game, not in the endgame. It's in the middle-game that you lack the depth to workout the endgame at the end of the PV, and it's in the middlegame that TB can more often overrule the search (because at middlegame the search of the endgames sub-tree is very shallow and mainly rely on the evaluation).

Ehm... that is not controversial at all... (Although it is obviously wrong to state that TBs do not improve the endgame.)
Have you really never read anything about this topic?

Assuming the above it is possible that probing at the end of the search is more efficient because you call probe less times (for instance all null search, razoring, etc don't end up in a TB probe because engine cut-offs earlier)

Is it still so difficult to visualise that probing one time in an interior node and cutting the subtree is more efficient than probing at least once in a leaf below that interior node? (And it is also more accurate.) Probing closer to the leaves certainly does not result in probing less. It is pretty amazing what you are writing here...

Does anyone else here have a problem in understanding this? Maybe a drawing is needed?

(What may be more efficient is using a higher probe depth for 6-piece positions than for 5-piece positions, knowing that the 5-piece positions are more likely to be cached in RAM. As it happens, this idea was already implemented in SF. But probing the same table in the leaves when it could have been done just once in a parent node is just silly.)

So complex that only testing legacy vs natural TB in real games will give us the answer.

You are probably thinking that something like alpha-beta is the result of lots of random hacking and testing instead of a flash of mathematical insight.

[Evert]

The point is that the traditional approach of people to TB assumes (implicitly and even without realizing it) that without TB engine is lost. This is very wrong and even more wrong today with powerful engines/hardware we have: engine is able to find the win in 99.9% of cases all alone by itself.

I'll take that bet. I don't think anyone who has given it some thought (or anyone who has seen their engine play a rook endgame correctly without knowledge) thinks that engines need tablebases to convert a win. That's why the Elo gain from tablebases is small, and why only a few actually make a difference (at least for 4 or 5 men).
You can reduce size of some tablebases considerably by just storing a few crucial positions and their evaluation, and leaving the rest up to the search. Identifying those few crucial positions is hard and needs to be done by hand (and is probably engine dependent).

Another point of view you should think of is that TB are not needed (to increase ELO) when root position is in TB. This is perhaps even more controversial than the assumption above,

Isn't it exactly the same? Given that an engine is usually able to win a TB position without help, of course it makes no difference if the root position is a TB position.

IMO TB are useful to make the engine stronger in the middle-game, not in the endgame. It's in the middle-game that you lack the depth to workout the endgame at the end of the PV, and it's in the middlegame that TB can more often overrule the search (because at middlegame the search of the endgames sub-tree is very shallow and mainly rely on the evaluation).

Again, isn't this obvious? A tablebase (bitbase) is most useful for preventing conversion of a won position into a draw (or a draw to a loss). The inverse, only accessing TBs from the root, has little use because by then the game is decided and you walked into it blindly.

[Laskos]

Indeed the idea should be carefully tested

Of course it should be carefully tested!

The point is that the traditional approach of people to TB assumes (implicitly and even without realizing it) that without TB engine is lost. This is very wrong and even more wrong today with powerful engines/hardware we have: engine is able to find the win in 99.9% of cases all alone by itself. TB is just the cherry on the cake in the very rare cases engine is not able to work out the position. If you start from this point of view (that is somewhat controversial), you will see that perhaps TB could "hint" the engine more then strictly command it and perhaps these extra hints are enough not to lose ELO in normal games.

Another point of view you should think of is that TB are not needed (to increase ELO) when root position is in TB. This is perhaps even more controversial than the assumption above, but IMO TB are useful to make the engine stronger in the middle-game, not in the endgame. It's in the middle-game that you lack the depth to workout the endgame at the end of the PV, and it's in the middlegame that TB can more often overrule the search (because at middlegame the search of the endgames sub-tree is very shallow and mainly rely on the evaluation). Assuming the above it is possible that probing at the end of the search is more efficient because you call probe less times (for instance all null search, razoring, etc don't end up in a TB probe because engine cut-offs earlier), but at the same time it is still a valuable help for the search. So as you see, the picture is much more complex than simply choosing what TB win/loss scores to return. So complex that only testing legacy vs natural TB in real games will give us the answer.

It seems Natural TB do deteriorate the strength ELO-wise too. First they seriously deteriorate the 5-men play at the root: on randomly occurring in games 5-men wins Natural fails to convert about 5% of them. On 5-men draws, it loses about 0.4% of them. On MES1258 varied endgame testsuite I got a SPRT stop for (-4,1):

MES1258
SPRT(-4,1)
H0 passed

Score of SF NATURAL vs SF SYZYGY: 2322 - 2476 - 3589 [0.491] 8387
ELO difference: -6.38 +/- 5.62
SPRT: llr -2.96, lbound -2.94, ubound 2.94 - H0 was accepted
Finished match

From regular openings the effect might be hard to detect, the difference might compress to 1 or so ELO points, but the deterioration should be there.

[jhellis3]

I updated the SF branch using some ideas from Marco and MateFinder, have been quite pleased with the results thus far... Will probably merge the changes into MateFinder if testing goes well...

https://github.com/jhellis3/Stockfish/tree/tb_fix_1

[mcostalba]

Score of SF NATURAL vs SF SYZYGY: 2322 - 2476 - 3589 [0.491] 8387
ELO difference: -6.38 +/- 5.62
SPRT: llr -2.96, lbound -2.94, ubound 2.94 - H0 was accepted
Finished match

From regular openings the effect might be hard to detect, the difference might compress to 1 or so ELO points, but the deterioration should be there.

Thanks for testing!

I am curious to see how natural goes in real games starting from the beginning....

[Rein Halbersma]

(What may be more efficient is using a higher probe depth for 6-piece positions than for 5-piece positions, knowing that the 5-piece positions are more likely to be cached in RAM. As it happens, this idea was already implemented in SF. But probing the same table in the leaves when it could have been done just once in a parent node is just silly.)

Pardon my ignorance, but your TBs still use memory-mapped I/O, correct? One avenue for experimentation might be to use conditional lookups after an is-in-RAM check. IIRC, at least on Linux there are OS calls to do this now.

Another thing is to use an asynchronous queue of positions-to-be-looked-up. You could then maintain a counter per position and do conditional lookups after a position is queried for a second time etc. But maybe the OS does this more efficiently than such a scheme.

At least in draughts in the old days before SSDs and huge RAM, the search would slow down 10x when in the late middle game, e.g. 4 Gb RAM + 100 Gb TBs on disk. When RAM ~ 32Gb and using SSDs, search speed is not affected significantly.

[syzygy]

I updated the SF branch using some ideas from Marco and MateFinder, have been quite pleased with the results thus far... Will probably merge the changes into MateFinder if testing goes well...

https://github.com/jhellis3/Stockfish/tree/tb_fix_1

Also the idea to first search the subtree of a TB position and probe there and only then probe the position itself?

[Uri Blass]

Assuming the above it is possible that probing at the end of the search is more efficient because you call probe less times (for instance all null search, razoring, etc don't end up in a TB probe because engine cut-offs earlier)

Is it still so difficult to visualise that probing one time in an interior node and cutting the subtree is more efficient than probing at least once in a leaf below that interior node? (And it is also more accurate.) Probing closer to the leaves certainly does not result in probing less. It is pretty amazing what you are writing here...

It is not the claim based on my understanding.

His claim is that probing one time in an interior node and cutting the subtree may be worse relative to the option to continue the search and maybe not probing later because of pruning and maybe probing later(you do not know it at the time that you are in the interior node).


I will be surprised if it happens but
if the average number of probing after the interior tablebase node is smaller than 1 then at least in theory he may be right.

[jhellis3]

Also the idea to first search the subtree of a TB position and probe there and only then probe the position itself?

No, if you clicked the link you would have seen what I have done....

[syzygy]

Assuming the above it is possible that probing at the end of the search is more efficient because you call probe less times (for instance all null search, razoring, etc don't end up in a TB probe because engine cut-offs earlier)

Is it still so difficult to visualise that probing one time in an interior node and cutting the subtree is more efficient than probing at least once in a leaf below that interior node? (And it is also more accurate.) Probing closer to the leaves certainly does not result in probing less. It is pretty amazing what you are writing here...

It is not the claim based on my understanding.

His claim is that probing one time in an interior node and cutting the subtree may be worse relative to the option to continue the search and maybe not probing later because of pruning and maybe probing later(you do not know it at the time that you are in the interior node).

Yes, but for that to work EVERYTHING would need to be pruned in that subtree before any node is probed. A single probe in the subtree and you haven't saved any probes and lose on searching the subtree and loss of accuracy. Two probes in the subtree and you lose already on the number of probes.

As I wrote near the beginning of this thread, the only sensible thing (unless beta is in mate area) is EITHER probe immediately and cut the whole subtree OR don't probe in the subtree at all.

This is the idea of probedepth: either the search determines that (relatively costly) probing is worth the effort because enough depth remains, or the search determines that the subtree is too small to replace searching it with a probe and then obviously the same applies to all the subtrees within that subtree. (As stated a few posts above, one refinement is that it may make sense to use lower probedepth for 5-piece positions than for 6-piece positions. This is in particular the case if probing a 6-piece TB is expected to require disk accesses and probing a 5-piece TB translates in a RAM lookup.)

Instead of a fixed probedepth value (or two values for 6- and 5-piece), more advanced criteria could surely be thought of. But the principle remains: try to probe as close to the root as you can.

I will be surprised if it happens but
if the average number of probing after the interior tablebase node is smaller than 1 then at least in theory he may be right.

But even then I am right: the decision to not probe the first TB position should translate in decisions not to probe in any of the nodes of the subtree (modulo the 5-piece vs 6-piece thing).