Author: Ulrich Tuerke
Date: 08:20:33 08/30/01
Go up one level in this thread
On August 30, 2001 at 10:30:53, Koundinya Veluri wrote: >On August 30, 2001 at 08:46:32, Ulrich Tuerke wrote: > >>On August 30, 2001 at 02:43:17, Pham Minh Tri wrote: >> >>>On August 29, 2001 at 22:09:20, Stuart Cracraft wrote: >>> >>>>So here is a pseudo-code fragment the attempts to implement >>>>futility cutoff but fails. The result is 2.67% less time for the >>>>same search and 4.35% fewer nodes, a far cry from what I heard >>>>it would do. So what's wrong with it? >>>> >>>>for all moves (sorting, etc.) >>>> make move (backup if move leaves king in check and proceed to next move) >>>> # Futility code follows >>>> if side that moved was not in check before move AND >>>> depth == 1 (i.e. 1 move until quiescence search, the "frontier") AND >>>> no extensions so far at this node AND >>>> this is not a principal variation node AND >>>> this move was not a capture AND >>>> side now on move is not in check AND >>>> ((material difference between side on move before move and side now on move >>>> PLUS the maximum of (maximum positional score of side not now on move, >>>> value of a knight) <= alpha) then >>>> unmake the move just made >>>> continue with next move (bypassing this move, i.e. the futility cutoff) >>>> endif >>>>: >>>> search move normally as usual >>>>end >>>> >>>>Stuart >>> >>>I did not see where your qsearch is after pruning. You seem to prune too much. >>>You should prune the last depth, but not qsearch, IMO. >> >>" depth==1 " above means that he only prunes the last ply of the full search (in >>qsearch you'd have depth <= 0). > >But here he's pruning not only the last ply of the search, but also the qsearch >that comes after the last ply. I think a qsearch should be done before the >"unmake move". I do something different. > >This code comes before any moves have been searched at the last ply, but after >the null move is done. > >IF depth == 1 && not extended for check && not extended for mate threat && not a >forced position (according to hash table) && not following pv THEN > window = ???; > qscore = Quiesce(alpha - window, beta + window); > if(qscore <= alpha - window) > return alpha; > if(qscore >= beta + window) > return beta; >END IF > >Seems to be safe and improves speed on tactics a lot, when the correct window is >chosen. Although it may look like a waste doing qsearch for every position at >depth == 1, this does a lot more pruning than it does add to the tree. I tried >the other futility pruning mentioned in the original post, but it didn't work as >well for me. > >Koundinya I understand, quite interesting idea. In fact, I'm doing a bit different too. I start q-search at depth=1 when the cutoff has been triggered (instead of cutting the search immediately). I admit, it seems even safer what you are doing. But there is the risk of searching larger trees instead of smaller ones. Well, perhaps a matter of finetuning your window size as you said. Uli > >> >>I think that this kind of pruning as suggested above is reasonable; I do >>something very similar. Although the benefit is rather modest, it may be >>worthwhile. >> >>Uli >> >>> >>>BTW, I prefer use Eval function to use material only (learn from Crafty 1.5x). >>>It is safer.
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.