Issues with futility pruning

[algerbrex]

I'm getting weird results when introducing futility pruning into Blunder. On the one hand, I'm getting a pretty sizeable reduction in nodes, and I'm searching a full ply deeper for some positions (e.g. kiwipete), but I'm getting no, or negative Elo gain when I'm testing.

Now, I understand this is because I'm likely pruning too many good lines, so the Elo gain from the increased search depth is being offset by missing winning tactical lines. Where I'm stuck is figuring out what I'm missing (or including) in my futility pruning code that's causing this "over-pruning". Over the past week or so, I've done quite a bit of research and have tried many different configurations and ideas, and none of them seem to be working for me.

I've also taken a look at the code of other engines, and it doesn't seem like I'm doing anything weird. Here are the relevant parts of my search code:

Code: Select all

// The primary negamax function, which only returns a score and no best move.
func (search *Search) negamax(depth, ply uint8, alpha, beta int16, doNull bool) int16 {
        ...

	//  Check if futility pruning can be done.
	canFutilityPrune := false
	futilityMargin := int16(200 * depth)
	if depth <= 4 &&
		!inCheck &&
		alpha < Checkmate {
		canFutilityPrune = staticScore+futilityMargin <= alpha
	}

	...

	// Set a flag to record if any pruning was done. If pruning was done, then
	// we can't declare a mate, since we didn't test every move.
	noPruning := true

	for index := 0; index < int(moves.Count); index++ {

                ...

		givesCheck := sqIsAttacked(
			&search.Pos,
			search.Pos.SideToMove,
			search.Pos.PieceBB[search.Pos.SideToMove][King].Msb())

		tactical := givesCheck || move.MoveType() == Attack || move.MoveType() == Promotion
		important := move.Equal(hashMove)

		if canFutilityPrune && legalMoves > 0 && !tactical && !important {
			search.Pos.UnmakeMove(move)
			noPruning = false
			continue
		}

		...
	}

	// If we don't have any legal moves, and we haven't pruned moves, it's either checkmate, or a stalemate.
	if legalMoves == 0 && noPruning {
		if inCheck {
			// If its checkmate, return a checkmate score of negative infinity,
			// with the current ply added to it. That way, the engine will be
			// rewarded for finding mate quicker, or avoiding mate longer.
			return -Inf + int16(ply)
		} else {
			// If it's a draw, return the draw value.
			return search.contempt()
		}
	}

	// Return the best score, which is alpha.
	return alpha
}

As I mentioned, I've fiddled in various ways with tuning the futility margin, what counts as a "tactical" move, and what counts as an "important" move. And nothing I've tried so far so shows any positive gain. And the other threads I've visited on TalkChess where futility pruning wasn't working didn't help much either.

I've also tried a debugging idea I saw in another thread, where at pre-horizon nodes (depth=1) if a move was pruned, I perform a normal full-search and make sure that the move failed-low and my futility margin was high enough and my pruning seemed to pass this test, so I must admit, at this point, I'm pretty stumped. Any ideas as to where I'm going wrong with my pruning would be appreciated.

[Chan Rasjid]

My program is not strong, but it seems my futility pruning is working. Most programs (I think) does an evaluation after make(); so when we enter search(), the eval score of the node is available. Futility should use pos->currstack->eval instead of the static material difference; must add the value of captures of the various moves. With this evaluation, at depth == 1, can detect standpat fail high in the child node thus pruning at depth == 1.

Try to avoid futility in pv-nodes; child nodes of pv-nodes has only a one piece placement difference from the pv-node and has higher likelihood to belong to a new pv.

Code: Select all

	/* futility before make(); moves not validated yet;
	(slightly edited) */		
	if (depth >= 2
        && depth <= 6
	/* less buggy to have first valid move and alpha. */			
        && best_score > M_MATE
        && pos->currstack->eval
        + vPiece[capture] +(ep? 100: 0)
        + 150 * (depth - 1) <= alpha
        && !(check || incheck || IS_PROMOTE(*move))
		&& pieces >= 2) /* w/o king */		        
    {
	continue;
}

[edited]; margin at depth == 2 is 150cp;

[algerbrex]

My program is not strong, but it seems my futility pruning is working. Most programs (I think) does an evaluation after make(); so when we enter search(), the eval score of the node is available. Futility should use pos->currstack->eval instead of the static material difference; must add the value of captures of the various moves. With this evaluation, at depth == 1, can detect standpat fail high in the child node thus pruning at depth == 1.

