Author: Johan de Koning
Date: 14:27:17 03/27/04
Go up one level in this thread
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"... It is if you consider null moves to be part of M, as I wrote 1 line down. But the equivalence of extension based and reduction based searches will start to look silly then. >>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... >:) Technically I'd say it is pruning unless you allow null moves in the PV. And I think I'll skip the religious part for this once. :-) ... 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.