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

[Jason House]

On 6/5/07, Don Dailey <drdailey at cox.net> wrote:
>
> But if you are taking the vacant points out it is probably not
> too biased as you say.
>
> But what I do is pretty fast.  Always choose a random point but
> keep shrinking the list.  When a point is occupied move it out
> of the way so it's never selected again.   You have to do some
> simple bookeeping - basically swapping the position of elements
> and shrinking the list (in your terminology, maintaining a set
> of empty points.)



Do you eliminate all illegal/stupid positions?  Filling eyes? Suicide
plays?  Disallowing suicides likely means you need a list for each color.
Sadly, if a move was rejected because it was an illegal suicide and then the
enemy chain puts itself in atari, the simple capture move would have been
pruned.


I don't think this is any slower than what you are proposing.
>
> I start a random game by collect vacant points - but after a
> capture move you have to re-do this operation.   Still, it's 2X
> faster to collect vacant points together like (even if you are
> doing everything else this way.)



It's likely that you could do an incremental update after a capture instead
of recomputing the entire list.  The only real issue is any moves pruned
because of suicides (potentially far away from the captured chain, but
guaranteed no more than one per neighboring chain)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070605/87381320/attachment.htm