Re: [gnugo-devel] Improvement of the hash table in GNU go

[Arend Bayer]

Thanks for this 2nd explanation. I see that I didn't understand what you
are planning to do before.

To make sure I understand it right: You want to have the cache be one
single array
         cache[N].
Each array entry consists of two entries that store
 * the 64bit hash value,
 * the other date we store now (komaster, routine, position)
 * the result (of course :-) ),
 * a cost function.

Each reading result gets stored at cache[hash value % N]. To make this
efficient, it is more important than before to not get multiple entries
with the same hash value. That's why you want to add the routine and the
position to the hash value (possibly also komaster?...)

No pointers at all!

This looks indeed nice. The biggest save I see (apart from making the
caching code itself faster) is that we are never in a situation where
the whole cache just got deleted, and hence have to recalculate
everything. I assume this is your whole point.

Optimal organization of the cache might turn out to be different than
for chess engines, but even a not-quite-perfect scheme along the lines
you describe will be, I bet, clearly better than the current scheme.

> > We would still need to be able to handle open nodes.
>
> Actually, we wouldn't.  We wouldn't have to "reserve space", as it
> were, for it in advance.

Looking up a node should be so cheap with your new scheme that I see now
need at all to have "open" nodes. (Well, unless we want to use them
for Super-Ko someday.) This would also make the code in the calling
functions cleaner.

Arend