Author: Tom Kerrigan
Date: 04:49:47 08/07/98
Go up one level in this thread
It's easy to argue semantics on this one. You can be selective by searching move A deeper than move B, as with the null move heuristic. You're "selecting" move A. Cheers, Tom On August 07, 1998 at 05:11:59, Robert Hyatt wrote: >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.