[computer-go] Re: The global search myth
>As any incomplete search, it can blunder, but why more than any other >incomplete search? Not worse, just not a magic bullet. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: The global search myth
Dave Dyer wrote: In cases where the good moves are the "obvious" ones, you've found them anyway. Ok. Here I agree. In other cases, you prune them away. You are not really pruning, just postponing. Of course you may overlook moves of genius, who doesn't? But if your probabilities are correct you may be emulating what a human does. You DO get wrong answers much faster this way though. Why? I don't see why. I see this order as the most human like way of searching. As any incomplete search, it can blunder, but why more than any other incomplete search? Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: The global search myth
On Dec 5, 2007 9:39 AM, Dave Dyer <[EMAIL PROTECTED]> wrote: > > The problem with this is that below a few ply, the probabilities are > all effectively zero. All you're really doing is enshrining the > prior probabilities used to sort the first few levels. Why would they be zero? floating-point types have a huge resolution near zero (they are logarithmic in nature, in some sense), so I don't think you are going to get zeroes fast. In cases where the good moves are the "obvious" ones, you've found them > anyway. In other cases, you prune them away. You DO get wrong answers > much faster this way though. You don't prune them away. You make them look more expensive, which means that they will be analyzed later in an iterative deepening loop. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: The global search myth
The problem with this is that below a few ply, the probabilities are all effectively zero. All you're really doing is enshrining the prior probabilities used to sort the first few levels. In cases where the good moves are the "obvious" ones, you've found them anyway. In other cases, you prune them away. You DO get wrong answers much faster this way though. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: The global search myth
The problem with this is that below a few ply, the probabilities are all effectively zero. All you're really doing is enshrining the prior probabilities used to sort the first few levels. In cases where the good moves are the "obvious" ones, you've found them anyway. In other cases, you prune them away. You DO get wrong answers much faster this way though. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: The global search myth
just a link : http://ticktockbraintalk.blogspot.com/2007/11/brain-clock-temporal-resolution-g-power.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: The global search myth
Raymond Wold wrote: >> The general rule (in my opinion) is that playing strength will require a >> huge amount of "power" because that's what A.I. is. This in no way implies >> that it should not be "efficient" or that it should foolishly squander >> resources (as an internal combustion engine does.) Instead it should be as >> efficient as possible specifically so that it can do more work. And your >> not going to squeeze much water out of a rock. You're not going to get a >> free ride. You are not going to produce a strong program that doesn't do an >> enormous amount of work. Naturally, you want to do that work as >> efficiently as possible. The reason you want the work to be as efficient >> as possible is so that you can do even more work, not because you are >> seeking the holy grail of a program that plays like a master with a few >> lines of clever code and a constant time algorithm. >> > > Don, I think you're very much arguing against a straw man at this point. > I don't think I have mis-represented the position that some have taken. What I did is put it in terminology that may make their position look a bit foolish. It doesn't exaggerate their position it just exposes it. I use that technique on myself quite often - to test if an idea really makes sense. Reword the idea (without changing it) and see if it still has the ring of truth. - 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] Re: The global search myth
> The general rule (in my opinion) is that playing strength will require a huge > amount of "power" because that's what A.I. is. This in no way implies that > it should not be "efficient" or that it should foolishly squander resources > (as an internal combustion engine does.) Instead it should be as efficient > as possible specifically so that it can do more work. And your not going to > squeeze much water out of a rock. You're not going to get a free ride. You > are not going to produce a strong program that doesn't do an enormous amount > of work. Naturally, you want to do that work as efficiently as possible. > The reason you want the work to be as efficient as possible is so that you > can do even more work, not because you are seeking the holy grail of a > program that plays like a master with a few lines of clever code and a > constant time algorithm. Don, I think you're very much arguing against a straw man at this point. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: The global search myth
I meant to expound a little on this: > (Not to mention that some algorithms are more scalable that others, I want > to talk about that in a minute.) In humans we often try to measure "intelligence" with tests and we call them IQ tests. It has been said that IQ tests actually only measure your ability to take IQ tests because they fall quite short of actually summing up intelligence to a single number.In fact, you can't. It's probably impossible to accurately quantify all the qualities of intelligence. Many people are genius's at some things and well below average in other things. Nevertheless, in each human is the machinery required for intelligence, a kind of computer we call the brain. We don't really understand very much about how it works, but it seems to consist of many key features that AI tries to emulate, pattern recognition, memory, ability to reason, etc. I would like to get the groups thoughts on this - because I'm on shaky ground here and don't claim any particular insights here - but I have a general theory about AI. It seems to me that you can view "intelligence" as a kind of physics. I would probably compare it to horsepower or "power" in physics. You can use whatever unit you choose, perhaps "watt" Work is not the same as power in physics. Work is the product of force and distance over which it moves in physical terms. In automotive terms it takes the same amount of "work" to move an equally heavy vehicle 100 miles or kilometers for instance. Of course I'm ignoring other physical factors such as air resistance in order to simplify. A scalable program can do any amount of work if you are willing to wait any amount of time. But some have much more horsepower than others. Mogo is a high horsepower engine. Brown is a seized up engine with so many inefficiencies that it works against itself. It can't really do any work. My basic idea here is that intelligence isn't static. Even in humans, as an approximation, it isn't about whether you can solve a problem or not, it's more about how long it takes you to solve the problem. We don't really think about it that way, but I believe it to be (more or less) true. With AI, computer memory is analogous to human memory. It's more like memoization in computer science. Once we learn something for the first time, we can use it over and over again throughout our lifetimes without having to rediscovery it. Of course the human brain is "hardwired" for many things it has been said. Much of what we need to survive and be intelligent, we don't have to learn - it was in us the day we were born. Sometimes, people who learn a lot of facts are considered intelligent. Even if they don't really understand or have much practical wisdom, we are impressed with someone who has so many facts stored in his brain and this probably should be considered one facet of intelligence. Computer Go programs have all these elements in them. They have memory, hard coded knowledge, reasoning ability (a life and death analysis can be considered a kind of reasoning ability as can an alpha/beta search) and so on. Sometimes we consider the ability to "figure something out" as being the main component of I.Q. as opposed to just "knowing the answer." And this is probably fair, because one is like having a fish and the other is like learning how to fish, a more useful skill in the long run. A scalable program has the ability to figure things out. A non-scalable program must be considered the type of AI that either "knows the answer" or doesn't. Sometimes we pretend there is no distinction because we are so time-conscious. We say that it doesn't matter if it can figure something out because we are too impatient to wait for the answer. We can measure the I.Q. of a GO program in a (very) rough way by calculating the ELO strength of the program and the amount of running time to produce this level of play. It's wrong to not consider time in this formula. In human I.Q. tests, the clock is part of the test and rightly so. Almost every problem in an I.Q. test is of the nature that you could figure out the answer eventually (if you are persistent and focused) but the clock holds you back. Time is an important variable in human intelligence, the accomplishments of the most brilliant scientists are often measured by the total body of knowledge they are able to contribute in a life-time as well as the quality of that knowledge. So my theory here is that A.I. is not a static quantity divorced from time but that time is a very important consideration. Every reasonably written chess program, for example, is equally strong if you don't time-constrain them. But only the best ones get considered as "strong" or "intelligent." The programs that play poorly are called "stupid" but they are only stupid because they are not efficient, not because they ca
Re: [computer-go] Re: The global search myth
Jim O'Flaherty, Jr. wrote: > Don, > > I think it is tenuous to predict, much less emphatically assert, that > just because the evidence is linear at the lower scale, it remains so > at higher scales. This is done all the time in science!Many things in science are considered facts that haven't been proven except in some empirical sense. This theory of scalability isn't something "way out there" either. It's crystal clear that increased search depth or effort yields improved play until the point perfect play is reached. The only thing we are arguing about here is the shape of the curve. Although it seems unlikely that we will ever achieve perfect play, it doesn't make sense to require the "fat lady to sing" to know the general form of this curve. The evidence is not just linear at the lower scale as you claim either. I presented the evidence already. We now have decades of improvement to directly observe. This near-linear scale held from the point that a weak beginner could beat a chess program and has continued beyond the point that even many chess masters thought was unattainable, (even for humans.)And there still seems to be no end. Since we don't know how good a chess playing entity can ultimately be, we can't say for sure how far we are from perfect play, so it's possible we are not even half way there (whatever that means.) But it still seem ludicrous to expect the curve to suddenly flatten out, then when perfect play is almost achieved to suddenly dart to the final point in the graph. That is what you and others are predicting from zero evidence. Because if it isn't a relatively regular curve as I predict, it's going to have an unnatural shape. Of course someone is going to say, "this isn't chess, we are talking about go." I know how you guys think. If I could prove it someone would probably say, "yes, but "Yes, but that was with the positional superko rule.You have "no evidence" that this would hold with situational superko.Technically you would be correct, but you stretch the boundaries of credulity. Nevertheless, I did the experiment with 7x7 then 9x9 go.The shape of the 7x7 go curve was not interesting because it tended to be one sided. With 7.5 komi (I think) white usually won.It is still a profound enough game that only at fairly high levels did white always win. It was easy to see the curve suddenly flatten out when near perfect play was achieved. (I can't really be sure near perfect play was achieved, I can only guess. It's possible that some early profound moves needed to be played that even the stronger versions could not see.) I think 7x7 is "grainy" in the sense that there are probably only a very few main lines and if you stumble into them you will win even if you are relatively weak compared to your opponent. 9x9 though, was highly interesting. I showed this graph to the group. I'm pretty sure the graph reflected raw beginner play at the low end, and Dan level play at the high end (I don't think we actually have an easy way to calibrate this so I can only guess.)At the high end Lazarus (which isn't a great program but doesn't suck either) was doing an enormous amount of work - it was playing at a level way beyond what was possible on CGOS. I'm not guessing at this, I could compare Lazarus on CGOS directly because I knew about how strong it was (and I also used gnugo as a control program.) Gnugo could rarely win a game at the higher levels. (I also estimated that gnugo was a stronger program "intrinsically" that Lazarus although not scalable. Since gnugo is fixed, you can compare a version of Lazarus that takes the same amount of time to run.Gnugo beats that version of Lazarus under those conditions, and yet rarely can win a game at higher levels. Since I believe in the work/strength curve I would estimate that a scalable version of Gnugo would be superior to Lazarus at any level. Of course it's not clear how to properly scale up Gnugo, but I'm speaking theoretically here. (Not to mention that some algorithms are more scalable that others, I want to talk about that in a minute.) So I certainly didn't capture the entire range of ELO ratings and thus everyone can say I don't have an iron clad proof. Someone says, "but 19x19 is a different game altogether with different characteristics." My response is that the phenomenon seems to apply to every kind of 2 player perfect information game.It also applies to 19x19 GO at lower levels because I did a similar test with 19x19. I did this test also with a game that has a much higher branching factor than GO, a game called Arimaa. Arimaa was designed purposely to be difficult for computers.David Fotland currently has the best Arimaa program - an alpha/beta searcher with a lot of knowledge. This is the "quacks like a duck" situation. We have something here that looks like a duck, qua
Re: [computer-go] Re: The global search myth
Seo, All I described was the scientific method plus simple probability theory combined with using intuition to explore unknown unknowns creatively. For a layman's explanation into this world, see the works by Talib of "Fooled by Randomness" and "The Black Swan". Not sure about your analogy either. If their theory is "Extra Terrestrial Intelligence exists", has their been evidence provided to invalidate the theory? I had not heard of any. And our existence certainly supports the speculation within the theory, i.e. We exist. Therefor it is possible other intelligence exists. And I am suspicious any evidence "invalidating" the core theory (given it is a simple and encompassing as I have summarized above) could be found anyway. It would require searching the entire universe in a very short period of time as longer periods of time, like millions of years allow for possible emergence of evolutionary life forms after the area has been searched. As to your then applying the analogy to computer chess/go - don't see the connection. Jim Sanghyeon Seo wrote: 2007/11/23, Jim O'Flaherty, Jr. <[EMAIL PROTECTED]>: Don, I think it is tenuous to predict, much less emphatically assert, that just because the evidence is linear at the lower scale, it remains so at higher scales. While it is reasonable to assume, it is not certain. I see your point that at this time, your theory about it applying to larger scales has yet to be invalidated. However, this does not preclude your theory being invalidated in the future. Nor does it make their intuitions about ways others might be able to do so (and keep an open mind about creating attempts) as superstitious. It just means they are yet to be convinced of your position just as you are yet to be convinced of theirs. Remember, the direct evidence used to support a theory that the world was flat. That theory was later invalidated and replaced with a new theory incorporating the old evidence as well as the new evidence. This starts to sound like a SETI advocate. After forty years of sustained failures, the burden of proof is on SETI advocates, not critics. Same goes for computer chess and computer go. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: The global search myth
2007/11/23, Jim O'Flaherty, Jr. <[EMAIL PROTECTED]>: > Don, > > I think it is tenuous to predict, much less emphatically assert, that > just because the evidence is linear at the lower scale, it remains so at > higher scales. While it is reasonable to assume, it is not certain. I > see your point that at this time, your theory about it applying to > larger scales has yet to be invalidated. However, this does not > preclude your theory being invalidated in the future. Nor does it make > their intuitions about ways others might be able to do so (and keep an > open mind about creating attempts) as superstitious. It just means they > are yet to be convinced of your position just as you are yet to be > convinced of theirs. Remember, the direct evidence used to support a > theory that the world was flat. That theory was later invalidated and > replaced with a new theory incorporating the old evidence as well as the > new evidence. This starts to sound like a SETI advocate. After forty years of sustained failures, the burden of proof is on SETI advocates, not critics. Same goes for computer chess and computer go. -- Seo Sanghyeon ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: The global search myth
Don, I think it is tenuous to predict, much less emphatically assert, that just because the evidence is linear at the lower scale, it remains so at higher scales. While it is reasonable to assume, it is not certain. I see your point that at this time, your theory about it applying to larger scales has yet to be invalidated. However, this does not preclude your theory being invalidated in the future. Nor does it make their intuitions about ways others might be able to do so (and keep an open mind about creating attempts) as superstitious. It just means they are yet to be convinced of your position just as you are yet to be convinced of theirs. Remember, the direct evidence used to support a theory that the world was flat. That theory was later invalidated and replaced with a new theory incorporating the old evidence as well as the new evidence. And you want other attempting to disprove your theory. It both educates them on the current theory and challenges and possibly convinces them to share holding your theory. And it also educates you in the event they find some error in your approach/assumptions/context/definitions or are actually able to disprove your conclusion. And it is likely someone will eventually disprove your theory while keeping the evidence upon which your theory rests. I would encourage you to keep your theory (every cycle's sacred, every cycle's great, if cycle's wasted, God gets quite irate) and work making assumptions based upon this being true. That's efficient. I would also encourage others to challenge your theory and work at invalidating your assumptions around low level efficiencies. Both you, they and computer_go will be stronger because of it. Jim Don Dailey wrote: Hi Dave, You are doing it.No matter what evidence is presented, people will find a way to say it doesn't exist.As I mentioned earlier, the argument was that didn't apply to chess except for the first 4 or 5 ply - then when that didn't happen they expanded it to the first 6 or 7 and to this very day people are denying it - although they are looking more and more foolish in the process. We have already seen that this holds in GO, I did a massive study of it month ago on 9x9 boards and showed everyone this beautiful plot with straight lines showing the ELO per TIME curve which was essentially flat. I also remember the response. "ok, it applies to a small boards but 19x19 is a completely different game that bears no resemblance." So I must give up on this. I know if I do the plot again someone will say, "it only applies to depths we can currently test." "Surely it will flatten out next year when the new processors come." I cannot answer to those arguments when no evidence is presented to back it up other than superstition of disbelief or my favorite, "the testimony of experts in the field." I can only say that every bit of evidence we have backs up what I am saying. - Don Dave Dyer wrote: I agree with your exposition of search as it applies to chess, but I think there is a qualitative difference in Go. In chess, evaluators can see clear progress, in the form of material balance and statically determined positional factors, so each additional ply gives you more opportunity to see progress. Until Go evaluators give similarly strong and reliable signals, search will be a very much weaker tool. ___ 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] Re: The global search myth
My experience from doing search only with Valkyria, is that Go is not different to Chess in the sense that each extra ply really makae a difference. Improving evaluation almost always means that search gets deeper in UCT-type programs. Monte-Carlo simulation + knowledge gives a better signal. The question is what knowledge is needed and how to effectively implement it such that search do not suffer but rather improves. -Magnus Quoting Dave Dyer <[EMAIL PROTECTED]>: I agree with your exposition of search as it applies to chess, but I think there is a qualitative difference in Go. In chess, evaluators can see clear progress, in the form of material balance and statically determined positional factors, so each additional ply gives you more opportunity to see progress. Until Go evaluators give similarly strong and reliable signals, search will be a very much weaker tool. -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: The global search myth
Don Dailey wrote: So I must give up on this. I know if I do the plot again someone will say, "it only applies to depths we can currently test." "Surely it will flatten out next year when the new processors come." I cannot answer to those arguments when no evidence is presented to back it up other than superstition of disbelief or my favorite, "the testimony of experts in the field." I can only say that every bit of evidence we have backs up what I am saying. The truth is that we don't know. Your have an insufficient statistical universe to draw conclusions from, no matter how much you want to beat down those who beleive differently from you. Perhaps go IS different. Until you have any kind of rigorous analysis of WHY you see your linear line, and can show that it WILL continue until go computers beat the best pros, you're as much into myth land. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: The global search myth
Hi Dave, You are doing it.No matter what evidence is presented, people will find a way to say it doesn't exist.As I mentioned earlier, the argument was that didn't apply to chess except for the first 4 or 5 ply - then when that didn't happen they expanded it to the first 6 or 7 and to this very day people are denying it - although they are looking more and more foolish in the process. We have already seen that this holds in GO, I did a massive study of it month ago on 9x9 boards and showed everyone this beautiful plot with straight lines showing the ELO per TIME curve which was essentially flat. I also remember the response. "ok, it applies to a small boards but 19x19 is a completely different game that bears no resemblance." So I must give up on this. I know if I do the plot again someone will say, "it only applies to depths we can currently test." "Surely it will flatten out next year when the new processors come." I cannot answer to those arguments when no evidence is presented to back it up other than superstition of disbelief or my favorite, "the testimony of experts in the field." I can only say that every bit of evidence we have backs up what I am saying. - Don Dave Dyer wrote: > I agree with your exposition of search as it applies to chess, but > I think there is a qualitative difference in Go. > > In chess, evaluators can see clear progress, in the form of material > balance and statically determined positional factors, so each additional > ply gives you more opportunity to see progress. > > Until Go evaluators give similarly strong and reliable signals, search > will be a very much weaker tool. > > ___ > 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] Re: The global search myth
I agree with your exposition of search as it applies to chess, but I think there is a qualitative difference in Go. In chess, evaluators can see clear progress, in the form of material balance and statically determined positional factors, so each additional ply gives you more opportunity to see progress. Until Go evaluators give similarly strong and reliable signals, search will be a very much weaker tool. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/