Hash table

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
cdani
Posts: 2095
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Hash table

Post by cdani » Mon Jun 12, 2017 10:38 pm

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

Re: Hash table

Post by bob » Mon Jun 12, 2017 10:49 pm

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

User avatar
cdani
Posts: 2095
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Hash table

Post by cdani » Tue Jun 13, 2017 2:05 am

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

Dann Corbit
Posts: 9289
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Hash table

Post by Dann Corbit » Tue Jun 13, 2017 3:05 am

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);
        }
    }
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Dann Corbit
Posts: 9289
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Hash table

Post by Dann Corbit » Tue Jun 13, 2017 3:11 am

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;
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

AlvaroBegue
Posts: 912
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Hash table

Post by AlvaroBegue » Tue Jun 13, 2017 3:57 am

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.

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

Re: Hash table

Post by hgm » Tue Jun 13, 2017 6:29 am

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&#40;entry&#41;; // 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;++;
Image

User avatar
cdani
Posts: 2095
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Hash table

Post by cdani » Tue Jun 13, 2017 1:23 pm

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.

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

Re: Hash table

Post by hgm » Tue Jun 13, 2017 1:40 pm

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.

User avatar
cdani
Posts: 2095
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Hash table

Post by cdani » Sat Jun 17, 2017 6:10 am

After a lot of tests, the best code I found is this:

Code: Select all

//basic test on every entry
bool use_entry&#40;)&#123;
	if &#40;unused entry&#41; &#123;
		return true;
	&#125;
	else &#123;
		if &#40;keys match&#41; &#123;
			save possible move if we don't have one;
			return true;
		&#125;
	&#125;
	return false;
&#125;

void save_hash&#40;) &#123;
	struct thash *h1;
	struct thash *h2;
	struct thash *h3;
	struct thash *h4;
	struct thash *replace;
	adjust mate score;
	h1 = first_entry;
	if &#40;use entry&#40;h1&#41;) &#123;
		replace = h1;
		goto end;
	&#125;
	h2 = h1 + 1;
	if &#40;use entry&#40;h2&#41;) &#123;
		replace = h2;
		goto end;
	&#125;
	h3 = h2 + 1;
	if &#40;use entry&#40;h3&#41;) &#123;
		replace = h3;
		goto end;
	&#125;
	h4 = h3 + 1;
	if &#40;use entry&#40;h4&#41;) &#123;
		replace = h4;
		goto end;
	&#125;
	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!

Post Reply