Storing Upper & Lower Bound in TT?

[Steve Maughan]

For each hash table entry Fruit 2.1 (and other Fruit versions) stores an upper-bound value and upper-bound depth, as well as a lower-bound value and lower-bound depth. I haven't come across any other engine that takes this approach. It makes the TT code a little more complex but since Lazy SMP is so common I would have thought storing more information in the TT is a good thing. It's possible that, in the vast majority of cases, only one bound is ever relevant so the other bound is simply taking up space.

Has anyone tried the dual bound / depth approach? Any insights as to why it may be good or bad?

— Steve

[syzygy]

It's possible that, in the vast majority of cases, only one bound is ever relevant so the other bound is simply taking up space.

I think this is correct.

Intuitively, I would say that, for almost all nodes, the reason a node is in the small fraction of nodes visited by alpha-beta is either to be a cut-node (to refute its parent) or to be an all-node (I guess to help the parent refute its parent). I suspect only very few nodes ever play both roles in the same search (and that should be nodes "close" to the PV). However, this intuition may be misguided and in any event cannot replace real testing.

I seem to remember reading that MTD(f) engines benefit from both bounds being stored. I doubt that storing both bounds is worth it even for MTD(f) engines, but it means there might be a few more engines than Fruit that do it.

[Steve Maughan]

Could it also enable a tighter approach to aspiration windows where you have positions searched multiple times with different alpha and beta windows?

— Steve

[syzygy]

I found this old thread: Hash tables: one bound or two bounds?

Two bounds probably help in endgame positions with very few pieces (or rather very few total positions and therefore all kinds of deep transpositions).

The threads also mentions that two bounds are required for MTD(f) to work because MTD(f) continuously switches between proving an upper bound for the root position and proving a lower bound for the root position.
This argument does not convince me. The minimal tree that proves the upper bound for a position has almost no overlap with the minimal tree that proves the lower bound for the same position.

Maybe two bounds are useful for nodes at distance 1 from the PV (I would have to think about this and draw some trees on paper).
But even if this is the case, the necessary information for these nodes will normally be found at distance 2 from the PV.

(MTD(f) does not set out to calculate a PV, but when the upper bound and lower bound for the root node meet, they meet on a sequence of moves that forms the PV.)

[syzygy]

Could it also enable a tighter approach to aspiration windows where you have positions searched multiple times with different alpha and beta windows?

I think what I wrote above about MTD(f) applies. But I would be happy to be proven wrong by reality

[hgm]

I once did an interesting experiment. I had a modified version of micro-Max searching an R vs K end-game position in Suicide. It disgusted me how long it took to find the distant win, as there are only 2x64x64 = 8K positions in that end-game. So the tree would completely fit in the TT, virtually without overwrites. Nevertheless it seemed to re-search the same position hundreds of times, judging by the number of nodes in the tree.

So what I did is switch from alpha-beta to pure minimax, by always keeping the search window at {-INF, +INF}. That had an amazing result: it now found the win in less than a second.

When I investigated this some more, it turned out that most positions were searched again and again because the bound was of the opposit type as what was needed, even though the depth was fine. It kept flipping the bound type. With minimax every score was of course exact.

So I tried a dual-bound TT, so that bound-flipping could never occur. This was not as fast as pure minimax, but still far faster than plain alpha-beta. Every node was still searched a few times, but only to improve the bound that was already there.

[Steve Maughan]

Hi Ron & HG,

I'm intrigued enough to give the dual bounds a go. I'll probably implement the single bound version as well and see which one is better. Thanks for the insights.

— Steve

[syzygy]

So I tried a dual-bound TT, so that bound-flipping could never occur. This was not as fast as pure minimax, but still far faster than plain alpha-beta. Every node was still searched a few times, but only to improve the bound that was already there.

Bound-flipping could also be prevented by not storing lower bounds (or upper bounds) at all in such endgame positions.

[JVMerlino]

So I tried a dual-bound TT, so that bound-flipping could never occur. This was not as fast as pure minimax, but still far faster than plain alpha-beta. Every node was still searched a few times, but only to improve the bound that was already there.

Bound-flipping could also be prevented by not storing lower bounds (or upper bounds) at all in such endgame positions.

I would also think that reducing the number of aspiration windows before doing a full-width search might also help alleviate this problem. But the overall tradeoff might be a loss. Hmmm.....

[syzygy]

So I tried a dual-bound TT, so that bound-flipping could never occur. This was not as fast as pure minimax, but still far faster than plain alpha-beta. Every node was still searched a few times, but only to improve the bound that was already there.

Bound-flipping could also be prevented by not storing lower bounds (or upper bounds) at all in such endgame positions.

I would also think that reducing the number of aspiration windows before doing a full-width search might also help alleviate this problem. But the overall tradeoff might be a loss. Hmmm.....

I don't think that is what caused the problem that HGM observed (in positions like KRK).
Pure minimax overcame the problem because it did not store lower or upper bounds at all (only exact values) and basically implemented a tablebase generator. A full-width search (which does not reset the window to (-INF,INF) at every node) will store lower and upper bounds.

But it would be interesting to do some experiments. A solution to the problem might also improve the search in endgame positions that have a lot of transpositions but are not yet tablebase-like.