Á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 _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