Try to avoid futility in pv-nodes; child nodes of pv-nodes has only a one piece placement difference from the pv-node and has higher likelihood to belong to a new pv.

Code: Select all

	/* futility before make(); moves not validated yet;
	(slightly edited) */		
	if (depth >= 2
        && depth <= 6
	/* less buggy to have first valid move and alpha. */			
        && best_score > M_MATE
        && pos->currstack->eval
        + vPiece[capture] +(ep? 100: 0)
        + 150 * (depth - 1) <= alpha
        && !(check || incheck || IS_PROMOTE(*move))
		&& pieces >= 2) /* w/o king */		        
    {
	continue;
}

[edited]; margin at depth == 2 is 150cp;

Thanks, Chan, I'll try some of those ideas.

With that said, one of the things that I've never understood is whether or not, or how, I check if a node is a pv node if I'm not using principal variation search. Because the check I've usually seen for whether or not a node is a pv node is if the alpha-beta window doesn't have a width of 1, since pvs searches only the principal variation with a full window.

[Chan Rasjid]

Thanks, Chan, I'll try some of those ideas.

With that said, one of the things that I've never understood is whether or not, or how, I check if a node is a pv node if I'm not using principal variation search. Because the check I've usually seen for whether or not a node is a pv node is if the alpha-beta window doesn't have a width of 1, since pvs searches only the principal variation with a full window.

Firstly, there should not be a reason not to use principle variation search (all top engines does it). It is just searching the moves after the first (if a pv-node, otherwise even for the first move) with a zero window (width = 1). If the search fails high (an improvement in alpha), a research is done with the relevant fully opened window. The gain comes as nearly 70% of all nodes are searched with a zero window with huge cutoff gains.

In iterative deepening, except for the first iteration we always have the principle variation of the previous iteration to try first. A pv node is one which is on the principle variation of the previous iteration. I think most programs have two search functions, one search_pv() and another plain search(). In a search of depth = N, search_pv() is called only about N times for the pv moves (following the pv, plus a few more nodes into qsearch). Inside search_pv(), we call search_pv() for the first move (a pv move with a full window), else we call search() normal with a zero window.

So we know we are dealing with pv nodes ONLY when we are within search_pv().

Hope this is clear.

[algerbrex]

Firstly, there should not be a reason not to use principle variation search (all top engines does it).

Right. My problem is that adding PVS leads to another can of worms. Whenever I add PVS to my engine, the number of nodes searched actually increases. I'm sure there must be a bug somewhere, but I've spent days trying to find it, so I just decided to put it aside for the time being and focus on something else.

Unfortunately for me, this something else also seems to be just as finicky.

[Chan Rasjid]

Firstly, there should not be a reason not to use principle variation search (all top engines does it).

Right. My problem is that adding PVS leads to another can of worms. Whenever I add PVS to my engine, the number of nodes searched actually increases. I'm sure there must be a bug somewhere, but I've spent days trying to find it, so I just decided to put it aside for the time being and focus on something else.

Unfortunately for me, this something else also seems to be just as finicky.

If you notice that the nodes searched become abnormally high when implementing PVS search, it may be because you do a research when there is no need to.

A true zero window search is only when alpha + 1 < beta; then you search with window bounds (alpha, alpha + 1):

Code: Select all

x = -search(depth - 1, zero? -alpha - 1: -beta, -alpha, xside, side, ply + 1, ...). 

A research is needed if there is an improvement in alpha where x does not go beyond beta! (x > alpha and and x < beta). The research would be with a new research window (x - 1, beta).

Note that you would face the problem of search instability with PVS. This could happen because of TT cutoff; a research may not be searching the same exact subtree so that your search may return a fail high followed by a fail low! Another problem to resolved.

Another thing to note is that when you search with a zero window, the subbranch would be all nodes with a width == 1 and they naturally are "zero" window and does not need any research if there is an improvement in alpha.

I think you cannot avoid searching with a zero window in a chess engine! In LMR, you expect certain moves with bad evaluation scores to fail low, so it is logical they are searched with a zero window, much cutoff savings.

[Chan Rasjid]

Firstly, there should not be a reason not to use principle variation search (all top engines does it).

Right. My problem is that adding PVS leads to another can of worms. Whenever I add PVS to my engine, the number of nodes searched actually increases. I'm sure there must be a bug somewhere, but I've spent days trying to find it, so I just decided to put it aside for the time being and focus on something else.

Unfortunately for me, this something else also seems to be just as finicky.

I think I misunderstood your concern about your PVS searching more nodes.

