Author: Robert Hyatt
Date: 18:56:20 02/09/98
Go up one level in this thread
On February 09, 1998 at 19:06:18, Don Dailey wrote: >Hi Bob, > >Here is my "opinion" on the subject. I realize it is only an opinion >and am NOT trying to refute you. In fact I am probably agreeing >with you at least in principle. > >In experiments I've done the selective version seems to get better with >depth (relative to full width) which seems to be the opposite of what >you >are saying. Against humans, I'd buy this instantly. Because you can afford to give up some accuracy at deeper depths, knowing that the human is likely not going to be able to mentally follow every variation and find that move you overlooked. But against another computer, this can be a problem... IE one example was the genius vs Cray Blitz match a few years ago. It was really ugly, and was *always* marred by a tactical flaw by genius, at a depth that would probably not be a problem with humans, but which was disastrous against CB. > >But the real question is what is selectivity? I don't beleive my >program >is selective although I make heavy use of null move prunning. >Basically >I have a strong full width component, after 8 or 9 plys I increase the >full >width depth on each iteration. > >Richard Langs program was always considered highly selective but his >program should also be considered a full width program (by my >definition.) I agree. Cray Blitz had three parts to the search: (1) full width for N plies (2) selective for M plies; (3) q-search. I never got overly wild with (2) however, and generally (2) was perhaps 1/4 of the total depth of (1) if that makes any sense to you... > >Does your program have a full width component? The old full width >programs had a selective quies search (just as ours does) but no one >considered them selective searchers. My program just extends this >a little more. It's a matter of semantics. yep... > >A truly selective program in my opinion will have the characteristic >that >there are certain tactics it will miss and never ever see even on a >computer >of infinite speed. > >Null move is a special case if done infinitely deep. Although it does >pretend >to have a full width base (due to the depth-n mechanism) this can be >wrong >since it's based on an incorrect assumption. The assumption is >that it's always at least as good to be on the move than not. When it >is >wrong there are tactics your program will never see no matter the depth. > >If your program does not gradually increases the full width component of >the search with increasing depth, then I believe this is a mistake and >true full width programs will overtake you at some depth level. But I >also believe limtied but agressive pruning near leaf nodes will always >be an improvement over a pure brute force program. I agree. I saw this with Genius a while back.. > >How much pruning? I don't know. Like you said, as you get deeper it >takes more effort not to kill overall performance with pruning. I >believe >there is a limit around 10 ply (give or take 5 ply or so) after which >even >a very occasional error limits your performance too much. > >- Don > > > > >On February 08, 1998 at 17:09:28, Robert Hyatt wrote: > >>On February 08, 1998 at 14:10:44, Don Dailey wrote: >> >>>Hi Bob, >>> >>>>it was "debunked" because of hardware issues. Chess 4.6 searched 6 >>>>plies >>>>full-width on a cyber 176. Mac Hack could barely search 5 plies, with >>>>no >>>>q-search, using severely tapered forward pruning, because of hardware >>>>speeds >>>>in the 60's... IE Greenblatt couldn't even do a 2 ply search full-width >>>>at those speeds. >>>> >>>>What selectivity is all about is being careful at the root by going >>>>full- >>>>width, and taking risks farther out in the tree where you believe that >>>>even >>>>if you make a mistake, you have time to catch it in the full width part >>>>of >>>>the search next time and "fix" it. >>>> >>>>It's a trade-off... do you want to find deeper tactical things? Or do >>>>you >>>>want to find deeper positonal things? Selectivity overlooks things. No >>>>way to avoid it. Question is, does what it find offset what it >>>>overlooks? >>>>Good question. But your estimate of +100 is simply a wild guess. I'd >>>>suspect that a good brute-force program will play just as well as a good >>>>selective searcher. They will each find things the other overlooks. >>>>The >>>>selective searcher will find deeper things, the full-width searcher will >>>>find things the selective searcher pruned away in error. >>>> >>>>Take your pick. I tend to err on the side of simpler algorithms... >>>>fewer >>>>bugs means more wins... >>> >>> >>> >>>You need to expand on your statement that a good brute-force program >>>will play just as well as a good selective searcher. I don't agree >>>with this unless you are talking semantics (like calling Richard Langs >>>program full width because he does a few full width plys.) Marty's >>>program may be the closest thing among the really strong ones but I >>>think he just put's all the selectivity in the quies search. >>> >>>- Don >> >>Here's what I "think": >> >>A full-width search is going to hit N plies deep, using traditional >>ideas >>like iterative deepening, etc. >> >>A selective program is going to reach depth N+X, where X depends on how >>aggressively they prune in the forward direction. IE null-move is one >>way, static analysis is another, etc. >> >>When I talk about "selective" vs "brute-force" however, the idea is >>this: >>to selectively throw out moves (or selectively include them in the >>search) >>requires a finite amount of computation. To make this more accurate >>ramps >>this requirement up. What if it ramps it up enough that the very >>selective >>program does just as much work analyzing what to prune as the full-width >>program spends searching those moves that are no good? >> >>Something tells me that both converge to the same asymptotic bound at >>some >>point. IE I think it is just as hard to cull moves as it is to search >>them, >>if it is intended to beat world-champion class players. My old >>selective >>program looked like a genius in some positions, and like an idiot in >>others. >>Too many of the latter will kill overall performance, no matter how many >>times you look like a genius. It's far easier to lose based on one bad >>move than it is to win after playing 3 fischer-like moves... Selective >>programs run a risk of dumping a bad move here and there... whether the >>selectiveness comes from null-move (crafty) or something else (rebel, >>etc.)
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.