Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: extensions + reductions + pruning = confusion

Author: Robert Hyatt

Date: 14:15:54 03/27/04

Go up one level in this thread


On March 27, 2004 at 12:54:57, Uri Blass wrote:

>On March 27, 2004 at 10:38:57, Robert Hyatt wrote:
>
>>On March 26, 2004 at 13:01:17, Uri Blass wrote:
>>
>>>On March 26, 2004 at 12:37:11, Robert Hyatt wrote:
>>>
>>>>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"...
>>>
>>>No a reduction means searching the right position to reduced depth (not the
>>>position with the wrong side to move).
>>
>>No  a reduction means searching to a reduced depth, period, rather than throwing
>>moves out a priori...
>>
>>null-move does exactly that...
>
>No
>
>null move decides to throw all moves out in case that search to reduced depth
>in a position that cannot happen in the game (it is illegal to play null move)
>suggest no threat.

Whether it is legal or not doesn't matter.  Null-move uses a reduced depth
search to decide whether any additional searching is needed.  Forward pruning
just throws moves away period..  It isn't based on any search result...


>
>>
>>
>>>
>>>>
>>>>
>>>>>
>>>>>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...
>>>
>>>Yes but not a search of the right position(side to move is wrong) so it can miss
>>>zugzwang forever.
>>
>>So?  reducing the depth can miss lots of things...  That is a type of error.
>>Forward-pruning introduces its own sort of errors...
>
>No
>
>reducing the depth should still find everything if you search deep enough.

Why?

Every additional ply gives me the chance for an additional reduction.  The net
gain for some moves could be zero.


>
>reduction means searching all moves to reduced depth in case of no threat
>
>
>>
>>
>>>
>>>Uri



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.