SEE on non-capture moves in main search

[Uri Blass]

• For the non-capturing moves after the hash move and killers, history move ordering performs better than no move ordering, as expected. But trying to refine this by using SEE values does not work. I have tried to sort the moves into two groups, first searching non-captures with SEE value zero ordered by history scores, and then searching losing non-captures by their SEE values. This performs slightly worse than simplistic history move ordering for all moves. I have no idea why.
• Searching the losing captures after the non-captures is slightly better than searching them before the non-captures. This is not entirely unexpected, but intuitively I would expect that searching the losing non-captures after the losing captures (i.e. first the hash move, then winning and equal captures, then killers, then non-losing non-captures, then losing captures, and finally losing non-captures) would perform better still. Surprisingly, this is not the case.

Are you searching tactical positions?

No. My move generation test contains of 500 randomly selected positions from my program's games. I disable LMR, loop through all the positions, search every position to a depth of 12 plies, and compute various statistics (total number of nodes, the arithmetic and geometric mean of the number of nodes per position, average effective branching factor, and so on).

If so, losing captures before non-captures would make sense. Otherwise, to me, it does not at all.

Why? Keep in mind that we are only talking about moves with negative SEE value here. As an example, consider the following position fragment:
[D]8/6p1/7b/7R/8/8/8/8 w - -
Why should Rg5 be searched before Rxh6? Wouldn't you expect the second move to have a much higher probability of being the best move? Still, my tests indicate that searching the losing captures after the losing non-capture performs slightly better. I wish I understood why...

Tord

I wonder if you tried to use move order that is not based on history(it means of course not using killer moves and not using hash for order of moves and caring to have move generator that always order the moves in the same order so you cannot use a piece list that has not constant order)

I think that it may be interesting to know if even in these conditions searching the non-capture perform slightly better and if not what is the reason that it is changed when you improve your order of moves.

Is it hash or killers?

Uri

[Tord Romstad]

Because my SEE is rather expensive, I do it slightly different than Tord: I first order the captures MVV/LVA, but than replace the primary sort key (the victim value) by the SEE value for the Higer x Lower captures. L x H or equal takes equal can never be bad captures, and if I am going to order the non-bad captures MVV/LVA anyway, there is no reason to SEE them at all if I can see that they are non-bad even without SEE.

If I understand correctly, this is not very different from what I do in the quiescence search. I first generate all captures, and score them by MVV/LVA. I then loop through the list of captures, picking and popping the highest-valued capture until no moves remain in the list. Directly before I search each capture, I look at the capturing and the captured piece. If the capturing piece is more valuable than the captured piece, I call the SEE, and search the move only if the SEE returns a non-negative value.

Tord

[hgm]

I wish I understood why...

Well, I can only speculate to offer a suggestion:

The example you give might put you on the wrong track, because you only look at moves by the same piece (the Rook). Then it seems obvious that getting a Bishop for that Rook is better than getting nothing.

But in a real position you have a variety of pieces. In particular, you have many Pawns. Now captures with Pawns are never bad captures. But non-captures might still be losing.

For a losing move to turn good, it should have a side-effect that the SEE did not take into account. The most common side effect is overloaded defenders. So playing losing moves in the first place mainly serves to lure away the piece with which the opponent tries to make the winning capture that refutes your move at SEE level. That then should give you a winning capture elsewhere on the board. (Works also for soft-pins.)

Now luring away a piece by a Rook sacrifice is not very likely to be turned into a gain, as the Rook is just too expensive. Even RxB or NxP invest two Pawns, and you then become dependent on a winning capture elsewhere that gets you back more than that. Such exchanges are not very plentiful. On the other hand, sacrificing a Pawn invests only one Pawn, and every winning follow-up that you create by this by definition gains back at least that. And Pawn pushing is usually encouraged in the evaluation, so Pawn moves that cannot be tactically refuted, have a high probability to give a high score. Pawns that cannot be taken are also very likely to mean tactical trouble for the opponent, as almost anything they attack has to be withdrawn.

My conjecture is thus that the effect you observe is caused by the fact that it likes to have the losing non-captures of Pawns before losing captures with pieces. (In other words, the LVA aspect dominates here.)

