[Computer-go] Random move selection algorithm

Steve Kroon kroon at sun.ac.za
Wed Apr 13 00:07:58 PDT 2011


Just to clarify: did your binary tree approach basically encode a decision tree for the binary search I suggested, thus saving
time on index calculations at the expense of storing an array twice the size?  Or was it something else?


On Wed, 13 Apr 2011, Steve Kroon wrote:

> An alternative approach is to keep the cumulative probabilities
> (a[j]=sum_{i=1}^j p_i) in an array, and then to do a binary search for R.  This
> can be done in two phases (row and then column) if you're considering all the
> moves on the board, but then you're searching through 19 values each time, so the linear
> search suggested below is likely more efficient in practice.
> Steve
> On Tue, 12 Apr 2011, Álvaro Begué 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

Steve Kroon | Computer Science Division, Stellenbosch University
(084) 458 8062 (Cell) | (086) 655 4386 (Fax) | kroonrs (Skype)
http://www.cs.sun.ac.za/~kroon | kroon at sun.ac.za

More information about the Computer-go mailing list