Author: Robert Hyatt
Date: 11:07:02 05/06/04
Go up one level in this thread
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 :) > >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.