Null Threat

[lucasart]

I'd like to know what other engine developpers have tried and found useful about these. For my part, I've tried everything I could find on the chess programming wiki, as well as the Stockfish implementation of threat detection at children of reduced nodes, and nothing worked (no measurable elo gain).
I've also tried to simply use the null threat as an indication to move ordering, but it was a regression (2 killers and a good history mechanism has proven to be a far superior and more general way of ordering moves in DiscoCheck).

[lucasart]

I'd like to know what other engine developpers have tried and found useful about these. For my part, I've tried everything I could find on the chess programming wiki, as well as the Stockfish implementation of threat detection at children of reduced nodes, and nothing worked (no measurable elo gain).
I've also tried to simply use the null threat as an indication to move ordering, but it was a regression (2 killers and a good history mechanism has proven to be a far superior and more general way of ordering moves in DiscoCheck).

I finally found a variant that works for my engine. It's basically a mate threat detection on null move fails low:

Code: Select all

// Null move pruning
bool mateThreat = false;
if (!is_pv && !in_check && !is_mate_score(beta)
		&& current_eval >= beta
		&& B.st().piece_psq[B.get_turn()])
{
	const int reduction = null_reduction(depth) + (current_eval - vOP >= beta);

	B.play(0);
	int score = -search(B, -beta, -alpha, depth - reduction, false, ss+1);
	B.undo();

	if (score >= beta)		// null search fails high
		return score < mate_in(MAX_PLY)
			   ? score		// fail soft
			   : beta;		// *but* do not return an unproven mate
	else if (score <= mated_in(MAX_PLY) && (ss-1)->reduction)
		// If the null move fails low on a mate threat, and the previous node was reduced, then
		// we extend at this node.
		mateThreat = true;
}

1/ Only doing it at nodes resulting from a reduced search seems better. I'm trying to mittigate the tactical weaknesses introduced by LMR here. So there's no reason to do it at every node. Besides it failed in testing, as it is too costly.
2/ In theory I should redo a null search when the null move fails low, with a zero window mate score
http://chessprogramming.wikispaces.com/ ... %20Threats
But doing so is very costly, as in most cases it's a waste of time, and there's no mate threat. Well it's not "very costly" in the sense that it multiplies by two your branching factor. But it's very costly compared to the little tactical precision gained. And that is why it always was a net regression for me.
3/ So I am trusting fail soft scores, which may seem heretic, but it works. The point is that is we fail low on a mated score, this score can be trusted, and the mate threat exists. Due to alpha/beta pruning, we may miss some mate threats, but at least the ones we detect are free!

PS: when mateThreat = true, I extend all moves at this node. What could be better is only extend the ones that prevent the null refutation (ie. the mate threat). I need to experiment with that

[Don]

I'd like to know what other engine developpers have tried and found useful about these. For my part, I've tried everything I could find on the chess programming wiki, as well as the Stockfish implementation of threat detection at children of reduced nodes, and nothing worked (no measurable elo gain).
I've also tried to simply use the null threat as an indication to move ordering, but it was a regression (2 killers and a good history mechanism has proven to be a far superior and more general way of ordering moves in DiscoCheck).

I have tried using the "threat move" too but we have never made it work in Komodo. Stockfish uses the threat move (what you call null threat) by never reducing or pruning a move that appears to answer the threat. For example if the null threat is BxQ stockfish will not prune certain moves such as moves of the queen, or positioning a piece between the bishop and queen to answer the threat. They are fairly thorough about identifying these moves.

It seems like a great idea and apparently it works in stockfish but I don't see other programs using this. We tried doing something very similar to what stockfish does and that does not work for us.

Komodo does have rules for avoiding pruning and LMR (or that "reduces the reductions") that definitely improves the program however. These go beyond the simple rules most programs have to not reduce checks captures and out of check.

My intuition is that responding to the threat move should be a great idea - and maybe it is in stockfish. But it's not in Komodo.