[Computer-go] effectiveness of transposition tables for go

Mark Boon tesujisoftware at gmail.com
Mon May 10 23:57:53 PDT 2010


On May 10, 2010, at 8:04 PM, David Fotland wrote:

> Many Faces just has a hash table, no tree.  There are no pointers to parents
> or children in the hash table.  There is a linked list for collisions.
> Nodes are bigger, because each node contains an array of all legal moves and
> their RAVE values.  However, I think this is more cache friendly than
> walking a linked list of children.

Thanks, that's a clear explanation. So basically the move and the RAVE values act as the reference to the next position. But I can see how it's more efficient with respect to a cache as you don't have to follow pointers to get the win-rate for each move from a potentially remote location. That makes some sense to me. Do you do something special at the leaves? As otherwise I can see this gets memory hungry very quickly.

> When MFGO had really light playouts it was doing about 53K 9x9 playouts a
> second per 2.4 GHz core.  Now it's more like 7K 9x9 playouts a second per
> core.

I take it the light playouts didn't do much more than calculating liberties? From 53K down to 7K means you do considerable extra work. Is that due to the original MFGO engine? Because in Java I could still do a lot of pattern matching and tactical reading before it would be down to 6K-7K per second on one core.

Mark




More information about the Computer-go mailing list