tt move vs null move

[hgm]

which solves your problem.

I don't have a problem. You present two alternatives. I just point out that one of the alternatives seems very bad. What remains is trying the null move at any depth, in nodes where you would do null move at high depth.

There is at least one downside but that one already decides the battle: trying the null move at d=1 can simply be proven to be wasted effort if at least one null move search fails low (and that will definitely happen). At a d=1 node all moves (subtrees) are searched with d=0 = QS (ignoring extensions here) until we get a cutoff. If you start by searching the null move with d=0 and you get a cutoff then the effort (in terms of tree size) is about the same as if you had searched one regular move to d=0 until getting a cutoff.

Agreed. The null move would be just another move.

But if the null move fails low then searching the null move simply adds nodes to the whole tree without any benefit. So you never save nodes this way but in general you search more nodes.

Of course you can save nodes. If you search 19 real moves that fail low before you find the cut move, under conditions where the null move would have failed high, doing the null move would have been 20 times faster.

As mentioned above, the null move at d=1 is just like any other move. So your reasoning here would actually apply to any move. "Can you play Nf3 in the node? Better not search it, because if it fails low once, the nodes of its search just add to the total you burn up to find the cut move. Better not search any moves at all, at d=1!".

In reality you want to try the moves that have the best chance to provide a cutoff first, if they take equal effort. The point I argue is that the null move has a better chance to fail high than most non-captures. Because a large fraction of the non-captures actually do something stupid that the null move can never do. To find a cut move amongst the non-captures you would have to search many.

Note that playing a capture often complicates things: you create a new tactical exchange on top of the existing ones. (It would probably be useful to distinguish 'simplifying captures' from 'complicating captures' here.) In alpha-beta you don't want to start with the best move, but with the simplest sufficient move.

[/quote]Why would anyone do this? Trying the null move with a reduction of zero is useless, that is known for decades already.[/quote]

[Sven]

There is at least one downside but that one already decides the battle: trying the null move at d=1 can simply be proven to be wasted effort if at least one null move search fails low (and that will definitely happen). At a d=1 node all moves (subtrees) are searched with d=0 = QS (ignoring extensions here) until we get a cutoff. If you start by searching the null move with d=0 and you get a cutoff then the effort (in terms of tree size) is about the same as if you had searched one regular move to d=0 until getting a cutoff.

Agreed. The null move would be just another move.

But if the null move fails low then searching the null move simply adds nodes to the whole tree without any benefit. So you never save nodes this way but in general you search more nodes.

Of course you can save nodes. If you search 19 real moves that fail low before you find the cut move, under conditions where the null move would have failed high, doing the null move would have been 20 times faster.

If making the null move is better than the first 19 real moves then we are already close to zugzwang.

Also you know that your scenario is statistically irrelevant since you usually get a cutoff after the first move in about 90% of all cases. And you also know how the phrase "you never save nodes" was meant, null move is mostly about statistics (as almost everything in search), not talking about one single node where the exceptional case can certainly occur.

Does any single one of your chess engines try the null move at d=1? If not, why don't you give it a try and test how much of an improvement (positive or negative) you get?

[nionita]

Barbarossa does null move at d==1. I just made a branch to try this. But it will take days until I can see significant Elo results. I will report when I have them.

[hgm]

If making the null move is better than the first 19 real moves then we are already close to zugzwang.

Well, on the average there are 35 moves, so there could still be plenty good moves. But 19 is of course extreme. However you could replace it by 1, and you would still save a factor 2.

Also you know that your scenario is statistically irrelevant since you usually get a cutoff after the first move in about 90% of all cases. And you also know how the phrase "you never save nodes" was meant, null move is mostly about statistics (as almost everything in search), not talking about one single node where the exceptional case can certainly occur.

That statistic includes the cases where you do have a hash move. As I already mentioned at the start of the thread it might be better to search the hash move in that case before the null move. In general, but certainly at d=1. Besides, even if in 90% of the cases the first real move cuts, it could still be that in 95% of the null move would have cut. In addition, the 10% of the cases where the first real move does not cut, might take on average 5 moves before you find the cut move. The probability on N=1 doesn't put any limit on the expectation value of N.

