Jason House wrote:
On Apr 15, 2009, at 6:50 PM, Michael Williams
<[email protected]> wrote:
You can change the value all you want. You just can't change the key.
Right... That's the design in the google talk. Remi said he "can reuse
cache entries" and so avoids resizing / copying (greatly simplifying
the algorithm). I find that 32 bit zobrist hashing takes a few minutes
before reusing a single hash value. That's too infrequent to use in
place of real cleanup. Smaller hashes (such as 16 bit) would have too
much ovelap to be useful... So rejecting that possibility leaves me
clueless about what reusing a hash entry could mean besides replacing
a complete slot in the table.
I simply consider entries from previous searches as free for
replacement, unless they descend from the current root. So I may replace
them completely by a new node. Date of birth is really what indicates
whether a slot is free or not.
The principle of the table is like this: I allocate an array of N nodes.
if hash code is h, I probe at h%N,(h+1)%N,...,(h+R)%N, were R is a
"rehash" parameter. There is never any node de-allocation, except
between searches, with the date-of-birth mechanism, but this not done
concurrently.
If the table is not big enough, then node allocation may fail, although
the table may still have plenty of free slots. In that case, I just
don't allocate the node, which is OK with a MC search. In practice, with
1Gb of RAM, this never happens.
I don't remember precisely, but maybe I needed to implement a special
logic to make allocation thread safe. It is not very difficult. I am
very confident that my implementation is correct, although I did not try
a formal proof. The only difficulty is when two threads try to allocate
the same slot. Also, it is important to avoid that two threads create
the same node in two different slots. This is not very difficult to do
with compare-and-swap. It may be a bit different from what Cliff Click
does, though.
Rémi
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
