According to my David Levy and Monty Newborn in "How computers play chess",
hash tables are used to prevent repetitions of seach....Thats fine but I am not clear
on one point they make. I am aware that when using a hash code of 32 bits,for example,
different positions may be assigned the same hash code. In this case they say that
"Programs have various strategies for deciding what to do when a clash occurs. Some
programs attempt to store the position at the next location. If that location is
found to be occupied also, the program can give up or it can replace the older of the
two entries just examined. Most programs try more than once to find an unoccupied
location; Cray Blitz tries eight times."
(maybe Robert Hyatt can comment on this)
I understand that even if a clash occurs, storing is a pretty easy task of finding
the next empty slot....But how about reading the position when the position crops up
again. What happens if I arrive at the position that had a clash before....How can
I read the scores and various other data stored. Aren't I going to read the wrong
position's scores and data??
Can somebody explain this to me?
Most don't "double hash" due to the extra time required. However, for
Cray Blitz, since we run on a vector machine that effectively makes loading
eight words just as fast as loading one word, we do use "double hashing" to
choose the best place to store a table entry.
The idea:
given a 64 bit (or whatever word size you want) take the low order "n"
bits where "n" is log2 (tablesize) and use this as the "first" entry (x)
to probe. take the next "m" bits (for Cray Blitz, m=9 and use this
as a "vector stride" (y) and then load eight words, table(x), table(x+y)
table(x+2y), ..., table(x+7y). One of these will be the one chosen to
be replaced by the current store, or else one of these will be the "match"
for the current lookup. The only minor difficulty to handle is that you
don't dimension the table for (n) entries [table(n)] but, rather, we have
to dimension the table larger [table(n+7*512)] to handle the positions
where we hash to near the end of the table, and the vector loads would then
step beyond the end... no, there isn't a "modulus" mechanism for vector
loads to make this load "wrap around" to the beginning.
Performance measurements seem to suggest that we have one of the best-performing
hashing algorithms around, based on the number of positions we typically find
in the table during a search (our average is around 30% in the middlegame
and much higher in endings) I am including (right below here) some hashing
statistics from one of our games from last year. the stat lines are formatted
with the following data: time: time for this move followed by the "real" chess
clock time (which started at 4:00). nn.np is the processor utilization on a 16
processor C90 (16.0 is perfect) Nodes is total nodes searched for this move,
the percentage after "h" is hash table positions successfully found. The
remaining two percentages are pawn hashing (which means we hardly ever have
to go through our complex pawn structure scoring code because we have already
seen this pawn structure before and scored it once) and king safety hashing
(same idea as pawn hashing.) the number at the end is nodes per second (on
a dedicated C90.)
time: 4:01 4:16 15.7p nodes:110752032 h 25% 99% 98% 458581 nps
time: 3:20 4:19 16.0p nodes: 95190816 h 23% 99% 98% 475906 nps
time: 3:20 4:23 16.0p nodes:101335537 h 26% 99% 99% 506627 nps
time: 3:20 4:26 16.0p nodes: 98571846 h 27% 99% 99% 492809 nps
time: 3:20 4:29 16.0p nodes: 99253399 h 28% 99% 99% 495895 nps
time: 3:20 4:33 16.0p nodes: 98689436 h 27% 99% 99% 493249 nps
time: 3:34 4:51 16.0p nodes:130879200 h 36% 99% 98% 610557 nps
time: 4:02 4:52 16.0p nodes:136365966 h 33% 99% 99% 563472 nps
time: 5:54 4:52 16.0p nodes:205142439 h 35% 99% 99% 578273 nps
time: 4:44 4:57 16.0p nodes:157608239 h 34% 99% 99% 554939 nps
As you can see, these are from very early (since the clock time is 4:16,
16 minutes have elapsed since the beginning of the game [off of Cray Blitz's
clock] in the game Cray Blitz vs Startech (HiTech on a CM-5 machine). For the
endgame, the following values are produced: (these are run using a 8 processor
Cray YMP)
time: 0:06 7:58 7.9p nodes: 1746702 h 58%100% 99% 279472 nps
time: 0:27 7:58 8.0p nodes: 9703616 h 62% 99% 99% 349932 nps
time: 0:50 7:58 8.0p nodes: 14689498 h 53%100% 99% 290593 nps
time: 0:36 7:59 8.0p nodes: 10495706 h 63%100% 99% 289536 nps
time: 0:24 7:59 8.0p nodes: 7699969 h 61%100% 99% 309235 nps
time: 1:06 8:00 8.0p nodes: 19833741 h 54%100% 99% 299512 nps
time: 0:57 8:01 8.0p nodes: 17203658 h 63%100% 99% 297795 nps
time: 0:07 8:01 8.0p nodes: 1911929 h 63%100%100% 254245 nps
Hope this helps some.
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
I previously answered the first part of your question. For the last part,
remember that a table entry contains a "key", score, score type, best move,
etc. This key must EXACTLY match the hash key before we consider this a
"hit". This means that the 64 bit hash key must match completely, even though
we only used the low order "n" bits of this key to probe into the table.
In fact, since we used the low order "n" bits to prob into the table, we don't
even bother storing them since we "know" what they were already (which saves
table space.)
Bob
>If Rob Hyatt's test had happened to include such values, he might have
>observed a radically different result. What is the probability of
>choosing a "bad" set of Zobrist values for Chess? What criterion
>gurantee that the values you use are "good" for Chess? As far as my
>limited knowledge goes, these are open questions.
>In conclusion, the very good result observed in a 32-bit version of
>Cray Blitz comes partially from the type of hashing done (Zobrist with
>values tested for uniqueness), and partly from sheer good luck in
>choosing the initial values. I wouldn't place too much faith in the
>result holding for a different chess program, or even for Cray Blitz
>with a different initial random seed.
Good point. I can speak from experience here. In the early versions of
my chess program Phoenix, I generated my Zobrist hash numbers using my
student id number as a seed, naively thinking the radom numbers
generated by this seed would be good enough. A few years later I put
code in to detect when my 32-bit hash key matched the wrong position.
To my surprise, there were *lots* of errors. I changed my seed to
another number and the error rate dropped dramatically. With this
better seed, it became very, very rare to see a hash error.
All randomly generated numbers are not the same!
I really don't understand this. My program Rookie until recently used
32bit hash keys. 16 bits were used as an index, the other 16 were stored
in the table. The keys are generated in exactly the same way as yours,
i.e. by XORing some random value for each piece-square combination,
and zeros for empty squares. Some special tests are run to ensure that
every legal move actually changes the hashkey in a unique way.
Whenever a position is _not_ found in the tables, I compute the 'closeness'
of the current hash key and the key stored in the table. 'closeness' is
defined as the number of high order bits that match, or in other words:
the length of the largest common prefix. E.g. The closeness of 100110 and
100011 is 3. During the search I keep track of the largest closeness value
encountered. This maximum is a measurement for the frequency of near-clashes.
In Rookie using 32bits hashes this value can range from 16 to 31.
A 31 means that two positions were searched that have keys that differ only
in the last bit.
I frequently see hashkeys in a <10^5 searches with closeness 31, indicating a
near-clash. For me this indicates that it is very likely that real hash
clashes also occured (but could not be detected, since positions with
closeness 32 are considered to be the same). This seems to contradict your
observation.
Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| mar...@stack.urc.tue.nl
O.K. lets go back to the "origin" of this technique. "how" did you generate
your random numbers? IE, did you use the usual "random()" program? (such
things as drand48() or whatever?" If so, what did you do about the exponent
field? If you left it on, you were not generating 32bit random values at
all, but, rather, something significantly less (no more than 24 and maybe less
than that.)
First, let's see how "random" your random numbers are, to make sure we are
comparing apples to apples here (see my previous post to see what I do in
Cray Blitz to strip the exponent off.)
Looks like this supports my claim that the more distance between the positions,
the more likely they are to hash to the same key. These positions are wildly
different and it would take many moves to make them match (yes, I know, you
really can't since you can't "make" pawns appear where there aren't any.
Hopefully, you see my point.)
mar...@stack.urc.tue.nl (Marcel van Kervinck) writes:
> I frequently see hashkeys in a <10^5 searches with closeness 31, indicating a
> near-clash. For me this indicates that it is very likely that real hash
> clashes also occured (but could not be detected, since positions with
> closeness 32 are considered to be the same). This seems to contradict your
> observation.
Robert Hyatt (hy...@cis.uab.edu) wrote:
> First, let's see how "random" your random numbers are, to make sure we are
> comparing apples to apples here (see my previous post to see what I do in
> Cray Blitz to strip the exponent off.)
I implemented my own random number generator, guided by Knuth's book.
It seems to work perfectly. I don't depend on routines by others.
So my numbers are truly '32bit' random.
I realized that some confusion might arise: I am refering to <10^5
searches that start with an already filled table. (Like in a game)
Starting with an empty table one needs almost 10^5 nodes to fill
most empty slots. Whenever I do start with an empty table, I usually
find the 1st 31bit match within 200,000 nodes, and have several (about
6? I didn't do this often enough to get an accurate estimate) pairs of
31bit matches before reaching 10^6 nodes.
Maybe I misunderstand what it is you are testing. Are you generating
positions to fill the table and then searching as the game proceeds
and logging the "hits"?? Or are you simply playing a game, and watching
for hits during normal play?
: Startech played at the Indianapolis tournament and ran on (I believe) a
: 512 node CM-5. Caused quite a bit of controversy as HiTech was also
: present at the tournament.
: I somehow don't have my tournament booklet from the event, and thus can't
: tell you where they finished. I believe that the final standing was that
: Socrates Won, we finished 2nd, and I don't remember beyond that. Bert,
: got your ears on? (or anyone else.)
: In any case, measuring their performance was difficult. They searched
: from 40K nodes per second up to 300K. Unfortunately, it seemed that when
: they were in trouble, they searched "at their worst" and slowed down
: quite a bit, which, of course, is exactly the opposite of what you want
: to see happen.
: Brad xxx (don't remember his last name) seemed to think that StarTech
: was better than HiTech, but I do seem to recall that they drew in this
: event. They were supposedly the same code, same book, same everything,
: except "smashed onto the CM-5 architecture." Actually played well,
: but I "believe" they finished at 2.5 out of 5.0 points (both them and
: HiTech, but don't quote me without a reliable source to back this up.)
: Bob
: --
: !Robert Hyatt Computer and Information Sciences !
: !hy...@cis.uab.edu University of Alabama at Birmingham !
The tournament program lists Bradley Kuszmaul, Charles Leiserson, and
Ryan Rifkin c/o BK,MIT Laboratory for Computer Science as the authors
of Startech. It was running on a Connection Machine CM-5, 128 processors.
I do not have a complete cross-table but what I do have shows them with
3 points, tied with Hitech and Zarkov.
Bert
Albert Gower
University of Southern Mississippi