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

[dhillismail at netscape.net]

On Sun, 2007-05-27 at 13:21 -0400, 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/

 If I had it to do over again, knowing what I know now, I would not spend a 
lot of time optimizing random games. These optimizations don't make much
difference for heavy playouts and heavy playouts are better.
 
- Dave Hillis 
 

























________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070527/b3abf6c4/attachment.htm