[Computer-go] effectiveness of transposition tables for go

David Fotland fotland at smart-games.com
Tue May 11 09:35:43 PDT 2010


It is quite memory hungry since near the leaves there are many positions
with very few active children.  On 9x9 I let a few playouts go through a
move before expanding it, and that gives me plenty of memory.  I ship with a
default of 300 MB reserved for the hash table, and that's enough.

David

> -----Original Message-----
> From: computer-go-bounces at dvandva.org
[mailto:computer-go-bounces at dvandva.org]
> On Behalf Of Mark Boon
> Sent: Monday, May 10, 2010 11:58 PM
> To: computer-go at dvandva.org
> Subject: Re: [Computer-go] effectiveness of transposition tables for go
> 
> 
> 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
> 
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go




More information about the Computer-go mailing list