Hash table

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

[bob]

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

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

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

[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);
        }
    }

[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 &#40;i = 0, best = Entry = Hash + &#40;High32&#40;Current->key&#41; & hash_mask&#41;; i < 4; i++, Entry++) &#123;
        if &#40;Entry->key == Low32&#40;Current->key&#41;) &#123;
            Entry->date = date;
            if &#40;depth > Entry->high_depth || &#40;depth == Entry->high_depth && value < Entry->high&#41;) &#123;
                if &#40;Entry->low <= value&#41; &#123;
                    Entry->high_depth = depth;
                    Entry->high = value;
                &#125; else if &#40;Entry->low_depth < depth&#41; &#123;
                    Entry->high_depth = depth;
                    Entry->high = value;
                    Entry->low = value;
                &#125;
            &#125;
            return;
        &#125; else score = &#40;Convert&#40;Entry->date, int&#41; << 3&#41; + Convert&#40;Max&#40;Entry->high_depth, Entry->low_depth&#41;, int&#41;;
        if &#40;score < min_score&#41; &#123;
            min_score = score;
            best = Entry;
        &#125;
    &#125;
    best->date = date;
    best->key = Low32&#40;Current->key&#41;;
    best->high = value;
    best->high_depth = depth;
    best->low = 0;
    best->low_depth = 0;
    best->move = 0;
    best->flags = 0;
    return;
&#125;

void hash_low&#40;int move, int value, int depth&#41; &#123;
    int i, score, min_score;
    GEntry *best, *Entry;

    min_score = 0x70000000;
    move &= 0xFFFF;
    for &#40;i = 0, best = Entry = Hash + &#40;High32&#40;Current->key&#41; & hash_mask&#41;; i < 4; i++, Entry++) &#123;
        if &#40;Entry->key == Low32&#40;Current->key&#41;) &#123;
            Entry->date = date;
            if &#40;depth > Entry->low_depth || &#40;depth == Entry->low_depth && value > Entry->low&#41;) &#123;
                if &#40;move&#41; Entry->move = move;
                if &#40;Entry->high >= value&#41; &#123;
                    Entry->low_depth = depth;
                    Entry->low = value;
                &#125; else if &#40;Entry->high_depth < depth&#41; &#123;
                    Entry->low_depth = depth;
                    Entry->low = value;
                    Entry->high = value;
                &#125;
            &#125; else if &#40;F&#40;Entry->move&#41;) Entry->move = move;
            return;
        &#125; else score = &#40;Convert&#40;Entry->date, int&#41; << 3&#41; + Convert&#40;Max&#40;Entry->high_depth, Entry->low_depth&#41;, int&#41;;
        if &#40;score < min_score&#41; &#123;
            min_score = score;
            best = Entry;
        &#125;
    &#125;
    best->date = date;
    best->key = Low32&#40;Current->key&#41;;
    best->high = 0;
    best->high_depth = 0;
    best->low = value;
    best->low_depth = depth;
    best->move = move;
    best->flags = 0;
    return;
&#125;

void hash_exact&#40;int move, int value, int depth, int exclusion, int ex_depth, int knodes&#41; &#123;
    int i, score, min_score;
    GPVEntry *best;
    GPVEntry * PVEntry;

    min_score = 0x70000000;
    for &#40;i = 0, best = PVEntry = PVHash + &#40;High32&#40;Current->key&#41; & pv_hash_mask&#41;; i < pv_cluster_size; i++, PVEntry++) &#123;
        if &#40;PVEntry->key == Low32&#40;Current->key&#41;) &#123;
            PVEntry->date = date;
            PVEntry->knodes += knodes;
            if &#40;PVEntry->depth <= depth&#41; &#123;
                PVEntry->value = value;
                PVEntry->depth = depth;
                PVEntry->move = move;
                PVEntry->ply = Current->ply;
                if &#40;ex_depth&#41; &#123;
                    PVEntry->exclusion = exclusion;
                    PVEntry->ex_depth = ex_depth;
                &#125;
            &#125;
            return;
        &#125;
        score = &#40;Convert&#40;PVEntry->date, int&#41; << 3&#41; + Convert&#40;PVEntry->depth, int&#41;;
        if &#40;score < min_score&#41; &#123;
            min_score = score;
            best = PVEntry;
        &#125;
    &#125;
    best->key = Low32&#40;Current->key&#41;;
    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;
&#125;

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

[hgm]

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&#40;entry->lock != hashKey && entry->age != searchNr && hashCount&#91;depth&#93; < hashCount&#91;1&#93;) &#123;
  entry = LowestDepth&#40;entry&#41;; // find lowest depth in bucket
&#125;
hashCount&#91;entry->depth&#93;--;
entry->lock = hashKey;
entry->depth = depth;
entry->age = searchNr;
hashCount&#91;entry->depth&#93;++;

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

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

[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 = &#40;int&#41;h1->age << 3;
	int a2 = &#40;int&#41;h2->age << 3;
	int a3 = &#40;int&#41;h3->age << 3;
	int a4 = &#40;int&#41;h4->age << 3;

	a1 += h1->type == exact ? 1 &#58; 0;
	a2 += h2->type == exact ? 1 &#58; 0;
	a3 += h3->type == exact ? 1 &#58; 0;
	a4 += h4->type == exact ? 1 &#58; 0;

	a1 += &#40;int&#41;h1->depth;
	a2 += &#40;int&#41;h2->depth;
	a3 += &#40;int&#41;h3->depth;
	a4 += &#40;int&#41;h4->depth;

	int i;
	if &#40;a2 <= a1&#41; &#123;
		replace = h2;
		i = a2;
	&#125;
	else &#123;
		i = a1;
		replace = h1;
	&#125;
	if &#40;a3 <= i&#41; &#123;
		replace = h3;
		i = a3;
	&#125;
	if &#40;a4 <= i&#41;
		replace = h4;
end&#58;
	save entry;
&#125;

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!