Hash tables: one bound or two bounds?

[lucasart]

This is somehow what i was thinking, in general. I thought that storing an upper and lower bound would help the search, because when you start a re-search the nodes that failed high can fail low afterwards,... but at the end, it seems that the main time, the search is using the last bound stored.
But i'm not sure, then, I want to know other experiences.

I did this back when mtd(f) was a hot topic. Since you bounce around the true score, things that failed high the last search now fail low as you pass over the score. Two bounds is a necessity.

I tested it on the normal search, and with one proviso, I found no Elo change of any kind. That proviso is that you can store the second bound without increasing the size of an entry, which means without decreasing the overall size of the hash table.

I can think of one well-known program that used two bounds, like Fruit did/does, and then later went back to one bound. I would assume he found the same result as mine. You can't just store two bounds, of course, you also need two draft values as well.

It was also tested by Marco in Stockfish, and the result was the same as yours: storing two bounds does not gain anything. But of course, it complicates the code, so the patch was not commited.

[hgm]

It was also tested by Marco in Stockfish, and the result was the same as yours: storing two bounds does not gain anything. But of course, it complicates the code, so the patch was not commited.

And then it blocked progress, because many potential search improvements only work well with dual-bound hashing, and test as regression with single-bound...

There once was an island in the middle of a big swamp, close to an area of prime real estate. It was suggested that a road should be build through the swamp. The city council investigated the matter, by questioning thousands of people, and finally decided against the project. Hardly anyone was frequently travelling to that island, so they could not justify the expense.

And that is still the same today. Almost no one lives on that island, and a survey has also scientifically shown that no one wants to. We forgot to ask them why, but who cares?

[bob]

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.

Certainly it does work. If you have the same position P, flagged as >s1 at depth d, at you are now at position P wanting to store >s2 at depth d2, it is obvious d2 is > d1, otherwise you would have used the hash hit and stopped the search. The answer here is to always store the greater depth for the same condition. How would that lesser depth ever be useful when the greater depth is not? The greater depth represents more accuracy...

[bob]

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.

I can think of several cases where it might help.

1. True singular extensions, where you regularly search with an offset window to prove singularity.

2. null-move thread detection (donning) where you do offset window search to discover that null-move still fails low, while one specific move failed high, likely holding off a powerful threat, but with just one move that does so, making that position very forcing and dangerous.

3. mtd(f) obviously

4. A program with a tiny aspiration window perhaps.

[asanjuan]

I use PVS search, and after implementing my hash table with upper and lower bound, with of course, their drafts, it helped only when I started to use aspiration.

A wide aspiration, in fact. Using [score - 100, score+100] was enough to improve the time-to depth test.
If I lower the delta in my aspiration window, then a lot of re-searches are triggered and cut-nodes became all nodes and viceversa. Having 2 bounds really seems to help, because if in the next iteration, a re-search is triggered for the same position, at least one of the two bounds can help you to prune some branches of the tree.

After the change, I could see Rhetoric reaching depth 20 from the starting position... a really big step for me. I had to wait some time, but I could see that the search was scaling well to higher depths.

I can try to get some statistics, when I have time, of course. It would be interesting.

Regards.

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.

I can think of several cases where it might help.

1. True singular extensions, where you regularly search with an offset window to prove singularity.

2. null-move thread detection (donning) where you do offset window search to discover that null-move still fails low, while one specific move failed high, likely holding off a powerful threat, but with just one move that does so, making that position very forcing and dangerous.

3. mtd(f) obviously

4. A program with a tiny aspiration window perhaps.