Searching worse moves first

[hgm]

That is one aspect, but I believe the more important one is that null moves are guaranteed to be worse except in zugzwang. There's not really a way to prove that, though.

Worse than what? Many of the non-captures (if not most) will be worse than a null move. Because the null move is also guaranteed to give nothing away. Many non-captures go to unsafe squares, compromise protection, unblock good captures... And then there are those that un-develop pieces. What you say is tautologous, because it is how zugzwag is defined, but in practice the null move is just a good representative of one of your best quiet moves.

Yes, at this point it becomes a heuristic. Whether the save in time is worth the occasional error will require testing to find out.

It's not about searching only the optimal moves. It's about searching them later.

Well, it was about reducing them more.

Yes, but there is still one optimal move in this position. And the move ordering is based on our guess of which one is best. The knowledge or assumption that this node is an all-node doesn't really affect move ordering.

It depends on how you define 'best'. I would say that has nothing to do with score. Order is all about high probability to do the job in a cheap way. Reducion is about how hard you expect it to be to reach the reliability you are aiming for.

Yes, totally. If you have already searched PxQ, the probability of RxQ goes up. However, if you can search RxQ first with the low prior probability (based on the assumption that PxQ is probably better), and get a cut-off, that will save a lot of time, and be right most of the time. Whether that will be an overall win or not would require testing.

That still means you would now have to re-search RxQ at the lower reduction if a posteriori you see that PxQ was no good.

Also, isn't it a bit strange that we only re-search if a node unexpectedly fails high? When we re-search we are considering the possibility that it won't fail high with a deeper search. But why do we trust the result when a move fails low as expected? Why don't we also re-search that to consider the possibility that it may unexpectedly fail high with a deeper search?

When things are as expected you will require less stringent proof that when they are unexpected. That is just Bayesian statistics. If the prior probability is low, weak evidence that the move fails low is enough to push the likelihood that the move fails low to the desired level. When the prior probability of a fail high was very small, you need very strong evidence to push it to the desired level.

[matthewlai]

PxQ vs RxQ is not a good example because both moves are good captures and both of them take the queen. Most engines do not reduce good captures, and most will search PxQ and RxQ among the first moves because of MVV/LVA and MVV. PxQ is still better because it has a higher chance of causing a cut-off (e.g. opponent blunder instead of trading queen for rook and minor).

Part of what I am arguing is that we SHOULD reduce RxQ, if there's PxQ. The justification for that is in my other reply.

PxQ does have a higher chance of causing a cut-off, but if RxQ causes a cut-off as well and we are reducing it, searching that first can result in a faster cut-off, just like with NMP.

Next, cut-off moves are still searched at full depth. So if you know that a move can cause a cut-off you don't want to reduce it. If you know that it doesn't cause a cut-off why waste time searching it early?

This gets a bit complicated. In that case, we don't reduce the late move because given the information that earlier moves did not cause a cut-off and this one did, there's now reason to believe this move is more likely to be best.

This case is much more difficult to analyze. Searching reduced moves first and accepting cut-offs can make the search go much faster, but we lose the information from moves before it.

But if that's bad, why are we doing it with null-move? Why do we search null moves first and accept cut-offs without re-search?

So if you have move A that gives the highest score, and B that improves the lower bound, you suggest that in some cases it's best to search B before A. Well, it might be true in some cases, but in general once A is searched B becomes very cheap because it can be searched with null-window while the reverse is not true.

That is true, but B is cheap anyways. Since we search A to a higher depth, a tighter bound may help more on the wall clock.

Captures are among the most tactical moves in chess. How do you know that PxQ is better than RxQ until you search them? PxQ might take away a critical defender, leaving you vulnerable to some sort of tactical shot, while RxQ leaves the defender in position. This is why most do not reduce captures at all, or at least those that do not appear to lose material directly (and -SEE moves can STILL be good moves at times).

BTW, the goal of alpha/beta is not to search the BEST move first. It is to search a "GOOD ENOUGH" move first, ideally the move that will fail high with the fewest nodes searched. In general this is a capture, obviously, since that reduces the size of the tree by reducing material available to move.

Obviously we don't know that. Any move can turn out to be the best.

The goal, like all heuristics, is to be right more often than wrong.

[bob]

PxQ vs RxQ is not a good example because both moves are good captures and both of them take the queen. Most engines do not reduce good captures, and most will search PxQ and RxQ among the first moves because of MVV/LVA and MVV. PxQ is still better because it has a higher chance of causing a cut-off (e.g. opponent blunder instead of trading queen for rook and minor).

