Author: Renze Steenhuisen
Date: 09:31:10 04/07/04
Go up one level in this thread
On April 07, 2004 at 11:55:16, Robert Hyatt wrote:
>On April 07, 2004 at 11:22:56, Renze Steenhuisen wrote:
>
>>
>>>Define collision first.
>>>
>>>(1) two different positions produce the same hash signature...
>>>
>>>(2) two different hash signatures address the same table entry...
>>>
>>>(1) should not happen with 64 bit signatures. (2) is common and is why the
>>>replacement strategy is so important.
>>
>>I defined collision somewhere in this thread but it is the same as (1):
>>
>>from code of DarkSight which is comparable with next.c in Crafty
>>/********************/
>>
>> case HASH_MOVE:
>> if( a tt_move is provided )
>> {
>> tree->stats.hashkey_requests++;
>> if( provided tt_move is valid move )
>> return tt_move;
>> else
>> tree->stats.hashkey_collisions++;
>> }
>>
>>/********************/
>>
>>Or is there something wrong?
>
>
>Could be something wrong there.
>
>IE if you store a bogus move, you will call it a hash collision when it is not.
>
>Do you use Internal Iterative Deepening? If so, there are opportunities to
>store a bogus move if you are not careful. Do you store a "best move" on
>fail-low nodes? Same deal. When you store a "best move" check it for legality
>at the point where you store it. If you get a legality failure there you have a
>bug to fix. If not, then you may have a hashing collision problem...
Sorry, but I don't understand what you mean.
I have all "special features" switched off, so there is no IID, Qsearch,
Futility, extensions, or NULL-move.
I initialise my TT to all 0's. my best_move gets initialised to NULL_MOVE (which
is 0 as well). I use PVS, so I initialise my best_value to -INFINITY. Every time
I get a value that is > best_value. I update best_value and best_move.
When the search is finished I store the data, and the best_move (which cannot be
illegal) in the TT.
But I'm getting loads of collisions. A hashkey tied to a illegal move for the
position with the same hashkey.
/***************** code from hashtable.c *********************/
typedef struct {
HASHKEY key;
signed draft : 15;
signed value : 17;
unsigned type : 2;
unsigned move : 21;
} TT_ENTRY;
void store_tt_entry(search_tree* tree, HASHKEY hashkey, int draft, int value,
MOVE move, unsigned int type)
{
TT_ENTRY* tt_entry;
TT_ENTRY* next_entry;
tt_entry = &transposition_table[ 2*(hashkey & (hash_table_size-1)) ];
/* Start of TWODEEP */
if( tt_entry->key==0 )
{
tt_entry->key = hashkey;
tt_entry->draft = draft;
tt_entry->value = value;
tt_entry->move = move;
tt_entry->type = type;
}
else
{
next_entry = tt_entry+1;
if( draft>=tt_entry->draft )
{
next_entry->key = tt_entry->key;
next_entry->draft = tt_entry->draft;
next_entry->value = tt_entry->value;
next_entry->move = tt_entry->move;
next_entry->type = tt_entry->type;
tt_entry->key = hashkey;
tt_entry->draft = draft;
tt_entry->value = value;
tt_entry->move = move;
tt_entry->type = type;
}
else
{
next_entry->key = hashkey;
next_entry->draft = draft;
next_entry->value = value;
next_entry->move = move;
next_entry->type = type;
}
}
}
int lookup_tt_entry(search_tree *tree, int depth, int *tt_value, MOVE *tt_move)
{
int ret;
TT_ENTRY *tt_entry;
tree->stats.tt_probes++;
ret = NO_TT_HIT;
tt_entry = &transposition_table
[ 2*(tree->game->position.hashkey & (hash_table_size-1)) ];
if( tt_entry->key==tree->game->position.hashkey )
{
tree->stats.tt_hits++;
if( tt_entry->draft>=depth )
{
ret = tt_entry->type;
*tt_value = tt_entry->value;
}
*tt_move = tt_entry->move;
}
else
{
tt_entry = tt_entry+1;
if( tt_entry->key==tree->game->position.hashkey )
{
tree->stats.tt_hits++;
if( tt_entry->draft>=depth )
{
ret = tt_entry->type;
*tt_value = tt_entry->value;
}
*tt_move = tt_entry->move;
}
else
{
*tt_move = NULL_MOVE;
}
}
return ret;
}
This page took 0.01 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.