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/
