Author: Tony Werten
Date: 02:58:52 11/10/03
Go up one level in this thread
On November 10, 2003 at 05:10:43, Uri Blass wrote: >On November 10, 2003 at 04:50:49, Tony Werten wrote: > >>On November 10, 2003 at 04:30:16, Uri Blass wrote: >> >>>On November 10, 2003 at 02:27:53, Tony Werten wrote: >>> >>>>On November 09, 2003 at 07:40:38, scott farrell wrote: >>>> >>>>>On November 09, 2003 at 04:55:40, Matthias Gemuh wrote: >>>>> >>>>>>On November 09, 2003 at 03:53:24, Daniel Shawul wrote: >>>>>> >>>>>>> >>>>>>> >>>>>>>>I do not remember if Ernst's paper said that you make the move first and then >>>>>>>>decide if it is futile. >>>>>>>> >>>>>>>>If it did, then it's definitely killing all the interest of futility pruning at >>>>>>>>depth 1! >>>>>>>> >>>>>>>>The idea is to prune before you make the move. So you stay at depth==1, look at >>>>>>>>the move, and say "hey, this move looks completely futile, let's ignore it!". >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> Christophe >>>>>>> >>>>>>>A futile move is futile before you make or after you make it. >>>>>>> before >>>>>>> mat_bal + move_gain + margin < alpha => futile move >>>>>>> after >>>>>>> mat_bal + margin < alpha => futile move >>>>>>>Anyway my question is since you go directly to quiescent search >>>>>>>(where stand pat cutoff of all futile moves occur) after making the move, >>>>>>>we only saved ourselves "making of the futile moves".I can comprehend the >>>>>>>extended futlity pruning but not this.For me as long as standing pat cut off >>>>>>>is there , futility pruning at frontier is unnecessary,and if it is,it only >>>>>>>saves the time to make and unmake futile moves.Where does the 60% tree shrinkage >>>>>>>comes from?Please try to see where my proble is. >>>>>>> >>>>>>>Daniel >>>>>> >>>>>> >>>>>> >>>>>>Your logic seems sound for me. We seem to save only >>>>>>MakeMove() + UnmakeMove() + Evaluate(). >>>>> >>>>>I think you are wrong, you save: >>>>> >>>>>MakeMove() + UnmakeMove() +alphaBeta()+ qSearch()+ stand-pat+ Evaluate(). >>>>> >>>>>qsearch of course can be a few plies also. >>>> >>>>No, only when you were wrong. That's the whole point with futility pruning, it >>>>only saves nodes when you were wrong. >>>> >>>>Normal: Make move, goto quiescence, eval>beta, cutoff. go back, unmake move. >>>> >>>>pruning: "eval" <alpha, skip. >>>> >>>>You save 1 make move, 1 function call, 1 eval and 1 unmake move but never a >>>>node. >>> >>>It is because you have different definition of node than me. >> >>No, you have a different definition than us :) > >I am not sure if there is a common definition for all the other programs. >I copied the idea of counting nodes in every makemove from tscp(I am not sure at >this moment if it counts nodes in every makemove or does something equivalent). > >Tscp does not use pruning but I did not see a reason to change my definition and >I only need number of nodes for search decisions (for example check times every >x nodes). > >> >>>I have nodes++ only when I make moves. >>> >>>Makemove is for me something expensive as I explained in another post. >> >>That wasn't really my point. My point was that if you count a skipped move the >>same as a made move, you should get the same count. The only time it is lower is >>when you were wrong. >> >>So you basicly can't search 60% less nodes though it's possible to spend 60% >>less time. >> >>Counting the skipped move seems logical, otherwise I have some more fantastic >>pruning algorithms with no sideeffects. "Never count positions on the last ply" >>is one of them wich saves over 70% of your nodes. >> >>Tony > >I have only one nodes++ in my program. >Doing it in the way that you suggest will force me to have nodes++ in more than >one place in my program. > >If I understand correctly you consider as a node every move that you consider to >make. No I don't. What I am saying is that when somebody says that futility pruning saves 60% nodes there are only 2 possibilities: 1) He is not searching less nodes, he is just counting them less often 2) He is really searching less nodes wich can only be done when the assumption "score cannot reach alpha" was wrong. Tony > >You may generate all moves and not consider all move as nodes but as soon as you >go to the next move in the list you consider it as a node. > > >Uri
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.