[computer-go] creating a "random" position

[Harri Salakoski]

> I think this is what I want.  Thanks!  So I might have to repeat this
> a few hundred times to actually get a legal position?
> - George

Implemented that and my test serie of number of rounds needed to generate 
legal board position is quite expected.

count=111, count=36, count=28, count=20, count=14, count=150, count=78, 
count=13, count=149, count=113, count=186, count=43

count=149, count=178, count=103, count=57, count=21, count=23, count=47, 
count=25, count=221, count=44, count=82

So it is actually 1.2% according ( 
http://homepages.cwi.nl:80/~tromp/go/legal.html) .
So average is fortunately less than hundred, so it is quite usable.
t. Harri
----- Original Message ----- 
From: "George Dahl" <george.dahl at gmail.com>
To: <computer-go at computer-go.org>
Sent: Monday, July 09, 2007 8:55 AM
Subject: Re: [computer-go] creating a "random" position


> On 7/8/07, Paul Pogonyshev <pogonyshev at gmx.net> wrote:
>> 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
>>
>
> I think this is what I want.  Thanks!  So I might have to repeat this
> a few hundred times to actually get a legal position?
> - George
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/