[Computer-go] effectiveness of transposition tables for go

Don Dailey dailey.don at gmail.com
Mon May 10 06:46:28 PDT 2010

On Mon, May 10, 2010 at 1:57 AM, Mark Boon <tesujisoftware at gmail.com> wrote:

> On May 9, 2010, at 6:22 PM, Don Dailey wrote:
> > So you are basically using the tree based data structure which is
> wasteful of space and supplementing it with a hash table to give you
> transposition information.   You are trying to get the best of both worlds
> by accepting the downside of both methods too.
> I never claimed it was the most memory efficient. It's a little more
> expensive than just trees. But I never experienced the memory-problems to
> the extent others have mentioned in the first place.
> I'm not being critical,  most programs I think are also using the tree
structure including my own program Lazarus.    I was just making the point
that this was supposed to be one of the advantages of transposition tables
and we were discussing how to get parent information from transpositions
tables.    That's why there was a misunderstanding with me about what you
are doing.   My brain was fixed on how to solve the parent problem with the
transposition table method.

If you are not experiencing memory issues it's probably because of some
combination of you either have a lot of memory, you are only playing fast
games or your program is slow.   If it's because your program is slow that
may not be a bad thing if it's because the program is very knowledge
intensive and you get a lot out of each playout.     Your method is a way to
get the advantage of transpositions with a tree data structure.

My machine when I developed Lazarus was only 2 gig and it was not a big
problem - I just couldn't have an infinite mode, where the program would
dwell on a single position for several minutes.    I found some compromises
that extended the possible thinking time to a few minutes if I remember
correctly without hurting the strength too signficiantly.

I wonder if it would be feasible to use a transposition table instead of a
tree (representing each node only once) and then tracking the parents
separately in the secondary hash table?    I'm not sure what the trade-offs
are but maybe this is more compact?

I don't know why people say the tree is easier.    Maybe it's my chess
background that makes this easy for me,  but the transposition table idea
seems more trivial than a tree and you are not managing pointers all over
the place.   I have done both methods so I  know.    Lazarus uses the tree
and I had to spend some time thinking about how to do the memory management
part.   I  found malloc/free for allocating nodes terribly expensive and
manage the memory myself by just reusing from a big pool of nodes.


> I started out with a tree because it's a little easier to debug. Then I
> tried transpositions to see if in principle it would work.
> I could have spent a lot of time trying to reduce the memory-footprint
> first. But then failing to make it work would have made me unhappier still.
> 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/89cf7c5c/attachment.html>

More information about the Computer-go mailing list