Author: Robert Hyatt
Date: 07:38:30 04/22/01
Go up one level in this thread
On April 22, 2001 at 05:03:37, Dan Andersson wrote: >One could get a rough idea of the speedup if we think of the problem >asymtotically. If we have a branching factor of ca 40 in chess, 40 processors >would give about one ply more, 1600 processors two ply more. In a-b search >without hashtable I would expect a speedup proportional to the square root of >40, and if the branching factor is lessened due to TT in a constant manner the >formula for a-b with TT would be that constant per ply. The same might or might >not be true for other search refinements. But we could get a guesstimate based >on the effective branching factor for the search. > >Regards Dan Andersson I did a bunch of this math in my Ph.D. dissertation a long time back. The basic finding was that for best-first ordered trees, linear speed-up is not hard with a good splitting algorithm. For worst-first ordered trees (basically pure minimax) linear speedup is also possible. But for real trees, it is much harder due to imprecise move ordering. But in the present case, I read into the question that this was about splitting at the _root_ of the tree only. If that was incorrect, then my answer didn't apply. If my assumption was correct, then a speedup of about 1.5 is all you can get regardless of how many processors you have. And obviously once you get to the number of processors that matches the number of root-ply moves, any more help zero... The real headache is how long the _first_ move takes compared to the remainder of the moves (assuming the first move is actually the best move which is pretty common in today's programs, it happens something like 80% of the time or more.) That is why algorithms like PVS (not the PVS used in serial programs), DTS (Cray Blitz) and Young Brothers Wait were developed...
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.