On 6/6/07, Jacques Basaldúa <[EMAIL PROTECTED]> wrote:
For the problem in which moves have probability in {0, 1/n} of being selected (n = number of legal moves or empty points depending on the approach), what Don does, i.e.:Keeping a vector of selectable/not selectable points with a moving limit: When you have to fill a gap, do it immediately by moving one from the border to the selectable area, sounds the best for me. But, how do you handle draws with different probabilities ?? Of course, it is trivial (but slow) if you add them all and keep an array of accumulated probabilities. I created something I call a ticket based lottery. Moves (legal in my case) "buy" tickets. An average move buys, say 10 tickets, the worst possible move buys just 1 and the most urgent buys 100. Of course these numbers should be tested empirically, because, the higher, the slower. (About 20 clockcycles per ticket. ~6ns·n is the difference between allocating 1 and allocating n (5 asm instructions)). And tickets are allocated in something similar to Don's idea. I have also considered doing multiple tickets just like coins. Having tickets of x1 and a separate tickets of x5 or some other value. Any ideas ?
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. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
