[Computer-go] effectiveness of transposition tables for go

Don Dailey dailey.don at gmail.com
Mon May 10 16:37:33 PDT 2010

On Mon, May 10, 2010 at 7:02 PM, Mark Boon <tesujisoftware at gmail.com> wrote:

> On Mon, May 10, 2010 at 12:05 PM, Don Dailey <dailey.don at gmail.com> wrote:
> > It's extremely cheap to generate the hash key of a child move if you use
> > zobrist hashing.   You just add the random number of the piece/point you
> are
> > placing.    Only a fraction of the moves requires substantially more
> work.
> Adding a checksum is cheap. The small fraction which needs substantial
> work is (relatively speaking) extremely expensive. Doing this for all
> successors is about equivalent to the amount of work needed to do one
> light-weight playout, where the total time taken is dominated by the
> few moves that require more work. And you need to do this several
> times before you reach a leaf.

I think you are wrong about this.  The small fraction of the nodes that need
more work are still not a lot of work,  this is cheaper than making a move
and making moves are cheap.   And when a capture IS involved most of them
are 1 or 2 stones.     I don't really see how we can debate this point
without something concrete, it's just you saying it's expensive and me
saying it's cheap.     One observation I might make is that it could depend
somewhat on your data structure for representing the board and the moves and
liberties and such.     Some authors like to use heavy data structures with
pointers and linked lists of chains and such to represent a position and
there could be significant logic computing the key for a position without
actually making the move with such data structures.

> So I have a hard time seeing how this is "extremely cheap". It sounds
> "extremely expensive". Unless you have extremely heavy playouts. In
> which case the memory is not an issue either, as you're not going to
> create many nodes.

We disagree.

> I wouldn't mind hearing from someone who actually implemented a
> hash-table this way, as we both obviously haven't.

I have done both things.   When I did Lazarus I wanted to try the tree style
and it ended up being my strongest program, but not because of this but for
other reasons,  I was using patterns and heavier play-outs.    I don't
remember having a strong opinion either way but I also don't remember what
specific measurements I used.    If there was anything noticeable I know I
would have remembered it.

> With regards to memory usage, let's do a little math. Let's say you
> have 1/2 a Gb per core, a fairly conservative estimate I believe. And
> on each core you do 100K playouts per second for 10 seconds straight,
> a rather optimistic scenario I believe.That leaves 500 bytes per node
> for 9x9. That is easily enough to store pointers to all 82 possible
> children in a node and store a whole lot more information. (This is
> for 9x9. Bigger boards may have longer thinking times and more moves
> compensated by lower playout speeds. Most likely it evens out to be
> the same regardless the board-size.) Actual numbers in my
> implementation are closer to 20K (semi-light) playouts per second for
> 5 seconds, or a leaving space for an order of magnitude more.
> So, yeah, like you said earlier, I pretty much believe memory is
> plentiful enough not to worry about it much.

Don't you remember that Mogo had an issue with memory?   They had to go to
some kind of collection scheme where they reclaimed nodes that were not
likely to be used.    I don't know about your calculation above, it is
pretty speculative and assumes a lot.   But Lazarus could only think for
about 2 or 3 minutes before running out of memory.


> Mark
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20100510/fe529515/attachment.html>

More information about the Computer-go mailing list