Author: Tord Romstad
Date: 08:35:59 08/12/04
Go up one level in this thread
On August 12, 2004 at 10:52:36, martin fierz wrote:
>thanks for the clarification! so you really RETURN when your
>almost_certainly_fail_high function returns true? isn't this a bit dangerous? i
>mean, probably it helps, but i can imagine that there are positions where
>gothmog will never find the right move because your almost_certainly_fail_high
>function returns 1 in a position where it shouldn't.
This is not a problem, because such pruning is not done when the remaining
depth is too big. Except in some very unusual cases, I only do it when
the remaining depth is 3 plies or less. More about this below.
>my philosophy (in my checkers program, my chess program is not in a stage of
>having a philosophy yet...) was always to make big reductions in depth possible,
>but never to allow a complete return - because then you can have such effects
>that you can never solve a position.
I agree with everything you write above. In my previous posting, I talked
about the distinction between pruning techniques for fail-high nodes and
techniques for fail-low nodes. Another useful distinction is between
pruning techniques which are useful when the remaining depth is big
and techniques which are useful when the remaining depth is small.
When the remaining depth is big, I think that successful pruning
techniques must be based on some kind of internal reduced-depth searches.
Recursive null-move, multi-cut, ProbCut and reducing the depth for moves
late in the move list are examples of this. Closer to the leaves, I think
static techniques are more effective. Razoring and futility pruning are
good examples.
My "almost certainly fail high" test essentially contains of a crude static
estimate of the return value of a null move search. I take the static
eval of the current position, subtract the value of capturing the
highest-valued hanging piece of the side to move, and compare the result
to beta. If it is bigger than beta, I return a fail high score.
In my experience, the risk when doing this kind of pruning is rather low,
as long as you do it only when the remaining depth is no more than 2 or 3
plies (i.e. when a null move search would drop us directly to the qsearch),
and there are no serious "warning flags" (advanced passed pawns, pinned
pieces, poor king safety, etc.) in the position.
A brief summary of the pruning systems discussed, sorted by the type of
node where they are useful:
+-----------------------+-----------------------------+
| Fail high nodes | Fail low nodes |
+----------------------+-----------------------+-----------------------------+
| | * Recursive null move | * Reduced-depth pre-search |
| Big remaining depth | * ProbCut | of moves late in the move |
| | * MultiCut | in the move list |
+----------------------+-----------------------+-----------------------------+
| | * Futility pruning | * Static null move pruning |
| Small remaining depth| * Razoring | |
+----------------------+-----------------------+-----------------------------+
Additions to the table are welcome, particulary for the upper right hand
corner.
Tord
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.