This sounds pretty good. Let me see if I understand. Basically when you create children you do the lookup to calculate zobrist keys and either find an existing record in the hash table or create a new entry. But after that, you just have pointers (or indices) to the children of a node to save time having to look up all the children.
Is that correct? It sounds like a pretty reasonable compromise between space and time. - Don On Fri, 2007-05-11 at 12:49 -0400, Álvaro Begué wrote: > We are using a compromise between the two options that Don described. > We have a tree using indices to a big vector (which is about the same > thing as pointers), and we have a separate structure that maps zobrist > keys to indices in the vector, using a hash. This map is only queried > when we add a position to the UCT tree. If we already have that > position, we simply point to the existing node. If not, we add it to > the map. The loss in speed is barely noticeable. But we haven't > investigated carefully how much performance we are getting out of it, > if any. It just seemed like the right thing to do. > > Álvaro. > > > On 5/11/07, Peter Drake <[EMAIL PROTECTED]> wrote: > > On May 11, 2007, at 9:20 AM, Don Dailey wrote: > > > > > Going along with this, the numbers won't add up (although I don't know > > > if that is important.) In other words, if you do 10,000 > > > simulations at > > > the root, all grandchildren will add up to more (due to > > > transpositions.) > > > If you propogate this up the tree you might come up with many more > > > than > > > 10,000 simulations at the root. > > > > As per the previous thread, it appears that one should not (even when > > using a direct tree) assume that > > the number of runs through the parent is the same as the sum of the > > runs through the children. > > > > Your other comments match my experience. > > > > Peter Drake > > http://www.lclark.edu/~drake/ > > > > > > _______________________________________________ > > 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/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
