Á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/
