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

[Jason House]

  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?