[computer-go] a few more questions

[Gunnar Farnebäck]

Álvaro Begué wrote:
 > On Tue, May 13, 2008 at 4:22 PM, Carter Cheng 
<carter_cheng at yahoo.com> 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