Hashtable aging

[fierz]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

[F. Bluemers]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

Sounds horrible,scanning all those hashentries.
Use a counter mod n,n being small f.i.7.
Increase it with every search for a new move.
Ingore entries with different n.

[bob]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

What I have been doing since the middle 70's is to simply use a short counter (3-4 bits is enough). Each time you start a search from the root position, increment this counter. Each time you store a hash entry, store the counter as part of the entry.

For replacement, you can now simply compare the current counter to the stored counter (for an entry you might replace). If the counters are different, this is an old entry and it should be overwritten before any entry that has the same counter value.

No "scanning" or "passing over" the entire table required...

[xmas79]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

Sounds horrible,scanning all those hashentries.
Use a counter mod n,n being small f.i.7.
Increase it with every search for a new move.
Ingore entries with different n.

don't ignore entries with different n, use them! simply replace them first if you have multiple n within the same bucket, imho.

[Robert Pope]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

What I have been doing since the middle 70's is to simply use a short counter (3-4 bits is enough). Each time you start a search from the root position, increment this counter. Each time you store a hash entry, store the counter as part of the entry.

For replacement, you can now simply compare the current counter to the stored counter (for an entry you might replace). If the counters are different, this is an old entry and it should be overwritten before any entry that has the same counter value.

No "scanning" or "passing over" the entire table required...

So you consider everything as "current search" or "old search"? i.e. hash entries from your last move's search are just as susceptible to replacement as one from 5 moves age? I don't do hash table aging yet, but I always assumed that both the current and the most recent prior search needed to be treated as special.

[Karlo Bala]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

I suggest you to look at the Fruit/Toga source code

Code: Select all

static const int DateSize = 16;

struct trans {
   ...
   int date;
   int age[DateSize];
   ...
};

void trans_init(trans_t * trans) {
   ...
   trans_set_date(trans,0);
   ...
}

void trans_clear(trans_t * trans) {
   ...
   trans_set_date(trans,0);
   ...
}

void trans_inc_date(trans_t * trans) {
   trans_set_date(trans,(trans->date+1)%DateSize);
}

static void trans_set_date(trans_t * trans, int date) {
   ...
   trans->date = date;
   for &#40;date = 0; date < DateSize; date++) &#123;
      trans->age&#91;date&#93; = trans_age&#40;trans,date&#41;;
   &#125;
   ...
&#125;

static int trans_age&#40;const trans_t * trans, int date&#41; &#123;
   int age;
   age = trans->date - date;
   if &#40;age < 0&#41; age += DateSize;
   return age;
&#125;

[bob]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

What I have been doing since the middle 70's is to simply use a short counter (3-4 bits is enough). Each time you start a search from the root position, increment this counter. Each time you store a hash entry, store the counter as part of the entry.

For replacement, you can now simply compare the current counter to the stored counter (for an entry you might replace). If the counters are different, this is an old entry and it should be overwritten before any entry that has the same counter value.

No "scanning" or "passing over" the entire table required...

So you consider everything as "current search" or "old search"? i.e. hash entries from your last move's search are just as susceptible to replacement as one from 5 moves age? I don't do hash table aging yet, but I always assumed that both the current and the most recent prior search needed to be treated as special.

You can do what you want with age. I consider everything "old" or "current". I had tried using the age to tie-break on replacement, but it had no effect...

[fierz]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

What I have been doing since the middle 70's is to simply use a short counter (3-4 bits is enough). Each time you start a search from the root position, increment this counter. Each time you store a hash entry, store the counter as part of the entry.

For replacement, you can now simply compare the current counter to the stored counter (for an entry you might replace). If the counters are different, this is an old entry and it should be overwritten before any entry that has the same counter value.

No "scanning" or "passing over" the entire table required...

Thanks Bob,

that also sounds sensible. However, I don't know if it's such a big performance difference as you suggest (no scanning over the entire table required). What I was suggesting was a single pass over the table at the start (or end) of the search, whereas you would be using the age field of the hashtable on every store, i.e. you are likely also accessing this field in a large part of the table, just spread out over the entire search. Of course, for very short search times your method wins clearly.

cheers
Martin

[bob]

Dear all,

up to now I have just been clearing my hashtable before each search which is obviously losing all the information gained during the last search. The chess programming wiki isn't very clear on how hashtable aging should be done.

I'm thinking of adding an "accessed" flag to my hashtable entry. I would set that to 0 at the start of each search, and during the search, to 1 if the position is ever looked up. At the end of the search, I would remove all the not-accessed hashtable entries.

Does that sound sensible?

cheers
Martin

What I have been doing since the middle 70's is to simply use a short counter (3-4 bits is enough). Each time you start a search from the root position, increment this counter. Each time you store a hash entry, store the counter as part of the entry.

For replacement, you can now simply compare the current counter to the stored counter (for an entry you might replace). If the counters are different, this is an old entry and it should be overwritten before any entry that has the same counter value.

No "scanning" or "passing over" the entire table required...

Thanks Bob,

that also sounds sensible. However, I don't know if it's such a big performance difference as you suggest (no scanning over the entire table required). What I was suggesting was a single pass over the table at the start (or end) of the search, whereas you would be using the age field of the hashtable on every store, i.e. you are likely also accessing this field in a large part of the table, just spread out over the entire search. Of course, for very short search times your method wins clearly.

cheers
Martin

Ripping through 64gb of hash table at the end of the search can be costly. It immediately trashes the TLB and flushes cache for starters. The age is only a couple of bits. In my case I store 9 bits just because there was that much unused space in a single hash entry.