[computer-go] Efficiently selecting a point to play in a random playout

[Peter Drake]

I've spent a lot of time struggling with this; it can have a huge  
impact on performance. The key thing to remember is to keep the  
common case fast.

Orego currently maintains a list (technically a stretchable array,  
analogous to the java.util.ArrayList class) of vacant points. I  
shuffle this list at the beginning of every playout. When it's time  
to choose a move, I work through this list until I find a legal move.  
Since vacant points are almost always legal, this usually produces a  
legal move very quickly.

I believe it's not worth maintaining a set of legal moves; when  
you're choosing a move randomly, you're not going to consider most of  
them, so any time spent checking their legality would be wasted.  
Maintaining a set of vacant points, on the other hand, is worthwhile,  
as it allows you to completely skip over verifying that the occupied  
points are illegal.

If your description of libego is accurate, it introduces a bias. If  
point X is vacant but illegal (say, it's inside an enemy eye), the  
next vacant point is twice as likely to be selected as some vacant  
point that doesn't follow an illegal one. I proposed an elaborate way  
to get around this bias here:

https://webdisk.lclark.edu/xythoswfs/webui/_xy-2352013_1-t_Gct7yJ5s%22

but I now believe that shuffling a list of vacant points is faster.

Peter Drake
http://www.lclark.edu/~drake/



On May 27, 2007, at 10:21 AM, Jason House wrote:

>  As I get into the home stretch of rewriting the core of my bot, I  
> want to add a monte carlo player.  I've realized that picking a  
> random move to play is non-trivial since it's such a key element in  
> playout speed.
>
>  An array of legal positions has easy lookup, but may not be easy  
> to maintain... I guess it'd require storing a mapping between board  
> position and index into the legal positions array so that a move  
> that becomes illegal can be quickly removed (by moving the item  
> from the tail of the array into the empty location).
>
>  Looking at libego, I see it does a variant on this where it  
> maintains an array of empty points.  If the random index it picks  
> is disallowed, it'll scan through the array (with wrapping around  
> the end) until it either finds an allowed move or returns to its  
> starting point.
>
>  Which methods have people tried and what works best?
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070527/1bdd50f9/attachment.htm