Re: [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 02:41 -0600, Nick Apperson wrote: I am not trying to say that you don't know what you are talking about, but how are you so sure that we must be on the linear part of the curve? Based on what you said, I estimate your ideal (non empirical) formula to be something like the following: S = P * (1 - e^-kt) where S is skill level and P is perfect play and k is some constant specific to the game. In fact this is an ideal formula that should apply given the reasonable assumption that the chance of reading one unit of skill is proportional to the amount of time taken and the amount left to be seen. This makes sense assuming a very specific distribution of the difficulties of different items that can be seen. That distrobution would have to have all units capable of being seen as equally likely to be seen. I think this could be a good theoretical model. Anyway, I would like to see you make more specific claims with formula and justifications for them. Vague statements about linear relationships that taper off and how we are clearly not anywhere near the top help nobody. You seem to know a lot about this. I would appreciate it if you would share your reasoning. You seem pretty skeptical of intuition. So, what is the reason you believe these things about go? Here is why I feel as I do and where I think the burden of proof is: All computer games of perfect information that I am aware of follow this curve. Chess, checkers, Armimaa, Othello, Go and others. So it seems to have nothing to do with the branching factor of the game. This curve is shown to also be true (even more-so) in HUMAN play, at least in Chess and anywhere from a fraction of a second per move to postal chess. From a perfectly logical point of view, what is the most reasonable conclusion to come to about this? Furthermore, I have anecdotal evidence (which you should always be skeptical of but I present nonetheless) that strong human players are not good judges in these matters because their ego's are involved. In Chess, there were some more humble players who understood the curve right away but they were the minority. In short, strong players will generally take the point of view that their game is not subject to mere computation, but to skill which only they possess. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
I second Mark Boon's comment. On 1/26/07, Mark Boon [EMAIL PROTECTED] wrote: Am I the only one who got tired of this rather pointless discussion a hundred messages ago? I also can't help feeling that the tone of the discussion tends to get such that it can easily be mistaken for lack of respect for each other. Can we get back to more mundane issues, like how MC scales to 13x13 and possibly later to 19x19? Or what other ways we could use connection-machine like hardware? Anything, really. Just a thought. Mark ___ 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: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 13:38 +, ivan dubois wrote: However, if you take for example a computer programm that does straight UCT (global UCT, with no sub-areas), then i believe it can not scale well when board size increases. Because the branching would factor increase proportinaly to the size of the board, and therefore the computation time for an equivalent search deapth will increase exponentialy. Any thoughts ? This can be tested directly. In my own experiments 19x19 improves very rapidly in UCT with each doubling of the number of play-outs. Of course someone will say, yes, but that won't continue and I will have no way to refute their intuition. I am presenting real evidence that it scales at least as far as I can test, and nobody has presented any evidence whatsoever to the contrary other than gut feelings. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
- Original Message From: Don Dailey [EMAIL PROTECTED] This can be tested directly. In my own experiments 19x19 improves very rapidly in UCT with each doubling of the number of play-outs. May I ask the range of number of playouts tested? Have you considered taking up David Doshay's offer and running some multi-computer simulations? With 72 processors whirling away for a month or so, one could have a lot of interesting data. Btw, how are your experiments with D coming along? Is it becoming competitive, performance-wise, with C or C++? It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 10:22 -0800, terry mcintyre wrote: - Original Message From: Don Dailey [EMAIL PROTECTED] This can be tested directly. In my own experiments 19x19 improves very rapidly in UCT with each doubling of the number of play-outs. May I ask the range of number of playouts tested? Have you considered taking up David Doshay's offer and running some multi-computer simulations? With 72 processors whirling away for a month or so, one could have a lot of interesting data. Yes, David agreed to let me use his system several weeks ago but I have procrastinated due to many other projects and my work schedule not to mention the time I have wasted posting on this group. Part of my procrastination is that I'm not sure how to make UCT scale to a large number of CPU's.I am an expert in scaling alpha/beta to a large numbers of processors (I did this with Socrates on 1836 processors a few years ago) but it's different with UCT which is inherently serial. I am also considering doing a public huge UCT scalability study with 19x19 go. My idea is for several programs to set their program up to a fixed level (n play-outs) and set up a CGOS server with really long time controls.But I want to just get a normal 19x19 server running first. Btw, how are your experiments with D coming along? Is it becoming competitive, performance-wise, with C or C++? D is a lovely language but the current compilers generate code that is too slow for my taste.I think this situation will improve in the future and I will keep my eye on D. There is no reason I am aware of that D cannot run as fast as C. - Don __ We won't tell. Get more on shows you hate to love (and love to hate): Yahoo! TV's Guilty Pleasures list. ___ 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 : Re : [computer-go] an idea... computer go program's rank vs time
You missunderstood my point. However, I admit it was not clear. What i wanted to say is this : Given a fixed amount of time, strength of monte-carlo algorithm will decrease exponentialy when boardsize increases. It does not mean that monte-carlo does not scale well with time on 19*19. Of course, it all depends on the referential you use to measure strength. By the way, it is not a critisism towards UCT : actualy I do think monte-carlo is the key to build realy strong programs. I just wanted to state that scaling with computation-time is not the only thing that matters. Scaling with board size matters too. It was not another criticism towards you opinion either. - Message d'origine De : Don Dailey [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Vendredi, 26 Janvier 2007, 19h05mn 40s Objet : Re: Re : [computer-go] an idea... computer go program's rank vs time On Fri, 2007-01-26 at 13:38 +, ivan dubois wrote: However, if you take for example a computer programm that does straight UCT (global UCT, with no sub-areas), then i believe it can not scale well when board size increases. Because the branching would factor increase proportinaly to the size of the board, and therefore the computation time for an equivalent search deapth will increase exponentialy. Any thoughts ? This can be tested directly. In my own experiments 19x19 improves very rapidly in UCT with each doubling of the number of play-outs. Of course someone will say, yes, but that won't continue and I will have no way to refute their intuition. I am presenting real evidence that it scales at least as far as I can test, and nobody has presented any evidence whatsoever to the contrary other than gut feelings. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : Re : [computer-go] an idea... computer go program's rank vs time
I see what you are saying. Yes, I agree with you that the strength of these programs will decrease exponentially as board sizes increase. By the way, I haven't been offended by any of these messages and I hope I haven't offended anyone either. This is a very interesting conversation to me and I welcome your thoughts and even if I sound too strong I mean no disrespect to anyone. - Don On Fri, 2007-01-26 at 19:05 +, ivan dubois wrote: You missunderstood my point. However, I admit it was not clear. What i wanted to say is this : Given a fixed amount of time, strength of monte-carlo algorithm will decrease exponentialy when boardsize increases. It does not mean that monte-carlo does not scale well with time on 19*19. Of course, it all depends on the referential you use to measure strength. By the way, it is not a critisism towards UCT : actualy I do think monte-carlo is the key to build realy strong programs. I just wanted to state that scaling with computation-time is not the only thing that matters. Scaling with board size matters too. It was not another criticism towards you opinion either. - Message d'origine De : Don Dailey [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Vendredi, 26 Janvier 2007, 19h05mn 40s Objet : Re: Re : [computer-go] an idea... computer go program's rank vs time On Fri, 2007-01-26 at 13:38 +, ivan dubois wrote: However, if you take for example a computer programm that does straight UCT (global UCT, with no sub-areas), then i believe it can not scale well when board size increases. Because the branching would factor increase proportinaly to the size of the board, and therefore the computation time for an equivalent search deapth will increase exponentialy. Any thoughts ? This can be tested directly. In my own experiments 19x19 improves very rapidly in UCT with each doubling of the number of play-outs. Of course someone will say, yes, but that won't continue and I will have no way to refute their intuition. I am presenting real evidence that it scales at least as far as I can test, and nobody has presented any evidence whatsoever to the contrary other than gut feelings. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.yahoo.com ___ 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: Re : [computer-go] an idea... computer go program's rank vs time
- Original Message From: Don Dailey [EMAIL PROTECTED] May I ask the range of number of playouts tested? I'm still curious about this question? Part of my procrastination [ about using 72 processors ] is that I'm not sure how to make UCT scale to a large number of CPU's. I am an expert in scaling alpha/beta to a large numbers of processors (I did this with Socrates on 1836 processors a few years ago) but it's different with UCT which is inherently serial. I surely appreciate the difficulties in adapting algorithms to multiple processors - I may be rusty, but some years ago I worked on Neuralware and multiple transputers, 860s, and so forth. It gets a little hairy! Hasn't Mogo been parallelized to 4 processors? Can this be extended to larger numbers? Due to the problems with heat dissipation at higher clock cycles, we'll probably be working with large numbers of processors per chip in the future, rather than Terahertz uniprocessors. Have a burning question? Go to www.Answers.yahoo.com and get answers from real people who know.___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
I personally would love to see more experimental results and less feelings and intuitions on this list. On 1/26/07, Don Dailey [EMAIL PROTECTED] wrote: On Fri, 2007-01-26 at 11:32 -0800, terry mcintyre wrote: - Original Message From: Don Dailey [EMAIL PROTECTED] May I ask the range of number of playouts tested? I'm still curious about this question? I think I started at 64 play-outs, and kept doubling the number of play-outs to some large number where it took an hour to play a single game. I don't currently have the data, but I am willing to reproduce the experiment. Other MC guys can verify it. I'll set it up on a slow computer I have free and I'll start at 64 simulations on a 19x19 board.I'll play 200 games in pairs, 64 vs 128, 128 vs 256, etc. - Don Part of my procrastination [ about using 72 processors ] is that I'm not sure how to make UCT scale to a large number of CPU's. I am an expert in scaling alpha/beta to a large numbers of processors (I did this with Socrates on 1836 processors a few years ago) but it's different with UCT which is inherently serial. I surely appreciate the difficulties in adapting algorithms to multiple processors - I may be rusty, but some years ago I worked on Neuralware and multiple transputers, 860s, and so forth. It gets a little hairy! Hasn't Mogo been parallelized to 4 processors? Can this be extended to larger numbers? Due to the problems with heat dissipation at higher clock cycles, we'll probably be working with large numbers of processors per chip in the future, rather than Terahertz uniprocessors. __ Any questions? Get answers on any topic at Yahoo! Answers. Try it now. ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 14:43 -0500, Don Dailey wrote: I don't currently have the data, but I am willing to reproduce the experiment. Other MC guys can verify it. I'll set it up on a slow computer I have free and I'll start at 64 simulations on a 19x19 board.I'll play 200 games in pairs, 64 vs 128, 128 vs 256, etc. Ok, I am starting the new study and will report the results after each 200 game match starting at 1k simulations. The way my program works is that level 1 does 1024 simulations, and each new level adds 1024 simulations, so I have to start at 1024 instead of 64. 1024 will be pretty weak but I'll keep building up as I go. Maybe I will get someone to help me with other computers. I have an autotester than manages the games and utilities that report statistics on the results. This is my UCT program, not my older Botnoid series. Two games have already been played and the score is tied, level 1 vs level 2 (1024 sims vs 2048 sims.) - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 14:47 -0500, Chris Fant wrote: I personally would love to see more experimental results and less feelings and intuitions on this list. I agree. I will post my data as I go. Just for reference, this is the the Lazarus program that is currently rated at 1807 on CGOS but running 19x19 games. Current results: Rating Win perc Tot Gms Ave Time Player --- --- -- 1600.075.0004 234.8 0002(1024 playouts) 1400.025.0004 117.5 0001(2048 playouts) Black wins:1 25.0 % White wins:3 75.0 % - Don On 1/26/07, Don Dailey [EMAIL PROTECTED] wrote: On Fri, 2007-01-26 at 11:32 -0800, terry mcintyre wrote: - Original Message From: Don Dailey [EMAIL PROTECTED] May I ask the range of number of playouts tested? I'm still curious about this question? I think I started at 64 play-outs, and kept doubling the number of play-outs to some large number where it took an hour to play a single game. I don't currently have the data, but I am willing to reproduce the experiment. Other MC guys can verify it. I'll set it up on a slow computer I have free and I'll start at 64 simulations on a 19x19 board.I'll play 200 games in pairs, 64 vs 128, 128 vs 256, etc. - Don Part of my procrastination [ about using 72 processors ] is that I'm not sure how to make UCT scale to a large number of CPU's. I am an expert in scaling alpha/beta to a large numbers of processors (I did this with Socrates on 1836 processors a few years ago) but it's different with UCT which is inherently serial. I surely appreciate the difficulties in adapting algorithms to multiple processors - I may be rusty, but some years ago I worked on Neuralware and multiple transputers, 860s, and so forth. It gets a little hairy! Hasn't Mogo been parallelized to 4 processors? Can this be extended to larger numbers? Due to the problems with heat dissipation at higher clock cycles, we'll probably be working with large numbers of processors per chip in the future, rather than Terahertz uniprocessors. __ Any questions? Get answers on any topic at Yahoo! Answers. Try it now. ___ 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/ ___ 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] an idea... computer go program's rank vs time
[EMAIL PROTECTED] wrote: Yes. Don's scalability argument states that ELO gain is proportional to time doubling. For me scalable use of time implies that time translates into depth. The extra depth is: m - m0 = log(2)/log(b). So if the ELO gain for time doubling in Chess equals 100 over a wide time scale and if Go has a 10 times larger branching factor than Chess, then the ELO gain for time doubling in Go would equal 100/log (10) = 43 (everything else assumed equal). I'm not sure i agree with Don, but i just want so say that if he is right, than mathematically he is also right with a larger branching factor. Yes, this seems obvious and to me it appears you are begging the question - presupposing the conclusion. You said it yourself in the last sentence: _if_ he is right then mathematically it follows for the larger branching factor. Can't argue with that. I was trying to compare a different relationship related to the branching factor and other characteristics of Go to capacity of human logical reasoning and thinking. The idea being to suggest a possible explanation for why Go may be qualitatively different than Chess in this regard. So I'll attempt to put the relationship I was trying to describe with words into a mathematical model and then further describe my thought process. Let b = branching factor Let f = Effective avg. pruning factor(0-1), thus b*f is an effective avg branching factor Let t = length of thinking time Let p = maximum ply or depth under consideration Let n = avg. number of positions a player can effectively evaluate in one unit of time (either explicitly or otherwise using whatever reading/learning/patterns/etc. to his avail) Both f and n can be considered idealized measures of skill and ability of the player. Let r = rough approximation (as this is a simplification/idealization) of the ratio of coverage of the game tree to depth p and defined as: r(b,f,t,p,n) = n*t/(b*f)^p for all n*t=(b*f)^p, otherwise r=1.0 Obviously if you double the time and keep the depth constant the ratio of coverage goes up in a linear relationship for all b. But as time is increased, p is increasing presumably. Now the graph of r is not linear and higher b results in a faster rate of decline. Now I understand that this doesn't necessarily have anything to do with strength ratings. So that is some background for the concept. Bear with me if this borders on the obvious for a while. So we all know that Go evaluation is very hard (for computers, but also for humans). You can't prune if you can't evaluate in some sense however (not with certainty anyway). You can't evaluate without understanding shapes/life and/or reading. In chess these things are arguably quite a bit simpler. So with chess with a much smaller starting branching factor and simpler more left-brain devices for pruning and evaluating the cost/benefit of looking deeper tends to have reasonable payback at relatively large depths. Contrast with Go, starting with a much higher branching factor and lacking left brain (logical/reasoning) methods for pruning and evaluating, depth tends to create more confusion and quickly exceeds the brain's ability to keep track of exploding variations. However, as you learn from experience you can recognize patterns for the different concepts and balance with analysis to effectively prune and evaluate position potential and group interaction and then you can go deeper with some confidence level in your understanding of the status of the game. Learning these skills while thinking about a particular game's next move is not generally practical and even if possible would presumably require enormous extra time. Yet without this ability you are left with a massively rapid expanding game tree to search. Finally this is why I think it may be the case that doubling human thinking time for Go might not produce linear improvements. Back to the model, we could add another variable perhaps: Let c = reliability/certainty factor for the pruning and evaluations done during the search. r*c might have some meaning... And again I am not saying this is black and white. Chess and Go share these same characteristics to different degrees. I believe Chess is more logical/analytical and Go is more balanced analytical - intuitive/holistic (yin-yang thing), thus each yields to both approaches in different situations and ways. But just because a rule of thumb holds for Chess doesn't mean it does for Go. Of course I could be wrong, but I was just trying to introduce reasonable doubt, since Don always seems so sure of himself ;-) Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Hi Matt, On 1/25/07, Matt Gokey [EMAIL PROTECTED] wrote: But just because a rule of thumb holds for Chess doesn't mean it does for Go. Of course I could be wrong, but I was just trying to introduce reasonable doubt, since Don always seems so sure of himself ;-) If I may venture trying to rephrase your arguments, do you mean that since difficulty grows exponentially there may be a qualitative leap between chess and go? Comparing chess and go is difficult, but I think this effect can be seen between 9x9 and 19x19 go too: the two games are quite different, because in 9x9 there is practically no strategic element and this element brings a whole new dimension to the game. Or did I misunderstand you? best regards, Vlad ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
On Thu, 2007-01-25 at 03:27 -0600, Matt Gokey wrote: Learning these skills while thinking about a particular game's next move is not generally practical and even if possible would presumably require enormous extra time. Yet without this ability you are left with a massively rapid expanding game tree to search. Finally this is why I think it may be the case that doubling human thinking time for Go might not produce linear improvements. You are still missing the point. What you are describing looks great on paper, but that's now how the extra time works. Even if you are given 10X more time, the benefit will come from not from suddenly being able to grasp master level concepts, but from repairing the little mundane problems that are just within your reach. And it will only effect a small number of moves. Most of the moves will be exactly as you say, confusing, and you will not be able to improve them (and I think this is the partly the source of what I consider the misconception some of us are having.) The other source of the misconception you also touched on. You mentioned enormous extra time, which is correct. It DOES INDEED require enormous extra time, even in computer chess to make anything more than a modest improvement.The reason you just can't imagine that a lot of extra time will help you play a better move is because most of the time it won't! Your intuition is correct but your conclusion is incorrect. The improvement will come only from little mundane improvements of a very small number of moves - but that is enough to make your level of play go up a bit. Please note that for weak players, a LOT of moves need to be improved, and for strong players only a few need to be improved. But the way this works is that the stronger you get, the more impact improving just a few moves makes because your opponent is more likely to take advantage of your mistakes. Someone once did a computer chess experiment with really long and deep searches and they studied how often computers changed their minds when making moves. As it turns out, the rate of change (per ply or per doubling) tapers off as you go deeper and deeper.And yet the strength improvement is almost the same for each doubling. The computers follow your cognitive intuition that you posted about, they can think for an enormous amount of time and still not improve on the move.Improvement isn't about making ALL the moves better, only a few. It's almost always possible, given more time, to find some improvements in a few of your moves and this is what makes you play better. Since it takes geometrically increasing amounts of time to make the same strength jump, there is no chance you will play enormously better given any practical amount of time, which probably matches both your intuition on this, and the actual facts. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Go, being a matter of efficiency over one's opponent, may be even more susceptible to improvement via many small improvements over many moves than is chess. As long as you don't leave weak shapes behind, picking up a point here, a point there at a slightly faster rate than your opponent will give you the game. Expecting? Get great news right away with email Auto-Check. Try the Yahoo! Mail Beta. http://advision.webevents.yahoo.com/mailbeta/newmail_tools.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
On Thu, 2007-01-25 at 08:23 -0800, terry mcintyre wrote: Go, being a matter of efficiency over one's opponent, may be even more susceptible to improvement via many small improvements over many moves than is chess. As long as you don't leave weak shapes behind, picking up a point here, a point there at a slightly faster rate than your opponent will give you the game. And this indeed seems to be the case. When I was testing 19x19 cgos with Steve, the performance rating between versions that did 2x simple MC play-outs was enormous, over 300 points per doubling. That rate of improvement tapered off with higher levels because the simple MC algorithm is strictly limited in scalability. I also had a difficult time producing a player that was less than 200 ELO stronger than a random player. Even a single play-out, which seems hardly enough to discriminate between moves, is enormously stronger than a random player.It was pretty much like this: ASSUME computer is black 1. play 1 random game. 2. If black wins, play one of the first N black moves in the play-out (all-as-first, for me it's some-as-first.) 3. If white wins, play one of the black move NOT in the play-out. 4. Crush a random player! Of course 2 play-outs was incredibly effective against against a 1 play-out player, 4 beats 2, 8 beats 4 and the tapering effect is very gradual up to the level we were able to test - where the computer was not able to play a game without losing on time. This was despite the fact that the algorithm is limited. There is a point in the 9x9 version where it hits the wall. For Botnoid (AnchorMan) 5000 simulations is almost as good as it gets and it plays very quickly at this level. This is not a refutation of the principle, it's just that AnchorMan has a very un-scalable algorithm. 1 ply monte carlo cannot discover much of anything even if given infinite number of play-outs but this changes completely when a tree is added such as in UCT. - Don __ Get your own web address. Have a HUGE year through Yahoo! Small Business. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Terry, Where's the notion that through small increments, there is no reasonable path from a house 3 bedroom house to a 10 story building? Isn't the consistency of the assumption set around how a house is designed and built fundamentally (as in pardigm-ally) different than that of how designing and building a 10 story building? And doesn't the assumption set for the 10 story building have to be mostly abandoned when creating the design and building a 100 story building? Isn't there's a point where the shift from one complex infrastructure to another results in a setback as nuanced assumptions must be abandoned when their lower dependent assumptions have to be reorganized or even replaced? Jim - Original Message From: terry mcintyre [EMAIL PROTECTED] To: [EMAIL PROTECTED]; computer-go computer-go@computer-go.org Sent: Thursday, January 25, 2007 10:23:13 AM Subject: Re: [computer-go] an idea... computer go program's rank vs time Go, being a matter of efficiency over one's opponent, may be even more susceptible to improvement via many small improvements over many moves than is chess. As long as you don't leave weak shapes behind, picking up a point here, a point there at a slightly faster rate than your opponent will give you the game. Get your own web address. Have a HUGE year through Yahoo! Small Business.___ 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] an idea... computer go program's rank vs time
On 1/25/07, Don Dailey [EMAIL PROTECTED] wrote: I also had a difficult time producing a player that was less than 200 ELO stronger than a random player. Even a single play-out, which seems hardly enough to discriminate between moves, is enormously stronger than a random player.It was pretty much like this: ASSUME computer is black 0. with probably P, play a random move (using the same selection methodology as the random player) 1. play 1 random game. 2. If black wins, play one of the first N black moves in the play-out (all-as-first, for me it's some-as-first.) 3. If white wins, play one of the black move NOT in the play-out. 4. Crush a random player! Surely by varying P, you can get a player arbitarily close to the random player? Or am I missing something? cheers stuart ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
ofcourse you are correct, P = 1.0 is just the random player. Obviously the ELO as a function of P is going to be continuous. So, being really close to P=1.0 will make for a player that is only very slightly better than random. I think it is also interesting to consider a player worse than random. Take your 1 trial MC program and instead of playing only moves than win, play only moves that lose. My guess is that the skill difference between this program and random would be greater than between random and 1 trial MC, but I would be interested to see a trial of this. On 1/25/07, Stuart A. Yeates [EMAIL PROTECTED] wrote: On 1/25/07, Don Dailey [EMAIL PROTECTED] wrote: I also had a difficult time producing a player that was less than 200 ELO stronger than a random player. Even a single play-out, which seems hardly enough to discriminate between moves, is enormously stronger than a random player.It was pretty much like this: ASSUME computer is black 0. with probably P, play a random move (using the same selection methodology as the random player) 1. play 1 random game. 2. If black wins, play one of the first N black moves in the play-out (all-as-first, for me it's some-as-first.) 3. If white wins, play one of the black move NOT in the play-out. 4. Crush a random player! Surely by varying P, you can get a player arbitarily close to the random player? Or am I missing something? cheers stuart ___ 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] an idea... computer go program's rank vs time
I am writing my program to scale to n processors because I think that is the direction hardware is headed. However, I think clever programming will do more than computational power with go. On 1/25/07, terry mcintyre [EMAIL PROTECTED] wrote: So what would it take to get corporate sponsorship of the sort which drove the chess computing field? Where is the Go equivalent of Deep Thought? Near as I can tell, David Doshay's Sluggo is the only large-scale parallel effort. Mogo uses at most 4 CPUs. What might be accomplished with one of the top500.org clusters of hundreds or thousands of CPUs? -- Expecting? Get great news right away with email Auto-Check.http://us.rd.yahoo.com/evt=49982/*http://advision.webevents.yahoo.com/mailbeta/newmail_tools.html Try the Yahoo! Mail Beta.http://us.rd.yahoo.com/evt=49982/*http://advision.webevents.yahoo.com/mailbeta/newmail_tools.html ___ 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] an idea... computer go program's rank vs time
On Thu, 2007-01-25 at 12:17 -0600, Nick Apperson wrote: I am writing my program to scale to n processors because I think that is the direction hardware is headed. However, I think clever programming will do more than computational power with go. I take the point of view that clever programming IS more computational power. I have never advocated WASTING power. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
That was just a statement, I have never advocated WASTING power to help make it clear that I believe in squeezing the most out of each cpu cycles, not just making some algorithm as fast as it can be but also using the best algorithms. I did not take your post as some kind of contradictory statement. - Don On Thu, 2007-01-25 at 14:27 -0600, Nick Apperson wrote: I don't rememeber citing you as saying that. My however was in reference to myself. On 1/25/07, Don Dailey [EMAIL PROTECTED] wrote: On Thu, 2007-01-25 at 12:17 -0600, Nick Apperson wrote: I am writing my program to scale to n processors because I think that is the direction hardware is headed. However, I think clever programming will do more than computational power with go. I take the point of view that clever programming IS more computational power. I have never advocated WASTING power. - Don ___ 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] an idea... computer go program's rank vs time
Vlad Dumitrescu wrote: Hi Matt, On 1/25/07, Matt Gokey [EMAIL PROTECTED] wrote: But just because a rule of thumb holds for Chess doesn't mean it does for Go. Of course I could be wrong, but I was just trying to introduce reasonable doubt, since Don always seems so sure of himself ;-) If I may venture trying to rephrase your arguments, do you mean that since difficulty grows exponentially there may be a qualitative leap between chess and go? Not really. I merely am raising a question about the assertion that human doubling of thinking time results in _linear_ improvements. I am not claiming that there is no improvement - never have. I am not claiming that every turn must produce better results to improve overall play - never have. However I am trying to explain a rationale for the possibility that improvements may not be linear based on the nature of Go. Comparing chess and go is difficult, but I think this effect can be seen between 9x9 and 19x19 go too: the two games are quite different, because in 9x9 there is practically no strategic element and this element brings a whole new dimension to the game. Yes it is difficult to compare. Don ventured into these waters by asserting that a relationship fairly well established and reliable in Chess holds for Go. As for between 9x9 and 19x19 Go, obviously 19x19 is harder and games are much more strategically and tactically interesting, but I think a similar relationship between chess and 9x9 Go probably holds, just differs by degree. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
let's step back a bit and define terms. How do we define a linear improvement in Go? Would that be a linear increase in ELO points, or what? Terry McIntyre Want to start your own business? Learn how on Yahoo! Small Business. http://smallbusiness.yahoo.com/r-index___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
On Thu, 2007-01-25 at 20:16 -0600, Matt Gokey wrote: Don Dailey wrote: You are still missing the point. I can say the same of you. I merely am raising a question about the assertion that doubling of _human_ thinking time results in _linear_ improvements. I am not claiming that there is no improvement - never have. I am not claiming that every turn must produce better results to improve overall play - never have. However I am trying to explain a rationale for the possibility that improvements may not be linear based on the nature of Go. It's possible, but I think my curve (it is a curve, it gradually tapers off as you get closer to perfection which is an obvious limit) holds in all non-trivial games of perfect information. The curve may have a different shape or slope but it's there. It's already easy to produce in computer go despite a reluctance by many (not you of course) to admit it. My sense is that many on this group want to believe that we just happen to be at the top of the curve but that it immediately falls off. There is no rational reason to believe that other than superstition. What you are describing looks great on paper, but that's now how the extra time works. Even if you are given 10X more time, the benefit will come from not from suddenly being able to grasp master level concepts, but from repairing the little mundane problems that are just within your reach. How do you know this? Improvements could come from many other different sources. I thought I was being generous. I do believe 10 or 20x is enough time to produce a lot of mini-conceptual breakthroughs.But I know from my experience in game programming that most of the improvement comes from fixing all the misconceptions that 1 less ply couldn't see. When I was young and naive about computer chess, I couldn't understand why going from 5 to 6 ply was almost as good as going from 3 to 4 ply, but it's clearly the case.A lot of very strong players never got over this type of incorrect thinking - they only focused on what a computer COULDN'T do with only 1 extra ply (or double the time.) And it will only effect a small number of moves. Most of the moves will be exactly as you say, confusing, and you will not be able to improve them (and I think this is the partly the source of what I consider the misconception some of us are having.) I don't have this misconception. I basically agree with this and don't think I said anything explicitly contradictory to this. That's why I used the terminology some of us, I would have said you are having if I thought it was your stance. The other source of the misconception you also touched on. You mentioned enormous extra time, which is correct. It DOES INDEED require enormous extra time, even in computer chess to make anything more than a modest improvement.The reason you just can't imagine that a lot of extra time will help you play a better move is because most of the time it won't! Your intuition is correct but your conclusion is incorrect. You are putting words into my posts. As I said several times already I am not claiming extra time won't help improve play. Of course it will. You are not listening to my conclusion. Step back and re-read my posts. I don't claim my writing to be of super clarity and I might not be explaining myself well enough, but why not try to keep an open mind and not make assumptions about things I didn't write. To an extent I admit that I was putting words in your mouth. I was in the mode where I was responding to the group as a whole even though I was really addressing you more specifically.You never said, you can't imagine that a lot of extra time would help so I apologize for being so loose with this. The improvement will come only from little mundane improvements of a very small number of moves - but that is enough to make your level of play go up a bit. Yes and improvement may also come from other insights as well. I agree, but for a modest amount of extra time, to be frank, you will be making far less errors and still playing pretty much the same perhaps with a few exceptions. With a LOT of extra time I believe you will be having insights and really finding a few nice moves. I believe go is rich in opportunities to do this, and I completely disagree with those that feel the game is closed beyond what you can quickly recognize and there is no scope to discover interesting things because it's just too complicated and confusing. Please note that for weak players, a LOT of moves need to be improved, and for strong players only a few need to be improved. But the way this works is that the stronger you get, the more impact improving just a few moves makes because your opponent is more likely to take advantage of your mistakes. Sounds reasonable. Someone once did a computer chess experiment with
Re: [computer-go] an idea... computer go program's rank vs time
On Thu, 2007-01-25 at 21:44 -0600, Matt Gokey wrote: Let me expand on this. Perhaps due to the nature of Go and the human style learning needed to judge some moves and positions to be advantageous many (like 20-60+) stones out with possible interplay between groups (a tree which cannot possibly be read excluding ladders), ranking gained by experience and training our super massively parallel pattern matching system out paces time doubling based improvements. So for a hypothetical example only, let's say for a player with an arbitrarily chosen rating of 1000, a time doubling from 30 minutes to 1 hour per game increases strength by 100 points. Another time doubling may only increase by 75 points and another by 40 and then another by 20. For a player with a different rating a doubling might increase by 200, then 150, then 90. Maybe its not a predictable curve even - maybe there are plateaus or steps or hills and valleys. That's the thought - due to the nature of go the increases might not be linear nor consistent between players of different strengths. I hesitate to venture what others believe, but it seems based on Ray's and Mark's and others' posts that there is a gut feeling amoung go players that this may be the case. Perhaps they care to comment further. I think this is a case where our gut feelings are not particularly reliable.I've already discussed several reasons why we might be led falsely to believe our strength is pretty much fixed, but I'll just summarize here: 1. How we perceive time. 2. The ranking system which puts us in a box. 3. Undo worship of stronger players. 4. Broken cognitive model of what it takes to play a better game. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
On Thu, 2007-01-25 at 21:40 -0600, Matt Gokey wrote: terry mcintyre wrote: let's step back a bit and define terms. How do we define a linear improvement in Go? Don can correct me if I'm wrong, The hypothesis is: For any player rating each doubling of thinking time creates a rating increase by a fixed constant value. Would that be a linear increase in ELO points, or what? Yes, but I suppose any presumably valid rating system. Of course this is an approximation since both rating systems and thinking effectiveness are not precise measures. ELO ratings are a very convenient statistical mechanism to predict performance between any 2 players. If you are 200 ELO higher than someone, you are expected to win about 3 out of 4 games. Although I claimed a linear improvement in ELO for each factor of X time increase, I do believe there is a very gradual fall-off as you get closer to perfection. This has been shown empirically with chess.It follows that this would happen in GO too. I believe the fall-off in go is much more gradual (just the opposite naturally of what many on this group are claiming) because it's a richer game strategically. - Don ___ 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] an idea... computer go program's rank vs time
Hi Don, On 1/25/07, Don Dailey [EMAIL PROTECTED] wrote: That's the thought - due to the nature of go the increases might not be linear nor consistent between players of different strengths. I hesitate to venture what others believe, but it seems based on Ray's and Mark's and others' posts that there is a gut feeling amoung go players that this may be the case. Perhaps they care to comment further. I think this is a case where our gut feelings are not particularly reliable.I've already discussed several reasons why we might be led falsely to believe our strength is pretty much fixed, but I'll just summarize here: I have to admit it is sometimes getting tiresome to continue to read some of your (in my mind) misconceptions about go, in particular when you always continue to push them because it is such-and-such in chess etc. without ever believing anything that some of the strong go players (some a lot stronger than me) have to say. I am EGF 4D. A friend of mine is EGF 6D. When I show him the opening of a game and some moves that I have thought quite some time during the game, and then some more time while reviewing the game -- then often he can still tell me immediately how I have been wrong, and explain me why. But of course that is just undo worship of stronger players. If a 6D shows one of his games to a pro, again the pro will be able to tell him some mistakes in direction in judgements by only giving the game a very quick glance. I am not sure why I am explaining this, since you will dismiss such experience anyway due to some odd consideration that has nothing to do with any go experience. Btw among go players around my strength I probably believe more than most in substantial improvements by longer thinking times - but it is still very small compared to the standard deviation of strength among the amateur go population. (Which is a much better scale when you want to compare strength differences for added thinking time between go and chess, rather than ELO, in my opinion.) Arend ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Ray Tayek wrote: ... I can say that I don't feel overwhelmed when playing chess. ... Now with Go as a beginner still, on the other hand, I almost always felt and still feel quite overwhelmed ... yes, i usually feel this way in tournament games. and again more time will help (for some small powers of 2). I'm glad I'm not the only one that feels this way ;-) i think more time works better because go has more battles going on at the same time. Which also makes it harder when there is interplay between them. if you are analyzing one battle, maybe more powers of two. if it's many battles, maybe fewer powers of two as you will hit your mental limit sooner. This seems to support the idea I was trying to express... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
- Oorspronkelijk bericht - Van: Matt Gokey [EMAIL PROTECTED] Datum: maandag, januari 22, 2007 9:59 pm Onderwerp: Re: [computer-go] an idea... computer go program's rank vs time Nick Apperson wrote: He is saying this (I think): to read m moves deep with a branching factor of b you need to look at p positions, where p is given by the following formula: p = b^m (actually slightly different, but this formula is close enough) which is: log(p) = m log(b) m = log(p) / log(b) We assume that a doubling in time should double the number of positions we can look at, so: m(with doubled time) = log(2p) / log(b) m(with doubled time) = log(2) * log(p) / log(b) Your math is wrong (I think). The correct equivalency for the last line would be: m(with doubled time) = (log(2) + log(p)) / log(b) Yes. Don's scalability argument states that ELO gain is proportional to time doubling. For me scalable use of time implies that time translates into depth. The extra depth is: m - m0 = log(2)/log(b). So if the ELO gain for time doubling in Chess equals 100 over a wide time scale and if Go has a 10 times larger branching factor than Chess, then the ELO gain for time doubling in Go would equal 100/log (10) = 43 (everything else assumed equal). I'm not sure i agree with Don, but i just want so say that if he is right, than mathematically he is also right with a larger branching factor. Dave ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
you are right about my math being wrong. I wasn't paying that much attention to that step, but with the correct math (as was pointed out) you end up with a linear equation assuming what I said to assume. Man, its only been a couple years and my precalc skills have gone to crap... Thanks for the correction. And Dave, you said what I was trying to say, except better. The only thing I have to add is that one major difference between humans and computers is that brains are able to think in parallel much more effeciently. For a game such as go, we are able to use that ability more because of the larger branching factor. On 1/23/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: - Oorspronkelijk bericht - Van: Matt Gokey [EMAIL PROTECTED] Datum: maandag, januari 22, 2007 9:59 pm Onderwerp: Re: [computer-go] an idea... computer go program's rank vs time Nick Apperson wrote: He is saying this (I think): to read m moves deep with a branching factor of b you need to look at p positions, where p is given by the following formula: p = b^m (actually slightly different, but this formula is close enough) which is: log(p) = m log(b) m = log(p) / log(b) We assume that a doubling in time should double the number of positions we can look at, so: m(with doubled time) = log(2p) / log(b) m(with doubled time) = log(2) * log(p) / log(b) Your math is wrong (I think). The correct equivalency for the last line would be: m(with doubled time) = (log(2) + log(p)) / log(b) Yes. Don's scalability argument states that ELO gain is proportional to time doubling. For me scalable use of time implies that time translates into depth. The extra depth is: m - m0 = log(2)/log(b). So if the ELO gain for time doubling in Chess equals 100 over a wide time scale and if Go has a 10 times larger branching factor than Chess, then the ELO gain for time doubling in Go would equal 100/log (10) = 43 (everything else assumed equal). I'm not sure i agree with Don, but i just want so say that if he is right, than mathematically he is also right with a larger branching factor. Dave ___ 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] an idea... computer go program's rank vs time
On Tue, 2007-01-23 at 21:08 +0100, [EMAIL PROTECTED] wrote: Yes. Don's scalability argument states that ELO gain is proportional to time doubling. For me scalable use of time implies that time translates into depth. The extra depth is: m - m0 = log(2)/log(b). So if the ELO gain for time doubling in Chess equals 100 over a wide time scale and if Go has a 10 times larger branching factor than Chess, then the ELO gain for time doubling in Go would equal 100/log (10) = 43 (everything else assumed equal). I'm not sure i agree with Don, but i just want so say that if he is right, than mathematically he is also right with a larger branching factor. It's trivial to prove programs are infinitely scalable. It's a bit more difficult to prove humans are - but I think it's probably a similar proof. I believe a scalable program can be highly scalable or less scalable meaning they improve less or more with time. Humans appear to be of the highly scalable variety, at least in chess they improve with time faster than computers do. A chess program playing at 3 minutes per move is about 300 ELO stronger than the same program playing at 5 seconds per move. A human is more like 400-500 ELO stronger. There is strong evidence that in chess this doubling tapers off at strong levels. This makes a great deal of sense. Ernst Heinz did some experiments that proved empirically (with high statistical confidence) that strength tapers off with search depth in computers. Although he measured this using search depth, I believe the tapering is more related to strength. It just happens that the deeper searching programs were playing stronger. If someone could construct a computer that played just as well with half the search depth, I think the tapering would be approximately consistent with the deep searching program of similar levels. The tapering is very gradual and even at high ply depths the ELO improvement for a doubling is quite good. That's why I believe in GO it will be hard to see this tapering effect. I believe GO players are farther from the ultimate top that chess players (I mean the very best players.) Once you are playing almost perfectly, you won't get quite as much from the extra thinking time. I did an experiment long ago with a checkers-like game I made up. It is simple checkers on a 6x6 board and only 1 jump allowed. It's possible to construct an enormously deep searching program with this little mini-game.I also found that the really super deep levels taper off, and yet it is gradual and you never seem to stop benefiting measurably from each additional ply of search. The program searches deep enough that it's easily to imagine that it can't make errors, but obviously one side is making errors. The worlds best checkers program are like this too. They go much deeper than in chess and they are quite amazing how deeply they search. I think they are way beyond human strength now, but they still lose games to each other and make mistakes that 1 more ply of search would solve. That's really the point - 1 extra ply always solves a thick layer of problems that you couldn't solve before. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
It is true that MC-programs has a bias towards overconcentration. But... 1) A improvements to the simulations of MC-program as implemented by MoGo and Valkyria does diminish the problem. In fact most of the strength of these programs from doing that. I think it is next to possible to explicitly program the concept of overconcentration, but fortunately you do not have to. The problem goes away when you fixed other more immediate problems with the simulations. 2) Deeper search makes these programs stronger. Valkyria always get stronger with increased search. Just playing MoGo on fixed time limits does not tell you anything about what it could possibly find out. It is more informative to watch the principal variation change over time. As it goes deeper the sequence always get better and better, and when you see that you know that increased thinking will imrove the principla variation forever. This does not mean that always plays the best move in the end, but it means that algorithm recursively improves the analysis all over the tree and only a serious bug can stop that from happen. Note that MC-programs do not have high level concepts programmed into them. Thus you will alwyays be able to say it played X because it does not understand Y whenver it plays a bad move but this is wrong. Correct is: it played X because it did not search deep enough. -Magnus Quoting terry mcintyre [EMAIL PROTECTED]: From: Don Dailey [EMAIL PROTECTED] On Mon, 2007-01-22 at 03:43 +0100, alain Baeckeroot wrote: The few games i played against mogobot on 19x19 shows that it does not know overconcentration. And i can safely bet that increasing thinking time will not solve this, By definition, a scalable program can solve all problems so your statement is incorrect. Is Computer Go infinitely scalable? Is Mogobot, in particular, scalable? Most programs reach scalability limits at some point. If the concept of overconcentrated shape is not inherent in a given program, it might take a vast number of simulations to compensate for that lack. I suspect that monte carlo will need to be merged with some method of learning patterns and concepts to play higher-level Go in human-scale timeframes. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Note that professionals do not play perfect endgame, ... Enough, apparently, that it separates a world champion from a run-of-the-mill 9-dan. Also, post-mortem analysis of pro games published in go magazines routinely finds some game-result changing improvements in the endgame. Yes, though in the Honinbo book I mentioned there is something like Ishida lost by 0.5pt in one game and in the post-mortem they decided he had played at least the last 100 moves correctly. (from my fuzzy memory - I don't have the book to hand). However he was probably the world's strongest endgame player at the time and at the peak of his concentration. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Been following this thread pretty closely and thought I would jump in with a thought and try to find some common ground. I think there is truth to be found in both sides of this argument. Of course people improve with time and so do computers with certain algorithms. The question is about the curve and whether there is a significant difference in this curve between chess and go. Don believes there is probably no difference and states a rule: doubling thinking time = linear improvement in play. What if we look at it mathematically by looking at the branching factor? Go’s branching factor is generally considered to be about an order of magnitude greater than chess – perhaps a bit less, right? That means that after each ply go becomes another additional order of magnitude more complex. Now of course, in practice it’s not so simple, as breaking the game into regions and doing local reading and global analysis reduces the complexity somewhat, but in general go explodes a lot faster than chess and this fact is commonly used as one of the reasons methods used for computer chess don’t work on go especially combined with the lack of reliable evaluation. For the sake of argument if we assume that doubling thinking time allows one to double the number of positions and alternatives that can be analyzed, this doubling would seem to have lesser impact in go where the explosion is much quicker than in chess and thus the same relationship may not hold. The improvement may not be linear or it may not hold for very long. The point of diminishing returns for a human due to this could be much earlier in go than in chess. As go players get better they must learn to “sense” the board based on years of experience combined with our evolutionary tuned super parallel visual pattern matcher. This provides the player shortcuts that otherwise would be impossible (for humans) to read out. Assuming enough processing power and memory this problem would not necessarily hold for computer-go. By the way, I think some of this very same thing applies to both chess and go, just a matter of different degrees. From my own experience with chess and go, I can say that I don’t feel overwhelmed when playing chess. That is, I always feel like I can think and reason about the moves fairly deeply and use simple evaluation like piece counts, protection, mobility, etc. to decide between lines of play. I may be entirely wrong but I feel like I can think about it anyway. I’m not a real strong player, but I had a friend in high school and college whose Dad was a Grand Master. His son was pretty good and we would play a lot of chess together. Once in while I would play against his Dad and usually get slaughtered. One time he was doing one of those events where he would play 30 people at once. I played and managed to keep him challenged well into the middle game. I could tell he was worried. On one trip around I still hadn’t made my move and was forced to make the best one I had. It was a blunder but I didn’t see it yet. Immediately he took advantage of it and I didn’t have a chance after that. He confirmed this after the game was over and set the pieces up as they were at that point and showed me what I should have done (I thought an amazing feat given he was playing 30 or more different simultaneous games). Anyway in this situation where I had a lot more time than he did I was able to challenge him and only after making a blunder was I in trouble. So I see where Don is coming from with Chess. Now with Go as a beginner still, on the other hand, I almost always felt and still feel quite overwhelmed without enough tools to understand how to plan and evaluate moves in all but the simplest isolated cases. I know that giving me tons of extra time against a good player would not help. The interactions between areas and the explosion of the game and lack of experience to be able to “sense” good shape and proper balance early enough to lead to life and territory just simply overwhelms me. The feeling is not as severe as it was when I first learned, but it is still there. I wonder whether even for strong amateurs this is still the case, but just happens a bit deeper. Is this the time limit that Ray talks about where any more time is not helpful? It is that point when it becomes so terribly complex and overwhelming that no more thinking can help given your current ability to judge potential in the positions. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
At 09:27 AM 1/22/2007, you wrote: ... Don believes there is probably no difference and states a rule: doubling thinking time = linear improvement in play. i agree with this over some small range of powers of two. ..., as breaking the game into regions and doing local reading and global analysis reduces the complexity somewhat, but in general go explodes a lot faster than chess ... ... I can say that I donât feel overwhelmed when playing chess. ... Now with Go as a beginner still, on the other hand, I almost always felt and still feel quite overwhelmed ... yes, i usually feel this way in tournament games. and again more time will help (for some small powers of 2). i think more time works better because go has more battles going on at the same time. ... The interactions between areas and the explosion of the game and lack of experience to be able to âsenseâ good shape and proper balance early enough to lead to life and territory just simply overwhelms me. The feeling is not as severe as it was when I first learned, but it is still there. I wonder whether even for strong amateurs this is still the case, but just happens a bit deeper. Is this the time limit that Ray talks about where any more time is not helpful? ... if you are analyzing one battle, maybe more powers of two. if it's many battles, maybe fewer powers of two as you will hit your mental limit sooner. thanks --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Le dimanche 21 janvier 2007 19:02, Don Dailey a écrit : On Sun, 2007-01-21 at 13:34 -0200, Mark Boon wrote: To move up 200 ELO points in Go is usually not achieved by looking at more positions but by acquiring new concepts. To acquire a new concept in just a few hours is a rare thing. Some of these concepts would maybe take years to acquire if there wasn't someone to teach it to them. And you can gain new insights or concepts in a single short study period. Study with books or teacher can lead to quick improvement. But alone more time can be useless, one just don't see the correct thing. Historically, Dosaku discovered overconcentration strategy, but it needed 150 years to find a global counter strategy (the Shusaku kosumi). The few games i played against mogobot on 19x19 shows that it does not know overconcentration. And i can safely bet that increasing thinking time will not solve this, and computer cannot reach amateur 1d without this concept (either explicit or implicit in large patterns like Mango) The example you gave about studying a position for two hours and then showing it to someone 600 ELO points stronger. I think in Go someone who is 600 ELO points stronger can let the other player think about every move for a whole day and still beat him using on average just 10-20 sec. per move. It doesn't scale the way it does with Chess. I don't believe this at all. You should ;) But it's difficult to argue about it since it is extremely difficult to construct a fair experiment in this regard. Just play a game, analyse it carefully with all the books and internet, try to find the mistakes, and after ask a strong dan to comment the game ! He will instantaneoulsy tell you nice things, very clearly, but you just have not seen that. Also, we should keep in mind that amateur in go are just hmm amateur, and they don't master the game, maybe not even the basis. Maybe strong dan can efficiently analyse their own games, but for kyus even with very long time, nothing very good will show up, kyu are limited by their knowledge and poor reading. And programs on 19x19 are weak kyus. But I continue to be amazed that so many people think GO cannot be approached in a methodical logical way or that the human mind cannot break it down with the application of time and effort. I am amazed that people think human can do anything ;) we are not gods, we are just humans :) (this is off-topic phylosophy, and not a troll) By the way, can I assume that in world champion GO matches they use fast time controls because long time controls don't help in Go? Important tournament have long thinking time, and need 2 days like in chess. In such games, sometimes one player spend 1 hour on one move... But they are pros, and maybe some other reasons (financial, tv ...) can explain why some tournaments are reducing the time from 8h each to 3h. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
From: Don Dailey [EMAIL PROTECTED] On Mon, 2007-01-22 at 03:43 +0100, alain Baeckeroot wrote: The few games i played against mogobot on 19x19 shows that it does not know overconcentration. And i can safely bet that increasing thinking time will not solve this, By definition, a scalable program can solve all problems so your statement is incorrect. Is Computer Go infinitely scalable? Is Mogobot, in particular, scalable? Most programs reach scalability limits at some point. If the concept of overconcentrated shape is not inherent in a given program, it might take a vast number of simulations to compensate for that lack. I suspect that monte carlo will need to be merged with some method of learning patterns and concepts to play higher-level Go in human-scale timeframes. Cheap talk? Check out Yahoo! Messenger's low PC-to-Phone call rates. http://voice.yahoo.com___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
On Sun, 2007-01-21 at 20:29 -0800, terry mcintyre wrote: From: Don Dailey [EMAIL PROTECTED] On Mon, 2007-01-22 at 03:43 +0100, alain Baeckeroot wrote: The few games i played against mogobot on 19x19 shows that it does not know overconcentration. And i can safely bet that increasing thinking time will not solve this, By definition, a scalable program can solve all problems so your statement is incorrect. Is Computer Go infinitely scalable? Is Mogobot, in particular, scalable? In theory, Mogobot is infinitely scalable with time and memory. In practice Mogobot probably used 32 or 64 bit integers to count statistics which would place a limit, but that could easily be overcome. When my program gets to the point it can do 4 billion play-outs, I will have to change to 64 bit counters. Most programs reach scalability limits at some point. If the concept of overconcentrated shape is not inherent in a given program, it might take a vast number of simulations to compensate for that lack. Where most people go wrong is to assume that for a computer to beat a human it must be able to understand every single thing a human does but only better. This is a ridiculous burden to place on any player including a go program. Each player has his own strengths and weaknesses whether human or computer. The trick is to maximize your strengths and minimize your weaknesses.That's how computers beat humans because they have some glaring weaknesses and yet they still win because the human has weaknesses too. It's been my experience that the computers discover concepts much quicker than you imagine that they would. They will play as if they know things they were not explicitly programmed to understand. For example in chess, even if you don't tell the program about weak pawns (which you should), it will discover this on it's own as soon as it has to take a well positioned piece and defend a weak pawn with it. This is a simple example of concept discovery. But to understand the strength curve you have to appreciate that playing strength is more about avoiding the mundane errors than it is making brilliant moves and understand deep concepts. Of course the definition of mundane changes as you get stronger. What is a basic error to a strong player is not going to hurt a weak player. So if you don't understand some dan level concept when you are 20 kyu player and you want to improve, the trick isn't to learn the dan level concept, it is to first learn the simple things that you are screwing up on every other move. Those are the things that are killing you. Those deep things don't matter at this point but once you fix the big problems in your play, then these things gradually start coming into view as important things to fix. I figured this out myself when I first learned chess and wanted to improve. I was trying to learn sophisticated stuff but I was losing every game due to trivial blunders. The low hanging fruit pathway to improvement for me was to stop making trivial blunders. This was worth far more ELO points than learning how to checkmate with a bishop and knight or even win the simple KP vs K ending. The thing about 1 extra ply of search in computer chess is that 1 extra ply is like a whole new layer of understanding. A 1 ply search will never make a simple piece hanging blunder, but it won't be able to understand the value of a trivial forking move. So giving it 2 ply opens up a whole new world. But 2 ply can't anticipate and defend against a simple forking move that the opponent might make, but give it 3 play and another wonderful layer of understanding has opened up. A 3 ply might actually start to sense a pawn is weak even without the explicit knowledge of weak pawns. Each extra ply is like a whole new world of understanding and blunder avoidance and attack skills, etc. My program Botnoid started out as pure 1 ply search Monte Carlo and it plays reasonable looking moves (and it has actually won a 9x9 KGS computer go tournament.) However there is no tree search and it was vulnerable to making the most trivial error, self-atari. Simple Monte Carlo (without UCT or tree search) has a way of simulating basic global understanding but not appreciating tactics in any way. So Botnoid often would play a self-atari move if it also seemed to attack the opponents chains.A simple fix to avoid this was like a 200 ELO improvement. The patched up version kills the unfixed version. This is pretty similar to what you would expect in computer chess. Of course GO program are far weaker than chess programs but the same principles apply. Fix the stupid things first. You can fix a lot of stupid things with a little bit of time so that you can get to the next level where you fix the next most important things etc. It's not productive to fix the hard problems if the dumb things are killing you. - Don I suspect that monte
