Author: Robert Hyatt
Date: 02:11:59 08/07/98
Go up one level in this thread
On August 07, 1998 at 05:00:23, Dan Homan wrote: >On August 07, 1998 at 01:19:09, Jeff Anderson wrote: > >>How exactly does a selective search work? Does the program search to a certain >>depth x then eliminate the worst moves, and then search the ones it did not >>eliminate? If so at what depth does it do this? Does it only do this once, or >>does it perhaps eliminate more moves deeper in the search, removing more and >>more moves as the search progresses? Is the number of moves eliminated >>dependent on the position? If any of the programmers, or anyother computer >>chess erudite could describe in detail how it works, I would be grateful. >>Jeff > >There are many ways to be selective. Here are 3 common ones used in most >(but not all) modern programs. > >1) Null move: Allow your opponent to make 2 moves in a row and then search > to a shallow depth (maybe 2 less ply). If the position is > still good for you (better than beta), then selectively ignore > that part of the search tree. > >2) Extensions: Selectively add search depth to certain lines that look > interesting. Perhaps they will have a check or a re-capture > or maybe a pawn push in the endgame. > >3) Razoring: Razoring is the opposite of extensions. Near leaf nodes > (deep down in the search) examine the position to see how > important it is likely to be. Is the material imbalance > keeping the score well below alpha? If so, reduce the the > search depth for any moves that aren't likely to help. > >Some programs use knowledge-based pruning rather than null-move. My program >only uses the 3 techniques above, so I don't have much experience with that. >My guess is that they combine some sort of swap-off routine with positional >knowledge to prune moves. I don't know if they prune more near the root >or deep in the tree. Pruning near the root means a much smaller search, but >could lead to gross errors. They probably have some sort of progressive >routine which moves the pruning to deeper depths as the search depth >increases, but I am really just guessing. > > - Dan Those are all good explanations, but your last paragraph really gets to the point of selective searching. "selective" as in not expanding all possible moves into sub-trees, rather tossing some out before doing *anything*. Null- move doesn't do this... it just reduces the depth of "uninteresting" branches to make them easier to search, giving more time for searching "interesting" moves. But with a selective search, you generate the list of moves, and without a full search, you throw some out immediately. Which means you won't have much of a clue about how they turn out. This was used heavily in the 60's and 70's (early 70's) but was tossed out as too dangerous as machine speed improved to the point where "exhaustive" move selection could be used without compromising on the search depth...
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.