Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: futility pruning?

Author: Christophe Theron

Date: 22:57:05 11/10/03

Go up one level in this thread


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 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 the same definition as Uri: I count a move only when I make the move.

That means that I generate more moves than I count (though I try to limit the
generated but not made moves).

I think that's the generally accepted definition of the counted moves by chess
programs.



    Christophe



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.