Author: Robert Hyatt
Date: 11:14:43 05/06/04
Go up one level in this thread
On May 06, 2004 at 14:07:02, Robert Hyatt wrote: >On May 06, 2004 at 12:07:47, Gian-Carlo Pascutto wrote: > >>On May 06, 2004 at 12:03:11, Robert Hyatt wrote: >> >>>If you reliably split at ALL nodes, super-linear is nearly impossible to hit. >> >>Yes, but you didn't really split all that reliably at ALL nodes :) I missed that. What are you basing that statement on? If I see a node with 45 moves, and 30 of them have been searched already, chances are _high_ that the rest will be searched. For example: In a match vs GM Paul Van der Steren (I hope that is spelled correctly, my handwriting on this old log file is very faint) I see statistics like this: splits done = 1540 early stops = 146 Early stops are what happens when I sic a processor on a node, and another processor later says "stop what you are doing, I have found a fail high refutation for this position and your work is not needed." Other positions show 2895, 220 for those two, or 3990, 79, or 2334,310. So I don't know what makes you conclude the above without _any_ data of any kind??? >> >>For example, just splitting at the root would already be enough to get a >>few >2.0's. And you did split at the root IIRC. >> >>-- >>GCP > > > >Nope. You are not reading carefully. We chose to accept the overhead of _not_ >splitting at the root for the reasons given in the "splitting at the root" >section of the paper given below. Crafty handles this _far_ better with its >adaptive split/dont-split at the root algorithm. But CB always searched each >root move with all processors, rather than splitting at the root and letting one >processor search each move (more efficient if you don't change your mind). > > >Splitting the search at the root (or not) uncovers some interesting problems. >First, most computer chess programs use the so-called iterated search where a >one ply search is done, then that information is used to order the moves for a >two ply search, and the information from that is used to order a three ply >search and so forth. This process is continued until the time allotted for this >move runs out. > >It should be obvious that the reason for doing a "depth+1" search is to find a >better move than the one found from the "depth" search. Often, the program does >not change its mind from iteration to iteration, and, in such circumstances, >splitting the tree at the root is an excellent idea. After searching the first >root branch completely, searching the remainder in parallel introduces almost no >overhead (some arises due to transposition table interaction.) However, when the >first move searched is not the best, and the program ultimately chooses a >different root move as best, searching root branches in parallel causes a >problem in timed tournament chess games. > >From prior analysis [Knuth75,Hyatt88,Hyatt89,Hsu90] the first branch from the >root produces a subtree much larger than the remainder of the branches (when the >first branch is best.) If the program then must "change its mind" and select a >different move as best, this move will also produce a much larger subtree than >the other moves. This "much larger subtree" causes an interesting problem in >timed events. > >Consider a case where the second branch is really the one that the "depth+1" >search will ultimately select. After searching the first branch (using parallel >processing) one processor selects the second move in the list (that is really >the best move) and starts searching the very large subtree it produces. Other >processors examine other root branches that are unimportant. If time runs out >before the second branch is completely examined, the first move will be chosen, >resulting in the program making a worse move than it really has to. An >alternative is to have all processors work on the first move, then all >processors work on the second move, and so forth. Then, when a new best move is >searched, all processors search it and complete the search before time runs out. > >Some might be quick to suggest that "the search should notice that the >unfinished move has produced a large tree, and is likely about to become a new >best, so don't give up until it has been completed." However, there are two >issues with this: (1) just because a root move produces a tree several orders of >magnitude larger than any other (than the first) root move does not imply that >this move is better. It might be better, or it might simply be a complicated >move that leads to positions which stimulate lots of search extensions and make >the tree quite large. Therefore, it is not safe to simply say the tree so far is >big, wait, because that might take a significant amount of time to finish. And >note the major problem here is that only one processor is searching that branch >should we choose to wait for a result. (2) "Just waiting" is not a particularly >good plan in a timed event. Since time is a factor, using it wisely is a major >part of any chess program, and having to burn many minutes just because the >search can't resolve whether a move further down the ply=1 move list is better >or not can lead to timing difficulties. > >The drawback to solving this is that we "know" that all branches at the root >should be searched (time permitting) and that searching them will cause no extra >overhead (after the first branch establishes a lower search bound, assuming that >the first move is actually the best move. This is true for a large majority of >positions, ). The root is therefore a highly favorable (from a search overhead >point of view) place to search in parallel. If the entire ply=1 move list was >searched, then splitting at ply=1 would work well. However, since time can run >out and stop the search, examining the first few moves on the list (searching >each in succession with all processors working together on each move) ensures >that the first few moves are COMPLETELY examined before time runs out. (Note: in >Cray Blitz and Crafty, an iteration is not completed after time has run out. >Rather, the search stops, the move is made, and then the ponder search picks up >and continues searching.) We chose to accept this inefficiency (searching extra >nodes) in order to let the program change its mind on the last iteration, if the >first move is not best. > >This often leads to a lively debate about (a) whether or not a parallel search >should split at the root and (b) whether or not the program should completely >search the root move list before stopping for a time limit. We have experimented >with possible alternative algorithms, but none have proven better to date.
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.