Futility pruning...

[thevinenator]

ok, after seeing example after example, I'm still not sure if I have it right...

consider code for a node...
Prior to looping the moves, I have the following...

Code: Select all

// this code combines some Booleans that are repeated a lot...
bool IsPrunable = !IsKingInCheck && !IsPV && (alpha > V_MATED_IN_MAX) && (beta < V_MATE_IN_MAX);

then I have the can I prune code...

Code: Select all

	bool can_prune = false;

	if ( (depth <= 3)
		&& IsPrunable   // from above...
		&& (eval + fmargin[depth]) <= alpha)
		can_prune = true;

then in the main moves loop...
after a move is made...

Code: Select all

if (can_prune     // from above
		&&   QuietMoves   // we've made some quiet moves..
		&& !(m->Flags & MOVE_MATERIAL_CHANGE)    // the move doesn't involve material change
		&& !IsChecking )    // the move isn't checking
		{
		m = ml.GetNextSortedRawMove();
		continue;
		}

is the following snippet, from the middle code example correct?
(1)

Code: Select all

(eval + fmargin[depth]) <= alpha)

or should it be
(2)

Code: Select all

(eval + fmargin[depth]) > beta)

also, (1) is based on the parent eval and (2) on the child (post move). does that make a difference? are we basing the decision on if we should prune on the "new" eval after the move is made? I haven't seen a good description of this.

[H.G.Muller]

Futility pruning is done when the move doesn't seem capable of bringing the score above alpha. That is what 'futile' means: it can gain you some, but not enough to matter. If the move can conceivably get above alpha, but not above beta, it can become PV, improvig on the score of the previous PV, and you would definitely want to know that.

It seems the code you posted only prunes non-captures. So it isn't really important whether you take the eval before or after the move; non-captures do not significantly change the eval. The margins used are so large that any conceivable positional eval change cannot beat them. So I suppose the code uses the eval before the move, as that would save you the trouble of calculating the eval after it.

If you would also want to prune captures, it is usually done based on the estimate of the eval after the move: eval + material gain. That also ignores ay positional eval changes.

[thevinenator]

Harm,
Thanks for the explanation. It prompted me to delve deeper. I found your article about deep futility and decided to try the simplest example.

in my move loop, I put the following line code...

Code: Select all

if ((depth == 1)
				&& IsPrunable
				&& ((eval + PIECEVAUE(m->CapturePiece) + 120) <= alpha))

where IsPrunable from my previous post....
eval is the eval from the parent done outside and before the move loop...
PIECEVALUE is a method that returns the value of the piece, or 0 if the move isn't a capture (have to think about promotions too)
and 120 is just a margin test value to get me started...

I ran the code and at least it didn't go nuts, but I did notice a lot of depths were returning 0 as the score.

my code is processing pseudo-legal moves and therefore it is possible for all the moves to be ignored (mate or stalemate). at the end of the loop, I check if the "good move" count was > 0 and if so, I know it must be mate. But, by adding the futility code, it is now possible for the loop to end without any moves (all below the threshold) being made. to catch this, I set a flag in the futility check when a move is skipped. that way I tell the difference between mate/stalemate/and all moves were futile. But if all moves are futile, I need to return a score. what should that score be? should I call QSearch or just return Eval?

my cursory web search couldn't find any examples, so I'm not sure.

V

[H.G.Muller]

It depends on whether you do fail soft or fail hard. When all moves are futile, you obviously have a fail low, and with fail hard this should by definition return alpha. With fail soft you keep a 'bestScore', which can be lower than alpha (and starts at -INF at d>1, and at eval in QS). A move you prune because of futility really represents a score eval + victimValue + MARGIN. So you could give it that virtual score (which is below alpha), and process it as you would usually do for moves that score below alpha. (Presumably only increase bestScore, if the virtual score is higher. Although in my engines I usually also accompany scores by a depth, and then I also may have to decrease the 'worstDepth', because the pruned move has virtual depth 1. In fact I just forgot to do that for the futile moves, in the engine I am writing, with pretty disastrous results, as worstDepth at d=1 starts at +MAXPLY, so if all moves were futile the position would go into the trasposition table with depth = MAXPLY, and it would never bother to search it again, effectively assuming the node would fail low at any depth, even though the futile move sometimes was the first move of an unavoidable mate-in-2...)

