Hash tables: one bound or two bounds?

[asanjuan]

I have changed my hash table to store 2 bounds and their depth. It doesn't seem to help, but it doesn't seem to hurt anyway.

But, after implement aspiration at the root level, it seems to help a bit. I don't have resources to test it until a narrow error margin. So here is the question:

Has anyone experienced a similar behaviour? and how much elo added to your programs? I mean, the hash table change, not aspirations.

Regards.

[hgm]

Do you mean opposite-type bounds, or just any two bounds?

All my engines store only a single score + bound type, and I am actually unhappy with that, and it is on my to-do list to change it. Not because I expect a significant Elo gain from the change itself, but because it would provide a more friendly environment for other search techniques that use shifted search windows. (E.g. a pilot search at reduced depth to determine whether a move is singular, so it must be extended.) With a single-valued hash table such pilot searches tend to overwrite high-draft results from a previous iteration with lower-draft results, because the bound in them was not sharp enough to be useful (and could not be sharp enough to be useful, because in fact the pilot search will get the opposite fail as the following unreduced re-search that this necessitates). So when the re-search then comes that could have benefited from the bounds in the high-draft entries, the latter have all been overwritten, erasing the hash moves because what used to be fail highs are now fail lows, etc.

Dual-score hashing would not suffer from this; it would use one bound type for the pilot searches, and then the opposite bound type for the following unreduced search, both surviving the iteration.

Another observation I once did:

The Rook vs King end-game in Suicide Chess is generally won for the Rook. With a regular alpha-beta source micro-Max had much difficulty finding the win, however. But when I changed from using alpha-beta to plain mini-max (forcing the window to {-INF, INF} in the recursive call to search) it became lightning fast (like one or two orders of magnitude faster). Because every hash entry became EXACT, the search could now use it both as upper bound and lower bound, and this was apparently a huge advantage. While in alpha-beta, the same position that is UPPER in one branch needs to be LOWER in another, and it was constantly re-searching all positions that had the required draft, but needed opposite bound type. But of course plain mini-max nearly halves your search depth in the middle-game.

So I figured a dual-bound table would be a good compromise: the middle-game should not suffer, and it would remove the need to flip bound type in simple end-games. And indeed, with dual-bound hashing and alpha-beta finding the stalemate was only twice as slow as with plain mini-max.

So I would even opt for a dual-score hash if it would be a small Elo decrease; this should be seen as an investment for making later search improvements more provitable, rather than painting yourself into a corner. Hash table is infra-structure of your engine, and you should not economize on infra-structure.

[asanjuan]

Do you mean opposite-type bounds, or just any two bounds?

Sorry, I mean, storing an upper and lower bound for the position.

All my engines store only a single score + bound type, and I am actually unhappy with that, and it is on my to-do list to change it.

It was also in my todo-list.

Not because I expect a significant Elo gain from the change itself, but because it would provide a more friendly environment for other search techniques that use shifted search windows. (E.g. a pilot search at reduced depth to determine whether a move is singular, so it must be extended.) With a single-valued hash table such pilot searches tend to overwrite high-draft results from a previous iteration with lower-draft results, because the bound in them was not sharp enough to be useful (and could not be sharp enough to be useful, because in fact the pilot search will get the opposite fail as the following unreduced re-search that this necessitates). So when the re-search then comes that could have benefited from the bounds in the high-draft entries, the latter have all been overwritten, erasing the hash moves because what used to be fail highs are now fail lows, etc.

Dual-score hashing would not suffer from this; it would use one bound type for the pilot searches, and then the opposite bound type for the following unreduced search, both surviving the iteration.

Another observation I once did:

The Rook vs King end-game in Suicide Chess is generally won for the Rook. With a regular alpha-beta source micro-Max had much difficulty finding the win, however. But when I changed from using alpha-beta to plain mini-max (forcing the window to {-INF, INF} in the recursive call to search) it became lightning fast (like one or two orders of magnitude faster). Because every hash entry became EXACT, the search could now use it both as upper bound and lower bound, and this was apparently a huge advantage. While in alpha-beta, the same position that is UPPER in one branch needs to be LOWER in another, and it was constantly re-searching all positions that had the required draft, but needed opposite bound type. But of course plain mini-max nearly halves your search depth in the middle-game.

So I figured a dual-bound table would be a good compromise: the middle-game should not suffer, and it would remove the need to flip bound type in simple end-games. And indeed, with dual-bound hashing and alpha-beta finding the stalemate was only twice as slow as with plain mini-max.

So I would even opt for a dual-score hash if it would be a small Elo decrease; this should be seen as an investment for making later search improvements more provitable, rather than painting yourself into a corner. Hash table is infra-structure of your engine, and you should not economize on infra-structure.

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.

[hgm]

Well, in a normal PVS search this is indeed uncommon (except in simple end-games, where you have very many paths to reach the same position, and that position will fail in the opposite way depending on the path). But as soon as you start manipulating the search window, and shift it to quite different values as plain PVS would use, it can become very common.

[bob]

Do you mean opposite-type bounds, or just any two bounds?

Sorry, I mean, storing an upper and lower bound for the position.

All my engines store only a single score + bound type, and I am actually unhappy with that, and it is on my to-do list to change it.

It was also in my todo-list.

