[Computer-go] Random move selection algorithm

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


Álvaro:

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?

Thanks,
Steve

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