On Mon, May 10, 2010 at 3:55 PM, Mark Boon <[email protected]> wrote:
> On Mon, May 10, 2010 at 3:46 AM, Don Dailey <[email protected]> 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. Both representations essentially form a tree, but it's more abstract with the hash table - the connection between nodes is NOT done with actual pointers but inferred from the rules of the game. So I don't see how you can say that a hash table has pointers. You don't need a single pointer if you use the hash table representation. Of course you can add them if you want to, but it's a waste of memory space. The child nodes can be located without pointers. The savings in space is that you can eliminate any pointers and every position has exactly one entry in the table. With a tree, you can reach any position many different ways and each way consumes an extra node. Of course a hash table, if sparse, has extra empty slots for node expansion or it can use linked lists to handles collisions in which case it does use pointers. But that is an implementation detail, not a requirement for hash tables. Please note that I am NOT endorsing one way over the other. Also please note that my own program uses explicit tree data structure, not hash tables. I am merely stating some facts - a hash table representation is inherently more compact for this. It's still not clear to me which is best as there appears to be numerous trade-offs here. I think the data structure you are using is as good as any if memory is not limiting you in any way. > 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. > There is no need for this unless it is a speed optimization. You can find any child by generating the hash key of each child. It seems ridiculous to me to store an average of at least 100 pointers per node. In my tree implementation I keep the children of any node together as a bunch. So I only need to know where the first one is and how many there are. So a node has a single pointer to the first child. The idea of having potentially several hundred pointers stored at each node is silly in either implementation. > > 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 don't think this is an issue. I'm not sure why you think this is how it has to be done. > 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. > It's possible something very clever is possible that I have not thought of. But this appears to be about trade-offs and I don't claim to have any special insights. Don > > Mark > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
