Author: Robert Hyatt
Date: 11:27:21 02/05/04
Go up one level in this thread
On February 05, 2004 at 13:47:39, Slater Wold wrote: >On February 05, 2004 at 13:24:01, Robert Hyatt wrote: > >>On February 05, 2004 at 12:54:08, Slater Wold wrote: >> >>>On February 05, 2004 at 12:50:44, Robert Hyatt wrote: >>> >>>>On February 05, 2004 at 12:46:04, Slater Wold wrote: >>>> >>>>>On February 05, 2004 at 12:22:44, Bob Durrett wrote: >>>>> >>>>>>Referenced by: >>>>>> >>>>>>http://www.talkchess.com/forums/1/message.html?345569 >>>>>> >>>>>>> An alpha cutoff is what happens when you search the second move, >>>>>>>> and you prove that if you play that move, your opponent has a move >>>>>>>> he can play that will produce a score less than your "lower bound" >>>>>>>> you established for the first move. There is no need to search >>>>>>>> further. >>>>>>>> >>>>>>>> For example, after that +1 on the first move, you try the second >>>>>>>> move and after trying the first move the opponent has in reply to >>>>>>>> that move, you discover you _lose_ a pawn. The score is -1.0... >>>>>>>> There is no need to search other opponent moves to produce a >>>>>>>> score even lower than -1.00, because you already know this move >>>>>>>> is at _least_ -1.00 and possibly worse, while the first move is >>>>>>>> +1.00. You stop searching this move and move on to your third >>>>>>>> choice... >>>>> >>>>>I haven't looked at many programs, other than TSCP, source, but I have a few >>>>>question about this also... >>>>> >>>>>When do most engines call the qsearch? After selecting a move believed to be >>>>>correct, of at the end of each search tree? >>>> >>>>When remaining depth = zero. IE if you want to do a normal 3 ply search, and >>>>you have no search extensions, I make a move at the root, subtract 1 from depth, >>>>and recursively call search. There I make a move for the opponent, subtract 1 >>>>from depth and if it is > 0 (2-1 > 0 so true here) I again call search, >>>>otherwise I call the q-search. At ply=3 I make a move for the program again, >>>>subtract one from depth and now call the q-search since depth==0 after the last >>>>subtraction. >>>> >>>>I did 3 full plies of looking at everything, but ply-4 and beyond are captures >>>>only. >>>> >>>>> >>>>>The reason I ask is, say you get a cutoff, because the 2nd move produced -1.0 >>>>>(as in above), but after 4 checks and a capture, you regain that pawn & better >>>>>position. >>>> >>>>Alpha/Beta is called a "depth-first" search strategy, because you _never_ stop >>>>searching before you reach a tip position, therefore in the above you regain the >>>>material before reaching the tip. >>> >>> >>>So the tip, is where captures and checks stop? >> >> >>tip or more commonly "leaf"/"leaves". Yes > >Got'cha. Thanks for clearing that up. > >I think I remember seeing in TSCP source, to extend on checks, but not captures. > But then again, I could be mistaken. I never knew extending on captures and >checks was a 'part' of Alpha/Beta. It really isn't a "part". Alpha/beta defines how the cutoff stuff works. And how the search compares stuff. Search extensions or reductions are a different issue and only affect the test of when to call quiesce() rather than calling search() again recursively. > Makes sense though. I guess I always took >it for granted that was qsearch's function. But I can see now, where that >wouldn't be real helpful, since you don't call eval() after qsearch. :) > >How much time in Crafty is spent in qsearch? Do you do captures or captures & >checks? Just captures, but it is still over 50% of the total search time, because the first call to quiesce is forced when depth=0, but captures beyond that point are optional. > >Thanks again Bob!
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.