Less null move pruning by trans map

[Sergei S. Markoff]

Do you mean that you try null move iteratively starting from the lowest say from depth=1 to depth=d-3 until all of fail high, implemented like IID or via an explicitly for-loop over the depths?

Code: Select all

int CalculateNullDepth(int Depth)
{
	if ((board->NumOfPieces[board->SideToMove] <= 8)) return Depth - 4 * INCPLY;
	if (Depth - 5 * INCPLY < INCPLY) return (Depth - 4 * INCPLY);
	return (Depth - 5 * INCPLY);
}

Code: Select all

	if (do_null)
	{
		board->SideToMove = ChangeSide(board->SideToMove);

		if (!QuickRefute(static_eval - beta) && (spm >= 0))
		{
			int cur_depth = NullDepth % INCPLY;
			undo[spm++].moves = ZERO_MOVE;
			tree[gl + 1].in_check = FALSE;
			tree[gl].extended_reason = 0;

			gl++;

			do
			{
				best = -NextNullSearch(-(beta + ZERO_SAFETY), -(beta + ZERO_SAFETY) + 1, cur_depth, FALSE);
				if (board->stopped || best < beta)
				{
					break;
				}
				cur_depth += INCPLY;
			} while (cur_depth <= NullDepth);

			gl--;
			tree[gl].ThreatMove = tree[gl + 1].LastThreatMove;

			board->SideToMove = ChangeSide(board->SideToMove);
			spm--;
			if (board->stopped) return 0;

			if (best >= beta + ZERO_SAFETY)
			{
				PutInHash(Depth, ZERO_MOVE, beta, LOWER, mate_threat, flags);
				return beta;
			}

			if (best == -INFINITY + gl + 2) mate_threat = TRUE;
		}
		else
		{
			board->SideToMove = ChangeSide(board->SideToMove);
		}
	}

I think that the current top programs use depths big enough to make null move searches negligible, using depth reductions function of depth itself say R=depth/4. From my limited perft-analysis of null move trees, even a constant reductions of 3 makes the cost negligible when you factor in the thing is applied recursively.

Probably I should experiment with it. Are you sure that % of nodes in null-move subtrees is neglible? Have you tried to measure it?

[bob]

Hasn't this been known and used for 20 years now???

In deed fairly obvious, so not surprising that it is known. Though not worth too much, it is certainly an improvement.

By code inspection I thought that this feature is missing in Stockfish. That's why I posted it.

I think I asked the same question about Stockfish 3 years ago http://www.talkchess.com/forum/viewtopi ... highlight=

The answer is that it interacts in a subtle way with LMR (at least at the time, not sure if that is still the case).

Funny that Bob's reaction then was the same as now. Why continue with this hobby if everything was already solved 20 years ago

what are you talking about? The "trick" he pointed out was to avoid null-move by using information from a hash hit where the draft was not enough to terminate the search... I don't see what you are trying to imply. The code he gave seems to match the idea as published by the DB guys perfectly. So what does "Bob" have to do with this at all. I pointed out it was not new. It wasn't. It still isn't.

[bob]

Hasn't this been known and used for 20 years now???

In deed fairly obvious, so not surprising that it is known. Though not worth too much, it is certainly an improvement.

By code inspection I thought that this feature is missing in Stockfish. That's why I posted it.

It was tried about three month ago by Lucas Braesch, but it failed at stage 2 (60+0.05) rather convincingly.

Interesting. As in was it implemented correctly? The idea is that the hash table can give a hint that says "if the depth is reduced a bit (as in by the null-move reduction amount) this position would not fail high based on the hash probe. Since a null is even worse it likely won't fail high there, making the null just overhead. It should not be wrong very often, if at all, although one could measure this easily enough, something I might try.

[Ralph Stoesser]

Hasn't this been known and used for 20 years now???

In deed fairly obvious, so not surprising that it is known. Though not worth too much, it is certainly an improvement.

By code inspection I thought that this feature is missing in Stockfish. That's why I posted it.

It was tried about three month ago by Lucas Braesch, but it failed at stage 2 (60+0.05) rather convincingly.

Interesting. As in was it implemented correctly? The idea is that the hash table can give a hint that says "if the depth is reduced a bit (as in by the null-move reduction amount) this position would not fail high based on the hash probe. Since a null is even worse it likely won't fail high there, making the null just overhead. It should not be wrong very often, if at all, although one could measure this easily enough, something I might try.

That was the tested condition for not trying a null move.

Code: Select all

if (    tte  
     && tte->depth() >= depth-R
     && tte->value() <= alpha
     && (tte->bound() & BOUND_UPPER))
     goto tt_predict_null_fail_low;

stage 1
http://tests.stockfishchess.org/tests/v ... 749a54acec

TC: 15+0.05 th 1
LLR: 2.95 (-2.94,2.94) [-1.50,4.50]
Total: 63247 W: 12505 L: 12227 D: 38515

stage 2
http://tests.stockfishchess.org/tests/v ... 749a54ad22

TC: 60+0.05 th 1
LLR: -2.96 (-2.94,2.94) [0.00,6.00]
Total: 7855 W: 1290 L: 1355 D: 5210

[bob]

Hasn't this been known and used for 20 years now???

In deed fairly obvious, so not surprising that it is known. Though not worth too much, it is certainly an improvement.

By code inspection I thought that this feature is missing in Stockfish. That's why I posted it.

It was tried about three month ago by Lucas Braesch, but it failed at stage 2 (60+0.05) rather convincingly.

Interesting. As in was it implemented correctly? The idea is that the hash table can give a hint that says "if the depth is reduced a bit (as in by the null-move reduction amount) this position would not fail high based on the hash probe. Since a null is even worse it likely won't fail high there, making the null just overhead. It should not be wrong very often, if at all, although one could measure this easily enough, something I might try.