Part of what I am arguing is that we SHOULD reduce RxQ, if there's PxQ. The justification for that is in my other reply.

PxQ does have a higher chance of causing a cut-off, but if RxQ causes a cut-off as well and we are reducing it, searching that first can result in a faster cut-off, just like with NMP.

Next, cut-off moves are still searched at full depth. So if you know that a move can cause a cut-off you don't want to reduce it. If you know that it doesn't cause a cut-off why waste time searching it early?

This gets a bit complicated. In that case, we don't reduce the late move because given the information that earlier moves did not cause a cut-off and this one did, there's now reason to believe this move is more likely to be best.

This case is much more difficult to analyze. Searching reduced moves first and accepting cut-offs can make the search go much faster, but we lose the information from moves before it.

But if that's bad, why are we doing it with null-move? Why do we search null moves first and accept cut-offs without re-search?

So if you have move A that gives the highest score, and B that improves the lower bound, you suggest that in some cases it's best to search B before A. Well, it might be true in some cases, but in general once A is searched B becomes very cheap because it can be searched with null-window while the reverse is not true.

That is true, but B is cheap anyways. Since we search A to a higher depth, a tighter bound may help more on the wall clock.

Captures are among the most tactical moves in chess. How do you know that PxQ is better than RxQ until you search them? PxQ might take away a critical defender, leaving you vulnerable to some sort of tactical shot, while RxQ leaves the defender in position. This is why most do not reduce captures at all, or at least those that do not appear to lose material directly (and -SEE moves can STILL be good moves at times).

BTW, the goal of alpha/beta is not to search the BEST move first. It is to search a "GOOD ENOUGH" move first, ideally the move that will fail high with the fewest nodes searched. In general this is a capture, obviously, since that reduces the size of the tree by reducing material available to move.

Obviously we don't know that. Any move can turn out to be the best.

The goal, like all heuristics, is to be right more often than wrong.

I agree. But if both PxQ and RxQ are SEE-safe, reducing one but not the other seems to REALLY invite search errors. A capture has its own "built-in reduction" because it removes pieces and narrows the tree search automatically.

[Evert]

But if that's bad, why are we doing it with null-move? Why do we search null moves first and accept cut-offs without re-search?

You don't have to, you can do a verification search. I guess people who have teted it have found it to be a waste of time, but I can't point to particular tests.

[kbhearn]

assuming the recapture is available, PxQ should already be a significantly smaller tree than RxQ on average as it has more room for recursive null move attempts to surrender material back and still succeed. Exceptions would of course exist.

null move first works well because it's such a drastic reduction (far more aggressive than LMR) that should it fail the time spent on it is rather negligible while should it succeed the time savings are large.

[bob]

I see null move as a special case of this. We see null move as probably the worst possible move, so we search it at a highly reduced depth (because we think it's the worst possible move), and accept the cut-off if that still fails high (and we don't re-search if it fails high).

That view is completely false. We reduce null moves because they are tactically quiet, guaranteed not to initiate any delaying tactics. Therefore a reduced search will in general be able to recognize the same threats as an unreduced search of the other moves would. Capture, OTOH, are not exactly quiet, and in fact almost always initiates delaying tactics, so that reducing them would just blind the engine.

That is one aspect, but I believe the more important one is that null moves are guaranteed to be worse except in zugzwang. There's not really a way to prove that, though.

The flaw in that is that you do not know in advance which Queen withdrawals are sub-optimal. This is why you search in the first place. If you knew that amove is sub-optimal, searching it is of course a complete waste of time. If I would only search the optimal moves my engine would reach a depth of a million ply in 1sec...

Yes, at this point it becomes a heuristic. Whether the save in time is worth the occasional error will require testing to find out.

It's not about searching only the optimal moves. It's about searching them later.

Actually we are working under the assumption that one of our moves leading to the position was sub-optimal, so that we are nowin an all-node.

Yes, but there is still one optimal move in this position. And the move ordering is based on our guess of which one is best. The knowledge or assumption that this node is an all-node doesn't really affect move ordering.

It is only less likely to be the best move while we are thinking that PxQ is a good move. Once search has proven that PxQ was actually a poor move, it becomes extremely likely that RxQ is the best move, as the probability that RxQ is a very good move has not changed much by the failure of PxQ, and all competition is now eliminated.

Yes, totally. If you have already searched PxQ, the probability of RxQ goes up. However, if you can search RxQ first with the low prior probability (based on the assumption that PxQ is probably better), and get a cut-off, that will save a lot of time, and be right most of the time. Whether that will be an overall win or not would require testing.

