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
Hashtable aging
Moderators: hgm, Rebel, chrisw
-
- Posts: 868
- Joined: Thu Mar 09, 2006 11:21 pm
- Location: Nederland
Re: Hashtable aging
Sounds horrible,scanning all those hashentries.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
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashtable aging
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.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
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...
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Hashtable aging
don't ignore entries with different n, use them! simply replace them first if you have multiple n within the same bucket, imho.F. Bluemers wrote:Sounds horrible,scanning all those hashentries.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
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.
-
- Posts: 558
- Joined: Sat Mar 25, 2006 8:27 pm
Re: Hashtable aging
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.bob wrote: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.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
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...
-
- Posts: 373
- Joined: Wed Mar 22, 2006 10:17 am
- Location: Novi Sad, Serbia
- Full name: Karlo Balla
Re: Hashtable aging
I suggest you to look at the Fruit/Toga source codefierz 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
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 (date = 0; date < DateSize; date++) {
trans->age[date] = trans_age(trans,date);
}
...
}
static int trans_age(const trans_t * trans, int date) {
int age;
age = trans->date - date;
if (age < 0) age += DateSize;
return age;
}
Best Regards,
Karlo Balla Jr.
Karlo Balla Jr.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashtable aging
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...Robert Pope wrote: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.bob wrote: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.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
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...
-
- Posts: 72
- Joined: Mon Mar 07, 2016 4:41 pm
- Location: Zürich, Switzerland
Re: Hashtable aging
Thanks Bob,bob wrote: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.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
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...
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
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashtable aging
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.fierz wrote:Thanks Bob,bob wrote: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.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
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...
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