Dual Bound TT

[joca]

Hello, has anyone made experiments with transposition tables that keep 2 bounds (and 2 depths respectively) instead of just one? And how were the results?

I am experimenting it in my engine (for a variant of checkers, not chess) and the results are significantly worse than with a regular tt. I was expecting the opposite, ideas?

[hgm]

Fruit does this. I never tried it myself, except in a special micro-Max derivative used to solve the K vs R end-game in suicide. There it gave a huge advantage over storing a single bound.But not as much as dropping alpha-beta and doing full minimax.

[bob]

Hello, has anyone made experiments with transposition tables that keep 2 bounds (and 2 depths respectively) instead of just one? And how were the results?

I am experimenting it in my engine (for a variant of checkers, not chess) and the results are significantly worse than with a regular tt. I was expecting the opposite, ideas?

Some have done it, but not quite as you suggest. If you play around with mtd(f), you need to store both bounds, because you can sometimes oscillate back and forth over the true value, one search fails low, the next fails high, the next fails low, as you try to narrow the alpha/beta window. If you don't store both, you go really slow. A normal program probably won't see much gain from storing both, and unless you have an excess of memory, storing both might actually cost you a bit since it makes the entries larger, which reduces the total number of entries.

[joca]

I re-run the experiment, but now with a better evaluation function, but still with 1 depth for each bound, as DUCHESS did (I cannot find the paper anywhere btw). The old evaluation function only did material balance. The program uses a null-window search (NegaScout more precisely).

What happened was that for some cases the number of cutoffs was slightly lower, the number of re-searches slightly higher, and the total number of nodes explored was also lower.
But for most cases the number of re-searches increased a lot, as well as the number of cutoffs and the total number of nodes explored.
I cannot explain this very well. The only thing that comes to my mind is search instability. As more information is stored, the probability of deeper subtrees transposing to parts of the game tree were a shallower subtree was expected increased. This accounted for more re-searches because the deeper subtrees are expectedly better scored.
I think this may also indicate the evaluation function needs more tuning?

Any ideas?

[bob]

I re-run the experiment, but now with a better evaluation function, but still with 1 depth for each bound, as DUCHESS did (I cannot find the paper anywhere btw). The old evaluation function only did material balance. The program uses a null-window search (NegaScout more precisely).

What happened was that for some cases the number of cutoffs was slightly lower, the number of re-searches slightly higher, and the total number of nodes explored was also lower.
But for most cases the number of re-searches increased a lot, as well as the number of cutoffs and the total number of nodes explored.
I cannot explain this very well. The only thing that comes to my mind is search instability. As more information is stored, the probability of deeper subtrees transposing to parts of the game tree were a shallower subtree was expected increased. This accounted for more re-searches because the deeper subtrees are expectedly better scored.
I think this may also indicate the evaluation function needs more tuning?

Any ideas?

I don't know that there is a thing wrong with your idea. In years past, maximizing # of entries was the key. With today's multi-gigabyte systems, storing both bounds might well be useful. Can't hurt (other than in reducing the number of entries). And it ought to be able to help here and there, although I would not expect it to be very significant. I might give it a test, just to see...

[hgm]

I once did an experiment with this in a micro-Max version that I had re-programmed to play suicide, to solve some simple end-games. (In partcular Rook vs. King.) I had noticed that plain minimax was orders of magnitude faster than alpha-beta in this case. But of course minimax is no good in other game phases (which are not dominated by hash efficiency). As the problem with alpha-beta seemed to be that hashedpositions had to be re-search time after time to get anopposite bound type, I tried to get the best of both worlds by using alpha-beta with dual bounds inthe TT. This did work, albeit still twice slower than plain minimax. (Understandable, because you still need an appreciable number of re-searches to improve a hashed bound ofthe required type.) This was still spectacularly faster than alpha-beta with single bound.

So I expect the advantages of dual bound hashing to manifest themselves in particular in the late end-game.