TalkChess.com

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

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

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.

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

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

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;

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.

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

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