Thanks for the replies. I will most likely be writing in C++ given the additional abstraction mechanisms and my current lack of understanding of preprocessor #define type tricks.
I remember reading about Zobrist's hash functions in some old messages on the list and some papers on the GHI issue but at this point I am still just implementing the basic light playout simulation code so I haven't quite gotten here yet. I wonder concerning GHI for doing searches in go that you could in principle encode extra information into the "position" key which could be use to discriminate board positions which appear to be the same but differ in crucial ways. Thanks everyone for the help. --- On Tue, 7/14/09, Don Dailey <dailey....@gmail.com> wrote: > From: Don Dailey <dailey....@gmail.com> > Subject: Re: [computer-go] memory management for search trees(basic question) > To: "computer-go" <computer-go@computer-go.org> > Date: Tuesday, July 14, 2009, 8:32 AM > There has been quite a few descriptions > on this forum about how people do this. > > I am guessing, but I think most of the authors allocate a > pool of memory and manage this themselves. Are you > writing in C? > > > In C you can declare a fixed size record (called a > struct) and just make an array of them. This is what > my program does. When I need new nodes I just use the > next ones available and a counter keeps track of where I > am. > > > It's a little more complicated if you also need to > remove nodes. I don't do this. When a new search > begins I can just start over again. > > I think there are a lot of variations of what people > do. Perhaps a better way is to use a hash table > instead of a tree. It's still a tree of course but > structured different. With a hash table a zobrist key is > used to index into a hash table. So you can build your > tree this way, again using a fixed pool of nodes or > whatever hash table method you need to. One advantage > of a hash table is that with transpositions you can resuse > information that has already been computed - but one > disadvantage is that you have to deal with Graph History > Interaction (GHI.) I think most program ignore GHI > for the most part (in a similar way that computer chess > programmers ignore the problem) but I'm not real sure on > this one. > > > You can also use malloc and free to allocate space for > nodes - but it is well known that this can be challenging > for writing bug free programs. I have found that you can > almost always avoid it and I personally only use it for top > level data structures - for instance I might allocate my > initial fixed pool of nodes this way (and so it can be user > configurable) but I won't allocate and free individual > nodes. > > > Also, if you use malloc and free you will surely see a > slowdown. > > Another option is to use the Hans Boehm garbage collector, > a library you simple link to in your C programs. It > will do the automated garbage collection for you - but I > think you will see a slowdown and I think there is a memory > overhead penality for using this as it probably needs > working space. > > > - Don > > > > On Tue, Jul 14, 2009 at 11:06 AM, > Carter Cheng <carter_ch...@yahoo.com> > wrote: > > > > This is something I have been curious about since I am > somewhat new to writing code in languages which require > explicit memory management (as opposed to have some sort of > garbage collector do it for you). The question is how do > most programs manage memory w.r.t. the search nodes? Is the > memory preallocated in advance or is there some strategy to > grow the space required as the nodes accumulate during a > search? > > > > > Thanks in advance, > > > > Carter. > > > > > > > > _______________________________________________ > > computer-go mailing list > > computer-go@computer-go.org > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > -----Inline Attachment Follows----- > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
