On Mon, May 10, 2010 at 1:57 AM, Mark Boon <[email protected]> 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. Don > 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 > [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
