Remi keeps a number that is the sum of all the probabilities (I'll call them that, although they are not normalized so they add up to 1) and also one number per row that is the sum of the probabilities of the points in that row. Now you pick from the distribution of rows, and inside the row from the distribution of points, and it can be done fast.
On 9/20/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > > -----Original Message----- > > From: Rémi Coulom <[EMAIL PROTECTED]> > > To: computer-go <computer-go@computer-go.org> > > Sent: Thu, 20 Sep 2007 10:22 am > > Subject: Re: [computer-go] Crazystone patterns > > Chris Fant a écrit : > > > Does this mean that you need to calculate the Bradley-Terry > > > probability for every legal move before selecting one on that > > > probability? Isn't that expensive? Have you tried selecting only N > > > legal candidates at random and then selecting one of those based on > > > their Bradley-Terry probability distribution to save time? > > > I only keep light-weight local features in the random simulations. So, it > is not expensive. A table of move urgencies can be > > > updated > incrementally after each move: only a few change. In fact, my program became > faster when I introduced 3x3 patterns > for the random simulations. I can > pre-compute a lot of information indexed by pattern shape, that are useful > to detect eyes > > > and move legality. From memory, Crazy Stone does about > 5k playouts / second from the empty position on 19x19, on one 3 > > GHz CPU, > which is "only" about 5 times slower than libego, if I remember correctly. > > > > Rémi > > > Suppose I can generate scores for all of the moves quickly enough. I still > face the problem of quickly choosing a move biased by the scores. Tournament > selection is fast, but that is a function of relative ranking of the scores, > not the values of the scores. Roulette wheel selection gives me an answer, > but it is slow slow slow, the way I implement it anyway. Can anybody > describe a good way to do this? > > - Dave Hillis > > > > ________________________________ > Check Out the new free AIM(R) Mail -- Unlimited storage and > industry-leading spam and email virus protection. > > _______________________________________________ > 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/
