[computer-go] Efficiently selecting a point to play in a random playout

[Álvaro Begué]

On 6/6/07, Rémi Coulom <Remi.Coulom at univ-lille3.fr> wrote:
> Álvaro Begué wrote:
> >
> > Actually, John had a better idea to do this. In two words: binary
> > tree. The root represents the whole board, and it contains the sum of
> > the probabilities of all the points (you don't need to force this to
> > be 1, if you use non-normalized probabilities). This node points to
> > two nodes, each of which represents about half the board and contains
> > the sum of the probabilities of all the points in its half. You keep
> > going down the tree until eventually you get to nodes that represent
> > individual points, with their probabilities. Picking a random move
> > according to the desired distribution now takes O(log(board_size))
> > (just toss biased coins at each level of the tree to decide whether to
> > follow the left subtree or the right subtree). Updating the
> > probability of a point also takes O(log(board_size)).
> >
> > I wonder if other people had thought about this before...
> >
> > Álvaro.
>
> Yes, I did it in the beginning. But I found that it is faster to divide
> by more than two. Currently, I keep the probability of the whole board,
> each line, and each point. It is simple, and more efficient than a
> binary tree.
>
> Rémi

That makes perfect sense! We will try that scheme instead.

Thanks!
Álvaro.