Not because I expect a significant Elo gain from the change itself, but because it would provide a more friendly environment for other search techniques that use shifted search windows. (E.g. a pilot search at reduced depth to determine whether a move is singular, so it must be extended.) With a single-valued hash table such pilot searches tend to overwrite high-draft results from a previous iteration with lower-draft results, because the bound in them was not sharp enough to be useful (and could not be sharp enough to be useful, because in fact the pilot search will get the opposite fail as the following unreduced re-search that this necessitates). So when the re-search then comes that could have benefited from the bounds in the high-draft entries, the latter have all been overwritten, erasing the hash moves because what used to be fail highs are now fail lows, etc.

Dual-score hashing would not suffer from this; it would use one bound type for the pilot searches, and then the opposite bound type for the following unreduced search, both surviving the iteration.

Another observation I once did:

The Rook vs King end-game in Suicide Chess is generally won for the Rook. With a regular alpha-beta source micro-Max had much difficulty finding the win, however. But when I changed from using alpha-beta to plain mini-max (forcing the window to {-INF, INF} in the recursive call to search) it became lightning fast (like one or two orders of magnitude faster). Because every hash entry became EXACT, the search could now use it both as upper bound and lower bound, and this was apparently a huge advantage. While in alpha-beta, the same position that is UPPER in one branch needs to be LOWER in another, and it was constantly re-searching all positions that had the required draft, but needed opposite bound type. But of course plain mini-max nearly halves your search depth in the middle-game.

So I figured a dual-bound table would be a good compromise: the middle-game should not suffer, and it would remove the need to flip bound type in simple end-games. And indeed, with dual-bound hashing and alpha-beta finding the stalemate was only twice as slow as with plain mini-max.

So I would even opt for a dual-score hash if it would be a small Elo decrease; this should be seen as an investment for making later search improvements more provitable, rather than painting yourself into a corner. Hash table is infra-structure of your engine, and you should not economize on infra-structure.

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.

[mvk]

So I would even opt for a dual-score hash if it would be a small Elo decrease; this should be seen as an investment for making later search improvements more provitable, rather than painting yourself into a corner. Hash table is infra-structure of your engine, and you should not economize on infra-structure.

I agree with everything your wrote.

It is frustrating that simple end games with small search spaces cannot be solved by the millions nodes per second forward searches we have now, whereas a retrograde analysis solves the endgame in a tiny fraction of a second. Continuously throwing away information by overwriting older bounds is one reason. But so far I haven't gotten my program so solve, for example, KBNK yet using such dual bounds, so there is more to it.

Anyway, one implementation idea is that if you have buckets, you can also store the dual bounds in two entries. Just a thought.

[syzygy]

It is frustrating that simple end games with small search spaces cannot be solved by the millions nodes per second forward searches we have now, whereas a retrograde analysis solves the endgame in a tiny fraction of a second. Continuously throwing away information by overwriting older bounds is one reason. But so far I haven't gotten my program so solve, for example, KBNK yet using such dual bounds, so there is more to it.

It is possible to solve KBNvK with just one bound per position/entry:
[D]8/8/8/6B1/8/8/4k3/1K5N b - -

Code: Select all

  2:06.497  55  6582615800   -Mate33   1...Kf3 2.Bh4 Kg4 3.Be1 Kf4 4.Kc2 Ke4 5.Ng3+ Kd4 6.Bc3+ Kd5 7.Kd3 Kc5 8.Nf5 Kb6 9.Kc4 Kc6 10.Bd4 Kc7 11.Kd5 Kb7 12.Nd6+ Kc7 13.Bc5 Kb8 14.Kc6 Ka8 15.Nb5 Kb8 16.Nc7 Kc8 17.Ba7 Kd8 18.Nd5 Ke8 19.Kd6 Kf7 20.Ne7 Kg7 21.Be3 Kf6 22.Bd2 Kf7 23.Bg5 Ke8 24.Ng6 Kf7 25.Nf4 Ke8 26.Be7 Kf7 27.Kd7 Kg8 28.Ke8 Kg7 29.Bg5 Kh8 30.Kf8 Kh7 31.Kf7 Kh8 32.Ng6+ Kh7 33.Nf8+ Kh8 34.Bf6#

(Mate in 48 was found in 46 seconds.)
Of course retrograde analysis is about 1000x faster...

[mvk]

(Mate in 48 was found in 46 seconds.)
Of course retrograde analysis is about 1000x faster...

That is pretty neat...! Thank for showing.

[syzygy]

(Mate in 48 was found in 46 seconds.)
Of course retrograde analysis is about 1000x faster...

That is pretty neat...! Thank for showing.

That it shows the full PV is mostly luck

[hgm]

Anyway, one implementation idea is that if you have buckets, you can also store the dual bounds in two entries. Just a thought.

True, but that is really wasteful, as you need a signature in each. Normally my hash entries are:

4 bytes signature
2 bytes move
2 bytes score
1 byte draft
1 byte flags (EXACT, LOWER or UPPER)

That is 10 bytes, so 6 entries per bucket, and then 4 bytes to spare (which I can use for age counters, if there are 4 depth-preferred and 2 always-replace entries in the bucket).

With dual bounds you would need an extra score and an extra depth, but you no longer need the flags, as you know which one is the UPPER and which the LOWER score bound (and for EXACT entries you set them both to the same value). The UPPER bound represents a fail-low, and does not need a move. So you get

4 bytes signature
2 bytes move
2 bytes upper bound
2 bytes lower bound
1 byte upper draft
1 byte lower draft

That is 12 bytes. So 5 entries per bucket, and room for 4 aging counters. So it doesn't cost that much extra space.