# [Computer-go] Random move selection algorithm

George Dahl george.dahl at gmail.com
Tue Apr 12 14:39:21 PDT 2011

```The book Non-Uniform Random Variate Generation by Luc Devroye is
freely available online at:
http://cg.scs.carleton.ca/~luc/rnbookindex.html

One efficient way described in the book to generate samples from a
fixed categorical distribution is to rewrite it as mixture of 2 state
distributions with uniform mixing probabilities. Then you can generate
one uniform discrete value, do a table lookup, then flip a biased
coin. Depending on practical details, this may or may not be useful,
but it should almost always be useful if you want to sample many times
from the same categorical distribution.

- George

On Tue, Apr 12, 2011 at 5:29 PM, Álvaro Begué <alvaro.begue at gmail.com> wrote:
> 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
>>
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>

```