Author: Robert Hyatt
Date: 11:29:31 10/04/01
Go up one level in this thread
On October 04, 2001 at 06:50:37, Tony Werten wrote: >On October 04, 2001 at 01:35:16, Tony Werten wrote: > >>On October 03, 2001 at 14:05:27, Robert Hyatt wrote: >> >>>On October 03, 2001 at 11:54:18, Uri Blass wrote: >>>> >>>> >>>>I did not say that super linear improvement is possible for the best search >>>>algorithm. >>>>The point is that I believe that humans did not find the best search algorithm. >>>> >>> >>>That I won't address. But at the moment, minimax with alpha/beta pruning is >>>the best there is. And _that_ will not produce a super-linear speedup. In >>>fact, _no_ algorithm can possibly produce one, if the comparison is done the >>>right way. A new search paradigm might produce a speedup > 2 using two >>>processors, if it is compared to serial alpha/beta. But then that new paradigm >>>would produce a speedup > 1 when compared with a 1-processor new algorithm vs >>>1 processor alpha/beta. >>> >>>Can't compare apples and oranges. >>> >>>And if you compare apples to apples, a super-linear speedup is impossible. >>> >>> >>> >>>>I do not express an opinion about the question if Diep has super linear >>>>improvement. >>>> >>>>I believe that nor Diep neither other programs are close to have the best >>>>possible search algorithm. >>>>One of the reason is the fact that Diep and most of the other programs do not >>>>use pruning rules except null move. >>>> >>>>I do not say that finding good selective search rules is an easy task and it is >>>>possible that we need a lot of programmers to investigate the problem if we want >>>>to get a big improvement by selective search but I believe that it is >>>>theoretically possible by thousands of pruning rules (when everyone of them may >>>>be relevant only in 1/1000 of the cases) to get a significant improvent. >>>> >>>>Uri >>> >>> >>>Nothing wrong with any of what you wrote. But it doesn't contribute to the >>>super-linear speedup discussion. I'm still waiting on any algorithm that >>>someone claims produces a super-linear speedup when comparing the same algorithm >>>with 1 processor to the same algorithm with > 1 processors, for any N they >>>choose. Simple math will poke a hole in any such example... >> >>Yes, putting it this way. >> >>I'll even go further. A serial algoritm will give a zero speedup on a >>multiprocessor since it will only use 1 processor. >> >>That's the whole point. A parallel search is by definition different from a >>serial search. This difference could have an additional value > than the >>parallel overhead. That was what this discussion was about (at least mine). > >Maybe not totally clear. (I wrote this while having my first cup of coffee.) > >What I mean is that by searching parallel, it's the parallel search itself that >already changes the algorithm since you are searching a different tree. So it >seems impossible to have the same algoritm for 1 as well as 2 processors. However, this is _exactly_ what everyone does. Alpha/beta minimax is _the_ algorithm everybody uses. It has a very well-defined sequential property that is part of the formulation of the algorithm. And that sequential property is the thing that prevents us from getting "linear" speedup at all. Super-linear is simply impossible. Just run the dual-thread application on 2 cpus and it runs 3 times faster? Then run the dual-thread application on 1 cpu and it will run 1.5 times faster. It _must_. > >If they were doing precisely the same work, then I agree that the speedup is >plain the number of processors. But since they are searching different trees, >there might be benefits that aren't there when searching serial. There might be. But there are _more_ negative things. Because alpha/beta depends on serial order of searching to establish a bound before using that bound to prune other branches. If you search there in parallel, you are searching the second branch without information you would have in a pure serial search. That kills... > >BTW it doesn't have to be a bigger np/s, less nodes to solution would be nice >too. > NPS is not the issue here at all. Time to solution is what is being measured. Doesn't matter whether it requires more nodes or less nodes, or whatever. It just can't produce the result in less than 1/2 the time, over a reasonable number of test cases... >> >>Tony
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.