Hashtable aging

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
fierz
Posts: 62
Joined: Mon Mar 07, 2016 3:41 pm
Location: Zürich, Switzerland
Contact:

Hashtable aging

Post by fierz » Mon Apr 25, 2016 4:11 pm

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
Posts: 860
Joined: Thu Mar 09, 2006 10:21 pm
Location: Nederland
Contact:

Re: Hashtable aging

Post by F. Bluemers » Mon Apr 25, 2016 4:27 pm

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

Re: Hashtable aging

Post by bob » Mon Apr 25, 2016 5:28 pm

fierz wrote: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
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Hashtable aging

Post by xmas79 » Mon Apr 25, 2016 5:30 pm

F. Bluemers wrote:
fierz wrote: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
Posts: 510
Joined: Sat Mar 25, 2006 7:27 pm

Re: Hashtable aging

Post by Robert Pope » Mon Apr 25, 2016 5:51 pm

bob wrote:
fierz wrote: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
Posts: 302
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Hashtable aging

Post by Karlo Bala » Mon Apr 25, 2016 7:48 pm

fierz wrote: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;

Best Regards,
Karlo Balla Jr.

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hashtable aging

Post by bob » Mon Apr 25, 2016 9:28 pm

Robert Pope wrote:
bob wrote:
fierz wrote: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
Posts: 62
Joined: Mon Mar 07, 2016 3:41 pm
Location: Zürich, Switzerland
Contact:

Re: Hashtable aging

Post by fierz » Tue Apr 26, 2016 5:34 am

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

Re: Hashtable aging

Post by bob » Tue Apr 26, 2016 4:52 pm

fierz wrote:
bob wrote:
fierz wrote: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.

Post Reply