[computer-go] Lockless hash table and other parallel search ideas

[Rémi Coulom]

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