[computer-go] Caching of local search in SlugGo

[Chrilly]

----- Original Message ----- 
From: "David G Doshay" <ddoshay at mac.com>
To: "computer-go" <computer-go at computer-go.org>
Sent: Wednesday, August 09, 2006 3:07 AM
Subject: Re: [computer-go] Caching of local search in SlugGo


> The multiple global searches done in SlugGo are cached using Zobrist 
> hashing. We do see hits that speed the lookahead.
>
> Cheers,
> David
>
Zobrist Hashing over the overall board or only some dirty region?. Currently 
I use in Suzie global hashing, but the hit-rate is not very high. A stone 
set in a completly unrelated area invalidates the entry.
If one makes some local scheme one has a) set the dirty region and b) 
Calculate some efficient key for this region.
I have not checked it in the code, but according the documentation GnuGo 
calculates the dirty region by marking every visited intersectiion and then 
expanding these region 4 steps in every direction.
But no hash-code is calculated, the dirty region is stored and if some stone 
is set in this region the cache is invalidated. I do not like this second 
step. A hashtable should not be dependent of move orders by not invalidating 
some entries. Additionally one invalidates probably more than is necessary. 
E.g. a move is done, the cache is invalidated, the move is taken back, 
another move is done which does not invalidate the chache. The entry should 
be still available for this move. But its probably no problem in GnuGo type 
programms were no global search is done. The only moves which are done are 
the moves played in the game. In this case the do-move undo-move sequence 
does not happen.
In case of Suzie even this is a problem, because when a move is played on 
the board, the interface always sends the whole move-sequence from the 
starting position. This is usuall in chess. It makes the invalidation of a 
cache tricky.

Chrilly