Author: Dan Homan
Date: 02:00:23 08/07/98
Go up one level in this thread
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
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.