Author: Tony Werten
Date: 22:35:16 10/03/01
Go up one level in this thread
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). 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.