Computer Chess Club Archives


Search

Terms

Messages

Subject: Unexpected problem with futility pruning ?

Author: Geoff

Date: 12:26:27 12/29/03


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);





This page took 0.1 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.