That was the tested condition for not trying a null move.

Code: Select all

if (    tte  
     && tte->depth() >= depth-R
     && tte->value() <= alpha
     && (tte->bound() & BOUND_UPPER))
     goto tt_predict_null_fail_low;

stage 1
http://tests.stockfishchess.org/tests/v ... 749a54acec

TC: 15+0.05 th 1
LLR: 2.95 (-2.94,2.94) [-1.50,4.50]
Total: 63247 W: 12505 L: 12227 D: 38515

stage 2
http://tests.stockfishchess.org/tests/v ... 749a54acec

TC: 15+0.05 th 1
LLR: 2.95 (-2.94,2.94) [-1.50,4.50]
Total: 63247 W: 12505 L: 12227 D: 38515

Here's a few test outputs from Crafty. The three values displayed are:
avoids = # of times ttable said "null move will not fail high, avoid doing the null search.
high = number of times a null-move search failed high in spite of what the ttable suggested.
low = number of times a null-move search failed low when the ttable said it would, making it wasted effort.

avoids=143627 high=28 low=143599
avoids=332679 high=339 low=332340

As you can see, it is VERY accurate. I don't see how a few missed fail highs will be a "convincing win" here unless there is something else at work. In the last case, done 332340 unnecessary null-move searches has to hurt more than not doing those 339 that failed high in spite of the tt prediction.

[Ralph Stoesser]

...
As you can see, it is VERY accurate. I don't see how a few missed fail highs will be a "convincing win" here unless there is something else at work. In the last case, done 332340 unnecessary null-move searches has to hurt more than not doing those 339 that failed high in spite of the tt prediction.

There is something else at work, we already discussed that a few years ago. SF uses the threat move from null-search for pruning decisions. It may be that the stage 2 run was bad luck, but bars for a successfull patch to become accepted are rather high. If something seems to be slightly better but not good enough to add code for, the code will not be added. Period.

[mjlef]

Stockfish uses the nullmove search to generate threat moves, which are used in pruning decisions. I that specific trick is not being done in another program,then the hash table proving a move with enough depth is under beta is faster (and often safer).

[Rein Halbersma]

Hasn't this been known and used for 20 years now???

In deed fairly obvious, so not surprising that it is known. Though not worth too much, it is certainly an improvement.

By code inspection I thought that this feature is missing in Stockfish. That's why I posted it.

I think I asked the same question about Stockfish 3 years ago http://www.talkchess.com/forum/viewtopi ... highlight=

The answer is that it interacts in a subtle way with LMR (at least at the time, not sure if that is still the case).

Funny that Bob's reaction then was the same as now. Why continue with this hobby if everything was already solved 20 years ago

what are you talking about? The "trick" he pointed out was to avoid null-move by using information from a hash hit where the draft was not enough to terminate the search... I don't see what you are trying to imply. The code he gave seems to match the idea as published by the DB guys perfectly. So what does "Bob" have to do with this at all. I pointed out it was not new. It wasn't. It still isn't.

The OP pointed out the same idea that I pointed out 3 years ago, and Lucas apparently tried out a while ago. Ralph then and also now pointed out that in Stockfish null move and LMR are tied together. You then and now again said "it's old stuff from Deep Blue, I thought everyone does it". In other words, it seems that you are not interested in retrying old ideas under new circumstances (different search speed, interaction with other search enhancements, etc.). I tried to imply my amazement at your apparent lack of appreciation for these ideas.

[bob]

...
As you can see, it is VERY accurate. I don't see how a few missed fail highs will be a "convincing win" here unless there is something else at work. In the last case, done 332340 unnecessary null-move searches has to hurt more than not doing those 339 that failed high in spite of the tt prediction.

There is something else at work, we already discussed that a few years ago. SF uses the threat move from null-search for pruning decisions. It may be that the stage 2 run was bad luck, but bars for a successfull patch to become accepted are rather high. If something seems to be slightly better but not good enough to add code for, the code will not be added. Period.

If you gain information from an unnecessary null-move search, that's a different issue of course. I've seen lots of approaches to using null-move outside of the normal scope. For example, if a move fails high, but null-move fails low, the move that fails high is interesting. It might be a move that holds off a deep threat that "passing" exposes. So if it is used in a non-traditional way, the ttable trick might not be worthwhile. For a traditional null-move search that is just used to prune parts of the tree with reduced effort, the ttable idea obviously has merit.

[Daniel Shawul]

Hmm I actually did not expect to see you are doing it iteratively as you saidd . It is good to know someone investigates all angles on null move including threat detections and botvinnik extensions etc. I almost forgot about this stuff now since the norm is to do more reductions instead. For mate-threats, I have gone from extending by 1, to not reducing, then to not reducing by as much as other moves IMO-YMMV.

As to the cost of nullmove, I believe it is minimal atleast for a brute force tree of average branching factor. If you have b=20, and you always try null move with R=3, its sub-tree size is going to be much less than the sub-tree of even a single full move even without considering its recursive nature. However when the tree is very selective , as in a real chess engine with BF of 2 or 3, then the cost of null move starts to be more significant. That is the only reason why the R=depth/4 also seems to help my engine. I actually tried to make theoretical quantitative analysis of null-move's cost in a step by step way (with a perft tree), for the purpose of answering questions by how much null move reduces branching factor compared to alha-beta. But in the end, you would have to assume certain quantities such as cut-off rate, to come up with effective branching factor formula. That is not the case for LMR however, which IIRC turned out to have roughly the same effect as alpha-beta has, meaning b_lmr ~ sqrt(b) if all but the first moves are reduced by 1. Anyway for nullmove, I believe its cost is minimal unless your branching factor is low enough to make it significant.