Author: Vasik Rajlich
Date: 04:32:03 03/26/04
Go up one level in this thread
On March 25, 2004 at 23:15:00, Johan de Koning wrote:
>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.
>
Yes, this is exactly what I meant.
It's true, though, the math is surprising. As an example:
30^7 = ~21,000,000,000
20^8 = ~25,000,000,000
So f=0.33 won't even take you from 14 ply to 16 ply.
Maybe, reducing really should be the mirror of extending. In both cases, most
moves get the lower depth.
So maybe it's just a question of extending (or reducing the others) because of
some easy property of the extended move (ie Junior ?!), or because of a big
analysis which suggests that the reduced moves are not tactically dangerous (ie
Shredder ?!). Maybe that's the big decision.
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.