Author: Bruce Moreland
Date: 01:01:19 01/26/99
Go up one level in this thread
On January 25, 1999 at 11:36:32, Christopher R. Dorr wrote: >Unless this 'selective search' is different from conventional definitions of >'selective search', selective search is *most definitely* stronger than brute >force. regardless of what the tech guy said. > >The reason is as follows (somewhat simplified). Brute force eveluates *every >position* is every branch of the search tree to a certain depth, dictated by >time constraints. Lets say that (in time control x) that the brute force mode is >able to examine every single position arising from the current position up to >depth 8 ply. That mean that the computer sees *every* possible position that can >arise in the next 4 full moves, and make is decision based on what it can force >within that search depth. > >The selective search mode utilizes it's time differently. It may well search the >first (say) 4 or 5 or 6 plies completely (ala brute force), but it will >selectively search out in certain lines much deeper (say to 10 or 12 or 14 ply). >If the position is tactically intersting (and therefore extended), this mode may >well find a win of a pawn on ply 6/14 (i.e. 6 ply brute force, extended to 14 >ply in certain lines). > >There are, of course, trade offs with each method. The selective search may miss >a tactic in a line that it prunes off at ply 5 at ply 8 in that line that brute >force sees. This isn't terribly likely, as selective search will follow a given >line down further as long as it's tactically 'interesting'. Brute force's trade >off comes because it sees *nothing* beyond a certain depth, because it has to >spend it's time examing every position in it's given search depth, regardless of >how ridiculous or unpromising it might be. > >The trade offs with brute force generally cost a program *far more* rating >points than do the trade offs of selective search. I've owned dozens of programs >and dedicated chess computers, and cannot remember any of them playing as well >with brute force search as with selective search. > >Chris I am coming in late, so if I say something stupid, my apologies. A random tech guy could be living on any planet, he could be talking about "selective search" as meaning a search you do on a machine that is so slow and so limited that you don't even have enough power to look at every reply to every root move. A 3-ply pure alpha-beta search (which is what I would call brute force) should kill this. There is a hardware disparity assumed here, which a random tech guy may consider as part of the whole package. I would call a search that uses null-move forward-pruning a selective search, although it's so easy to implement that it's almost cheating to call it this. It's domain-independent, so you don't have to have any chess brains to do it. A null-move selective search will kill straight alpha-beta in the general chess domain on any computer that wouldn't more profitably be used as a boat anchor. I have no idea how I'd implement other kinds of selective pruning techniques, particularly domain-dependent techniques. If anyone has done this successfully, would you care to comment? bruce
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.