Author: Tord Romstad
Date: 12:02:36 11/07/05
Go up one level in this thread
On November 07, 2005 at 14:42:52, Steve Maughan wrote:
>Tord,
>
>[snip]
>>Engine improvements in Scatha: An ugly hash table bug in the
>>Scatha engine (also present in Glaurung Mainz, by the way) ...
>
>Any chance that you could release a bug-fixed version or does it have little
>impact on game play?
I don't know the impact on game play yet. If I find out that it is a serious
improvement, I will of course release a bug-fixed version.
In case somebody is curious, the bug is in the function store_tt in the
file tt.c:
void store_tt(int value, int depth, move_t mv, int type, int mthreat) {
hashentry_t *h, *replace = NULL;
int i;
h = replace = TT + (Pos.key & (TT_size - 1)) * 4;
for(i = 0; i < 4; i++) {
if((h+i)->key == Pos.key) {
if(!mv) mv = move(h+i);
(h+i)->data = (mv&0x1FFFF)|(type<<19)|(mthreat<<21)|(Generation<<22);
(h+i)->score = value; (h+i)->depth = depth;
return;
}
if(generation(replace) == Generation) {
if(generation(h+i) != Generation) replace = h+i;
else if((h+i)->depth < replace->depth) replace = h+i;
}
else if(generation(h+i) != Generation && (h+i)->depth < replace->depth)
replace = h+i;
}
replace->key = Pos.key;
replace->data = (mv&0x1FFFF)|(type<<19)|(mthreat<<21)|(Generation<<22);
replace->score = value; h->depth = depth;
}
As the name indicates, this function is used to store data to the transposition
table. My transposition table is organised in clusters of four entries, and the
new information replaces the information stored in the least valuable of the
entries in one of these four-entry clusters. At the end of the 'for' loop in
the code above, the 'replace' pointer points to the entry that should be
replaced.
The bug is the very last statement in the function:
h->depth = depth; // SHOULD BE: replace->depth = depth
The pointer 'h' points to the first entry in the four-entry cluster, which is
of course not always the correct one to replace. The result is that there
is a risk that two of the four entries in the cluster will end up with
an incorrect depth after storing to the transposition table.
Tord
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.