Have you tried sorting losing and captures and non-captures together by SEE value? Another important point is: have you collected statistics for nodes where a threat exist (eval>beta, but null move fails low) from nodes without a threat? Threat nodes might really need a completely different move ordering, aimed at quickly finding the solution to the threat, rather than finding your own best attack option. With your Queen en prise and eval>beta, the non-captures are very likely to contain the safe withdrawal you need, and trying anything else is just a waste of time. While with eval < alpha, trying non-captures is mostly a waste of time.

[hgm]

If the capturing piece is more valuable than the captured piece, I call the SEE, and search the move only if the SEE returns a non-negative value.

OK, we do exactly the same upto the point where we have the SEE score. At that point, even if the SEE is positive, I replace the victim value by the SEE score, and sort it back in the list. So if there are captures of a Victim more valuable than the SEE score present, it tries those first. (e.g. QxR with SEE = +1) would go after PxB.)

I must admit that I don't really do that by design, but for historic reason. My old algorithm extracted captures from the move list in MVV order, calculated the SEE of all of them, and then extracted captures in SEE order to subject them to QS. The idea was that as soon as the SEE suggested a cut-move, I could search it immediately without SEEing other moves, and that captures with higher MVV had a higher probability of having a cut-move SEE. But this proved counter-productive, it was better to wait with QS until having the SEE for all moves, so that you know for sure you start with the best. (First sorting by MVV still has the advantage, though, that you can stop as soon as the victim value falls under the futility threashold, while the SEE doesn't tell you if the move is futile or not.)

So now I SEE all captures. But in stead of replacing the victim value in the sort-key field of my move list by the SEE value, the quickest patch was to suppress this replacement when victim >= attacker. The second phase of move picking for QS then acts on this mix of MVV and SEE scores.

I guess you could rationalize it by noting that a RxB capture with a winning SEE either occurs because of the Bishop is completely undefended (in which case it does not matter if you use SEE or MVV, they are the same), or has a follow-up like NxR, QxN where you end the capture sequence yourself. Such odd-ply exchanges are not very attractive to start with if you have a winning capture elsewhere, for they would leave the initiative with the opponent. So try other captures of victims higher than this SEE first, they either give a better score immediately (if undefended), or he has to capture back, and then this capture does not go away.

N.B. Note that the way I do it as opposed to Tord, does solve Bob's counter example:

The QxR, RxQ, RxR (apparently with QR battery) with SEE=+1, VV=+5 wil not be tried befor the RxB, SEE=+3, VV=+3. Both wil see their VV replaced by the SEE as they are HxL, and the SEE of the latter is higher.

[hgm]

By the way, it is easy to prove that it is never worse to do an Equal-takes-Equal (let alone Lower-takes-Higher) capture of a victim with value VV>=s, than to capture something with a SEE=s. (Apart from accidental side effects, such as recapture by the intended victim of another capture, to which both SEE and MVV are completely blind, and which always can go either way.)

If the opponent does not (or cannot) recapture you, and uses his turn to solve the problem at the square with SEE=s, you retract your capturer, and you have gained VV >= s.

If he does recapture, you have stayed equal in the past two plies, (or gained something), and then you can do the capture with the good SEE anyway.

