On Tue, Apr 5, 2011 at 9:45 PM, Aja <[email protected]> wrote: > I don't think your current work is not valuable, and fully agree with you > that MM/SB-based engines have a much greater effect on strength, which is > clearly proved by Erica. But recently my feeling is that current MCTS almost > reaches its limit on 19x19. We will need another breakthrough/good ideas to > overcome KGS 5d or 6d. >
I would like to ask you to reconsider your feeling on this, because I think they are misguided. Let me explain why I feel that way and you can take it for what it's worth. Many months ago there was a discussion on computer chess and people were divided on the issue if most of amazing progress in computer chess was due to software or hardware. Most had always assumed it was hardware and that is the standard sound bite cut and pasted into articles that talk about the progress of computer chess. However, I was swayed convincingly to the software side of the issue and I think most real experts on computer chess agree now that it's roughly even - the software progress in computer chess has been absolutely astounding when measure over decades and it has kept pace and perhaps even outstripped hardware. But here is the thing ... the whole process was long and gradual and it never involved any major breakthroughs. Yes, there were things that stood out and some refer to them as breakthroughs, but none of them were even a fraction of what we got from Monte Carlo methods for Go. Go was really ripe for this one because it was long overdue anyway and global search was the only way forward and had been dismissed for so long. At each step along the way, it was almost impossible to imagine making a program play much stronger as it seemed like we were doing everything reasonably possible. In 2004 a program called "Fruit" came out and it astounded the computer chess community with it's incredible strength. The strange thing about this is that there are NOW chess programs that are hundreds of ELO stronger than Fruit, running on the SAME hardware. It's not hardware, it's real software advancements, good ideas and good engineering. And there have been no "major breakthoughs" since Fruit to produce these programs. Even Fruit itself did not have any new ideas of major significance, it just did a lot of things a little bit better. (Probably the biggest factor in Fruit was something called LMR which was worth something like 50 ELO, but even that was just an old idea all polished up with a better formulation. And many think the major thing that made it strong was simplicity and bug free code.) The lesson from this, is that if you are standing in a dense forest, you can only see a few trees around you. YOUR feeling that we have "almost reached our limit" and that we have exhausted all the good ideas in MCTS and need something new is certainly shortsighted and I mean no disrespect. I have fallen for this kind of thinking a few times myself. What you are very likely going to see is gradual steady progress and constant refinements of ideas and incremental improvements which will add up to an overwhelming amount of power in a relatively short time. There will not be any major new ideas but probably a lot of little ideas, each contributing a small amount. Here is an example of how this works, using a principle every top chess program author understands very well: Imagine that you can make your program strong enough in a months time to win 51% of the games against the previous version. If you can do that, you will have added something like 5-10 ELO to the strength of your program. 5-10 ELO is a small amount of improvement and it is so difficult to measure that it requires thousands of games to verify. So we are not talking about a herculean task. And yet, if you do that for a year you will have added 1 dan of strength to your go program! 1 Dan in 1 year is a lot. But I don't think the engineers in Go programming think like that yet. (Maybe some do, I applaud you if you so.) They seem to get frustrated if they cannot find an immediate big gain and speak of not making progress without some major breakthrough because they cannot imagine their program playing much better without one. The way you make a strong program is 1-10 ELO at a time over months and years. I think it is extremely unlike that anybody will find a single 1 dan idea that is relatively painless to code up. However there are probably many good ideas that will add up to 1 dan with a lot of engineering and tuning and hard work. I admit that a big hurdle with GO is the ability to test 10,000 games (for instance) in a reasonable amount of time. It would probably tax the patience of most GO authors to try to measure small improvements and thus the mentality to only look for big things and dream of major breakthroughs. But I seriously doubt anything that is quickly measured is likely to be found and I'm convinced that even the best ideas need a lot of refinements and engineering - the stuff that takes so long and requires so many games. So my predictions is that without anything really major (but no doubt some new small ideas) we are going to see your KGS 5 and 6 dan and much higher in 5 to 10 years. I'm assuming that the good engineers in computer go will improve on their testing methodology (and I think multi-core newer hardware will make this much easier to do.) Don > Aja > > ----- Original Message ----- From: "Brian Sheppard" <[email protected]> > > To: <[email protected]> > Sent: Wednesday, April 06, 2011 7:00 AM > > Subject: Re: [Computer-go] 7.0 Komi and weird deep search result > > > I spend a lot of time on computer Go, but probably not in the right >> places. >> >> My work currently focuses on expressing positional features using 3x3 >> neighborhoods, so that domain knowledge is easier to express as data rather >> than if/else code. This is useful stuff, to be sure. >> >> Instead, I really ought to build two systems: an MM-based engine to >> prioritize moves in the tree search, and an SB-based engine for random >> search in the playout. I am sure that these would have a much greater effect >> on strength. >> >> But I started the other effort, and I should continue for a while before >> changing. Probably I will do MM next. >> >> Brian >> >> -----Original Message----- >> From: [email protected] [mailto: >> [email protected]] On Behalf Of Aja >> Sent: Tuesday, April 05, 2011 1:35 PM >> To: [email protected] >> Subject: Re: [Computer-go] 7.0 Komi and weird deep search result >> >> I might not really catch what you meant, but I wonder why. :) >> >> Aja >> >> -----原始郵件----- From: Brian Sheppard >> Sent: Wednesday, April 06, 2011 12:29 AM >> To: [email protected] >> Subject: Re: [Computer-go] 7.0 Komi and weird deep search result >> >> I don't know if the worst could be worse; UCT convergence for a 1-ply >> search >> is a probabilistic function with an exponential bound. The bound for an >> N-ply search is a tower of N exponentials: Exp(Exp(Exp(...Exp()))). Ugh. >> >> Because of this bound, guessing good moves quickly is absolutely vital for >> strong play from UCT. Which calls into question why I haven't taken MM and >> Sim Balancing more seriously. :-) >> >> -----Original Message----- >> From: [email protected] >> [mailto:[email protected]] On Behalf Of Petr Baudis >> Sent: Monday, April 04, 2011 10:27 PM >> To: [email protected] >> Subject: Re: [Computer-go] 7.0 Komi and weird deep search result >> >> On Mon, Apr 04, 2011 at 12:56:54PM -0400, Brian Sheppard wrote: >> >>> >> MCTS using RAVE prioritization *does* converge to game theoretic >> >>> values >>> in a >>> >> binary-valued space. >>> >>> >Can you reference some more detailed analysis claiming this? >>> >>> >>> >>> Theorem: In a binary-valued game of finite length, the RAVE score of all >>> winning moves converges to 1, provided that 0 < FPU < 1. >>> >> >> Oh of course, it is obvious. Sorry for being slow and confused. >> >> But it seems it should be possible to prove that even theoretical >> convergence in case of RAVE discrepecancies is much slower than with >> plain UCT... Might be a fun exercise. >> >> Petr "Pasky" Baudis >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> > > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
