Re: [computer-go] a few more questions
Thanks for the help with this. I suspect I will go directly for a heavy playout implementation and avoid writing some of the trickier the light playout code so I probably will be implementing this soon. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
Álvaro Begué wrote: > On Tue, May 13, 2008 at 8:10 PM, Weston Markham > <[EMAIL PROTECTED]> wrote: >> On Tue, May 13, 2008 at 7:08 PM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: >> > And I agree, don't even think of doing this with floating point >> > numbers. >> >> This is a bit tangential to computer go. But you have piqued my curiosity >> >> Offhand, that sounds rather extreme to me. Perhaps I haven't really >> thought this through completely, but it seems as if there is a simple >> modification to the stated algorithm, that would ensure that it works >> fine with floating point numbers. Or at least well enough for any >> conceivable purpose: >> >> Make sure that you select each random number from a slightly larger >> range than prescribed by the exact totals. (For example, always round >> up while calculating the totals. If you do not have control over the >> rounding mode, just add on some small fraction of the largest weight.) >> Then, in the event that subtracting the weights of the >> points/rows/buckets never reduced the selected number to a >> non-positive value, just select a new random number and start over. >> >> Would this work fine, or is there some flaw in my thinking that Álvaro >> and Gunnar have already considered? > > John Tromp and I spent quite a bit of time patching the > floating-point implementation and hunting down the subsequent > bugs. I am not saying that making it robust is impossible, but I > ended up so frustrated that I don't think I will ever try again. > Integers are much better behaved and are sufficient for everything > we wanted to do. I did the same, until I decided that it was utterly pointless. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
On Tue, May 13, 2008 at 8:10 PM, Weston Markham <[EMAIL PROTECTED]> wrote: > On Tue, May 13, 2008 at 7:08 PM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: > > And I agree, don't even think of doing this with floating point > > numbers. > > This is a bit tangential to computer go. But you have piqued my > curiosity > > Offhand, that sounds rather extreme to me. Perhaps I haven't really > thought this through completely, but it seems as if there is a simple > modification to the stated algorithm, that would ensure that it works > fine with floating point numbers. Or at least well enough for any > conceivable purpose: > > Make sure that you select each random number from a slightly larger > range than prescribed by the exact totals. (For example, always round > up while calculating the totals. If you do not have control over the > rounding mode, just add on some small fraction of the largest weight.) > Then, in the event that subtracting the weights of the > points/rows/buckets never reduced the selected number to a > non-positive value, just select a new random number and start over. > > Would this work fine, or is there some flaw in my thinking that Álvaro > and Gunnar have already considered? John Tromp and I spent quite a bit of time patching the floating-point implementation and hunting down the subsequent bugs. I am not saying that making it robust is impossible, but I ended up so frustrated that I don't think I will ever try again. Integers are much better behaved and are sufficient for everything we wanted to do. As to the optimal branching factor for the tree (assuming there are many many leaves), I believe it's n=3, if all you care about is picking random points fast. Outline of the proof: On a particular level of the tree you will make about n/2 comparisons before you pick your branch and descend. The number of leaves is l = pow(n,k), so the number of levels is k = log(l)/log(n). The total number of comparisons will be something like (log(l)/2)*(n/log(n)). The first part is fixed, so we need to minimize n/log(n). That function reaches its minimum at n=e, but unfortunately n has to be an integer value. Among the integers, n=3 is the best, with n=2 and n=4 tied at as close seconds. Of course, in practice you will also need to do updates to the weights (actually more often than picking random points), so the number of levels in the tree becomes more relevant, which favors larger values of n. My original implementation had n=2 and the tree was beautifully implemented as an array, in the same style as the usual implementation of a heap. However, Rémi pointer out that cheaper updates were important. I think the two-level solution using rows is easy to implement and probably close to optimal. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
On Tue, May 13, 2008 at 7:08 PM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: > And I agree, don't even think of doing this with floating point > numbers. This is a bit tangential to computer go. But you have piqued my curiosity Offhand, that sounds rather extreme to me. Perhaps I haven't really thought this through completely, but it seems as if there is a simple modification to the stated algorithm, that would ensure that it works fine with floating point numbers. Or at least well enough for any conceivable purpose: Make sure that you select each random number from a slightly larger range than prescribed by the exact totals. (For example, always round up while calculating the totals. If you do not have control over the rounding mode, just add on some small fraction of the largest weight.) Then, in the event that subtracting the weights of the points/rows/buckets never reduced the selected number to a non-positive value, just select a new random number and start over. Would this work fine, or is there some flaw in my thinking that Álvaro and Gunnar have already considered? Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
This could be extended rather easily to an n-ary tree. With 9x9 a natural choice is 3, but unfortunately 19 is prime. It's basically a tradeoff between how many adds and how many compares you want to do. I suppose you would do one update for every pick (unless you pick an illegal point and want to remain uniformly random, hehe). So it seems that it would be best to make n as small as possible, at least theoretically... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
Álvaro Begué wrote: > On Tue, May 13, 2008 at 4:22 PM, Carter Cheng <[EMAIL PROTECTED]> wrote: >> 2) When generating random variables for the case where the "values" >>of placing a stone on different points on the board are >>different. Are there good ways to throw and determine which >>point has been selected for the next move by the random player? > > I can answer this. The best way I know of getting a random point with > different weights (proportional to probabilities) for each point is to > keep a sum of weights per row and a total sum of weights for the > entire board. These are easy to update dynamically when an individual > weight changes. In order to pick a point, start with a random number > between 0 and the total sum. Go down row by row subtracting the weight > of each row, until you would get a negative number. Then walk the row > subtracting the weight of each point until you would get a negative > number. The place where you stop is the selected point. > > This method may not be very robust if you use floating-point numbers > to represent weights (because you can't rely on associativity of > addition), but it works fine if you use an integer type. > > If the description is not good enough, I can write some C++ code for you. Or you can read the source code of GNU Go 3.7.12, lines 1629-1658 of engine/montecarlo.c. The only difference is that GNU Go doesn't bother about actual rows but instead makes a two level structure where it uses the N lowest bits of the board coordinate to determine a partition number. N varies from 1 to 4 depending on the maximum board size GNU Go is compiled for (3 for 9x9, 4 for 19x19). And I agree, don't even think of doing this with floating point numbers. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
On Tue, May 13, 2008 at 4:22 PM, Carter Cheng <[EMAIL PROTECTED]> wrote: > 2) When generating random variables for the case where the "values" of > placing a stone on different points on the board are different. Are there > good ways to throw and determine which point has been selected for the next > move by the random player? I can answer this. The best way I know of getting a random point with different weights (proportional to probabilities) for each point is to keep a sum of weights per row and a total sum of weights for the entire board. These are easy to update dynamically when an individual weight changes. In order to pick a point, start with a random number between 0 and the total sum. Go down row by row subtracting the weight of each row, until you would get a negative number. Then walk the row subtracting the weight of each point until you would get a negative number. The place where you stop is the selected point. This method may not be very robust if you use floating-point numbers to represent weights (because you can't rely on associativity of addition), but it works fine if you use an integer type. If the description is not good enough, I can write some C++ code for you. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] a few more questions
Thanks for all the comments so far. Hopefully you don't mind a few more questions. 1) Do UCT bots check for atari and urgency? my understanding was that first generation Mogo did this to some extent IIRC. I am curious if anyone does this it seems like it might be important but so far I cannot think of a fast detection scheme. 2) When generating random variables for the case where the "values" of placing a stone on different points on the board are different. Are there good ways to throw and determine which point has been selected for the next move by the random player? Thanks again, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
