[computer-go] Analysis of 6x6 Go
Erik van der Werf wrote: > ... > Optimal play on 6x6 under Chinese rules is expected > to give a Black win by 4 points. I want to lay open, why my expectation for 6x6-Go under Chinese rules is +2 for Black. With Leela, I played two games (or game fragments) in analysis mode, starting the machine from fresh in each situation, and stopping analysis after 500,000 nodes. Game 1: Whenever it was Black's turn, komi was set to 3.5 . Whenever it was White's turn, komi was set to 4.5 . The numbers in brackets are the win percentages, as shown by Leela after 500,000 nodes. 1.c3 (39.9) 2.d4 (73.7) 3.c4 (46.0) 4.d3 (77.0) 5.d5 (55.3) 6.e5 (85.6) 7.d2 (42.0) 8.e2 (91.8) 9.e4 (24.5) 10.e3 (96.1) 11.e6(17.6) Resigned on behalf of Black. Game 2: Whenever it was Black's turn, komi was set to 1.5 . Whenever it was White's turn, komi was set to 2.5 . The numbers in brackets are the win percentages, as shown by Leela after 500,000 nodes. 1.c3 (71.5) 2.d4 (55.5) 3.d3 (75.4) 4.c4 (60.2) 5.b3 (64.1) 6.e3 (74.5) 7.e2 (59.2) 8.e4 (68.2) 9.b5 (58.9) 10.b4 (73.3) 11.a4 (53.3) 12.a5 (73.6) 13.a3 (65.2) 14.c5 (72.6) 15.a6 (77.1) 16.f2 (81.6) 17.e1 (81.7) 18.c6 (76.6) 19.a5 (81.4) 20.e5 (94.3) 21.c1 (98.6) So, both sides are optimistic to reach their respecitve goals. Conclusion: From the viewpoint of Leela (at 500,000 nodes), komi=2.0 is in the "habitable zone" for the the starting position of 6x6-Go, whereas komi=4.0 is not. When instead fair komi would be 4, each of the games above should contain errors. Ingo. -- Der GMX SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen! Ideal für Modem und ISDN: http://www.gmx.net/de/go/smartsurfer ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo v.s. Kim rematch
Its exactly what I derived myself, so I understand it :) But it might be difficult for causal reader. My suggestions: - you could add factor graph to ease thinking about it. - [most important] describe what x, sigma_i, and u_i are - [important] you could explicitly state bayes theorem to derive posteriori f(x). - rename f(x) to P(X = x) or density p(x) - you can comment that mean is at the mode (peak) as posterior likelihood is - you should state what RAVE estimator is, and why it is biased - [important] you should state your final estimator that is alternative to RAVE - experimental setup would be useful :) Lukasz 2008/9/23 Jason House <[EMAIL PROTECTED]>: > On Mon, Sep 22, 2008 at 1:21 PM, Łukasz Lew <[EMAIL PROTECTED]> wrote: >> >> Hi, >> >> On Mon, Sep 22, 2008 at 17:58, Jason House <[EMAIL PROTECTED]> >> wrote: >> > On Sep 22, 2008, at 7:59 AM, Magnus Persson <[EMAIL PROTECTED]> >> > wrote: >> > >> > The results of the math are most easilly expressed in terms of inverse >> > variance (iv=1/variance) >> > >> > Combined mean = sum( mean * iv ) >> > Combined iv = sum( iv ) >> > >> > I'll try to do a real write-up if anyone is interested. >> >> I am very interested. :) >> >> Lukasz > > > Attached is a quick write up of what I was talking about with some math. > > PS: Any tips on cleanup and making it a mini publication would be > appreciated. I've never published a paper before. Would this be too small? > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Analysis of 6x6 Go
I think a better way to do this is to self-play a few hundred games with various komi values. The correct komi will be clear from those games. This worked on 7x7 so I assume it would work on 6x6. Of course this cannot be considered a "proof." - Don On Wed, 2008-09-24 at 09:53 +0200, "Ingo Althöfer" wrote: > Erik van der Werf wrote: > > ... > > Optimal play on 6x6 under Chinese rules is expected > > to give a Black win by 4 points. > > I want to lay open, why my expectation for > 6x6-Go under Chinese rules is +2 for Black. > > With Leela, I played two games (or game fragments) > in analysis mode, starting the machine from fresh > in each situation, and stopping analysis after > 500,000 nodes. > > Game 1: > Whenever it was Black's turn, komi was set to 3.5 . > Whenever it was White's turn, komi was set to 4.5 . > The numbers in brackets are the win percentages, as > shown by Leela after 500,000 nodes. > 1.c3 (39.9) 2.d4 (73.7) > 3.c4 (46.0) 4.d3 (77.0) > 5.d5 (55.3) 6.e5 (85.6) > 7.d2 (42.0) 8.e2 (91.8) > 9.e4 (24.5) 10.e3 (96.1) > 11.e6(17.6) > Resigned on behalf of Black. > > Game 2: > Whenever it was Black's turn, komi was set to 1.5 . > Whenever it was White's turn, komi was set to 2.5 . > The numbers in brackets are the win percentages, as > shown by Leela after 500,000 nodes. > 1.c3 (71.5) 2.d4 (55.5) > 3.d3 (75.4) 4.c4 (60.2) > 5.b3 (64.1) 6.e3 (74.5) > 7.e2 (59.2) 8.e4 (68.2) > 9.b5 (58.9) 10.b4 (73.3) > 11.a4 (53.3) 12.a5 (73.6) > 13.a3 (65.2) 14.c5 (72.6) > 15.a6 (77.1) 16.f2 (81.6) > 17.e1 (81.7) 18.c6 (76.6) > 19.a5 (81.4) 20.e5 (94.3) > 21.c1 (98.6) > So, both sides are optimistic to reach their respecitve goals. > > Conclusion: From the viewpoint of Leela (at 500,000 nodes), > komi=2.0 is in the "habitable zone" for the > the starting position of 6x6-Go, whereas komi=4.0 is not. > > When instead fair komi would be 4, each of the games above > should contain errors. > > Ingo. signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Analysis of 6x6 Go
Don Dailey wrote: > I think a better way to do this is to self-play a few hundred games with > various komi values. Do you mean HUMAN self-play or COMPUTER self-/auto-play? When you mean human self-play, I am not sure that this is a safer way for such small boards. > The correct komi will be clear from those games. > This worked on 7x7 Are such 7x7-games documented somewhere, for instance in the internet? > so I assume it would work on 6x6. Of course this > cannot be considered a "proof." Right. What I did is a computer-aided (incomplete) analysis: running repeated Monte-Carlo searches where the komis for both sides differ by 1. Ingo. -- GMX Kostenlose Spiele: Einfach online spielen und Spaß haben mit Pastry Passion! http://games.entertainment.gmx.net/de/entertainment/games/free/puzzle/6169196 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Analysis of 6x6 Go
On Wed, 2008-09-24 at 15:17 +0200, "Ingo Althöfer" wrote: > Don Dailey wrote: > > I think a better way to do this is to self-play a few hundred games with > > various komi values. > > Do you mean HUMAN self-play or COMPUTER self-/auto-play? > > When you mean human self-play, I am not sure that > this is a safer way for such small boards. I am talking about computer self-play on small boards - I think it gives a very reliable way to determine komi (on small boards.) It's of course not a proof, just as your method is not a proof. Somewhere in the archives I posted data based on a lot of games at 7x7 using 9.5 and 8.5 komi. I used Lazarus, not a particularly strong program, but not a weak program either (about 2200 ELO on CGOS.) I don't have the numbers in front of me, but it was ridiculously one-sided. I did not have to set Lazarus to a very high level in order to get almost 100% win results with white using 9.5 komi. When I went to 8.5 komi, Black wins almost every single game. My empirical conclusion is that the correct komi is probably 9.0 for the 7x7 board size. This method I propose doesn't give a proof. However, you can improve your confidence like this: Play (let's say) 1000 games for each komi we are testing, then do a statistical analysis of the results. If for instance it looks like black wins 98% of the games with some komi, we could take a look at the 2% he lost and try to determine if black just made a stupid move, or white happened to find a very difficult move which actually leads to a win regardless of black does.If there is some evidence that white found a very difficult move which changes things, we could do a further analysis based on the same methodology, but from this new starting position. I would like to do this test but Lazarus doesn't support even size boards (although I might be able to fix this without a lot of trouble) and I don't have a copy of Leela although I might convince Gian Carlo to send me a copy.I'm not sure what mogo supports. > > The correct komi will be clear from those games. > > This worked on 7x7 > > Are such 7x7-games documented somewhere, for > instance in the internet? Yes, I posted my results some time ago. This may go back a couple of years or more. I will look for it. > > so I assume it would work on 6x6. Of course this > > cannot be considered a "proof." > > Right. > What I did is a computer-aided (incomplete) analysis: > running repeated Monte-Carlo searches where the komis > for both sides differ by 1. I don't know if even size boards are special, but it seems to me that such small boards should have very high komi's. 4.0 seems pretty low but then I'm really no expert on komi's and I'm a pretty weak player so I'm not in any position to really say. - Don > > Ingo. signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Analysis of 6x6 Go
To satisfy my standards of proof, games would have to be post-analyzed to determine whether either side could have made better moves. Duplicate games would be thrown out; games with inferior play would be tossed. We might not have the resources to completely solve the game, but we could improve the quality of the estimate. At this date, computer-vs-computer matches still tend to have gross errors in the evaluation of seki, nakade, etc. Programs think they are ahead when the real result is the opposite. Terry McIntyre <[EMAIL PROTECTED]> "Go is very hard. The more I learn about it, the less I know." -Jie Li, 9 dan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Analysis of 6x6 Go
On Wed, Sep 24, 2008 at 6:30 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > I don't know if even size boards are special, but it seems to me that > such small boards should have very high komi's. 4.0 seems pretty low > but then I'm really no expert on komi's and I'm a pretty weak player so > I'm not in any position to really say. The center is the best opening move for all small odd size boards. Small even size boards have a lower komi because there is no center point. I'm quite confident that 4.0 is the correct komi for 6x6. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] MoGo v.s. Kim rematch (Jason House's paper)
> "The approach of this paper is to treat all win rate estimations as independent estimators with additive white Gaussian noise. " Have you tried if that works? (As Łukasz Lew wrote "experimental setup would be useful") I guess there may be a flaw in your idea, but I am not a specialist. I will try to explain it. If it wasn't for the fact that the tree is learning, the probability of a playout through a node to win would be constant each time the node is visited. This is, of course, a simplification because the tree does learn, but, at least between playouts that are not very distant in time, it is true. So my argument holds to some (I guess, much) extent. The same applies to the RAVE estimator which is also the result of counting wins (assume P(win|that move) = constant) and dividing by some appropriate sample size. Therefore, these estimators follow a binomial distribution. It does converge to the normal, but with some fundamental caveat: Unlike the normal in which mean an variance are independent, in this case the variance is a function of p. The variance of the binomial = n·p·(1-p) is a _function of p_. Therefore, the variance of the normal that best approximates the distribution of both RAVE and wins/(wins + losses) is the same n·p·(1-p) If this is true, the variance you are measuring from the samples does not contain any information about the precision of the estimators. If someone understands this better, please explain it to the list. Jacques.* * ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Analysis of 6x6 Go
On Wed, 2008-09-24 at 09:42 -0700, terry mcintyre wrote: > To satisfy my standards of proof, games would have to be post-analyzed to > determine whether either side could have made better moves. Duplicate games > would be thrown out; games with inferior play would be tossed. We might not > have the resources to completely solve the game, but we could improve the > quality of the estimate. At this date, computer-vs-computer matches still > tend to have gross errors in the evaluation of seki, nakade, etc. Programs > think they are ahead when the real result is the opposite. Yes, as I mentioned this is not a proof. Neither is post-analysis, but it would at least add some confidence. There is always the possibility that some nakade glitch or something makes it return the wrong results. Also, the possibility that some difficult to find key move masks the true result. It's also possible that a strong go program is more likely to return a false result due to having more idiosyncrasies. On 5x5 and 7x7 it DID return what is believed by humans to be the correct komi, but that doesn't mean it will at any other board size. I like the idea of playing thousands of games and building a tree for later inspection. If anything looks really wrong, it can be further analyzed. - Don > Terry McIntyre <[EMAIL PROTECTED]> > > > "Go is very hard. The more I learn about it, the less I know." -Jie Li, 9 dan > > > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Analysis of 6x6 Go
On Wed, 2008-09-24 at 19:48 +0200, Erik van der Werf wrote: > On Wed, Sep 24, 2008 at 6:30 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > > I don't know if even size boards are special, but it seems to me that > > such small boards should have very high komi's. 4.0 seems pretty low > > but then I'm really no expert on komi's and I'm a pretty weak player so > > I'm not in any position to really say. > > The center is the best opening move for all small odd size boards. > Small even size boards have a lower komi because there is no center > point. > > I'm quite confident that 4.0 is the correct komi for 6x6. I'm sure you know more about this than I do. - Don > > Erik > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo v.s. Kim rematch (Jason House's paper)
On Sep 24, 2008, at 2:40 PM, Jacques Basaldúa <[EMAIL PROTECTED]> wrote: > "The approach of this paper is to treat all win rate estimations as independent estimators with additive white Gaussian noise. " Have you tried if that works? (As Łukasz Lew wrote "experimental set up would be useful") I guess there may be a flaw in your idea, but I am not a specialist. I will try to explain it. I will try to address your concerns in the next revision of the paper. I'll discuss computing the properties of the estimators and add extra rigor using Bayes Theorem (as Łucasz suggested). More comments below. If it wasn't for the fact that the tree is learning, the probability of a playout through a node to win would be constant each time the node is visited. This is, of course, a simplification because the tree does learn, but, at least between playouts that are not very distant in time, it is true. So my argument holds to some (I guess, much) extent. The same applies to the RAVE estimator which is also the result of counting wins (assume P(win|that move) = constant) and dividing by some appropriate sample size. Therefore, these estimators follow a binomial distribution. It does converge to the normal, but with some fundamental caveat: Unlike the normal in which mean an variance are independent, in this case the variance is a function of p. That's all true, and does conflict with my simplistic RAVE bias discussion... The variance of the binomial = n·p·(1-p) is a _function of p_. That's when binary samples are summed. When averaging, it's p•(1-p)/ n. My RAVE discussion essentially used p=1/2. Therefore, the variance of the normal that best approximates the distribution of both RAVE and wins/(wins + losses) is the same n·p·(1-p) See above, it's slightly different. If this is true, the variance you are measuring from the samples does not contain any information about the precision of the estimators. If someone understands this better, please explain it to the list. This will get covered in my next revision. A proper discussion is too much to type with my thumb...___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] MoGo v.s. Kim rematch
This is an interesting idea, but do you have any actual results? If you implement this kind of rave formula do you get a stronger program? David > -Original Message- > From: [EMAIL PROTECTED] [mailto:computer-go- > [EMAIL PROTECTED] On Behalf Of Jason House > Sent: Wednesday, September 24, 2008 4:34 AM > To: computer-go > Subject: Re: [computer-go] MoGo v.s. Kim rematch > > On Tue, 2008-09-23 at 18:08 -0300, Douglas Drumond wrote: > > > Attached is a quick write up of what I was talking about with some > math. > > > > > > PS: Any tips on cleanup and making it a mini publication would be > appreciated. I've never published a paper before. Would this be too > small? > > > > > > Better add an abstract, but what I missed most was bibliography. > > Ask and you shall receive :) > Actually, I spent most of my free time learning Tex/Lyx, so there are > very few changes in this version. I'm out of time for a while, so I > figured I'd just share what I have so far. > > > > > > > > []'s > > > > > > > > > > Douglas Drumond > > - > > Computer Engineering > > FEEC/IC - Unicamp > > ___ > > 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/
