Author: scott farrell
Date: 17:30:15 12/29/03
Go up one level in this thread
On December 29, 2003 at 15:26:27, Geoff wrote:
>Hi
>
>I have attempted to implement futility pruning for the first time today in my
>program. I was expecting it to be fairly straightforward to get working as far
>as reducing the number of nodes searched.
>Unfortunately I hit a strange problem that when I enable my futility and
>extended futility pruning I generally see an increase in the number of nodes
>searched and the time to depth can be greatly increased !!
>This weird effect is due to my beta cutoffs being made lower, I would guess I am
>seeing a typical 90% beta cutoff on the first move being reduced to 80% once I
>switch on the futility pruning. I wasn't anticipating this and for the moment
>cannot see a reason why it should have this adverse effect on my beta cutoffs ?
>Has anyone come across this problem before, or any ideas what could be going on
>? I have included a code snippet at the end in case I am doing something stupid
>? I wish the search archive was working as there is probably tons of relevant
>info on this topic. Thanks for any advice/suggestions.
>
> Regards Geoff
>
>
>
>
>For info
>
>My pruning code has been put in the normal search routine after the makemove but
>just before the call to the recursive alphabeta search function
>
>Futility code currently looks like this
>
>/* if not in check before move was made and not close to Mate score and not a
>capture or a promo move and not a checking move */
>
>if ((depth == 1) &&
> !weAreInCheck && (alpha > -9900) && (alpha < 9900) &&
> (!(gen_dat[i].m.b.bits & CAPTURE_MOVE)) &&
> (!(gen_dat[i].m.b.bits & PROMOTE_MOVE)) &&
> !inCheck(sideToMove))
>{
> lazyEval = lazyEvaluate();
>
> if ((lazyEval + FUTILITY_PRUNE_THRESHOLD) < alpha) /* le+300 */
> {
> /* dont bother searching this move any deeper just ignore it */
> futilityCutNodes++;
> takeBack();
> /* try next moved at this depth */
> continue;
> }
>}
>
>/* recurse search function */
>value = -search(-beta, -alpha, (depth + extensions - 1), TRUE);
yeh, I think you have a bug.
firstly most people implement futility pruning _before_ makemove - you are
basically trying to save the effort of make/unmake. You have to fiddle the score
for captures a little, if you have SEE that is easy.
secondly, you are pruning the wrong moves, given you have done makeMove,
sideToMove has reversed, and you need to reverse a/b (-beta,-alpha), so you need
to compare to -beta _not_ alpha, if you move the code to before makeMove you
compare to alpha. I think you are throwing away beta nodes and not alpha nodes.
my suggestion, futuilty prune only the last ply, and before makemove just to
save the makemove. There has been other threads about this.
Scott
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.