The basic conjecture still stands: when all moves have equally expensive searches, it is best to search the move that has the highest probability to cut first. You have provided no arguments yet why this could not be the null move.

Does any single one of your chess engines try the null move at d=1? If not, why don't you give it a try and test how much of an improvement (positive or negative) you get?

All my engines do null move at d=1, when null move is appropriate. And yes, taking statistics is always interesting. I can try that in KingSlayer. Modify it to ignore null-move cutoffs at d=1, and make a histogram of how often the Nth real move cuts when the null move was tried for the separate cases where the null move failed high or low.

[pkumar]

Barbarossa does null move at d==1. I just made a branch to try this. But it will take days until I can see significant Elo results. I will report when I have them.

Your result would be interesting. Another engine vajolet2_2.3 does null move at depth >=ONE_PLY according to the following code excerpt.

Code: Select all

		//---------------------------
		//	 NULL MOVE PRUNING
		//---------------------------
		// if the evaluation is above beta and after passing the move the result of a search is still above beta we bet there will be a beta cutoff
		// this search let us know about threat move by the opponent.
		//---------------------------

		if( depth >= ONE_PLY
			&& eval >= beta
			&& !sd[ply].skipNullMove
			&& ((pos.getNextTurn() && st.nonPawnMaterial[2] >= Position::pieceValue[Position::whiteKnights][0]) || (!pos.getNextTurn() && st.nonPawnMaterial[0] >= Position::pieceValue[Position::whiteKnights][0]))
		)

[cdani]

Barbarossa does null move at d==1. I just made a branch to try this. But it will take days until I can see significant Elo results. I will report when I have them.

Your result would be interesting. Another engine vajolet2_2.3 does null move at depth >=ONE_PLY according to the following code excerpt.

Andscacs don't do it at depth 1, but I will try, also with the variant of doing it after the hash move does not works but before the rest of the moves, and I report.

[Karlo Bala]

If making the null move is better than the first 19 real moves then we are already close to zugzwang.

Also you know that your scenario is statistically irrelevant since you usually get a cutoff after the first move in about 90% of all cases. And you also know how the phrase "you never save nodes" was meant, null move is mostly about statistics (as almost everything in search), not talking about one single node where the exceptional case can certainly occur.

Does any single one of your chess engines try the null move at d=1? If not, why don't you give it a try and test how much of an improvement (positive or negative) you get?

I doubt that there is a significant difference, but who knows?!

If a static eval is <beta, then most probably search skips the null move.

If a static eval >=beta then:

a) if there is no tactical threat (positional threats are not considered in a qsearch), then the null move is perhaps the simplest solution because some other move can create a treat for the opponent.

b) if there is a tactical threat, then an engine will search 1 move more than necessary. Now, the question is if an engine will search 2 moves instead of 1, or 35 instead of 34, etc. It is not easy to pick up the best move against a dynamic threat, it is pure luck when a search will find the move.

The open question is also, how often there is a 1-ply threat in (almost random) position?!

[cdani]

Andscacs don't do it at depth 1, but I will try, also with the variant of doing it after the hash move does not works but before the rest of the moves, and I report.

When I went to try, I saw that Andscacs was not doing null move even for depth 2, so this was the first think to try. As I understood that this must work at any time control, I went for very fast time controls:

Code: Select all

3 seconds + 0.03
1 Andscacs 0.91055    : 2859.0    2.5   7330.5   14413   50.9%
2 Andscacs 0.91054    : 2853.0    2.5   7082.5   14413   49.1%

15 seconds + 0.04
1 Andscacs 0.91055    : 2856.7    1.6  13823.5   27540   50.2%
2 Andscacs 0.91054    : 2855.3    1.6  13716.5   27540   49.8%

Mmm... I don't know what to think. The logical next I think should be to try at even longer time control with much more games, to see if the change downscales or is magically good, or maybe I just stop trying and forget about this...

[hgm]

For d=1 playing games is a very poor way to test this. Time to depth on a few hundred representative positions would be far more accurate.

[nionita]

Barbarossa does null move at d==1. I just made a branch to try this. But it will take days until I can see significant Elo results. I will report when I have them.

Now the results are clear: doing null move for d >= 2 brings 9 Elo (after 52000 games) in Barbarossa.