Author: Robert Hyatt
Date: 07:32:26 10/23/99
Go up one level in this thread
On October 23, 1999 at 05:30:05, Alessandro Damiani wrote: >On October 23, 1999 at 02:31:23, Will Singleton wrote: > >>On October 23, 1999 at 01:37:47, Christophe Theron wrote: >> >>>On October 22, 1999 at 13:08:44, Robert Hyatt wrote: >>> >>>>On October 21, 1999 at 15:55:21, Jeremiah Penery wrote: >>>> >>>>>On October 21, 1999 at 12:54:47, Christophe Theron wrote: >>>>> >>>>>> >>>>>>But no program of today do brute force. All the good programs are highly >>>>>>selective. >>>>>> >>>>>>If you are not talking about "true brute force" (simple-alpha beta + QSearch) I >>>>>>don't know what you mean. Everything else is selective. >>>>> >>>>>We must be using different definitions. I don't consider the use of null-move, >>>>>for example, a selective search. >>>> >>>> >>>> >>>>A word of caution. "selective search" has a precise definition in the CS >>>>literature, dating all the way back to Shannon's "How to program a computer >>>>to play chess" in the 1950's. >>>> >> >>I believe it was 1947-48, but I don't have my ICCAJ here... my Dad and Claude >>used to play a lot in NY around that time. >> >> >>>>Selective search means, very explicitly, to generate all moves at a node in >>>>the tree, and then to dismiss some of those a priori without any searching of >>>>any kind. This is also called 'forward pruning'. >>>> >>>>The idea of selective extensions was mentioned by Shannon, in the context of >>>>what he called a "variable depth search" which is exactly what all of our >>>>extensions and null-move reductions actually accomplish. >>>> >>>>I personally don't call a "null-move search" a "selective search" because it >>>>is an incorrect term of a previously established term. Any more than I would >>>>self-define the term "ampere" to mean resistance, rather than using the more >>>>accepted "Ohm". I don't know of anyone doing what I would call purely >>>>selective search, although our q-search is a perfect example, since we toss >>>>out some moves with no searching of any kind, while keeping others and searching >>>>them deeper, all in a pretty arbitrary way. >>>> >>>>It makes more sense to keep a common vocabulary when we discuss things so that >>>>every post doesn't require a personalized "glossary of terms" so that we can >>>>communicate. :) >>> >>> >>>You are right. It is indeed better that we all use the same vocabulary (and the >>>idea of a glossary in the "Computer Chess Resource Center" pops up again). >>> >>>But in this case, how can we call the kind of "selectivity" we get from, for >>>example, a null move search? >>> >>>Are we going to call this "variable depth search"? It's pretty misleading I >>>think. >>> >>>It is true that we would need some discussion about these terms. The terms >>>"selectivity" and "full width" are often misunderstood. >>> >>>A suggestion, the null move selection could be put in the category of "dynamic >>>selectivity" (or dynamic pruning) instead of simply "selectivity", to emphasize >>>on the fact that selection is decided by a search? >>> >>>What do all interested readers think? >>> >>> >>> Christophe >> >>I do think it's interesting how the language has evolved. I'm not so sure that >>we ought to be bound by what was originally intended by a particular term. >>Selectivity, for example, used to mean something other than what it does today; >>no one implements his program in the old sense of the word. Same goes with >>razoring, cut, and others. >> >>I don't know whether it's possible to get folks to agree on these definitions, >>since the literature itself presents conflicts. It would be a noble experiment >>to try to define the terms, however, and perhaps useful for many programmers >>here. >> >>Will > >Forward pruning is the opposite of backward pruning. With this in mind I would >say null-move is forward pruning: it prunes before the subtree is searched. > but it doesn't. It does a search itself, to make the pruning decision. That is far different from just saying "I am not going to search this group of moves because they don't appear to be interesting, but I am going to search this other group of moves because they are interesting." >Forward pruning should be the name of a general technique and not only for >excluding moves from search (like Qsearch). > >I would make two classes: forward pruning, backward pruning. > >Alessandro Both are already defined very precisely in the literature. 'backward pruning' is what alpha/beta does. it uses search results to make decisions about which branches can be pruned. Forward pruning makes decisions _before_ any searching is done.
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.