On 6/6/07, Rémi Coulom <[EMAIL PROTECTED]> 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.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
