[computer-go] creating a "random" position

[Harri Salakoski]

In normal board size 1% random positions is legal, so it needs some rounds, 
but method is still superior propably any other if position must be random.
t. Harri

----- Original Message ----- 
From: "Paul Pogonyshev" <pogonyshev at gmx.net>
To: <computer-go at computer-go.org>
Sent: Monday, July 09, 2007 12:38 AM
Subject: Re: [computer-go] creating a "random" position


> George Dahl wrote:
>> How would one go about creating a random board position with a uniform
>> distribution over all legal positions?  Is this even possible?  I am
>> not quite sure what I mean by uniform.  If one flipped a three sided
>> coin to determine if each vertex was white,black or empty, then one
>> would have to deal with stones with no liberties somehow.  Could those
>> just removed?
>
> As I remember from theory of probability, you can create such a uniformly
> "random" position this way[1]:
>
>  1. create a really random position, i.e. traverse all intersection and
>     assign a black/white/empty state at random to each;
>
>  2. if it happens to be not legal, discard and repeat step 1.
>
> I believe it should be very fast, and this mustn't be difficult to check.
> I.e. rate of discards should be low enough for speed of algorithm to be
> speed of step 1 times C, where C is small.
>
> However, this will tend to give you very artificial-looking positions.
> Whether it is fine for your use-case, you know better.
>
>  [1] http://en.wikipedia.org/wiki/Rejection_sampling
>
> Paul
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/