Hash tables: one bound or two bounds?

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
abulmo
Posts: 151
Joined: Thu Nov 12, 2009 5:31 pm
Contact:

Re: Hash tables: one bound or two bounds?

Post by abulmo » Mon Dec 16, 2013 11:49 pm

bob wrote: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.
Richard

syzygy
Posts: 5048
Joined: Tue Feb 28, 2012 10:56 pm

Re: Hash tables: one bound or two bounds?

Post by syzygy » Tue Dec 17, 2013 12:05 am

abulmo wrote:
bob wrote: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
Posts: 151
Joined: Thu Nov 12, 2009 5:31 pm
Contact:

Re: Hash tables: one bound or two bounds?

Post by abulmo » Tue Dec 17, 2013 12:21 am

syzygy wrote:
abulmo wrote:
bob wrote: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.
Richard

bob
Posts: 20930
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hash tables: one bound or two bounds?

Post by bob » Tue Dec 17, 2013 12:27 am

abulmo wrote:
bob wrote: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
Posts: 20930
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hash tables: one bound or two bounds?

Post by bob » Tue Dec 17, 2013 12:29 am

abulmo wrote:
syzygy wrote:
abulmo wrote:
bob wrote: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
Posts: 151
Joined: Thu Nov 12, 2009 5:31 pm
Contact:

Re: Hash tables: one bound or two bounds?

Post by abulmo » Tue Dec 17, 2013 12:58 am

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.
Richard

abulmo
Posts: 151
Joined: Thu Nov 12, 2009 5:31 pm
Contact:

Re: Hash tables: one bound or two bounds?

Post by abulmo » Tue Dec 17, 2013 1:07 am

bob wrote: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.
Richard

bob
Posts: 20930
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hash tables: one bound or two bounds?

Post by bob » Tue Dec 17, 2013 3:50 am

abulmo wrote:
bob wrote: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
Posts: 151
Joined: Thu Nov 12, 2009 5:31 pm
Contact:

Re: Hash tables: one bound or two bounds?

Post by abulmo » Tue Dec 17, 2013 7:33 am

bob wrote:
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.
Richard

User avatar
hgm
Posts: 26576
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Hash tables: one bound or two bounds?

Post by hgm » Tue Dec 17, 2013 7:54 am

abulmo wrote: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.

Post Reply