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

[Inge Wallin]

Arend wrote:
> 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.

Yes, except that the cost is a value, not a 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?...)

Good point!  Maybe the komaster and komaster point should also be part
of the hash value.

> No pointers at all!

Exactly.

> 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.

Not the whole point, but part of it.

> 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.

Actually I model this cache scheme precisely after the chess engines. 

> > > 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.

For possible future super ko handling I have another scheme up my
sleeve.  :-)  That one doesn't have to be included into the main hash
table at all.

         -Inge