Author: Uri Blass
Date: 08:54:18 10/03/01
Go up one level in this thread
On October 03, 2001 at 10:32:35, Robert Hyatt wrote: >On October 03, 2001 at 10:12:49, Uri Blass wrote: > >>On October 03, 2001 at 09:42:58, Robert Hyatt wrote: >> >>>On October 03, 2001 at 09:12:59, Vincent Diepeveen wrote: >>> >>>>On October 02, 2001 at 04:54:13, Bruce Moreland wrote: >>>> >>>>>On October 01, 2001 at 00:36:48, Robert Hyatt wrote: >>>>> >>>>>>On September 30, 2001 at 14:47:21, Bruce Moreland wrote: >>>>>> >>>>>>>On September 29, 2001 at 14:54:03, Robert Hyatt wrote: >>>>>>> >>>>>>>>On September 29, 2001 at 10:41:37, Miguel A. Ballicora wrote: >>>>>>> >>>>>>>>>Super-linear speedups are "probably" impossible but so far I did not see that >>>>>>>>>they are "provably" impossible. I would settle with "They are believed to be >>>>>>>>>impossible". >>>>>>>>> >>>>>>>>>Regards, >>>>>>>>>Miguel >>>>>>>> >>>>>>>> >>>>>>>>They simply _are_ impossible. Unless you believe in perpetual >>>>>>>>motion, infinite compression, a fire that will burn forever, etc. >>>>>>> >>>>>>>Take a human who can move a 200-pound box, but only by scraping it along the >>>>>>>ground. Compute the time it takes him to move 10 such boxes 100 yards. >>>>>>> >>>>>>>Assume that two humans can move a 200-pound box more easily. Can they move a >>>>>>>200-pound box more than twice as fast as one human? Would this violate laws >>>>>>>against perpetual motion? Of course not. It is perfectly valid to consider >>>>>>>working in parallel rather than working serially. The mechanics of the task >>>>>>>might change, resulting in much increased efficiency -- they can lift the box >>>>>>>off the ground. >>>>>> >>>>>> >>>>>>I think that after you think about this example, you will see the flaw. >>>>>>Lifting the box off the ground takes _more_ effort. So the two people are >>>>>>doing _more_ work in a given period of time than two people pushing two boxes >>>>>>at the same time. The ancient Egyptions found that dragging was better than >>>>>>lifting. :) >>>>>> >>>>>> >>>>>> >>>>>>> >>>>>>>Two workers cooperating to perform a task, do not *have* to go less than or >>>>>>>equal to the speed of two workers, each of whom does exactly half of a task that >>>>>>>can be fairly divided in two. >>>>>>> >>>>>>>There exists the opportunity for synergy. >>>>>>> >>>>>>>The argument that the above violates the prohibition against perpetual motion is >>>>>>>fallacious. >>>>>>> >>>>>>>bruce >>>>>> >>>>>> >>>>>>Not after you think about it. If two people work and each of them moves 5 >>>>>>blocks, then they do no more work than the 1 person did moving 10. But they >>>>>>did it in twice the time. If they _lift_ the block _and_ move it, they are >>>>>>doing _more_ work per unit of time. They should have moved the blocks >>>>>>faster one at a time, but they were taking it easy... >>>>>> >>>>>> A computer can't do that. >>>>> >>>>>You can't possibly be arguing that there is nothing that N (N>1) people can't do >>>>>in less than 1/N the time that it takes one person. >>>>> >>>>>I was trying to find an obvious example. If you don't like that one, I'm sure >>>>>there is another one. >>>>> >>>>>bruce >>>> >>>>Obvious example is killermoves. It improves branching factor too. >>> >>> >>>You can't improve branching factor beyond the normal serial search branching >>>factor. >> >>It is truth only if the normal serial search is perfect and cannot be improved. >>I do not believe in it. >> >>Uri > > >Believe what you want. If you believe random chance is going to improve the >branching factor consistently, be my guest. But random chance is all you get >when you search in parallel and find a better move quicker. The average case >is _not_ going to make that happen. > >super-linear speedup is simply _impossible_. I can't say that strongly enough. >I am backed up by people like Knuth. Pretty good company. The timeslicing >idea is _the_ refutation to any of this. 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. 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
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.