[Computer-go] Random move selection algorithm

Álvaro Begué alvaro.begue at gmail.com
Wed Apr 13 05:01:17 PDT 2011


On Wednesday, April 13, 2011, Steve Kroon <kroon at sun.ac.za> wrote:
> Á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?

We organized a binary tree using an array by considering that the root
is element 1 and the children of element n are 2*n and 2*n+1. The last
361 elements are leafs where we store the individual probabilities of
each point, and in non-leaf nodes we store the sum of the
probabilities of the subtree they represent.

I would hardly consider 360 integers to be an "expense". The real
expense is the O(lg N) steps involved in getting a move and in
modifying the probability of a leaf.

In some sense, the probability-of-rows method is using a 19-ary tree.
It is likely that using something in between could be faster. Perhaps
a three-level tree? I didn't experiment much with this.

Álvaro.


>
> 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