[Computer-go] Random move selection algorithm

Álvaro Begué alvaro.begue at gmail.com
Tue Apr 12 14:29:40 PDT 2011


John Tromp and I initially implemented this using a binary tree
(efficiently implemented in an array, the way heaps are often
implemented), but then someone (I believe it was Rémi) gave us a more
efficient method, which is keeping track of the sum of probabilities
for each row. You can then roll a U(0,1) die, loop through the rows
subtracting the probability of each row from that number until it
would cross 0, then go along the row subtracting the probability of
each point from tat number until it reaches 0.

The bigger problem is how to make this method robust to floating-point
inaccuracies. I don't know if this is a common problem, but at least
we had some trouble getting that right.

Álvaro.


On Tue, Apr 12, 2011 at 4:05 PM, Yuanxin Xi <xi11west at gmail.com> wrote:
> Hi all,
>
> I've been reading posts on this list and this is my first post.  I'm
> looking for an algorithm related to move generation. Suppose there're
> N possible moves with probability p_1,p_2...p_n (sum(pi)=1), I
> generate a random number R between 0 and 1 to choose one move w.r.t
> the probabilities.  How to find the move efficiently, instead of
> enumerating p_1, p_2 until the accumulating p is greater than R?
>
> I remember this has been discussed before but I cannot find it.  Can
> someone please remind me the name or keyword I can search?
> Thank you.
>
> Best regards,
>
> Yuanxin Xi
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>



More information about the Computer-go mailing list