I think most programs completely ignore this issue except for simple ko. I think for all practical purposes you can consider 2 positions identical if they have the same set of legal moves possible, considering only simple ko.
Of course this is not entirely correct, but I don't think it will weaken the program in any way that you could easily detect. At any rate, the cure might weaken the program more than the disease. You probably don't want to ignore this in the tree itself though. If a move is illegal due to any kind of ko, don't expand it. So your tree will be proper and correct, but some particular node may have data generated from positions that are technically different due to GHI issues. If anyone handles this any differently, it would be good to say something here ... - Don On Tue, Jul 14, 2009 at 12:10 PM, Carter Cheng <[email protected]>wrote: > > 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 <[email protected]> wrote: > > > From: Don Dailey <[email protected]> > > Subject: Re: [computer-go] memory management for search trees(basic > question) > > To: "computer-go" <[email protected]> > > 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 <[email protected]> > > 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 > > > > [email protected] > > > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > > > > > > -----Inline Attachment Follows----- > > > > _______________________________________________ > > computer-go mailing list > > [email protected] > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
