Author: Johan de Koning
Date: 20:15:00 03/25/04
Go up one level in this thread
On March 25, 2004 at 08:26:05, Vasik Rajlich 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*.
>>
>>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.
It seems I chose the subject header quite well. :-)
Let me try again ...
You say that extending and reducing searches could be the same.
You say that in practice they aren't.
They aren't because {reductions} is not the complement of {exensions},
because in your view both sets are very small compared to {legal}.
Let's assume I'm with you now ...
Then I think you're not going to gain much by applying reductions rarely.
Even when assuming reduced branches are not searched at all, the math
tells us you gain only (1-f)^(D/2), with f being the fraction of moves
to be reduced. That's not very interesting until f > 0.5 or so.
... 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.