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

[Don Dailey]

Here is what I do, don't know if it's best ....

Basically you want a list of empty points, since most of them are legal.
When I apply a move to the board I then do any needed legality
testing.  

At the beginning I start with a list of ALL points on the board.   When
a non-empty point is encountered I "put it away", placing it behind a
point in the list that represents all the occupied points.   To find a
random move I choose an index at random among the set of untested
points.  If that point is occupied, it gets put away, if it's not it's
the next move (and it still get's put away since it will not be
occupied.)    If the point is not occupied but illegal, it gets "set
aside" until a legal move is found - then it is good again.   

When a capture occurs,  I have found nothing much faster than just
starting all over, due to my very simplistic data structure.    One
could take the time to restore those points but this is expensive  with
naive data structures.  

It's often not productive to play to points that have been captured -
often a complete waste of time for either side.   There may be some
enhancements where this fact is used to advantage, but I'm not sure how
to reliably test when this should and shouldn't be done.

Lukasz Lew does something far more sophisticated and very fast using the
concept of pseudo liberties which you might want to look into.

- Don




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/