Re: [computer-go] creating a "random" position
I know that might sound crazy, but it is working towards the eventual goal of creating feature extractors for Go positions. By learning to map Go positions as an array of stones to Go positions as graphs of strings (instead of just mapping them with a hand coded algorithm) I can take intermediate results in the learner's computation and use it as a feature for another learner. Sounds interesting. I was thinking about learning graph patterns from pro games for a while, but I guess the difficult thing is mastering the complexity of comparing graphs. If you can past that somehow I would guess that string-based pattern matching will be far better than "flat" patterns, if that's the thing you want to do. But I don't really understand how you want to do the mapping and what you want to do with the graph. Anyways, good luck with it =) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/9/07, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: Erik wrote: > Sure, but that does not necessarily matter because there are many more > end- than middle-game positions. The reason I brought it up is that I > remembered a statement by someone (sorry forgot the source, maybe John > or Gunnar remembers) that from all legal positions nearly all can be > considered final. Of course one could argue about what makes a > position final, obviously not all borders will be nicely closed and > generally there will still be some points to be gained, but I think > the main idea was that at that point the winner is relatively easy to > determine (so one side would normally resign). This also makes sense > if you simply look at the expected number of stones on the board. I don't remember that statement. My guess, without trying it out, is that most legal positions are rather unsettled and that the number of positions that are final in any strong sense is a tiny fraction of the legal positions. Ok, then probably I'm mistaken and read it in a different context. In any case, my statement should be relatively easy to falsify; just generate some positions and count the fraction that is easily solved. If correct, a decent uct search, or maybe even a traditional solver, would in most cases quickly converge to an extreme probability of winning. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
Erik wrote: > Sure, but that does not necessarily matter because there are many more > end- than middle-game positions. The reason I brought it up is that I > remembered a statement by someone (sorry forgot the source, maybe John > or Gunnar remembers) that from all legal positions nearly all can be > considered final. Of course one could argue about what makes a > position final, obviously not all borders will be nicely closed and > generally there will still be some points to be gained, but I think > the main idea was that at that point the winner is relatively easy to > determine (so one side would normally resign). This also makes sense > if you simply look at the expected number of stones on the board. I don't remember that statement. My guess, without trying it out, is that most legal positions are rather unsettled and that the number of positions that are final in any strong sense is a tiny fraction of the legal positions. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
If I took a set of game positions, generated by flipping a coin, and generated a histogram of x = black_stones - white_stones I would expect to see the distribution of x looking like a nice Gaussian, centered at zero. If I looked at positions generated by playing out moves, I would expect to see *much* more weight in the tails and the center at a positive value between zero and true Komi. Removing illegal positions from the coin flip set might change the distribution in ways that would be easy to measure and rash to predict. When I look at statistics such as this for real games, I?generally see measurable differences between strong and weak players. - Dave Hillis Check Out the new free AIM(R) Mail -- Unlimited storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: On 7/9/07, Erik van der Werf <[EMAIL PROTECTED]> wrote: > > On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: > > 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? > > Are you aware that nearly all of these positions will be final positions? > > So I'll repeat my question: why do you need any of this? If you only > need final positions it's probably much better to take them from real > games, and if you actually need middle game positions you will have to > use a different procedure... > > E. > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > Won't the final positions be much more likely to be rejected since they are much more likely to be illegal? Sure, but that does not necessarily matter because there are many more end- than middle-game positions. The reason I brought it up is that I remembered a statement by someone (sorry forgot the source, maybe John or Gunnar remembers) that from all legal positions nearly all can be considered final. Of course one could argue about what makes a position final, obviously not all borders will be nicely closed and generally there will still be some points to be gained, but I think the main idea was that at that point the winner is relatively easy to determine (so one side would normally resign). This also makes sense if you simply look at the expected number of stones on the board. What is your claim about the distribution of the number of stones on the board with this scheme? Simply that for most interesting purposes you will have too many of them on the board. Further, depending on the purpose, one might argue that there are more interesting distributions to sample from (e.g., you could sample from all positions ever played by strong players on KGS). I am hoping to use this method to help generate training data for a learning system that learns certain graph properties of the board that can also be computed deterministically from the board position. I know that might sound crazy, Not to me ;-) but it is working towards the eventual goal of creating feature extractors for Go positions. By learning to map Go positions as an array of stones to Go positions as graphs of strings (instead of just mapping them with a hand coded algorithm) I can take intermediate results in the learner's computation and use it as a feature for another learner. Well, I'm not sure whether this way you will be able to beat hand coded algorithms, but it's certainly interesting to try. In any case I would still think that, to make a strong program, it's better to sample from real games, or maybe do both to see if it makes much difference. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 9, Jul 2007, at 8:37 AM, George Dahl wrote: On 7/9/07, Erik van der Werf <[EMAIL PROTECTED]> wrote: On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: > 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? Are you aware that nearly all of these positions will be final positions? This depends upon the distribution function for w/b/e. The greater the % given to empty the further from "endgame" you will be. So I'll repeat my question: why do you need any of this? If you only need final positions it's probably much better to take them from real games, and if you actually need middle game positions you will have to use a different procedure... E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Won't the final positions be much more likely to be rejected since they are much more likely to be illegal? Probably, but again, it will depend upon the distribution function. What is your claim about the distribution of the number of stones on the board with this scheme? I am hoping to use this method to help generate training data for a learning system that learns certain graph properties of the board that can also be computed deterministically from the board position. I know that might sound crazy, but it is working towards the eventual goal of creating feature extractors for Go positions. By learning to map Go positions as an array of stones to Go positions as graphs of strings (instead of just mapping them with a hand coded algorithm) I can take intermediate results in the learner's computation and use it as a feature for another learner. Have you read Ken Friedenbach's thesis Abstraction Hierarchies: A Model of Perception and Cognition in the Game of Go (UC Santa Cruz 1980)? From what you are saying it sounds like you should. - George Cheers, David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
In that case, you would probably rather have actual Go positions, right? Just grab a bunch of CGOS games (assuming you are studying 9x9) and pick a game and move number at random. On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: On 7/9/07, Erik van der Werf <[EMAIL PROTECTED]> wrote: > On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: > > 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? > > Are you aware that nearly all of these positions will be final positions? > > So I'll repeat my question: why do you need any of this? If you only > need final positions it's probably much better to take them from real > games, and if you actually need middle game positions you will have to > use a different procedure... > > E. > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > Won't the final positions be much more likely to be rejected since they are much more likely to be illegal? What is your claim about the distribution of the number of stones on the board with this scheme? I am hoping to use this method to help generate training data for a learning system that learns certain graph properties of the board that can also be computed deterministically from the board position. I know that might sound crazy, but it is working towards the eventual goal of creating feature extractors for Go positions. By learning to map Go positions as an array of stones to Go positions as graphs of strings (instead of just mapping them with a hand coded algorithm) I can take intermediate results in the learner's computation and use it as a feature for another learner. - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/9/07, Erik van der Werf <[EMAIL PROTECTED]> wrote: On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: > 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? Are you aware that nearly all of these positions will be final positions? So I'll repeat my question: why do you need any of this? If you only need final positions it's probably much better to take them from real games, and if you actually need middle game positions you will have to use a different procedure... E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Won't the final positions be much more likely to be rejected since they are much more likely to be illegal? What is your claim about the distribution of the number of stones on the board with this scheme? I am hoping to use this method to help generate training data for a learning system that learns certain graph properties of the board that can also be computed deterministically from the board position. I know that might sound crazy, but it is working towards the eventual goal of creating feature extractors for Go positions. By learning to map Go positions as an array of stones to Go positions as graphs of strings (instead of just mapping them with a hand coded algorithm) I can take intermediate results in the learner's computation and use it as a feature for another learner. - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
>> 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? > > Are you aware that nearly all of these positions will be final positions? > ...if you actually need middle game positions you will have to > use a different procedure... (The procedure from Paul Pogonyshev is repeated below.) On average it will have 54 stones, 27 empty points. It you want a more middle-game-ish position, increase the probability of an empty point (e.g. empty 0.6, black 0.2, white 0.2). This will also give you a legal position more frequently. Darren 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. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/9/07, George Dahl <[EMAIL PROTECTED]> wrote: 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? Are you aware that nearly all of these positions will be final positions? So I'll repeat my question: why do you need any of this? If you only need final positions it's probably much better to take them from real games, and if you actually need middle game positions you will have to use a different procedure... E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
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" <[EMAIL PROTECTED]> To: Sent: Monday, July 09, 2007 8:55 AM Subject: Re: [computer-go] creating a "random" position On 7/8/07, Paul Pogonyshev <[EMAIL PROTECTED]> 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@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/8/07, Paul Pogonyshev <[EMAIL PROTECTED]> 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@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On Jul 8, 2007, at 2:38 PM, Paul Pogonyshev 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. The check is easy: play all the stones (in any order, e.g., whatever order you have the points indexed) and see if there are any captures. If so, the position isn't legal. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
i'd suggest that you need to consider whether what you really mean is a "position chosen from the uniform distribution of all legal go positions", or if you mean a position from somewhere near the middle game. (i.e. would you be comfortable with a board with 4 stones on it as one of these uniformly chosen boards?). do a single playout from an empty board with a normal distribution centered around whatever you think that the "average number of moves" is for a game to decide when to stop playing out)[1]. this isn't a uniformly chosen board position, but it will very likely accomplish whatever it is that you want to accomplish. s. [1] alternatively, you could have a fixed probability that you "stop playing out" that you check/evaluate after every new move. Yahoo! oneSearch: Finally, mobile search that gives answers, not web links. http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
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: 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@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
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@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
At 21:54 08/07/2007, you wrote: I don't have such algorithm, you can count legal positions like: http://www.lysator.liu.se/~gunnar/legal.pike.txt Modifying it could provide some way select random position atleast for small boards. Ported that for java but not studied much of it yet, intresting anyway. t. Harri This page seems more up to date, and links a paper http://homepages.cwi.nl/~tromp/go/legal.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
Start with an empty board and do a large number (eg 1, depending on how accurate you need the uniformity) of 'operations' on it, where an operation is the following: 1) choose an intersection at random 2) toss a fair coin 3) change the occupation of the intersection according to the following table Old occupation Coin New occupation BlackH White WhiteH Empty EmptyH Black BlackT Empty WhiteT Black EmptyT White 4) If the new position is illegal, undo the change and go to 1) 5) Exit At 21:22 08/07/2007, you 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? - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- This email has been verified as Virus free Virus Protection and more available at http://www.plus.net ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
I don't have such algorithm, you can count legal positions like: http://www.lysator.liu.se/~gunnar/legal.pike.txt Modifying it could provide some way select random position atleast for small boards. Ported that for java but not studied much of it yet, intresting anyway. t. Harri - Original Message - From: "George Dahl" <[EMAIL PROTECTED]> To: "computer-go" Sent: Sunday, July 08, 2007 11:22 PM Subject: [computer-go] creating a "random" position 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? - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] creating a "random" position
On 7/8/07, George Dahl <[EMAIL PROTECTED]> 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? - George All legal positions can be enumerated, so just create a database containing all legal positions and then select one at random. If this does not work for you, e.g., due to insufficient storage, just keep generating random positions (using your special coin) until you hit one that's legal. OC, once you start 'correcting' illegal positions it probably won't be uniform over all legal positions any more, that's why, unless you come up with something clever, you should regenerate the entire position. May I ask why you need any of this? E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] creating a "random" position
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? - George ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
