Re: [HELP] Zobrist Hashing

["Weimin Xiao" <ranxiao@xxxxxxxxxxxx>]

I thought Mousheng can use board string directly without losing efficiency
Say, if Mousheng has only about 4 billion (2^32) patterns, he will need to
put all the patterns in an increase (or decreasing) order (pattern list).
Having a pattern at hand, first look at the middle element of the pattern
list. If the pattern is equal to the middle element, then matched. If the
pattern is smaller than the middle element, lower-half list will be
considered for next look-up step, otherwise, higher-half list will be
considered. No ore than 32 look-up steps will be needed to match a pattern

For 3x3 patterns, the number of total patterns will less than 3^9 =19683. If
remove symmetric situations, 19683/8 ~ 2500 real patterns which is less than
2^12. So 12 searches is the maximum look-up steps to find a pattern.

Weimin

-----Original Message-----
From: <Compgo123@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Date: Saturday, October 31, 1998 8:50 PM
Subject: Re: [HELP] Zobrist Hashing


First thank Dave Dyer and David Fotland for answering the questions.

>For a complete go board, you would need a string in the range 0-3^361:
>an inconventiently large number.  Using Xor, you can reduce the range
>to 0-2^31, an easy to deal with 32 bit number.

>From the posts my understanding is that for a complete go board, if your
table
is going to store all possible positions, then scheme stated by Mousheng Xu
is
the better approach. However, in reality the number of patterns contained in
most practical pattern database is far less than the total number of all
possible positions. In this case, the scheme stated by Mousheng Xu would
not
be as efficient as possible, because a vast number of entries would not be
used. The purpose of Zobrist or any other hash table method is to reduce the
total number of entries that has to be considered as much as possible for a
given size of pattern database. For these hash methods the bit length of the
index is mainly determined by the actual database size rather than the total
number of all possible positions. Or at least that's what those hash methods
trying to accomplish.  An ideal hash function would give an index length
exactly the same as the number of patterns in the database. Since such an
ideal hash method does not exist, usually the hash index length is larger
than
the number of patterns in the database. 2^31 =2.15*10^9, about two billion.
It's still a very large number considering most pattern databases only
contain
several thousands of patterns.

Dan Liu