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

[Don Dailey]

On Tue, 2007-06-05 at 13:12 -0700, Peter Drake wrote:
> > So I'm only temporarily maintaining a list of illegal but unoccupied
> > points - this list gets "discarded" as soon as a legal move is
> tried.
> 
> Does that mean you have to regenerate the list every move?

I keep the list of un-occupied points - but the tiny list of illegal
points
gets regenerated from move to move.

However, this list is so tiny that it rarely amounts to more than 0
moves.  Near the end of the game it could get bigger, but if it does it
is starting to save some real time.   I think this is win/win.    

> > What you are doing is to avoid the call to the random number
> generator
> > by
> > trying the moves as a circular list.  This may be faster, but it's
> > biased,  perhaps the bias is insignificant enough that it doesn't
> have
> > an impact on the strength.
> 
> No, I pick a random point in the list every time, so there's still a  
> call to the random number generator. Just proceeding through the
> list  
> would be horribly biased (unless the list were pre-shuffled, as I
> was  
> doing previously). 

So it's possible that in a degenerate case you could pick many illegal
moves over and over again.   Technically, you could get into an infinite
loop if the period of your RNG was such that a legal move could not get
seen.   But I'm being really picky :-)

I am perhaps being too anal making sure I don't choose the same illegal
move twice.   However the code is trivial and it's not a major
difficulty managing. 

But I'm wondering if starting at a random point in a list of unoccupied
points and searching sequentially is really that terrible?    Another
idea I have is that when you do hit an illegal point, swap it with a
random element so that this particular bias point is changed for the
next move, then continue to search sequentially for a legal move.   You
could eliminate most of the RNG calls and the swaps.   But there are
probably not that many anyway.

- Don