Whether a program is scalable or not has nothing to do with how well it plays at practical time controls. So your whole post here completely misses the point. All you are doing is finding classes of common positions that are really difficult. But I never claimed otherwise. It's like you are trying to argue some point that we do not even disagree on.
Scalability simple means that a program is guaranteed to improve it's general playing ability with ever increasing CPU resources. It doesn't mean you cannot find common positions that would take 1000 or even a trillion years to solve. By your limited definition the best MCTS programs are not scalable and neither are the best chess programs. But of course we know they are. A scalable program will always find the best move, it just may not do it in your lifetime or even the lifetime of the universe. But scalability is not just an abstract theoretical consideration because with ever increasing computing power a program needs to be scalable - you want the program to play better on todays hardware than it did on yesterdays hardware. But please note: being scalable has nothing to do with how good the algorithm or program is and I never argued as such. I also never once argued in favor of not doing heavy play-outs, so STOP trying to convince me they suck, I already know that. In fact you are arguing with the wall because I did write a go program using uniform random playouts and improved it by hundreds of ELO by adding heavy playouts, so I don't understand why you are wasting your time on these painfully obvious examples that nobody here disagrees with. Now, most everything you said is correct, but you did say something that is completely wrong and reveals your ignorance of what scalability means. You said, "If playouts have a strong bias against that correct move, your program is toast, no matter how fast it may be." But that is not true if the program is scalable. The quoted statement is so imprecise that I don't know where to start, but I think what you are attempting to say is that a program with a poor playout policy will take more time than you or I are willing to give it, even on a computer many times more powerful than what we have today. If that is your meaning, then it's true. But if you are serious that "no matter how fast" a computer is it will NEVER find the answer, then your statement reveals a total misunderstanding of how things work. Don On Thu, Jun 2, 2011 at 10:24 AM, terry mcintyre <[email protected]>wrote: > When trying to discover whether a semeai favors white or black, correct > information is far more useful (but harder to discover) than bad > information. If playouts systematically avoid the correct line of play, the > program will lose to any program (or human ) smart enough to exploit that > gap - even if given hours to ponder the move. > > Numerous examples of "snatching defeat from the jaws of victory" semeais > have been posted here, and many more are to be discovered in the KGS > archives. ( BTW, all examples of program winning on time should be reviewed; > at blitz settings, many humans are losing winning positions due to the time > constraints; often programs blitz themselves into losing-but-complicated > situations. ) > > Imagine a line of play in chess where your program has a blind spot - > perhaps a book line where "I just know that the correct move is X", but that > knowledge is wrong - the chess program does not know the correct refutation. > > > In go, many positions are such that you only get one chance to make the > correct move; everything else fails. If playouts have a strong bias against > that correct move, your program is toast, no matter how fast it may be. > > Terry McIntyre <[email protected]> > > Unix/Linux Systems Administration > Taking time to do it right saves having to do it twice. > > > ------------------------------ > *From:* Don Dailey <[email protected]> > *To:* [email protected] > *Sent:* Thu, June 2, 2011 7:25:23 AM > > *Subject:* Re: [Computer-go] Direct DX11 and graphics cards for cheaper > simulation hardware? > > > > On Thu, Jun 2, 2011 at 1:08 AM, Hideki Kato <[email protected]>wrote: > >> Michael Williams: <[email protected]>: >> >Well, not literally useless, as long as you are building a tree equally >> >fast. >> >> Well, but the tree is expanded in a wrong direction, which is also >> useless, isn't it? >> #I'd like to agree to add "almost" is literally correct but I believe >> that speed is really useless in that case. It's unknown if expanding >> tree in wrong directions helps. According to the convergence theorem of >> UCT, I bet this does not help becaues the simulations return wrong >> results. >> > > I don't understand your concept of "wrong direction." When you expand > the tree for ANY move you get more information about how good or how bad > that move is, so it's always helpful (on average) to have more time. > > Of course it's true that you want the highest quality play-outs but it > doesn't follow that extra time doesn't help, it always helps. I think > all simulations return the "wrong results" in many positions and that's why > there is a tree in the first place. Uniform random play-outs return a > less accurate picture but it's still correlated roughly with winning and > losing. > > Many times we make the mistake of trying to turn gray into black and > white because it's often easier to think about that way. There were > numerous examples of that in what you said, for example: "return wrong > results" should be "often returns wrong results" and "wrong direction" I > think you should have said, "tends to expand less relevant parts of the > tree" and "useless" should be "of less value." > > > > >> >> Hideki >> >> >On Wed, Jun 1, 2011 at 8:13 PM, Hideki Kato <[email protected]> >> wrote: >> > >> >> Although speed matters, the quality of simulations is dominant. When >> >> the simulations cannot manage a postion correctly, speed is useless. >> >> >> >> Hideki >> >> >> >> Bojun Huang: <[email protected]>: >> >> >It seems to me that, there is a thread of efforts that try to improve >> the >> >> playing capability >> >> >of GO bots by dramatically increasing playouts/sec. Now we know that >> FPGA, >> >> GPU, and SIMD can >> >> >make much more playouts per second than single-core CPU, but all these >> >> results are based on >> >> >"light" playout schemes. So everytime when these kind of results come >> out, >> >> people would doubt >> >> >the likelihood that these designs really generate strong programs. >> >> > >> >> >So my question is, Is there a "widely accepted" baseline performance >> to >> >> compare with for all >> >> >these works? >> >> > >> >> >For example, we may pick a known program with "lightest" playout >> scheme >> >> among those >> >> >frequently attending the KGS monthly. So if a high-performance design >> >> implements similar >> >> >playout scheme of that program but achieves much higher playout/sec, >> we >> >> could reasonably >> >> >expect a stronger program based on this design. >> >> > >> >> >Another question ... does more playouts really provide a *consistent* >> >> improvement on the ELO >> >> >score, especially for those strongest programs? I remember that some >> >> programs running on >> >> >laptop rank very high in the Olympaids, that seems imply that speed >> simply >> >> doesn't matter >> >> >here ... >> >> > >> >> >Thanks, >> >> >Bojun Huang >> >> > >> >> >>Date: Wed, 25 May 2011 22:23:29 +0200 >> >> >>From: Antoine de Maricourt <[email protected]> >> >> >>To: [email protected] >> >> >>Subject: Re: [Computer-go] Direct DX11 and graphics cards for cheaper >> >> >> simulation hardware? >> >> >>Message-ID: [email protected]> >> >> >>Content-Type: text/plain; charset=ISO-8859-1; format=flowed >> >> >> >> >> >> >> >> >>> Despite the challenges using it in a tree, and the contentious >> issue of >> >> >>> whether light playouts can make a really strong program, I think >> this >> >> is >> >> >>> interesting research. By 1.6 times quicker than libego, do you mean >> as >> >> >>> it runs on the CPU? Or is this a simulated speed as if it was >> running >> >> on >> >> >>> the GPU? I think libego was the clear leader in light playout >> speed, so >> >> >>> working out a way to do playouts even faster (if that is what you >> have >> >> >>> done) is amazing. >> >> >>I just emulated data structures and algorithms that are targeting GPU >> >> >>in C++ for a CPU. 128-bit CPU's SIMD instruction set simply emulates >> 4 >> >> >>GPU-like threads working on 32-bit registers. After several attempts >> >> >>made to test various ideas, the first complete implementation had >> >> >>performances similar to libego, without a simple CPU specific >> >> >>optimization. I then put back some specific CPU optimizations (not >> >> >>likely to be effective on GPU) + tuning and easily improved the >> >> >>performances. This is really how it runs on the CPU. The same data >> >> >>structure and algorithm is likely to have an even better ratio >> against >> >> >>libego with an AVX enabled processor. >> >> >> >> >> >>Light playout was a beginning to start with. The random move >> generator >> >> >>has been designed to take into account a probability distribution >> (with >> >> >>a little slowdown) that can be derived from local pattern matching. >> >> >> >> >> >>Regards, >> >> >> >> >> >> Antoine >> >> >---- inline file >> >> >_______________________________________________ >> >> >Computer-go mailing list >> >> >[email protected] >> >> >http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> >> -- >> >> Hideki Kato <mailto:[email protected]> >> >> _______________________________________________ >> >> Computer-go mailing list >> >> [email protected] >> >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> >> >> >---- inline file >> >_______________________________________________ >> >Computer-go mailing list >> >[email protected] >> >http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> -- >> Hideki Kato <mailto:[email protected]> >> _______________________________________________ >> 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
