Don Dailey wrote:
These are used in parallel chess programs, and it's very common. A
pretty good article on this written by Hyatt (Crafty programmer and
author of former world computer chess champion Cray Blitz) and it's
called "A lock-less transposition table implementation for parallel
search chess engines",
I see an on-line version of a similar article here:
http://www.cis.uab.edu/hyatt/hashing.html
- Don
Hi Don,
Yes, I knew Bob's paper. In his approach, an entry will be lost in case
of a collision. In my Go program, I never replace hash entries of the
current search, because I have enough memory to store them all. I only
have to be careful when allocating a node for the first time, so that
two threads do not allocate the same slot. This happens rarely enough
that the cost of a Test-And-Swap is negligible, so I prefer to do it
that way. What I do is essentially the beginning of the Google talk I
indicated yesterday, without resizing. I believe it is a lot cleaner
than Bob's idea, although atomic increments are costly.
In fact, now that I think a little more about it, Bob's scheme would
probably not work at all, because updating counters would mean updating
the hash code, and any collision would cause a loss of the hash entry.
It does not matter for alpha-beta, but losing an entry near the root in
MC search would be very bad. Really ugly stuff would be necessary to
repair the consequences of such a collision.
So, I believe Bob's idea would not work.
Rémi
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
