[computer-go] February KGS online computer Go Tournament
I have already posted this once, but one regular reader did not see it, so I am posting again in case some others have missed it. The February 2007 KGS computer Go tournament will be this Sunday, in the Asian evening, European morning and American night, starting at 09:00 UTC and ending at about 12:00 UTC. It will use small boards and fast time limits. There are details at http://www.gokgs.com/tournInfo.jsp?id=264 and at http://www.gokgs.com/tournInfo.jsp?id=265. Registration is now open. To enter, please read and follow the instructions at http://www.weddslist.com/kgs/how/index.html. The rules are given at http://www.weddslist.com/kgs/rules.html. I shall be away from my computer for much of tomorrow, so if you try to enter tomorrow and don't get an immediate response, don't worry. I hope to check my emails around 23:30 UCT on Saturday, and again around 08:00 UCT on Sunday, before play starts. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go Misnomer?
David Doshay wrote: I am a physics guy, and my thesis project was a large MC simulation. The clusters that run SlugGo are usually busy doing MC simulations when not playing Go. In general MC needs to sample according to the proper distribution for the problem. For some problems in quantum mechanics and most in statistical mechanics, the distribution cleanly partitions into percentages of the total, and in those simulations it is easy to do things like generate random numbers and then see what range the random number is in. For Go I could easily argue that sampling random points on the board is clearly the wrong distribution, and those programs using some kind of pattern knowledge are really doing something much closer to MC simulations rather than true random playout. So, I do not think that MC is the misnomer. Thinking that pure random playout is the same as MC is the mistake. Got it. I was thinking Monte Carlo (name based on the gambling city) meant it must be random, but looking into it deeper other statistical sampling methods designed specifically for the problem to reduce the number of simulations can and are often used. Looks like there is some level of confusion about this out on the net too. Wikipedia perhaps needs updating for one. Thanks for clarifying that. Go requires a pretty complex simulation to be run and using more selective moves for the play-outs, if not done very carefully, could have an adverse effect by being too restrictive or sampling the wrong distribution. I'm sure random is not the best distribution also, but at least it is not biased. Are there any methods from other MC research areas to help find good sampling distributions and reduce variance or is Go just wildly different than most domains where MC is used? Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go Misnomer?
I agree with what you say here and I'll try to make my point better. First, my limited experience working with Monte-Carlo simulations involved photons traveling through scattering media. The sequences of moves described in the Mogo paper are pleasantly reminiscent of this. I did not mean to suggest that heavy playouts, incorporating go knowledge, makes the Monte-Carlo description incorrect. Rather, the term is increasingly insufficient as a Go engine description because it lumps together such very different algorithms. The earliest MC engines were extremely simple and easily described. It seems inevitable that someone new to the field will seize on this description, and then combine it with the success of current Monte-Carlo engines, leading to unnecessary confusion. On a tangential note: MC/UCT with light playouts and MC/UCT with heavy playouts are different beasts. If SlugGo's mixture of experts work expands to include MC/UCT, you might want to consider adding one of each. - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Fri, 2 Feb 2007 12:30 AM Subject: Re: [computer-go] Monte-Carlo Go Misnomer? I am a physics guy, and my thesis project was a large MC simulation. The clusters that run SlugGo are usually busy doing MC simulations when not playing Go. In general MC needs to sample according to the proper distribution for the problem. For some problems in quantum mechanics and most in statistical mechanics, the distribution cleanly partitions into percentages of the total, and in those simulations it is easy to do things like generate random numbers and then see what range the random number is in. For Go I could easily argue that sampling random points on the board is clearly the wrong distribution, and those programs using some kind of pattern knowledge are really doing something much closer to MC simulations rather than true random playout. So, I do not think that MC is the misnomer. Thinking that pure random playout is the same as MC is the mistake. Cheers, David On 1, Feb 2007, at 8:33 PM, [EMAIL PROTECTED] wrote: I think of it as a continuum going from light to heavy. Pure random playouts are the lightest. But then you add some rules about filling in eyes, then maybe discourage self-atari,... and the playouts keep getting heavier. I agree with you that the current crop of MC engines are not nearly as go-knowledge naive as the name implies. - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thu, 1 Feb 2007 11:22 PM Subject: [computer-go] Monte-Carlo Go Misnomer? Is MC Go a misnomer for programs in this genre not using simple random playouts and combining with other techniques like pattern matching? Technically, does the general Monte-Carlo method require random or pseudo-random sampling? If so, should we dub a new name for these non-random deep play-out sampling based go programs? Maybe Quasi-MC or Directed Sampling... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Check Out the new free AIM(R) Mail -- 2 GB of 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Check Out the new free AIM(R) Mail -- 2 GB of 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] Monte-Carlo Go Misnomer?
On 2, Feb 2007, at 9:08 AM, [EMAIL PROTECTED] wrote: I agree with what you say here and I'll try to make my point better. First, my limited experience working with Monte-Carlo simulations involved photons traveling through scattering media. The sequences of moves described in the Mogo paper are pleasantly reminiscent of this. I did not mean to suggest that heavy playouts, incorporating go knowledge, makes the Monte-Carlo description incorrect. Rather, the term is increasingly insufficient as a Go engine description because it lumps together such very different algorithms. It is clear that a wide variety of MC attempts are in use and under construction, each with their own way of attempting to construct a proper distribution (and some with no idea that this is even an important part of the procedure). I think that MoGo is being so successful because they have gone the farthest is getting the sampling closest to a distribution appropriate for Go. Unfortunately, there is nothing like a Boltzman function that helps us with Go. The earliest MC engines were extremely simple and easily described. It seems inevitable that someone new to the field will seize on this description, and then combine it with the success of current Monte-Carlo engines, leading to unnecessary confusion. I am not sure what you mean by that. Do you mean that different people will use the term MC in different ways and cause confusion in the minds of third parties? In other words, some people are using the simplest pure random playout (no consideration of distribution at all) and calling that MC while others are trying hard to keep the moves searched Go-like. and thus get different results. Or do you mean that naive programmers will try pure random playout and wonder why the MoGo folks are doing so very much better, not realizing the importance of getting a decent distribution for MC to be effective? On a tangential note: MC/UCT with light playouts and MC/UCT with heavy playouts are different beasts. If SlugGo's mixture of experts work expands to include MC/UCT, you might want to consider adding one of each. I am quite open minded about what kind of experts we add to SlugGo. We are limited more by the time required to implement and integrate than anything else. Integration is a problem that can be quite severe for experts (or move suggesters) with completely different evaluation functions. How does one arbitrate between suggestions that come to you with evaluations of move quality that are on scales that are not co-linear? This point has kept SlugGo as a pure GNU Go dependent engine for longer than we had originally expected. But I am not sure what the value is in what you are calling light playouts. As per the above, it seems to me that light playout is simply ignoring any proper distribution, and thus is just a much more inefficient way to sample. Cheers, David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go Misnomer?
David Doshay wrote: But I am not sure what the value is in what you are calling light playouts. As per the above, it seems to me that light playout is simply ignoring any proper distribution, and thus is just a much more inefficient way to sample. Well maybe Sylvain is willing to answer some related questions of mine. Mogo seems to be much stronger then the rest, so I am more then curious what is more important: 1) A clever random playaout (I assume this is called a proper distribution now?) OR 2) Clever things within the UTC tree and/or above that. (Go knowlegde, selectivity etc.) And: is the answer the same for 9x9 and 19x19 boards? Thanks, Edward de Grijs _ Nieuw: Live Mail. Mis het niet en profiteer direct van de voordelen! http://imagine-windowslive.com/mail/launch/default.aspx?Locale=nl-nl ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go Misnomer?
-Original Message- From: [EMAIL PROTECTED] ... The earliest MC engines were extremely simple and easily described. It seems inevitable that someone new to the field will seize on this description, and then combine it with the success of current Monte-Carlo engines, leading to unnecessary confusion. I am not sure what you mean by that. Do you mean that different people will use the term MC in different ways and cause confusion in the minds of third parties? In other words, some people are using the simplest pure random playout (no consideration ^of distribution at all) and calling that MC while others are trying hard to keep the moves searched Go-like. and thus get different ^results. Or do you mean that naive programmers will try pure random playout and wonder why the MoGo folks are doing so very much better, not realizing the importance of getting a decent distribution for MC to be effective? I mean both. But IMHO the most serious distinction is whether the MC is combined with tree search or not. I'm not embarking on a nomenclature crusade. Just remarking that when people say Monte-Carlo does this or that, it's often ambiguous what algorithm they are actually talking about. On a tangential note: MC/UCT with light playouts and MC/UCT with heavy playouts are different beasts. If SlugGo's mixture of experts work expands to include MC/UCT, you might want to consider adding one of each. I am quite open minded about what kind of experts we add to SlugGo. We are limited more by the time required to implement and integrate than anything else. Integration is a problem that can be quite severe for experts (or move suggesters) with completely different evaluation functions. How does one arbitrate between suggestions that come to you with evaluations of move quality that are on scales that are not co-linear? This point has kept SlugGo as a pure GNU Go dependent engine for longer than we had originally expected. Well this is a common problem when combining heterogeneous experts and there is no shortage of approaches, just as you point out, a shortage of time and energy to experiment with them. One very simple approach that sometimes works in some domains is to gather a number of experts, have them rank the choices and combine at that level. In this case, it's usually good to have experts that are qualitatively different. But I am not sure what the value is in what you are calling light playouts. As per the above, it seems to me that light playout is simply ignoring any proper distribution, and thus is just a much more inefficient way to sample. AntIgo with heavy playouts is about 300 ELO points stronger on CGOS than AntIgo with light playouts. If you're going to choose just one, I don't think it's a close call. - Dave Hillis Check Out the new free AIM(R) Mail -- 2 GB of 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] Monte-Carlo Go Misnomer?
[EMAIL PROTECTED] wrote: -Original Message- From: [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] ... The earliest MC engines were extremely simple and easily described. It seems inevitable that someone new to the field will seize on this description, and then combine it with the success of current Monte-Carlo engines, leading to unnecessary confusion. I am not sure what you mean by that. Do you mean that different people will use the term MC in different ways and cause confusion in the minds of third parties? In other words, some people are using the simplest pure random playout (no consideration ^of distribution at all) and calling that MC while others are trying hard to keep the moves searched Go-like. and thus get different ^results. Or do you mean that naive programmers will try pure random playout and wonder why the MoGo folks are doing so very much better, not realizing the importance of getting a decent distribution for MC to be effective? I mean both. But IMHO the most serious distinction is whether the MC is combined with tree search or not. I'm not embarking on a nomenclature crusade. Just remarking that when people say Monte-Carlo does this or that, it's often ambiguous what algorithm they are actually talking about. This is the condition that led me to first think of and submit the original question. Sometimes you can't tell what people are talking about when they mention MC go. So does anyone have any thoughts on the follow-up comment and question? That selective move playouts could have adverse effects, and that random is probably not very good but not biased. Also, what MC distribution techniques (from general or specific research areas) might be used to help create better sampling distributions and reduce variance, improving overall results? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/