Since the SEE value can never be larger than the value of the first victim, (he can always refrain from recapturing), ordering the LxH and ExE captures MVV/LVA irrespective of their SEE (with the additional advantage that you don't have to waste time on the SEE either), and compare their VV against the SEE of HxL captures, seems quite natural. Putting LxH and ExE captures below a HxL capture of a lesser or equal victim, only because the have a lower SEE, can only be worse.

That being said, it is not obvious to me if one has still enough freedom left to do better. Pretty much the only thing you could do without violating the requirement formulated above, is to push HxL captures further down the list. Perhaps based on their result from the first two ply, or the odd vs evenness of their result. An example would be RxN (SEE=+3) in the presence of QxR, QxQ, BxQ, RxB (SEE=+2, with a QB and QR battery forcing capture with Q to go first). If you take the Knight right away, your gain will remain limited to a Knight, as he saves his Rook. OTOH, if you start with the QxR, the opponent cannot break of the exchange at any point without losing a full Rook, and if he carries it through to the end you still take the Knight. So the better order is to try the SEE=+2 before the SEE=+3 in this case, as 2 is even and 3 is odd.

[bob]

First, read the following sentence, quoted verbatim from Tord's comments:

=====================================================
"However, among the winning and equal captures, MVV/LVA move ordering performs better than SEE move ordering, which is counter-intuitive to me. "
=====================================================

Now, please point out exactly _where_ I managed to misread something?

So he is not using pure MVV/LVA, as in pure MVV/LVA you would order QxR before PxB, even if the R is defended. But in the latter case QxR is not likely to be a good or equal capture, so it goes in the back with the losing captures, after the (obviously) winning PxB.

Again, read _what_ I wrote. QxR wins a pawn (queen for 2 rooks). That is a winning exchange by SEE. It should _not_ be searched prior to RxN which wins a knight.

This repairs the major shortcoming of pure MVV/LVA, and it repairs it much bettwer than pure SEE ordering does. Ordering on SEE-scores only is some 20-30% slower with me than the MVV/SEE/LVA Tord describes.

"slower with me". I am running some tests right now. So far, for my program, this has hurt performance, not helped. More when I have the entire test completed so I can post overall averages...

Comparing it with pure MVV/LVA ordering, a you are insistantly doing, is not at all relevant, as no serious engine is using pure MVV/LVA ordering, and it is old hat that it is stupid to order QxR early if you don't know if the Rook is defended.

Can we stop with the blanket statements that are wrong? "no serious engine uses MVV/LVA". Let me name a few, from older to newer:

(1) Belle
(2) chiptest
(3) deep thought
(4) deep blue
(5) dark thought
(6) Hydra

MVV/LVA is the only viable solution when using special-purpose hardware. But plenty of programs have used it (my list above is not complete) with reasonable results. As I mentioned, I produced _real_ data on this comparison about 15 years ago, and SEE only improves on MVV/LVA by 10% if you don't do the prune losing captures trick And it is significantly faster. In fact, it is fast enough to be a "break-even" deal compared to SEE, without the bad capture pruning feature turned on...

(Nevertheless microMax still uses pure MVV/LVA, as its 10-character SEE is not significantly faster than a full QS with futility, so SEEing before QSing is mainly a waste of time there.)

To me it seems intuitively clear that an equal QxQ (SEE=0) should be ordered before a winning NxR (SEE=+2). Because in 99% of the cases the equal QxQ of course will also have a QS=2, as the STM will simply follow it up by the NxR. The goo captures don't go away

What if after QxQ, RxQ the NxR is no longer possible because the rook retreated to capture the queen. The best plan, period, is to search the move with the best potential gain. NxR is better than QxQ unless QxQ has a higher SEE score because the queen is undefended...

The other hand-waving doesn't do much to convince me otherwise, because I have tried so many different move ordering ideas over the years, and SEE is the one that keeps working.


[/quote]if you take an even higher piece (MVV!) in an equal capture, as he has to capture back. If he doesn't, he will lose more that the victim of the good captures is worth, so certainly more than its SEE value.[/quote]

You forgot a critical case as I pointed out, making this a false assumption in plenty of cases.

And if you go for the crumbs first, the opponent will go berserk with his heavy pieces. The quickest way to prove a winning line (i.e. through the smallest tree) is by annihalating his counter-strike capability first. If you will not try QxQ first, he will certainly try it in the reply, and it can only end worse (as your Queen might be undefended).

I don't buy that either. The queen is not always _the_ piece that is causing difficulty. That is a dynamic characteristic of the position that you are attempting to generalize on and recognize using static criteria. alpha/beta is sensitive to producing scores outside the window as quickly as possible. You seem to be suggesting that playing moves that win more slowly are more efficient, which I don't buy at all.

However, there's apparently little reason to continue down this argument, although I will post my SEE + MVV/LVA results when they are done. Early results were worse, but I am running a lot of positions to be sure.

[bob]

• For the non-capturing moves after the hash move and killers, history move ordering performs better than no move ordering, as expected. But trying to refine this by using SEE values does not work. I have tried to sort the moves into two groups, first searching non-captures with SEE value zero ordered by history scores, and then searching losing non-captures by their SEE values. This performs slightly worse than simplistic history move ordering for all moves. I have no idea why.
• Searching the losing captures after the non-captures is slightly better than searching them before the non-captures. This is not entirely unexpected, but intuitively I would expect that searching the losing non-captures after the losing captures (i.e. first the hash move, then winning and equal captures, then killers, then non-losing non-captures, then losing captures, and finally losing non-captures) would perform better still. Surprisingly, this is not the case.

Are you searching tactical positions?

No. My move generation test contains of 500 randomly selected positions from my program's games. I disable LMR, loop through all the positions, search every position to a depth of 12 plies, and compute various statistics (total number of nodes, the arithmetic and geometric mean of the number of nodes per position, average effective branching factor, and so on).

If so, losing captures before non-captures would make sense. Otherwise, to me, it does not at all.

Why? Keep in mind that we are only talking about moves with negative SEE value here. As an example, consider the following position fragment:
[D]8/6p1/7b/7R/8/8/8/8 w - -
Why should Rg5 be searched before Rxh6? Wouldn't you expect the second move to have a much higher probability of being the best move? Still, my tests indicate that searching the losing captures after the losing non-capture performs slightly better. I wish I understood why...

Tord

It shouldn't. But why should Rxh6 be searched _before_ all the _safe_ rook moves that exist as well? That's what I don't follow or buy into... Most likely Rxh6 will fail low since it drops material. Any of the other safe rook moves might be good enough to not fail low and become a PV or fail-high move. I'd rather search Rxh6 after I have raised alpha as high as possible.

[Tord Romstad]

If so, losing captures before non-captures would make sense. Otherwise, to me, it does not at all.

Why? Keep in mind that we are only talking about moves with negative SEE value here. As an example, consider the following position fragment:
[D]8/6p1/7b/7R/8/8/8/8 w - -
Why should Rg5 be searched before Rxh6? Wouldn't you expect the second move to have a much higher probability of being the best move? Still, my tests indicate that searching the losing captures after the losing non-capture performs slightly better. I wish I understood why...

It shouldn't. But why should Rxh6 be searched _before_ all the _safe_ rook moves that exist as well?

I never said it should. Again, I am only talking about the sorting of moves with negative SEE value here, not about moves with zero SEE value (which includes all safe rook moves). When all captures and non-captures with non-negative SEE value have been searched, which moves should we search first? Losing captures or losing non-captures? My experience is that either searching losing non-captures before losing captures perform better. To me, this is hard to understand.

Tord

[Tord Romstad]

Again, read _what_ I wrote. QxR wins a pawn (queen for 2 rooks). That is a winning exchange by SEE. It should _not_ be searched prior to RxN which wins a knight.

Perhaps, but this particular case (which is not at all common in practise) is one of the very few cases where it is no longer possible to capture the hanging piece after the initial exchange. The superior performance of MVV/LVA in the more common cases far outweigh the superior performance of SEE in cases like Q vs R+R exchanges, in my experience.

An unrelated point: Although two rooks are usually worth slightly more than a queen, I've found that it works better to treat Q vs R+R as an equal capture in the SEE. Here I am not talking about move ordering, but about not pruning too many promising captures in the quiescence search: In practise, giving two rooks for a queen seems to be strong more often than giving a queen and a pawn for two rooks. YMMV, as always.

I use piece values of 1, 3, 3, 5 and 10 in my SEE.

MVV/LVA is the only viable solution when using special-purpose hardware.

Clearly not. It seems clear that this is something which depends on the program, but it is an indisputable fact that several authors of decent chess programs (Fruit, Glaurung, Joker, and certainly many others) have experimented with both approaches and found that MVV/LVA move ordering for winning and equal captures is better than SEE. I have tested this very thoroughly the last few months, and there is no doubt about what works best for me. The difference is small, but consistent across all my tests.

Perhaps Fruit, Glaurung and Joker are not quite in the same league as Crafty, but they are not so far behind that you can dismiss our experimental results as incorrect or worthless simply because they do not agree with your results. For some reason, our programs behave differently from yours in this respect. It would be interesting to know why, but we shall probably never find out.

Tord

[Tord Romstad]

I wonder if you tried to use move order that is not based on history(it means of course not using killer moves and not using hash for order of moves and caring to have move generator that always order the moves in the same order so you cannot use a piece list that has not constant order)

No, I haven't tried anything like this. I agree that it would be interesting to test some day.

Tord