You expect that if a certain position is searched to a certain depth, that the score, the PV and the nodes searched should not be dependent on whether we are using PVS with an aspiration window or just a plain alphabeta where the root window is (-infi,+infi).

I just fixed the analysis mode codes of my program. I searched the following position with PVS and also with zero window disabled:
7n/5bk1/2p1r2p/p1Pp1Rp1/P3p1P1/1q2P1P1/4B2Q/3N2K1 w - - 1 69

I disabled all futility/reverse futility/see-qs-prune, but retain lmr and nullmove for searchpv() and search().
You can see that at depth 17, the nodes searched are different, but the return scores are the same. The best move at root too is the same. PVS reaches depth 17 much faster and searched fewer nodes.

I am not too sure yet that the manner of traversing the search tree and the alphabeta pruning would be the same or different with PVS.

Code: Select all

//PVS
info depth 15, score -375 cp, time 4397, nodes 6092783, nps 1385668, ebf  2.71,  pv h2f2 b3a4 f2e1 a4a3 e1c3 a3c3 d1c3 h8g6 f5f1 e6e7 f1a1 e7a7 a1f1 a5a4 f1f2  
info depth 16, score -391 cp, time 8129, nodes 11785859, nps 1449853, ebf  2.65,  pv h2f2 b3a4 f2e1 a4a3 e1c3 a3c3 d1c3 h8g6 f5f1 e6e7 f1f2 e7a7 c3a4 g6e5 f2f5 a7e7  
info depth 17, score -387 cp, time 13842, nodes 19864954, nps 1435121, ebf  2.58,  pv h2f2 b3a4 f2e1 a4a3 e1c3 a3c3 d1c3 h8g6 f5f1 e6e7 g1h1 g6e5 f1f5 g7h7 f5f1 h7h8 f1f6  


//zero window disabled
info depth 15, score -392 cp, time 8952, nodes 12169043, nps 1359365, ebf  2.82,  pv h2f2 b3c2 f2e1 c2c5 e1d2 h8g6 d2b2 g7f8 g1g2 c5b4 g2g1 g6e5  
info depth 16, score -395 cp, time 17801, nodes 24584679, nps 1381084, ebf  2.76,  pv h2f2 b3c2 g1h2 e6e7 f2e1 c2c5 e1d2 c5b4 d2d4 g7h7 f5f6 c6c5 d4c3 b4c3 d1c3 h8g6  
info depth 17, score -387 cp, time 22462, nodes 31211372, nps 1389518, ebf  2.63,  pv h2f2 b3c2 f2e1 c2c5 e1d2 h8g6 d2d4 c5d4 e3d4 g6e7 f5f1 e6f6 f1f2 f6f2 g1f2 f7e6 d1e3  

[algerbrex]

Firstly, there should not be a reason not to use principle variation search (all top engines does it).

Right. My problem is that adding PVS leads to another can of worms. Whenever I add PVS to my engine, the number of nodes searched actually increases. I'm sure there must be a bug somewhere, but I've spent days trying to find it, so I just decided to put it aside for the time being and focus on something else.

Unfortunately for me, this something else also seems to be just as finicky.

If you notice that the nodes searched become abnormally high when implementing PVS search, it may be because you do a research when there is no need to.

A true zero window search is only when alpha + 1 < beta; then you search with window bounds (alpha, alpha + 1):

Code: Select all

x = -search(depth - 1, zero? -alpha - 1: -beta, -alpha, xside, side, ply + 1, ...). 

A research is needed if there is an improvement in alpha where x does not go beyond beta! (x > alpha and and x < beta). The research would be with a new research window (x - 1, beta).

Note that you would face the problem of search instability with PVS. This could happen because of TT cutoff; a research may not be searching the same exact subtree so that your search may return a fail high followed by a fail low! Another problem to resolved.

Another thing to note is that when you search with a zero window, the subbranch would be all nodes with a width == 1 and they naturally are "zero" window and does not need any research if there is an improvement in alpha.

I think you cannot avoid searching with a zero window in a chess engine! In LMR, you expect certain moves with bad evaluation scores to fail low, so it is logical they are searched with a zero window, much cutoff savings.

Hmm yeah thanks, I’m gonna try those suggestions, because last night I tried PVS again and it worked in the sense the number of nodes was reduced. But testing it against the version with out it, it was a -30 Elo gain.

So I’m still doing something wrong, and I think you’re onto what the problem is when you mentioned searched stability, because I forgot since I use a TT, I can run into search stabilities.

With regards to handling the instabilities, I just need to check if the score returned is greater than alpha AND less than beta, and then do a research with a full window? Or do I need to use a window of (score-1, beta)?

