Searching worse moves first

[matthewlai]

It's commonly believed that perfect move ordering results in the optimal tree size in alpha-beta. That is true for uniform-depth searches, but not with extensions/reductions.

With extensions/reductions, the optimal tree size is achieved, on CUT nodes, by searching moves with highest reduction that will still cause a cutoff first.

Now this leads to an interesting observation - after applying LMR (or similar heuristics), there's actually no need to search in the original move order.

For example, if there's a position where an opponent's defended queen can be captured by either a rook (exchanging a rook for a queen) or a pawn (exchanging a pawn for a queen), SEE/MVVLVA ordering + LMR would give the pawn capture less reductions, because it's more likely to be the best move in this situation. That's perfectly correct.

But it doesn't mean we actually have to search PxQ first. Since we have assigned lower depth to RxQ, we should search that first, and if it causes a cutoff already, we just saved a bunch of time.

And this may sound risky, but it's actually a perfectly safe optimization that won't change the result of the search, because if there's a move that would have caused a cutoff given the depth assignments, the overall result will be a cutoff no matter in which order we searched the moves.

And yes, this does make LMR a huge misnomer.

This should apply to ALL nodes as well.

This may or may not apply in PV nodes. In PV nodes there's an argument for searching the best moves first, because they improve alpha. However, if the second or third best move will still improve alpha, it may be beneficial to search them first, so we can search the big first move with better alpha.

[hgm]

This is why we search null move before all others, although it will almost certainly not be the best.

But there is something fishy here. In LMR you would re-search the move at full depth when it is a cut move. So the only thing you would save on is the comparatively insignificant size of the pilot search. For which you would take the risk that RxQ might not be good enough while PxQ would have been, so that you do the RxQ pilot search in vain.

Besides, it seems a mistake to apply a different reduction to PxQ and RxQ. Or indeed applying a reduction to them at all, if you expect them to fail high. You would just have wasted time on the reduced search. I guess that you could justify it if you had some heuristics to predict whether moves are futile. (The most simplistic of this would be to check if the capture brings you above alpha, but there might be other unresolved tactics on the board that would guarantee you other gains.) If both the R for Q and P for Q exchanges would be expected to fail high, I see no reason to reduce them differently. It is strange that how much RxQ should be reduced depends on the accidental possibility that there also was a PxQ possible.

[brtzsnr]

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).

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?

However, if the second or third best move will still improve alpha, it may be beneficial to search them first, so we can search the big first move with better alpha.

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.


This is based on my experience playing with move-ordering. In the early versions of zurichess I kept a table order[attacker][victim] which I had generated via some heuristics, evolutionary algorithms, and manual tuning. I also tried various tricks like penalizing moving into pawns attack range, avoiding forks, pawn/king takes queen first, etc. For captures MVV/LVA produces almost the optimum order.

[Henk]

Maybe this is applicable when doing no research after a fail high when lb = ub -1 (or is this the same as late move pruning).

[matthewlai]

[moderation]Sorry, but due to a mistake the original text of this posting has been lost.

H.G.

[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.

[hgm]

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.

For example, if we have a position where our queen is hanging, then a null move won't work, but any move that moves the queen away to a safe square may get us a fail high. Now one of the escape may be clearly better than others - for example, maybe we can use the queen to win a rook. We can still search a non-optimal queen escape at a shallower depth first, and see if that already generates a cutoff, and save a bunch of time.

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...

The quality of a search is as good as its weakest branch. This is why you want to balance effort, and not search some moves very deep and others hardly at all without good reason. What good and what poor locations are for the Queen to withdraw to can be determined by events many, many moves away, and deciding this on the base of some static heuristics reduces the quality of the search to the quality of that heuristics. Even the reduced search is likely to be far more accurate than any heuristics, so it would be a wasteof time to search the move it points out any deeper than the others, because it wouldessentially just be a randomly chosen branch.

Yes, it does require heuristics to predict which moves are likely non-optimal. But we are already working under that assumption with move ordering + LMR.

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

I personally don't see why a move shouldn't be reduced just because they fail high.

This is very true, but rarely exploited. A move that fails high by a large margin proves (even at low depth) that a preceding move of the opponent was a severe blunder, and doesn't really deserve much search. Unfortunately we hardly ever know how poor a move really is, because out of alpha-beta laziness we only marginally refute moves. It doesn't really seem crazy to shift a null window up by the heuristically expected gain of a preferred move (e.g. a PxQ when eval = alpha - 50cP) during a pilot search, and accept the fail high resulting from it, and do the nominal-depth search on all moves otherwise.

A position could have 10 legal moves, 5 of them having the potential to fail high, and 4 of them clearly inferior to the 1st.

It makes sense to me because the existence of PxQ means RxQ is less likely to be the best move.

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.

[matthewlai]

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?

[Henk]

Actually you want to prune all late moves for they are all worthless (assumption). But you can not do that for assumption is not 100% correct so you only do a quick search and a research when assumption proved to be 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.