Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: extensions + reductions + pruning = confusion

Author: Robert Hyatt

Date: 13:40:26 03/25/04

Go up one level in this thread


On March 25, 2004 at 01:56:43, Johan de Koning wrote:

>On March 24, 2004 at 11:09:41, Robert Hyatt wrote:
>
>>On March 23, 2004 at 05:05:56, Vasik Rajlich wrote:
>
>>>Junior, however, appears to come at the problem of selective search via
>>>discussions about this in the CCC archives. Amir has claimed that the best way
>>>to search selectively is via extensions. To complete the reductions vs
>>>extensions thought from above, an extension strategy will have the profile that
>>>most moves have the same basic search depth, while certain special moves will
>>>have a higher search depth. The profile of a search based on reductions compared
>>>to a search based on extensions will be different.
>>
>>It is easy to prove that last statement wrong.
>>
>>You write a program that only does search depth reductions.  I write a program
>>that only does extensions.  I can make mine _identical_ to yours.   Where you
>>reduce, I do nothing.  Where you don't reduce, I extend.  IE if you don't reduce
>>a check, I extend the check.  We search _exactly_ the same tree.
>
>Indeed, assuming fractional plies, it is rather trivial to build
>the same tree using either extensions or reductions.
>
>But it's better to avoid the term "reductions" since it is confusing.
>The real issue is extensions versus *pruning*.

Let me define _my_ vocabulary to avoid further confusion.

1.  Extension.  extending the depth of a move based on some property it
exhibits, such as being a check or whatever.

2.  Reduction.  Reducing the depth of a move based on some property it exhibits,
such as not being a capture, check, threat, etc.

The two terms are inverses.  I can extend the set of moves {X} or I can reduce
the set of moves {M-X} and get _exactly_ the same result, to the node.  Note
that M is the set of all moves we will search.

3.  Forward-pruning.  Taking some set of moves at the current ply and throwing
them out with no additional searching of any kind.

4.  Backward-pruning.  IE alpha/beta pruning that doesn't change the final
result at all.


>
>Assuming Vasik intended "pruning" in that last statement, he is
>quite right: different profiles (called search envelopes by Beal).
>And *very* different back-up values.
>
>To add to the confusion an, earlier (snipped) paragraph from Vasik's:
>| Of course, in principle there is no difference between
>| selective search via pruning and selective search via extensions, the two
>| approaches could be equivalent.
>IMHO that is the right words but the wrong conclusion. :-)
>
>... Johan



This page took 0.01 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.