Author: Alessandro Damiani
Date: 12:58:48 10/23/99
Go up one level in this thread
On October 23, 1999 at 10:32:26, Robert Hyatt wrote: >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." > Yes, null-move does a search. The point is: every artificial pruning decision is based on information. Where this information comes from is not important (black box). Whether the information comes from static knowledge or from a search doesn't change the way it works: if information tells to cut-off then do cut-off before searching all moves > > >>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. yes, backward pruning is mathematically correct. Null-move makes the decision before searching the LEGAL moves. You say before ANY searching is done, but we don't have to forget that null-move is not a legal move. Searching the null-move doesn't mean we already search the subtree, since the subtree starts with LEGAL moves. Alessandro
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.