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

[Peter Drake]

On Jun 5, 2007, at 12:58 PM, Don Dailey wrote:

> On Tue, 2007-06-05 at 12:28 -0700, Peter Drake wrote:
>> Don't maintain the list of legal moves -- maintain the list of vacant
>> points (almost all of which are legal). When it's time to pick a  
>> move,
>> pick a random point in the list and iterate through checking each  
>> move
>> for legality. As soon as you find a legal one, play it.
>
> But you can do both.  It's simpler than it sounds.  I'm essentially
> doing what you suggest, but it's perfectly random, no bias.   And I
> doubt there is any cost that can be easily measured.
>
> 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?

> 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).

> You might improve the bias by "shuffling on the fly", perhaps when you
> find a legal move in the un-occupied point section of the list you  
> could
> do a swap with the first move and a random move.

I did something like this in an earlier version.

> I'm wondering if the
> biased ordering of the list persists from move to move?
>
> Maybe I benchmark your idea at some point.

Feel free...

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