[Computer-go] effectiveness of transposition tables for go
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
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