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/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/