Yes, Jason expresses my very concern about the hash table approach. I feel that is technically "wrong", but it's not clear to me whether it's the type of problem that will have a large impact on performance.
Lazarus tries to be a KISS program, so I took the easy way out and kept it real simple. It's hard to ignore the potential benefits however. I do believe the possibilities for transpostions are rich with UCT. Perhaps someone can produce some data on that? The number that would be most interesting is what is the effective number of simulations done vs the actual number of sims. It might be tricky getting the instrumentation correct. - Don On Fri, 2007-05-11 at 13:31 -0400, Jason House wrote: > > > On 5/11/07, Brian Slesinsky <[EMAIL PROTECTED]> 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. > > Maybe this is obvious, but it seems like the numbers do add up > if you > think about it differently? When the program does a > simulation that > has multiple ancestors, it is effectively working on multiple > simulations at once (counting each transposition > separately.) The > count at each node would then be the number of virtual > simulations > done. You could count the number of actual simulations > separately and > see what the ratio is between them at the root to see how > effective > the tables are. > > > > > Consider a node who's had one child extensively evaluated through > transpositions. When UCT does come to visit it, the sqrt(sum(child > simulations)) will be very high. That will artificially favor > exploration of children with less simulations. That will have a > continuing negative impact on the exploitation. > > ... but then once the parent gets updated with the sum(child > simulations), UCT may simply stop searching that branch for a long > time... Because it likely had a low average win rate, and now looks to > be extensively explored. When UCT eventually does come back to it, > the problem in the previous paragraph will still apply. > _______________________________________________ > 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/
