Natural TB

[Michel]

TB wins are pretty exact. Just like a "mate in 10" is an exact score even if one iteration later the position could turn out to be a "mate in 9".

Well think about it this way. If alpha>=TBWIN and we return TBWIN then we are telling the rest of the search that TBWIN is an _upperbound_ for this position. This is something we know is wrong.

So I believe we should return alpha (if bestValue<TBWIN). It is the best we can do with the information we have.

Well I cannot prove I am right (I don't have the time).

I think the two approaches will perform very similarly, because (from my point of view) it is simply the difference between fail soft and fail hard.

I never said one should switch to fail hard. That would be a waste of valuable information.

I gave two specific cases where I believe fail hard is the right thing to do from the point of view of a-b search.

[syzygy]

TB wins are pretty exact. Just like a "mate in 10" is an exact score even if one iteration later the position could turn out to be a "mate in 9".

Well think about it this way. If alpha>=TBWIN and we return TBWIN then we are telling the rest of the search that TBWIN is an _upperbound_ for this position. This is something we know is wrong.

No, we are telling it that TBWIN is the exact heuristic score for the position at the depth at which it was searched. That is perfectly fine.

Exact scores in iterative a-b are exact heuristic scores. They are not usually and they do not need to be "the truth". (But TBWIN is anyway as close to the truth as you can get.)

I think the two approaches will perform very similarly, because (from my point of view) it is simply the difference between fail soft and fail hard.

I never said one should switch to fail hard. That would be a waste of valuable information.[/quote]
You did not, but your approach translates to fail hard from my point of view, which is still fine.

I'm not saying that your approach is wrong. I am explaining why returning TBWIN is theoretically sound.

[Michel]

I'm not saying that your approach is wrong. I am explaining why returning TBWIN is theoretically sound.

Let's agree to disagree then...

I believe returning bounds known to be incorrect is wrong (anything you return outside the window is interpreted as a bound by the rest of the search). But it is a belief. I cannot rigorously justify it.

[Joerg Oster]

Thanks Joerg for testing it

You're welcome.

After now 2200 games of 3000 played, NaturalTB seems to be slightly weaker.
After about 400 games it settled to -4 elo, and this never changed noticeably since then.

Conditions: time control 15"+0.2", 16 MB Hash, 12moves opening book, 5men syzygy on SSD.

[petero2]

(1) sacrificing your queen takes you into a won 6 piece ending, but one which is harder to win than keeping the queen on. Unfortunately, you can't search nearly deep enough to see the win with the queen kept on the board, so transitioning to the egtb win is the only winning option you can see;

Do you have an example of such a position? It seems to me that if you are enough ahead to still be able to win after a queen sacrifice, you will also often be able to force a more advantageous trade if you keep searching.

The hardest position I could find after arbitrarily trying some positions was this:
[D]8/4bk2/4br2/8/8/8/8/QRRK4 w - - 0 1
Even in this position it only takes texel about 2.5 seconds to find something better than the queen sacrifice:

For Natural TB queen sacrifice is never an option (even at shallowest depths), insetad it finds rather quickly mate in 14

Code: Select all

  +-  (#14)   Depth: 32/84   00:01:16  143mN, tb=1957882
1.Rc1-c7 Be6-g4+ 2.Kd1-d2 Rf6-d6+ 3.Kd2-c3 Rd6-e6 4.Rb1-f1+ Kf7-g6 5.Qa1-b1+ Kg6-h6 6.Rc7xe7 Re6xe7 7.Rf1-f6+ Kh6-g5 8.Qb1-g6+ Kg5-h4 9.Qg6-h6+ Kh4-g3 10.Qh6-f4+ Kg3-h3 11.Rf6-h6+ Bg4-h5 12.Rh6xh5+ Kh3-g2 13.Rh5-g5+ Kg2-h3 14.Qf4-g3# 

How much it takes Texel to find mate in 14?

Using 1 thread and 2GB hash texel finds mate in 14 after 335 seconds. This is quite a bit slower than stockfish but still 60 times faster than texel without tablebases, which takes around 20000 seconds to find mate in 14.

I tried this position with a few different engines, all using 1 thread and 2GB hash, and the time required to find mate in 14 varied a lot.

Code: Select all

Stockfish Natural TB, using 6 men syzygy   : 101 seconds
Stockfish Natural TB, not using TB         : 107 seconds
Texel 106 alpha, using syzygy + gaviota TB : 335 seconds
Cheng 4.39, not using TB                   : 585 seconds
Senpai, not using TB                       : 11688 seconds
Texel 106 alpha, not using TB              : 19971 seconds
Komodo 8, not using TB                     : not found after 39260 seconds

By the way, when I tested your natural TB version, it did prefer Qxf6 most of the time from depth 8 (3.15s) to depth 32 (12.8s).

[jhellis3]

Ok, I reverted the broken code and simplified things further.

No longer does eval biasing, but appears to work just fine (and faster too).

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

Compare: https://github.com/official-stockfish/S ... 3:tb_fix_1

I consider it "job done" at this point...

[jhellis3]

'Tis mate in 13 btw .

[syzygy]

I'm not saying that your approach is wrong. I am explaining why returning TBWIN is theoretically sound.

Let's agree to disagree then...

Well, I do agree that your approach is theoretically fine. But my approach is theoretically just as fine.

I believe returning bounds known to be incorrect is wrong (anything you return outside the window is interpreted as a bound by the rest of the search). But it is a belief. I cannot rigorously justify it.

Alpha-beta takes as input a game tree in which every terminal node has a value. It returns the "exact" value of the tree: the value of the terminal node that will be reached by minimaxing.

In an engine, at iteration d, the terminal nodes are the nodes at a distance d from the root (ignoring reductions/extensions etc.). The values of these terminal nodes are (in most cases) the heuristic values returned by calling eval().

Those values returned by eval() are usually known to be "wrong" in the sense that the only possible correct values are "+mate in x", "-mate in x" and "draw". But that does not matter for the soundness of alpha-beta. Alpha-beta's task is to find the value of the terminal node that will be reached by minimaxing and that is what alpha-beta does.

So now I have, for a particular iteration, a search tree where some terminal nodes have the heuristic value "TB win". A value that is smaller than any mate value and larger than any score returned by evaluate(). That's just fine. If that terminal node is searched, the search may always (independently of the values of alpha and beta) return the value of the terminal node: TB win.

[jhellis3]

That's just fine. If that terminal node is searched, the search may always (independently of the values of alpha and beta) return the value of the terminal node: TB win.

Yeah, it's fine, but the problem is the nodes that stop being searched because they get detected and saved into hash at a depth greater than the next iteration, which guarantees that entry will be used (and not searched). And if it ever expires it gets auto-refreshed and returned before the next search. The exact bound isn't necessary either, it just makes the entries more difficult to replace, which is not really what you want when trying to resolve the shortest mate ASAP.

[bob]

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.

How? the probe being discussed terminates the search completely. So how can searching even one more node be "more efficient"? And this is about searching MANY more than one extra node.

In theory if searching more nodes is faster than the probe then it can be more efficient.

Not if you do probes somewhere in those extra nodes, which is the issue...