Page 1 of 4
Hash table
Posted: Tue Jun 13, 2017 12:38 am
by cdani
Hello. I'm trying to improve again the main hash table, and specifically I'm trying to find which of the standard parameters are the most important and which less, to decide which of the 4 entries in any hash position is the best to be overwritten when the 4 are occupied.
So for each entry I have the standard
* age
* type (exact, alpha, beta)
* depth
Are there any study over any clear best strategy?
Thanks.
Re: Hash table
Posted: Tue Jun 13, 2017 12:49 am
by bob
cdani wrote:Hello. I'm trying to improve again the main hash table, and specifically I'm trying to find which of the standard parameters are the most important and which less, to decide which of the 4 entries in any hash position is the best to be overwritten when the 4 are occupied.
So for each entry I have the standard
* age
* type (exact, alpha, beta)
* depth
Are there any study over any clear best strategy?
Thanks.
Best move is certainly critical. (I have to assume you store a score / bound, otherwise it is pointless).
Re: Hash table
Posted: Tue Jun 13, 2017 4:05 am
by cdani
bob wrote:cdani wrote:Hello. I'm trying to improve again the main hash table, and specifically I'm trying to find which of the standard parameters are the most important and which less, to decide which of the 4 entries in any hash position is the best to be overwritten when the 4 are occupied.
So for each entry I have the standard
* age
* type (exact, alpha, beta)
* depth
Are there any study over any clear best strategy?
Thanks.
Best move is certainly critical. (I have to assume you store a score / bound, otherwise it is pointless).
Sorry, I was not clear enough. Of course I store best move, and the key, and the eval (is Andscacs
), but the three-item list I put here was about the parameters I was considering to make the decision of which of the 4 buckets to overwrite. And the question was about the best known algorithm for it. Thanks
Re: Hash table
Posted: Tue Jun 13, 2017 5:05 am
by Dann Corbit
This is what Stockfish does:
Code: Select all
void save(Key k, Value v, Bound b, Depth d, Move m, Value ev, uint8_t g) {
assert(d / ONE_PLY * ONE_PLY == d);
// Preserve any existing move for the same position
if (m || (k >> 48) != key16)
move16 = (uint16_t)m;
// Don't overwrite more valuable entries
if ( (k >> 48) != key16
|| d / ONE_PLY > depth8 - 4
/* || g != (genBound8 & 0xFC) // Matching non-zero keys are already refreshed by probe() */
|| b == BOUND_EXACT)
{
key16 = (uint16_t)(k >> 48);
value16 = (int16_t)v;
eval16 = (int16_t)ev;
genBound8 = (uint8_t)(g | b);
depth8 = (int8_t)(d / ONE_PLY);
}
}
Re: Hash table
Posted: Tue Jun 13, 2017 5:11 am
by Dann Corbit
Gull has an interesting method. There are 3 distinct store functions for exact, high, and low
Code: Select all
void hash_high(int value, int depth) {
int i, score, min_score;
GEntry *best, *Entry;
min_score = 0x70000000;
for (i = 0, best = Entry = Hash + (High32(Current->key) & hash_mask); i < 4; i++, Entry++) {
if (Entry->key == Low32(Current->key)) {
Entry->date = date;
if (depth > Entry->high_depth || (depth == Entry->high_depth && value < Entry->high)) {
if (Entry->low <= value) {
Entry->high_depth = depth;
Entry->high = value;
} else if (Entry->low_depth < depth) {
Entry->high_depth = depth;
Entry->high = value;
Entry->low = value;
}
}
return;
} else score = (Convert(Entry->date, int) << 3) + Convert(Max(Entry->high_depth, Entry->low_depth), int);
if (score < min_score) {
min_score = score;
best = Entry;
}
}
best->date = date;
best->key = Low32(Current->key);
best->high = value;
best->high_depth = depth;
best->low = 0;
best->low_depth = 0;
best->move = 0;
best->flags = 0;
return;
}
void hash_low(int move, int value, int depth) {
int i, score, min_score;
GEntry *best, *Entry;
min_score = 0x70000000;
move &= 0xFFFF;
for (i = 0, best = Entry = Hash + (High32(Current->key) & hash_mask); i < 4; i++, Entry++) {
if (Entry->key == Low32(Current->key)) {
Entry->date = date;
if (depth > Entry->low_depth || (depth == Entry->low_depth && value > Entry->low)) {
if (move) Entry->move = move;
if (Entry->high >= value) {
Entry->low_depth = depth;
Entry->low = value;
} else if (Entry->high_depth < depth) {
Entry->low_depth = depth;
Entry->low = value;
Entry->high = value;
}
} else if (F(Entry->move)) Entry->move = move;
return;
} else score = (Convert(Entry->date, int) << 3) + Convert(Max(Entry->high_depth, Entry->low_depth), int);
if (score < min_score) {
min_score = score;
best = Entry;
}
}
best->date = date;
best->key = Low32(Current->key);
best->high = 0;
best->high_depth = 0;
best->low = value;
best->low_depth = depth;
best->move = move;
best->flags = 0;
return;
}
void hash_exact(int move, int value, int depth, int exclusion, int ex_depth, int knodes) {
int i, score, min_score;
GPVEntry *best;
GPVEntry * PVEntry;
min_score = 0x70000000;
for (i = 0, best = PVEntry = PVHash + (High32(Current->key) & pv_hash_mask); i < pv_cluster_size; i++, PVEntry++) {
if (PVEntry->key == Low32(Current->key)) {
PVEntry->date = date;
PVEntry->knodes += knodes;
if (PVEntry->depth <= depth) {
PVEntry->value = value;
PVEntry->depth = depth;
PVEntry->move = move;
PVEntry->ply = Current->ply;
if (ex_depth) {
PVEntry->exclusion = exclusion;
PVEntry->ex_depth = ex_depth;
}
}
return;
}
score = (Convert(PVEntry->date, int) << 3) + Convert(PVEntry->depth, int);
if (score < min_score) {
min_score = score;
best = PVEntry;
}
}
best->key = Low32(Current->key);
best->date = date;
best->value = value;
best->depth = depth;
best->move = move;
best->exclusion = exclusion;
best->ex_depth = ex_depth;
best->knodes = knodes;
best->ply = Current->ply;
}
Re: Hash table
Posted: Tue Jun 13, 2017 5:57 am
by AlvaroBegue
I haven't done anything systematic about this, but it seems to me the criteria should be
1) If one of the entries has the correct verification bits, use that one.
2) If there are entries form previous searches, write over those first.
3) In case of equality, write over the entry with the lowest depth.
After some experimentation it became clear to me that at least you always want to write the new information somewhere.
Re: Hash table
Posted: Tue Jun 13, 2017 8:29 am
by hgm
cdani wrote:Are there any study over any clear best strategy?
I systematically investigated this some 10 years ago. What worked best was "equidistributed depth". Apart from the obvious things (replacing an earlier entry for the same position, and replacing entries that are no longer reachable from the current root if you have that info and are not in analysis mode), replace the entry on which you get the primary hit if its depth already has more than its fair share in the depth-preferred table, and replace the lowest depth otherwise.
To get that information I keep a histogram hashCount[MAXPLY], updated on every replacement. As in a depth-preferred table the lowest depths tend to be squeezed out, the number of entries of the lowest depth can be used as a threshold for when a higher depth is over-represented.
Code: Select all
index = hashKey & mask;
entry = hashTable + index; // primary hit
// hash probe
'entry' = KeyMatch(entry); // leaves entry unchanged if no match
...
// hash store
if(entry->lock != hashKey && entry->age != searchNr && hashCount[depth] < hashCount[1]) {
entry = LowestDepth(entry); // find lowest depth in bucket
}
hashCount[entry->depth]--;
entry->lock = hashKey;
entry->depth = depth;
entry->age = searchNr;
hashCount[entry->depth]++;
Re: Hash table
Posted: Tue Jun 13, 2017 3:23 pm
by cdani
Thanks to all! I'm trying various own ideas and I will try also some of the proposals. I will explain whatever result I obtain.
Re: Hash table
Posted: Tue Jun 13, 2017 3:40 pm
by hgm
Note that it makes sense to protect exact scores better, as they represent more search effort than upper or lower bounds. I never studied the effect of that, but I guess one should treat exact scores in the replacement decision as if they were one ply deeper.
Re: Hash table
Posted: Sat Jun 17, 2017 8:10 am
by cdani
After a lot of tests, the best code I found is this:
Code: Select all
//basic test on every entry
bool use_entry(){
if (unused entry) {
return true;
}
else {
if (keys match) {
save possible move if we don't have one;
return true;
}
}
return false;
}
void save_hash() {
struct thash *h1;
struct thash *h2;
struct thash *h3;
struct thash *h4;
struct thash *replace;
adjust mate score;
h1 = first_entry;
if (use entry(h1)) {
replace = h1;
goto end;
}
h2 = h1 + 1;
if (use entry(h2)) {
replace = h2;
goto end;
}
h3 = h2 + 1;
if (use entry(h3)) {
replace = h3;
goto end;
}
h4 = h3 + 1;
if (use entry(h4)) {
replace = h4;
goto end;
}
int a1 = (int)h1->age << 3;
int a2 = (int)h2->age << 3;
int a3 = (int)h3->age << 3;
int a4 = (int)h4->age << 3;
a1 += h1->type == exact ? 1 : 0;
a2 += h2->type == exact ? 1 : 0;
a3 += h3->type == exact ? 1 : 0;
a4 += h4->type == exact ? 1 : 0;
a1 += (int)h1->depth;
a2 += (int)h2->depth;
a3 += (int)h3->depth;
a4 += (int)h4->depth;
int i;
if (a2 <= a1) {
replace = h2;
i = a2;
}
else {
i = a1;
replace = h1;
}
if (a3 <= i) {
replace = h3;
i = a3;
}
if (a4 <= i)
replace = h4;
end:
save entry;
}
Sure can be improved, but I think I will keep it for the moment.
Of the examples shown in this thread, I tried hgm approach but was maybe 2 elo worst. But Andscacs stores also quiescence nodes and static eval in the hash, nodes that where keep out of the "hasCount" array and had a simpler replace schema, so probably could be improved somehow.
The
int a1 = (int)h1->age << 3;
idea from Gull seems a little bit better that simpler
int a1 = h1->age < currentage ? -200 : 0;
Now I will do a 4cpu test to be sure that it scales enough well.
Thanks all!