Author: Christophe Theron
Date: 22:56:35 10/22/99
Go up one level in this thread
On October 22, 1999 at 08:16:29, Jeremiah Penery wrote:
>On October 21, 1999 at 18:26:22, Christophe Theron wrote:
>
>>On October 21, 1999 at 15:55:21, Jeremiah Penery wrote:
>>
>>>We must be using different definitions. I don't consider the use of null-move,
>>>for example, a selective search.
>>> The way I am defining selective search is more like what a human might do. A
>>>truly selective program will completely throw out most of the moves _before_
>>>even really searching them.
>>> For example, in the initial position, a selective searcher might search ONLY
>>>the moves 1. e4, 1. d4, and 1. Nf3. Other moves aren't even considered. This
>>>same strategy applies to _all_ positions.
>>>This is the kind of selectivity they were doing in the past.
>>>
>>>Programs of today, however, use a more brute-force approach. They may
>>>eventually throw out some moves, but only _after_ they are searched and shown to
>>>be inferior. This is the difference.
>>
>>
>>There is no difference. It does not matter what you do to prune away moves. If
>>your definition is simply that to be selective you must not try the move before
>>you prune it away, I don't buy it.
>>
>>You can consider the selection method to be a "black box". You don't have to
>>know what happens inside to say that a program is selective or not.
>>
>>For example you might not really call "makemove" in your selection algorithm,
>>but maybe the things you do act exactly as if you were doing the move and see
>>what happens after.
>>
>>You can define selection the way you propose, but it is too much restricted to
>>be useful.
>
>Maybe I should use 'full-width' instead of where I've been using 'brute-force'.
In fact Bob points out in another post that from a well accepted vocabulary
point of view your definition is correct, for historical reasons (Shanon used it
to describe forward pruning without any kind of search to decide on the pruning,
and did not think about other techniques).
>Would you agree that programs of today are full-width searchers? My definition
>of selective search has been !full-width - that is, programs that examine <=N
>moves/position.
That's not clear. If you examine less moves than there are legaly in a position,
is it still Shannon's definition?
Do you call full width the fact that you generate all moves, look at the
position that arises after each of them, and dismiss some of them only by
looking at the move and/or resulting position?
We really need an accurate glossary somewhere.
> Perhaps the true definition will be somewhere in-between. I
>think the way you define it would make _all_ programs selective searchers. I
>don't think there has ever been a program (other than a program just for the
>sake of doing so) that has not used some sort of extensions, quiescence,
>...<whatever techniques you think determine whether a program is a selective
>searcher>. I'm not really willing to buy this.
We can exclude quiescence search from the discussion if you want.
>But, before Chess 4.x, most of the programs were selective searchers in the
>style I showed - they did such things as search _only_ x moves/position.
>Because of this, these programs could play 49 brilliant moves, even on very slow
>hardware, but then play one horrible move, losing the game.
I have written such programs myself.
>Back then, any sort of full-width search would only reach very shallow depth,
>and so it would be very weak. With their 'true' selective search techniques,
>they were able to reach respectable depths.
>
>>Null move for example, could be implemented to some extend without actually
>>doing the move. In this implementation you would call it selection, in the
>>classical implementation you would say: "hey, this is no selection at all".
>>
>>I think you are going to be upset, but I consider all the following to be
>>selection:
>>
>>* null move and related techniques
>>* extensions
>>* QSearch
>>
>>Selectivity can be additive or substractive. You restrict selectivity to
>>"immediate substractive", but in fact
>
>>doing an extension is substractive
>>selectivity because you are going to look at everything else less deep.
>
>Why would you look at everything else less deep? Or do you mean only less deep
>than the line being extended?
>
>> QSearch
>>is additive selectivity because you generate only some moves, not all.
>
>I'm pretty much ignoring quiescence - it can be considered almost part of the
>evaluation function, because it is used to prevent the evaluation from being
>completely wrong because of tactics.
OK - if you want.
>>With your definition of selectivity you miss all these successful techniques.
>
>I didn't say that with my definition of selectivity one still couldn't use
>extensions. And when depth 0 is reached in the search, quiescense search would
>still happen.
>
>>Anyway, even humans do much more than your definition of selectivity. Almost all
>>moves pruned by humans are pruned because the guy says: "after I play this move
>>the opponent play this one and I don't like the position".
>
>That's only if the move is considered in the first place - Even if there is no
>real refutation, many moves simply won't be considered at all for
>positional/other reasons. For example, after 1. e4 2. c5, a good human probably
>wouldn't even consider Qf3, even though there is no refutation - it is simply a
>pointless move. IMO, of course, because I'm not a 'good human'. :)
I don't see how you can reasonnably discard a move without first look at the
position after the move, at least.
I think that this is a little bit pointless. You can write an algorithm that
does not make the move, but looks at the consequences of the move in such a way
that it's exactly like doing the move and looking at the resulting position.
You could even write an algorithm that does not actually make the move, but is
able to understand the resulting position and some possible moves of the
opponent.
You can call it a different name than another algorithm that does the same but
makes then umakes the move, but still you extract almost the same information
from the position, possibly with the same computational effort.
Call it selection or not, but the name you put on it has little impact on what
it is doing. It is "selective", because the potential tree of this algorithm is
smaller than a "non-selective" version.
Once again, I think we need to give definitions to these terms to avoid future
misunderstandings.
Christophe
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.