Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: extensions + reductions + pruning = confusion

Author: Vasik Rajlich

Date: 05:26:05 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*.
>
>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.
>

Ok I'm still slightly new to this - but I meant reductions, not pruning. IMO
pruning is appropriate for near-leaf positions, but bad moves near the root
should be reduced, not extended.

Let me try a reformulation. An "extension-based search" is one in which various
extension rules are applied, each of which is triggered by a fairly small
percentage of the possible moves. (Ditto for a "reduction-based search".) So,
Bob's non-check reduction fails this criterion for a true reduction, since it
triggers too often.

So, practically, an extension-based search would look a bit different than a
reduction-based search.

My theory is that it's cheaper to decide to extend a small class of moves than
to decide to reduce a small class of moves. Junior and Shredder would appear to
support this - Junior appears to search very quickly, and it appears to use
extensions heavily; while Shredder appears to search slowly, and it appears to
use reductions.

Not sure about Chessmaster :-)

>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. :-)
>

There I used the wrong word - I meant "reducing" rather than pruning.

Practically speaking, I am about to get back into making my search selective.
There's a question of framework for doing it. Ie, 1) do you look for moves to
extend, or for moves to reduce 2) do you do a complicated static tactical
analysis to support the decisions. Re. the first question, theoretically it may
end up the same, but the code will look much different, and the evolution from a
flat search will be different.

Vas

>... 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.