[algerbrex]

Firstly, there should not be a reason not to use principle variation search (all top engines does it).

Right. My problem is that adding PVS leads to another can of worms. Whenever I add PVS to my engine, the number of nodes searched actually increases. I'm sure there must be a bug somewhere, but I've spent days trying to find it, so I just decided to put it aside for the time being and focus on something else.

Unfortunately for me, this something else also seems to be just as finicky.

I think I misunderstood your concern about your PVS searching more nodes.

You expect that if a certain position is searched to a certain depth, that the score, the PV and the nodes searched should not be dependent on whether we are using PVS with an aspiration window or just a plain alphabeta where the root window is (-infi,+infi).

I just fixed the analysis mode codes of my program. I searched the following position with PVS and also with zero window disabled:
7n/5bk1/2p1r2p/p1Pp1Rp1/P3p1P1/1q2P1P1/4B2Q/3N2K1 w - - 1 69

I disabled all futility/reverse futility/see-qs-prune, but retain lmr and nullmove for searchpv() and search().
You can see that at depth 17, the nodes searched are different, but the return scores are the same. The best move at root too is the same. PVS reaches depth 17 much faster and searched fewer nodes.

I am not too sure yet that the manner of traversing the search tree and the alphabeta pruning would be the same or different with PVS.

Code: Select all

//PVS
info depth 15, score -375 cp, time 4397, nodes 6092783, nps 1385668, ebf  2.71,  pv h2f2 b3a4 f2e1 a4a3 e1c3 a3c3 d1c3 h8g6 f5f1 e6e7 f1a1 e7a7 a1f1 a5a4 f1f2  
info depth 16, score -391 cp, time 8129, nodes 11785859, nps 1449853, ebf  2.65,  pv h2f2 b3a4 f2e1 a4a3 e1c3 a3c3 d1c3 h8g6 f5f1 e6e7 f1f2 e7a7 c3a4 g6e5 f2f5 a7e7  
info depth 17, score -387 cp, time 13842, nodes 19864954, nps 1435121, ebf  2.58,  pv h2f2 b3a4 f2e1 a4a3 e1c3 a3c3 d1c3 h8g6 f5f1 e6e7 g1h1 g6e5 f1f5 g7h7 f5f1 h7h8 f1f6  


//zero window disabled
info depth 15, score -392 cp, time 8952, nodes 12169043, nps 1359365, ebf  2.82,  pv h2f2 b3c2 f2e1 c2c5 e1d2 h8g6 d2b2 g7f8 g1g2 c5b4 g2g1 g6e5  
info depth 16, score -395 cp, time 17801, nodes 24584679, nps 1381084, ebf  2.76,  pv h2f2 b3c2 g1h2 e6e7 f2e1 c2c5 e1d2 c5b4 d2d4 g7h7 f5f6 c6c5 d4c3 b4c3 d1c3 h8g6  
info depth 17, score -387 cp, time 22462, nodes 31211372, nps 1389518, ebf  2.63,  pv h2f2 b3c2 f2e1 c2c5 e1d2 h8g6 d2d4 c5d4 e3d4 g6e7 f5f1 e6f6 f1f2 f6f2 g1f2 f7e6 d1e3  

Right, that was mostly my concern.

I'll have to keep playing around with PVS, because while I'm getting a node reduction, I'm getting no Elo gain, which I don't really understand since as far as I understand, PVS isn't doing any sort of pruning or anything, it's just a way to reduce the total nodes searched, and it corrects itself by researching with a full window if alpha is raised and below beta.

So at this point, I think I have a bug somewhere, probably in the transposition table, that's causing PVS to fail.

[Cardoso]

Assuming you don't have bugs it's always a question of finding the right equilibrium.
Too much futility pruning and the engine starts to get blind.
Please check if your staticScore describes your current position with some precision.
Another thing you can do is to insert code to test your futility mechanism but without ever applying futility.
Instead of continuing/skipping to the next move in case canFutilityPrune is true, just continue as normal
as if no futility pruning is implemented.
If you fail high where canFutilityPrune is true then you should dump this position to a log file, along with alpha, static score, depth, ply, etc.
Also use 2 counters: one for how many futility cases would occur (the number of times canFutilityPrune is set
to true), another for how many FHs occur in cases where futility should kick in.
Dump these counters when you dump the position with false futility cases.
This way you can catch bugs of incorrect futility cases.
Of course there always should be false/incorrect futility cases, but usually these should happen because there is a tactical shot.