On Wed, 2007-02-07 at 16:28 -0500, Don Dailey wrote:
> On Wed, 2007-02-07 at 16:17 -0500, Don Dailey wrote:
> > I have a hash funciton that creates a 64 bit "cannonical" hash of
> > the position. The same hash is produced after a rotation for
Most people do incremental hashing, which is cheaper even if 8(16)
symmetric copies are to be maintained. YMMV.
> > example. A book entry is a record with 3 fields, a priority
> > value (how many times the deep search selected this position),
> > the cannonical hash of the parent position and the cannonical
> > hash of the posiiton AFTER the move is played. This makes
> > collision very unlikely. The cannonical hash takes into
> > consideration simple ko, so if a ko is possible it will hash
> > differently than the same position where the ko is illegal.
>
> Here is some more detail to make this clearer:
>
Since you seem to be replying to yourself, I'll add some comments.
> typedef struct
typedef is useless here, IMO.
(but this is a matter of style, I agree)
> {
> int count; // number of times this position/response seen
> (priority)
Warning: alignment will cause this struct to be 3* sizeof(U64), wastong
32 bits.
Warning2: if the count is never negative, "unsigned" would be more
appropiate.
> u64 key; // cannonical position key
> u64 resp; // resulting cannonical position
Warning: you are wasting (64- ~9) bits here, since the response stems
from a set of 361+1 choices, maximal.
(this would be different if you intend to search backwards in the
tree/dag, with 'resp' as search key)
> } book_entry;
That could reduce your struct to:
struct booklet {
u64 key;
u32 count;
u16 move;
/* you *could* store the de-canonilisation-info here: */
u16 spare;
};
, which will take only 2*64 bits.
>
> These book_entry records are stored in a file and I keep them
> sorted. So the procedure to see if there is a book move is
Sorted on key? (Keep them sorted == resort periodically)
In that case, some kind of hashing would seem more appropiate, IMHO
> to binary search the file on the parent position key,
> collect all of these records together (making sure there is a
> legal move which leads to the cannonical response key) and then
You are not clear here.
Is there only a one-move-step between key and resp ?
Why not store the move in the first place ? (instead of the resulting
hash)
> choose one of the available moves in proportion to the
> priority values (the count field.)
HTH,
AvK
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
