Author: Robert Hyatt
Date: 10:29:32 01/25/99
Go up one level in this thread
On January 25, 1999 at 04:12:28, Christophe Theron wrote: >On January 24, 1999 at 23:11:54, Robert Hyatt wrote: > >>On January 24, 1999 at 18:41:13, Amir Ban wrote: >> >>>On January 24, 1999 at 17:31:15, Melvin S. Schwartz wrote: >>> >>>>I contacted a technical advisor from Saitek in Hong Kong who assured me that >>>>Brute Force was superior to Selective Search. His reason was that Brute Force >>>>searches more extensively and therefore minimizes the risk of an occasional >>>>oversight. Apparently the Selective Search is quicker but not as thorough. >>> >>>This can't be right in this day and age. Does Brute Force even exist any more, >>>other than in the initial implementations of amateurs ? >>> >>>I estimate that by making a decision to be brute-force (no forward pruning, no >>>extensions), you lose around 300-400 rating points to start with, meaning that >>>you won't score more than 15% or so against a strong program. >> >>I don't call brute force "no extensions". IE the original chess 4.0, which >>was the first successful brute-force program, had extensions for getting out >>of check, etc... as did we all back then. > > >But by doing extensions, you "select" some lines... You can view this as: you >prune some moves by looking at the history of moves that lead to the position. >The lines that have no extended moves are pruned earlier. > >Extensions = A kind of selection ? > > As I said, my definition of 'selective search' may be somewhat _weak_. But if we say selective == extensions, that to the best of my knowledge there has _never_ been a true brute force program. IE 'tech' in the early 70's extended. chess 4.x and bell in the late 70's/early 80's extended. So what would we call those? To date, they have been called 'brute-force'... because the classic definition of a 'selective' program was a program that makes a-priori decisions about not searching moves, at the point the moves are produced, not after searching them to a limited depth and seeing what that produces. That has generally been called 'forward pruning' and goes back to the days of the Green- blatt program MacHack. That is what I would call a 'selective search'... you generate the moves at a node, and select only a few of them for expansion/ search, throwing the others out with only static analysis... or whatever.. > >>I've always considered brute force to be 'no chess-knowledge-based forward >>pruning'. IE null-move is still a brute-force idea, although it stinks of >>selectivity when you look at what it is doing. But it is ignorant about the >>game of chess, generally, and works just as well in other games that don't have >>zug problems... > >Null move pruning uses chess-dependant knowledge: the fact that generally there >exists a move that is better than doing nothing. As you stated, this would not >apply to any game. For example this does not work in Othello/Reversi... > can't work there because it is possible to 'pass' if you have no legal move, without losing/drawing the game as a result. But in "go" it would work just fine, for example... >Null move also relies on the fact that to create and identify an additional >threat in chess you (generally) need at least 2 more plies (hence the popular >R=2). This fact is often overlooked. > >So I would say that the null move pruning idea uses at least 2 kind of chess >related knowledge. this is a war of semantics. :) Null-move is domain independent, because it works the same in _any_ game where it is applicable. It uses the search and evaluation of the 'host program' which is certainly not domain-independent, but the null-move assumption itself has no chess knowledge of any kind, other than giving someone two moves in a row ought to be a crushing advantage... > > > >>from that perspective, the Saitek guy was probably 1/2 right... because I think >>the 'good commercial programs' are brute force early and selective later. >>where 'early' is close to the root, and 'later' is closer to the leaves. >> >>I call 'selective' a program like my original chess program where we did a _lot_ >>of plausibility analysis and weeded the ply-1 move list from N down to 6-9 moves >>max... ditto for every ply in the tree. _that_ is selective. :) and _very_ >>dangerous too... :) > > >After all this time I realize that we don't have a clear definition of what >"selectivity" really means!!! > >Are extensions (or reductions) a kind of selectivity ? > >Is null move a real selective algorithm ? > >Isn't a standard quiescence search a kind of selective search ? > absolutely, because you generate (maybe) all the moves, but specifically exclude non-captures (in my case, anyway). Even moreso, as I not only exclude non-captures, I exclude lots of captures that a static analysis says are 'bad'. > > > 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.