On Thu, 2007-02-08 at 01:00 +0100, Unknown wrote:
> 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.
I'm an expert in zobrist incremental hashing and have been doing
it since the early years of computer chess. However, I have
some other considerations here:
No hashing is still faster than incremental hashing - which is why
I don't do any hashing during the play-out phase.
Since I am only hashing for the purpose of building or looking up
a book position, this is the best approach. If I wanted to get
clever, I could pass a flag to the move maker to tell it whether
to do hashing or not and then do it incrementally, but for all
this trouble I would not get a speedup I would ever notice since
I only hash to find a book move.
> > > 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)
There are some advantages to NOT doing it my way, but I prefer
the concise way - I don't like having to define it as
"struct book_entry" all over my code. It's a matter of style.
> > {
> > 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.
I'm not concerned about space usage in the slightest because I have
about 100 book positions currently, and in my dreams I might get
to a few thousand.
But you are right, I could save a few bits if I didn't worry about
structure alignment.
> > 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)
But if I use the compact approach I lose a lot of safety. These
are hash keys and if I get a collision in "key", then it's extremely
unlikely that I will get a collision in any of the child hash keys.
But if I use your scheme, I have very little extra safety (although
I still have a little bit since a move might prove to be legal in
one and not in the other, but this is probably only worth an extra
bit or two.)
To be honest, 64 bits is probably safe enough for a few hundred moves,
unlikely to cause a collision.
>
> > } 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.
>
Based on the considerations I have presented, a better layout is
something like this:
u64 key;
u32 child_key:32;
u32 count;
I'm extremely unlikely to get a collision with a 64 bit parent
and a 32 bit child, so I would use something like this to save
space.
If I wanted to use bit fields I could do something like this if
I want to sacrafice a few more bits of safety:
u64 key;
uint child_key:28;
uint count:4;
I would be happy with just a few bits in child_key because
64 bits is reasonably safe by itself.
> > 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
I don't need a complicated scheme. The book is small and always
will be small and when I insert a record I just used insertion
sort, on the fly, which is faster than quicksort on a file that
is already sorted except for one record. This is trivial easy
stuff and is bug-free. I dump the book to a file using fwrite
and it's trivial.
If I use a hashing scheme, I have to worrry about resizes and
other complexities and how to put them on the disk.
If I really get to the point where I think I can generated a
huge book, my plan would be to use the sqlite library and
I would store them using this very easy to use embedded database.
> > 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 ?
Yes, if a book position has 3 book responses, there are 3 records
in the book database.
> Why not store the move in the first place ? (instead of the resulting
> hash)
One issue is that I would also have to store the move in cannonical
form, so in order to use it I would have to un-cannonicalize it :-)
But it's simple to just reuse the code I have. Since I have a routine
that converts a position to a cannonical form, all I have to do
is test all the legal moves (and their resulting cannonical positions)
to the database to see if I have a match.
The code I'm using for these things is utterly simple and it finds
or inserts a book move instantly. If it needed to be a high
performace module, which it doesn't, I would be faced with these
things to follow your suggestions:
1. More complexity to turn off and on incremental hashing.
2. A more complex storage scheme for the book that has to
utilize chaining, hashtable resizing or some other much
more complicated scheme.
3. Extra code to convert cannonical moves from a cannonical
posiiton to the actual move from a position that is not
cannonical (I would have to determine the difference
between the actual position and the connnical position
and then apply this transformation to the suggested
move itself.
There is no need to go to all this trouble to speed up the
look-up of a book move which even with a horrible implementation
happens in some tiny fraction of a second and is only done
one time per move choice the program makes.
- Don
P.S. If I WERE going to set this up something other than
a sorted list, I would
use a simple binary tree. Since the hash keys are well
distributed, I would ignore tree-balancing issues, it's
just not an issue, the tree would have nice properties
without any extra work.
> > 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/
