Hash tables: one bound or two bounds?

[abulmo]

You can't just store two bounds, of course, you also need two draft values as well.

I do not understand what you mean.One draft is enough. You just need to check the depth is the same for the two bounds.

[syzygy]

You can't just store two bounds, of course, you also need two draft values as well.

I do not understand what you mean.One draft is enough. You just need to check the depth is the same for the two bounds.

Usually that won't be the case. What do you do then.

[abulmo]

You can't just store two bounds, of course, you also need two draft values as well.

I do not understand what you mean.One draft is enough. You just need to check the depth is the same for the two bounds.

Usually that won't be the case. What do you do then.

I set the two bounds to their correct values. The result is exactly the same as when you have one value and an UPPER/LOWER/EXACT flag, ie you have lost exactly the same information.
I just change one bound and keep the other one when the depth is the same. Here we save a little more information than when using the UPPER/LOWER/EXACT flag.

[bob]

You can't just store two bounds, of course, you also need two draft values as well.

I do not understand what you mean.One draft is enough. You just need to check the depth is the same for the two bounds.

How can you guarantee that? And when you have a different draft for the second bound you want to store, what do you do?

requiring both bounds to be at the same draft is not a lot better than storing just one bound. And when I tested this, I found absolutely no gain by adding a second bound, unless you do mtd(f).

Rybka once used a fruit-like two bound hash algorithm, but by version 4, according to the author, he had converted to an 8-byte hash entry with just one bound. Which further suggests that the second bound really doesn't offer anything except taking up memory.

[bob]

You can't just store two bounds, of course, you also need two draft values as well.

I do not understand what you mean.One draft is enough. You just need to check the depth is the same for the two bounds.

Usually that won't be the case. What do you do then.

I set the two bounds to their correct values. The result is exactly the same as when you have one value and an UPPER/LOWER/EXACT flag, ie you have lost exactly the same information.
I just change one bound and keep the other one when the depth is the same. Here we save a little more information than when using the UPPER/LOWER/EXACT flag.

What draft do you store? The draft of the deepest? Then the other bound will produce false cutoffs when it appears to be useful. Keep the draft of the shallowest? Then you decrease the effectiveness of the other (deeper draft) bound. You really do need both.

[abulmo]

And here some statistics after one chess game (40 move in 40 seconds):
upper = 6861319, lower = 1413931, exact = 78754, two_bounded = 34607
So there are not many positions with two different bounds, but they are some.

Personally I prefer the two bound approach than the one with flags, because I think it is simpler and less error prone. But I agree this will nor bring, neither cost much elo.

[abulmo]

What draft do you store? The draft of the deepest? Then the other bound will produce false cutoffs when it appears to be useful. Keep the draft of the shallowest? Then you decrease the effectiveness of the other (deeper draft) bound. You really do need both.

Of course I set both bounds (one to +/- infinity in case of upper/lower bounds) when I change the draft. I do not keep a bound with a wrong value.
How do you do with an UPPER/LOWER/EXACT flag? You can do the same things here.

[bob]

What draft do you store? The draft of the deepest? Then the other bound will produce false cutoffs when it appears to be useful. Keep the draft of the shallowest? Then you decrease the effectiveness of the other (deeper draft) bound. You really do need both.

Of course I set both bounds (one to +/- infinity in case of upper/lower bounds) when I change the draft. I do not keep a bound with a wrong value.
How do you do with an UPPER/LOWER/EXACT flag? You can do the same things here.

Not the same thing. You can find position P is > s at depth d1, but < t at depth d2. All you need to do is shift the alpha/beta window at the root. Since mtd(f) depends on that, that is where two bounds really helps. Not so much elsewhere that I have been able to find. Ditto for others.

But you need a draft for each bound. there really is no way around that. EXACT is a different case, where you then set both bounds to the same value, and both drafts to the same value as well.

You can look at Fruit source, it does this already...

[abulmo]

Of course I set both bounds (one to +/- infinity in case of upper/lower bounds) when I change the draft. I do not keep a bound with a wrong value.
How do you do with an UPPER/LOWER/EXACT flag? You can do the same things here.

Not the same thing. You can find position P is > s at depth d1, but < t at depth d2.

You can also find position P is > s1 at depth d1 and is > s2 at depth d2, and so on, so it does not help so much as it does not cover every possible case.

All you need to do is shift the alpha/beta window at the root. Since mtd(f) depends on that, that is where two bounds really helps.

In mtd(f) or with aspiration windows, you should usually retrieve the same position at the same depth. So I do not think having two depths saved is important here. It may help because of search extension/reduction, though.

[hgm]

And here some statistics after one chess game (40 move in 40 seconds):
upper = 6861319, lower = 1413931, exact = 78754, two_bounded = 34607
So there are not many positions with two different bounds, but they are some.

From this it seems that dual bounds hardly occur. But since you reject entries that have two different bounds of different draft, I am not sure how meaningful those statistics are. The unequal draft could be far more abundant. I also had the impression that in the late end-game the number of dual bounds goes up enormously. (Because transpositions in general occur much more frequently there.)

But the major point I wanted to make is that it depends on the search strategy. As soon as you will do reduced searches with shifted windows, it should become much more common to have dual bounds. Because the reduced pilot search will typically fail one way, and the unreduced search this triggers will then fail the opposite way. If the pilot search would destroy the hashed info of the unreduced search by erasing the useful bound and replacing it with one of lower draft (like would happen in a dual-bound scheme that required same draft!), such search strategies are more likely to wreck things than doing any good, while with better hashing they might pay off.