Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Unexpected problem with futility pruning ? Anymore opinions ?

Author: Frank Phillips

Date: 07:57:22 12/30/03

Go up one level in this thread


On December 30, 2003 at 05:26:42, Geoff wrote:

>Hi Scott
>
>>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.
>
>Thanks for the help. I put the futility code in after the makemove to eliminate
>the illegal moves that are filtered out by makemove(). It would be a problem if
>I moved it earlier I think ?
>
>> 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.
>
>I was fairly convinced I was correct with using Alpha here but you might be
>correct. I was thinking that alpha and beta swap when you call the search
>function but not for just switching sidetomove in makemove().
>
>I had a quick look at razoring in Beowolf, from what I can see it prunes after
>makemove() but uses alpha like I did ? That would seem to suggest I was correct
>initially ? I need to have a longer think about this one it is getting confusing
>now ;-)
>
>Anyone with a casting vote ? Should it check alpha or beta here ?
>
>        Regards Geoff


Presumably you are trying to guess whether the score you are likely to get from
searching the sub tree (of the  move you just made) will greater than alpha.

ie

if (your_score + margin <= alpha) then prune.

Just make sure you test against your_score, which since you have moved will be
-Evaluate()  if Evaluate returns the score for the side to move.

I periodically try pruning, but never stay with it for long.  Here is some code
I added to experiment quickly with pruning. MatBalanceXstm is a macro for the
material balance from the perspective of the side _not_ on the move.  So if
white just moved and I am deciding whether to search, then I am calculating
(WHITE-BLACK).  Like you I made the move first before deciding whether to search
the sub-tree, because I update some evaluation terms in makemove.

(This saved nodes but not time, for me.).


		//int cut_flag=FALSE;
		next_depth=depth+dec;
		if (next_depth<3 &&
			!pboard->in_check[ply] && !pboard->in_check[ply+1] &&
			MatBalanceXstm+razor[next_depth]<=alpha)
		{
			UnMakeMove(pboard,pmove,&pboard->node[ply]);
			stat.cuts++;
			continue;
			//cut_flag=TRUE;
		}





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.