Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: extensions + reductions + pruning = confusion

Author: Robert Hyatt

Date: 09:37:11 03/26/04

Go up one level in this thread


On March 25, 2004 at 22:52:02, Johan de Koning wrote:

>On March 25, 2004 at 16:40:26, Robert Hyatt wrote:
>
>>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.
>
>Fair enough, but null moving doesn't fit in your vocabulary.

Actually it does.  It is a "reduction"...  The reduction is "R" and it is done
when the shallow search can't find bad after I "pass"...


>
>One solution is to define null moves as part of the reference tree
>(a search that utilizes 4. at most).
>
>Another way is to allow searches under 3. After all, null move is an
>estimate *and* it is used to disqualify members of M. That's sounds
>like pruning! :-) And after hiding the null searches in an (expensive)
>black box there is no difference at all.


Note it really doesn't prune, as in throwing things away with no search, it does
a search to a reduced depth...

Whether that is pruning or not is probably a religious vs technical argument...
:)


>
>... Johan



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.