Author: Vincent Diepeveen
Date: 13:19:28 09/13/02
Go up one level in this thread
On September 13, 2002 at 12:32:33, Robert Hyatt wrote: >On September 13, 2002 at 08:30:36, Vincent Diepeveen wrote: > >>On September 11, 2002 at 22:09:26, Robert Hyatt wrote: >> >>>On September 11, 2002 at 15:27:32, Dann Corbit wrote: >>> >>>>On September 11, 2002 at 15:10:49, Gian-Carlo Pascutto wrote: >>>>[snip] >>>>>>2. That there is definitely a linear improvement in new CPUs and 64 CPUs is >>>>>>almost exactly twice as good as 32 CPUs. I think that is pretty astonishing, >>>>>>and so however it is that communication happens between nodes should be tried >>>>>>in other systems. >>>>> >>>>>It's a natural consequence of the fact that they have (almost) no >>>>>synchronisation costs. >>>> >>>>Well, that's pretty interesting, isn't it? Can the same model be copied to >>>>other algorithms? >>>> >>>>Surely they have to coordinate the information from the entire set of processors >>>>somehow. The processors cannot be purely independent of one another or no >>>>resolution would be reached. If a similar speedup could be obtained with >>>>another scheme, it might be very valuable. >>>> >>>>Also, since they have done a test with 64 CPUs, I assume that they are using >>>>some sort of NUMA architecture, since there are not many 64 CPU SMP systems >>>>around. Hence, it might scale to stupendous CPU counts like the DoD >>>>supercomputers with thousands of CPUs. If if the efficiency is 1%, if you have >>>>10000 CPUs you will be at 100x the speed of a single CPU system. Maybe no other >>>>system can match that. >>> >>> >>>Two comments to _everybody_ fiddling with this thread. >>> >>>1. The best serial algorithm is generally _not_ the best parallel >>>algorithm. This has been shown over and over and over. The best parallel >>>algorithm, by inverse thinking, is not necessarily the best serial algorithm >>>either. Just because we use alpha/beta today doesn't mean we will be using >>>it in 5 years on massively parallel machines. Quicksort is the best serial >>>sort today. It isn't necessarily the best parallel sort for large numbers >>>of processors. >>> >>>2. Best-first is not thought much of today, because it has never worked well >>>in the past. But that doesn't mean it _can't_ work well, just that nobody has >>>really worked with it anywhere near as much as with Shannon's original minimax >>>approach later augmented with the now infamous alpha/beta modification... >> >>In the general case i don't disagree, but in case of chess i completely >>disagree, assuming a game playing program. >> >>It is well proven that best first search, or any search related to it >>like for example CNS or whatever, that can work pretty well to solve >>certain things. > > >Once again, we need to discuss "proven". Alpha/beta is working well for >chess. That does _prove_ that it works well. It does not prove that it >is the best there is, it doesn't prove that others might not eventually >be better. You can't prove a "not" event... > >All you can say is that "today, evidence suggests that alpha/beta is better >than breadth-first type algorithms..." > >Emphasis on "today". Not really, the statistics show such an overwhelming evidence that it works better to use a depth limited search (either with or without extensions or fractional ply whatever you want to call it, or units or whatever, but DEPTH limited). Not a single researcher who made a best first search program compared their program in game play objectively to an optimized program of their own that's using depth limited search with a bunch of extensions. The few examples we know here, they no longer use best first search... So i don't want to throw all their researches through the toilet, as no one is going to stop them trying, the research is simply not done properly in that respect. > > > > >> >>We see that they solve some tricks pretty quick with best first search. >> >>However, that's a trivial thing to do with best first search. Best first >>search is *known* to work well for problems where the heuristics are >>simplistic and the search space easy to define. >> >>Good example is for example is junior. Just put these tricks at it >>and you'll see it finds it within seconds, because it is extending >>captures and checks more than most other programs do. >> >>Yet their search IS a depth limited search, NOT a best first search. >> >>If we compare a depth limited program optimized to find tricks with >>any best first search, the best first search programs get already >>completely *outgunned* everywhere. >> >>The simple proof is, modify the crafty version they used to solve >>these tricks to a version which gives an extension of 0.5 ply for >>every capture and every check performed. >> >>If you compare that with the teams findings, their best first >>search thing will look immature in all respects. > >Maybe or maybe not, but that only means _their implementation_ might need >more work. It is not a proof of anything about best-first in general. From >a theoretical point of view, both are equivalent. Both in what they can >"see" and in what they "can't". > > > > > >> >>What they do not realize is that captures and checks limit the >>number of 'plausible moves', so it is very likely that best first >>search projects find tricks seemingly fast, whereas the reality >>is that they suck ass. >> >>In case of positional play however, the best first search quality is >>based upon the quality of the estimation which subdomain to search, so >>there it works against them. >> >>We see that world champion junior's real weakness is that if it is >>at a depth of 19 ply, some positional lines which are not trivial moves, >>just sees up to a depth of 5 ply at most, as they have 3 basic >>moves seemingly (perhaps they want to comment on it?) >> - good moves costing 1 unit >> - average good moves costing 2 units >> - bad moves (such as moving a rook to a non-open file) costing 3 units. >> >>Any of such systems completely outgun tactical any best first search >>approach, and i need to note here that junior definitely tries to find >>positional problems. >> >>A simple version of DIEP which i modified to find just tactics in the >>above 1,2,3 unit way (which works 100x better for hashtables than >>fractional extensions, so please do NOT compare it with fractional >>search depths which are EXTENDING rather than doing other things), >>it obviously finds all the tactical tricks at lightspeed, despite that >>it didn't have mating extensions nor singular extensions, which is >>what their 'comments' is in the article. >> >>So throwing rocks at them is not the right thing to do as they prestented >>their results as they were, but obviously i do not share their conclusion >>at all and can in fact EXPLAIN why best first search *seemingly* is not >>too bad with regard to tactics. >> >>The real test to do with their program is of course to play 100 games >>without learning on both sides against other programs with both a >>depth limited version as we all use, and a best first search version. >> >>It says something on how serious we must take their 2 hours project. >> >>>I hesitate to throw rocks at people trying new ideas. Sometimes they waste >>>tons of time, but _sometimes_ they find remarkable results...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.