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

[Peter Drake]

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.

(My "legality" check does eliminate playing in a probable eye.)

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



On Jun 5, 2007, at 12:18 PM, Jason House wrote:

>
>
> 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)
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070605/3e2195e2/attachment.htm