> You don't need to know the whole tree, you only need to know some of the > tree and it's a very small fraction of the whole. That's what > alpha/beta pruning is all about.
Certainly we are seeing gains by looking at smaller portions of the tree. Perfect play and the question of God however seem akin to generating the entire tree. Since we are using statistics to decide which parts of the tree are interesting or good... we are still missing other potential playouts. Judging by the number of samples vs. the number of possible games, we are missing many possible moves, some good, some bad. I guess it all depends on your definition of God... but my mental image would be that he knows all paths of the game.. and thus would not be tricked when we are only looking at a subset of the tree. Same goes for perfect move. We can never judge accurately if we found the perfect move unless we know what all possible moves are. We can only guess with a certain amount of confidence. However... humans are not anything like God and are missing huge portions of the tree as well. Generating a better move than a human is in no way related to the need to generate the entire tree. I do agree that it is very much possible that this technique alone could scale to the point of crushing a person. I just don't know yet if we can accurately guess that. People are rather flexible in the way they play and learn and it is still very trickly to evaluate a goban. I am not completely familiar with Mogo's inner workings.. but it does have a base heuristic that helps it judge where to start looking. If it doesn't find a certain group of moves.. it goes to random spots. It seems that adding this heuristic stage helped CrazyStone and Mogo greatly. I am totally on your side with beating human players. It is obvious that it will happen one day. I am just very curious of the number crunch vs. heuristics vs. a whole new paradigm debate. MC is kind of a new paradigm for number crunching (at least in go).. and it is great. I am just curious if new barriers will be hit. And I am happy either way... if MC does not turn out to be the panacea of computer go... then new methods will be combined with it or whole new methods will come out. A number of barriers have already been hit.. computer go seemed stuck around 12-8k for a while.. and it was a bit worse before right? I am not trying to crush anyone's dreams.. I am just curious if this breakthrough has really removed all of the barriers to number crunching or if it has just helped us push up to the next level, one where we will once again have to work on heuristics or go back to the drawing board. I wish we could rely on hardware scaling.. but I am not so sure that it is the answer yet. That is a hunch.. but so are many claims I have seen. I can't turn my hunch into a theory until I have more data. I haven't seen a source of data that convinces me we are home free yet. When we start putting these machines against seasoned pros... and watch what happens when you scale... I think we will have a much better answer. And to Don, I think we had plenty of misunderstandings and miscommunications... I know you aren't saying we are home free and you have put a lot more work in it than I have. When you said "proven to be scalable to perfect play" you probably meant it in a different sense than I read it and many people on here might have understood what you were trying to point out. I'm not trying to spray your parade with yellow rain... I just feel that there are still many unknowns. On Mon, Aug 11, 2008 at 12:23 PM, Robert Waite <[EMAIL PROTECTED]>wrote: > > Yes, but "exhausitve search" does not improve your player by 63% (eg.) > > for a doubling in CPU time. > > This part was done in an empirical scalability study. Please check the > > > archives of the list. > > > In the (inifinite) limit minimax+evaluation-function would find the > > perfect move > > too, but UCT/MC already find "good" moves before the limit. > > Yes... I agree... UCT/MC seems to find the good moves before the limit and > from statistics.. seems that the good moves come out long before we have > exhaustively searched the tree. I was questioning the rate at which we > approach "perfect play". This term seems silly to me... as it would imply > actually solving the game. The whole idea of playing vs. god and drawing or > winning only means one thing to me... and that would be actually knowing > every possible path to determine the best path. The results of the MC > statistics simply say that this move appears to be better given the sample > size. To me.. I don't think anyone could say that you could beat god without > actually knowing the whole tree. That would be conjecture at least at this > point. And having God in the equation already moves us to mysticism (or some > sort of statement that the game has a solution). > > As far as the 63% gain... I feel that there are certain additional > descriptors needed there. We did not see a statistical increase in ability > vs. human players. We saw a 63% gain when putting programs against programs. > This is hardly the same problem. It is valuable information and I am not > discounting it at all. I just feel that this evidence DNE what it seemed to > be used for in previous discussions. > > > ...Why are you trying to share it with us in the first place. > > For myself, i believe that what you are trying to do, is to > > begin to analyses all the data the community has gathered so far... > > > Well.. things certainly got heated and as I looked at the list.. I started > feeling guilty that I kind of took over. The list seems primarily used for > coordination between you guys and perhaps at times theoretical discussion. I > apologize for the rants that have perhaps shown up suddenly. > > The background reason I came in here was that I love go and have loved it > ever since I learned to play about 5 years ago. I am also a developer and > long ago had read many articles on computer go. At the time.. and perhaps up > to now.. there have been many go players, computer scientists and lay people > who have worried that perhaps the greatest strength of the computer, fast > computation, would not be such a great help with playing go. There were > taunts from this side saying that computers couldn't really beat children > who were decent. After reading and hearing these sorts of discussions... I > started to fall into that group. My personal feeling was that AI now is akin > to a human taking a lot of time trying to create a particular algorithm. > Then this algorithm would work in a particular scenario. This seems > difficult for go as each of these heuristics are focused and meanwhile, you > have a human who is constantly changing his heuristics during their years of > learning. > > I feel that to have what movies consider "AI" or what the general public > expects from "AI", we will need a new paradigm where computers learn to > solve problems by themselves through experimentation and learning. This does > not necessarily apply to go, but is possible. > > The reason I brought up complexity theory is not to confine computer go to > a particular complexity class... but to discuss the fact that our current > model of computing machines do appear to solve many important problems.. but > that there some classes of problems that we are not so certain can be solved > with the computer model we all have at our desks or in our datacenters. > > When I read the article by the DeepBlue guy called "Cracking Go", I was > very skeptical. I felt that he was assuming too much. When I read that Mogo > was going to get a nice big cluster.. I was very excited and couldn't wait > to watch the game. When Mogo started to turn around... I had completely > swtiched from skeptic to cheering it on. I think the Mogo team and many > people on here have done a great job. > > So then I jumped into conversation here and perhaps had not fully > researched previous topics and breakthroughs... but I felt that I was cut > down pretty quickly with the phrase "proven to be scalable to perfect play". > The phrase itself was used to completely nullify my argument. That is > perhaps where it started to get out of hand. Don's "Duck" does not really > seem to be clearly a duck. In his analogy... his duck is almost an axiom and > I am some crazy freak who thinks the world is flat. I felt it was a bit > condescending and did feel I had to try to clear the logic up. > > At this point.. I have read the Bandit paper and am pretty sure where he > got this phrase. In the paper it is phrased differently. I am probably at > fault here because I have just jumped in here and have not been a part of > much previous discourse. Perhaps that phrase has a different meaning here > and people would assume what he meant. When I saw that phrase... the first > thing I thought was that they surely meant practical. Afterall... what use > is something that takes more memory that we have in the universe and more > time than the age of the universe. Obviously we are hoping that it gets > somewhere good well before that... but the phrasing in the original paper > did not seem to use this phrase to show why it is practical. > > I looked at the empirical evidence (at least what I think is being referred > to).. and to me it does not overwhelmingly show that this can be practically > scaled to beat humans. I just don't see the duck... and I don't think that > is from having a weak intellect or flawed logic. It seems that they are > datapoints that are valuable in computer go... but they are datapoints that > I feel do not prove or even begin to prove how Mogo will scale against > humans. I don't think that the experiment in this case has covered the > model. > > My reasons to start discussing things on here was that I was curious about > the future of computer go. As a few discussions got heated.. I felt that > some weak logic was being thrown at me so I probably got a little heated and > started firing back. I will try to keep such discussions out of the list. > > I have however enjoyed reading many people's responses and from all of > this... I have started getting much deeper into complexity theory... from my > schooling.. we only knew about big O notation and how to apply it to our > code. > > > > >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
