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

[Rémi Coulom]

Á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