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

[Gunnar Farneback]

Inge wrote:
> I plan to implement the replacement scheme that he calls TWO-BIG1.  It
> is a scheme where every cache node has two entries: 
> 
> 1. The one with the biggest amount of work invested in it.
> 2. The most recent one.
> 
> The work is counted in number of nodes that were investigated to get
> the result in the node.  In our case, we can immediately use the same
> measurement and for owl and semeai nodes, we just add the tactical
> reading nodes that are used to get the result of this owl/semeai node
> and the ones leading up to it in the owl search.
> 
> When we get a hash collision and the node is full, i.e. both entries
> are filled, we compare the new one with the first one.  If the amount
> of work needed to recalculate the new entry is bigger, we replace the
> first entry, otherwise we replace the second entry.  This means that
> the new entry becomes the new "most recent" one.

Make sense and sounds good.

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

That's good then. It bothers me that I don't remember why we have to
do that currently. I'm sure it was some good reason...

> I have to refer back to Breuker here.  The only thing that would lead
> to an increased risk for collisions is that we might be able to use
> more entries in the table.  This increase is very small, and 64 bits
> will still be very much enough.

That sounds about what I was thinking. More precisely, without
checking any references, I would guess that the collision probability
is proportional to M^2*2^(-N), where M is the number of entries in the
table and N is the number of bits in the Zobrist hash.

Arend wrote:
> My assumption was that Inge's scheme uses a 64-bit hash value to
> identify board position, the routine, and the attacked/defended objects
> (whereas now it's used to identify the board position).
> But that's pretty much non-sense, as Inge can still store that
> information in the actual entry.

Are you certain that would make a difference? I think it's very nice
if we can collect all input information into a single Zobrist hash.

> Yes.  Lookup is simple to improve, with a hash table. As for replacement,
> I was so far not able to think of a non-messy solution that is not
> O(cache size). But yes, it's certainly possible.

A standard heap?

/Gunnar