Also, isn't it a bit strange that we only re-search if a node unexpectedly fails high? When we re-search we are considering the possibility that it won't fail high with a deeper search. But why do we trust the result when a move fails low as expected? Why don't we also re-search that to consider the possibility that it may unexpectedly fail high with a deeper search?

The reason "why" is not quite right.

We use null move because:

(1) doing nothing should always be worse than doing anything, so long as zugzwang is not an issue;

(2) doing the search takes much less effort since we reduce by some significant number of plies.

It really doesn't have anything to do with tactics or quiet or anything else. The main idea is you are a queen up, you pass and do not make a move, and your opponent moves again. Giving him two successive moves in a row with no intervening move by you, and if he STILL can't win anything, your position is superior enough you can just fail high here without searching any real moves (which would take more effort).

The "null-move observation" is a powerful concept, which is also a simple one. And it really shines more in tactical positions, rather than quiet positions.

[hgm]

It really doesn't have anything to do with tactics or quiet or anything else. The main idea is you are a queen up, you pass and do not make a move, and your opponent moves again. Giving him two successive moves in a row with no intervening move by you, and if he STILL can't win anything, your position is superior enough you can just fail high here without searching any real moves (which would take more effort).

That in itself provides no justification for the reduction. Why can the fact that the opponent cannot gain anything in d-R ply after null move 'prove' that he cannot gain anything in d ply after your best real move? That can only be true because your best move tends to solve existing threats, or at least delays cashing of those by R play. And that has everything to do with tactics. Delaying tactics.

[jwes]

I see null move as a special case of this. We see null move as probably the worst possible move, so we search it at a highly reduced depth (because we think it's the worst possible move), and accept the cut-off if that still fails high (and we don't re-search if it fails high).

That view is completely false. We reduce null moves because they are tactically quiet, guaranteed not to initiate any delaying tactics. Therefore a reduced search will in general be able to recognize the same threats as an unreduced search of the other moves would. Capture, OTOH, are not exactly quiet, and in fact almost always initiates delaying tactics, so that reducing them would just blind the engine.

That is one aspect, but I believe the more important one is that null moves are guaranteed to be worse except in zugzwang. There's not really a way to prove that, though.

It doesn't need to be proved because the definition of zugzwang is that no moves are as good as not moving. The problem is knowing when, and how often, zugzwang occurs.

[bob]

It really doesn't have anything to do with tactics or quiet or anything else. The main idea is you are a queen up, you pass and do not make a move, and your opponent moves again. Giving him two successive moves in a row with no intervening move by you, and if he STILL can't win anything, your position is superior enough you can just fail high here without searching any real moves (which would take more effort).

That in itself provides no justification for the reduction. Why can the fact that the opponent cannot gain anything in d-R ply after null move 'prove' that he cannot gain anything in d ply after your best real move? That can only be true because your best move tends to solve existing threats, or at least delays cashing of those by R play. And that has everything to do with tactics. Delaying tactics.

This is based on the null-move observation. Giving your opponent two moves in a row to somehow wreck your position is a POWERFUL advantage. I would be willing to bet that if I could do this a couple of times in a game against a GM, it would GREATLY change the results.

You can't move your queen to any square I can attack in one move, else I will attack it and then capture it. Etc.

Beal's gave a really good justification for this. The question is "R". Giving you two moves in a row is strong enough to offset several plies of search. Question is "how many".

null move is primarily set up to refute positions where we are far enough ahead that the opponent can't do anything to salvage the position. Which is primarily refuting "hung material". If I am a rook ahead, and give you two consecutive moves, searching to a reduced depth is just as effective as searching the normal tree to full depth.

[hgm]

In reality it is not much of an advantage at all, if the opponent did not know beforehand that he would be allowed to do two moves in a row. If he did know, he could of course abuse that knowledge to wreck tremendous havoc. But that is not unique to the null move. It holds for almost any move. If I tell my opponent: "It is your turn, but I swear to you that the next move I will play is Qh5", he would be more than happy to wreck his King fortress by playing g6. (That reminds me of the days that people played correspondence chess by snail-mail, and that to save on stamps you could 'pre-move'. The classical mistake was to reply to 1.d4 with "1... g6 2. any Bg7". White then of course played 2. Bh6! to play Bxg7 and Bxh8 on his next two moves. )

This is not how engines use it, however. If there is no direct threat, passing a turn is often only a very slight disadvantage. Even in the opening, where speed iscomparatively valuable, because the start position is so poorly developed, there is the rule "3 tempi is a Pawn". In most cases losing a tempo will cost much less than 33cP.

So what you are saying does not sound convincing at all. The null move just measures if there are tactical threats that you might risk pushing over the horizon when doing the real moves.