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" <[EMAIL PROTECTED]>
To: <[email protected]>
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
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