When I generate captures in order of decreasing victim value (which I do in this new engine), the first futile victim I encounter will imply that all later victims, including all non-captures, will also be futile. So I can immediately stop generating moves and abandon the node (not forgetting to to off bestScore to alpha and lower worstDepth to 1). If I would have wanted to search checks, I could invoke a specialized check generator at this point.

[thevinenator]

It depends on whether you do fail soft or fail hard

I'm using hard, so I modified the code to return alpha.

When I generate captures in order of decreasing victim value (which I do in this new engine), the first futile victim I encounter will imply that all later victims, including all non-captures, will also be futile. So I can immediately stop generating moves and abandon the node ...

I saw that idea in your article. I need to check my move generator to insure that I'm doing the same thing, and if so, I will try the "abandon the node" idea. that should speed things up a bit.

the node is generating pseudo legal moves, but I check for each one being legal in the loop after making the move. the pruning is currently being done after the legality check, but it appears that I could move the pruning before I make the move since the condition is only based on material value. but that brings me to a another question. what about checking moves? can they be ignored or should they be made? I say this because it is at this point where I test for check extension, which is only done at d=1. if I skip checking moves, then I'll have to do the test once I enter a node (am I in check).

every little change has such big ramifications!

[H.G.Muller]

There are two ways to get all checks (or any kind of moves that fit a certaing requirement). One way is to generate all moves, and then test all moves to see if they fit the requirement. The second way is to only generate the moves you need in a selective way. If only a small fraction of the moves on average fits the requirement, the latter way is far more efficient.

I don't recall whether your engine is bitboard or mailbox. With mailbox there is't any real need to make the move to test whether it is legal. Or whether it delivers check.

You can make a move generator for specifically generating checks by tabulating how far a piece should step, and in which direction, to align with the King. Like checkStep[pieceType][kingSqr - pieceSquare][n], where a sequence number n is needed because there are in general 2 (and for a Queen even 12) possibilities. You can the run through the pieces in the piece list, and generate the checking moves for each of those, after verifying that the checking square has a free path to both the piece and the King. As a King is usually boxed in for most of the game, you could tabulate the distance of the potential checking square to King when running through the checking squares, and then start scanning the ray from King (wih mailbox) to see if you can reach it. Usually this would make you bump into a Pawn or a board edge in the first step, which excludes the check. This could be much cheaper than generating al non-captures, and test each of them to see if there are checks amongst them (in a situation where non-captures are futile).

[thevinenator]

My engine is bitboard.

I quickly tried the following regarding the futility pruning dialog in previous posts...

I calculate the FutilityLimit value without a margin. When I put any margin in, move selection is affected. the "eval", in my code is not a lazy eval but is a full eval and has non material scoring as well, so isn't this what the margin is suppose to emulate? anyways, it is a lot more stable without it. I'll play around with this later.

Code: Select all

int FutilityLimit = alpha - eval;

Then, if we are at depth 1 and the FutilityLimit is positive, I only generate pseudo (raw) capture moves, otherwise, I generate all pseudo moves.

Code: Select all

	if ((depth == 1) && (FutilityLimit > 0))
		ml.GenerateAllRawCaptureMoves(false);	// if futile, only try capture moves
	else
		ml.GenerateAllRawMoves();

then at the top of the move loop, BEFORE making the move, I do the following...

Code: Select all

		if ((depth == 1) 
			&& (m != hm)							// don't prune the hash move
			&& IsPrunable
			&& (MoveValue(m) <= FutilityLimit) )
			{
			break;
			}

I didn't know what to do about the hash move in this situation. Should I ignore any hash move and just go with the move ordering, or, does the hash have more "info" that we should consider and make the move anyway. seems subtle since it is only one move we are talking about.

I have been trying various positions with this code, a previous version without it (but has some older pruning type code) and Stockfish (for move accuracy). So far the results seems promising. the "best move" usually aligns with SF so I haven't introduced any major bugs, but more testing is needed. I'm also going to test my own two version against each other. my latest version was playing 50 ELO or so better than the last, so I would hope these changes will extend that.

as for your "checking moves" comments, I currently don't have specific code just to look for checking moves. that will take more time to develop.