[Computer-go] effectiveness of transposition tables for go

Mark Boon tesujisoftware at gmail.com
Mon May 10 12:55:29 PDT 2010

On Mon, May 10, 2010 at 3:46 AM, Don Dailey <dailey.don at gmail.com> wrote:
> 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.

Different things are easier or harder for different people.

But I find a lot of the posting about hash-tables inconsistent. You
tout it as being more memory-efficient than a tree. Yet you worry
about memory usage. Yes, a tree has pointers. But so does a hash-table
as it basically represents the same tree. But it's probably just
represented in a different way. One of the things I understand is
commonly done in the hash-table representation is that every position
stored contains references to all possible children. To alleviate the
memory problem this causes, many implementations delay the expansion
of nodes.

With trees I find I have a lot more flexibility. I can always expand a
node when needed, as a child does not necessarily have to carry the
weight of referencing all children.

I'm not claiming superiority of one method over the other. But I think
it's a lot more nuanced than the impression I get from reading this
list. As to speed, I'd be interested to see a comparison.


More information about the Computer-go mailing list