> > 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.
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. > > 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. 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. -David > > 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
