[Computer-go] effectiveness of transposition tables for go

Mark Boon tesujisoftware at gmail.com
Mon May 10 16:02:29 PDT 2010


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.

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.

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

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.

Mark



More information about the Computer-go mailing list