SEE on non-capture moves in main search

[sje]

This means that it makes sense to make some extra effort to improve the move ordering at PV nodes. You can afford to do something very expensive, because the PV nodes are very few, and have big sub-trees. I think there is great scope for improvment in this area. Most programs use the same (or almost the same) move ordering techniques in PV nodes as in non-PV nodes. It is hard to believe that this approach is optimal.

I was going to post this, but Tord did it first.

The number of PV nodes as a fraction of the entire node count in a traditional A/B search is extremely small and so aggressive move ordering is justified.

Symbolic's A/B searcher keeps track of "first time down" status of a node which identifies each node as to whether or not it's the first time for the search at a given depth. There are separate flags for first time per iteration and first time per candidate move. The per iteration flag is roughly the same as a PV node identifier, and this triggers much more extensive move ordering efforts.

[Zach Wegner]

I guess that the old PV move would disqualify itself anyway, as when you start the search at low depth its lower, but exact score would be satisfied from the hash table as it was already searched to higher depth.

Really you would want to not probe the hash at that same node because it would be immediately satisfied by a hit. It is not exactly the same position, because you are pretending there is one move less. The idea is to get an exact score for the second best move, and this is done best by IID with an exact score at every depth.

I guess IID really should go like this:
1) Keep the depth, score and bound type for every move in the move list. When first entering the node, if hash and null move do not fail high, fill this from the hash.
2) reset the depth of all moves with upper-bound scores above the current alpha to -1, and their score to alpha.
3) As long (and as soon) as you have a move with a lower-bound score above beta, deepen that one. If the score remains good all the way, you are done.
4) Lacking such moves, look for the move with lowest depth. If that depth is the required depth, we are done. If not, and there are more of that depth, take the one with the highest score first.
5) if the depth is lower than required, search that move one deeper, with the current window (i.e. not upping alpha on any score above it that was not obtained at the currently requested depth or better!).
5) continue 3-5 until there are no more moves with depth below the requested one.

This is nearly how Joker's search works. (What lacks is that it does not reset the depth of moves with insufficiently sharp upper bounds.) It would pretty much solve the problem you sketch: If you were deepening evenly, and your PV move suddenly drops in score at depth d, you re-search all moves of which you are not yet sure at depth d-1 that they are no good, starting at d=0, in the hope to cheaply discover that there is one that might have some merit. The PV move will never be re-searched, as it already has an exact score at depth d. If none of the other moves at depth d-1 is able to beat alpha at depth d-1, there is little hope that they will be able to do so at depth d, and they will be searched to depth d in the order of their meaning-poor upper bounds (so that the ones we already know to be lousy for sure at least go in the end). But if some of them have scores above alpha at d-1, they are searched in the order of their scores, in the hope that they will not suffer the same drop as the old PV move.

An interesting idea. I am not sure it would be better than a normal IID though, because the initial move ordering might not work very well. You could end up deepening a lot of moves that look good at depth 1, when the best move could become better than the others at (say) depth 3. Have you tested this?

[bob]

I think the problem is this: with things like hash moves, good captures, killers, etc, by the time you have tried all of those, either you have already failed high, or you are never going to fail high at this position.

Perhaps, but if it were as simple as this, wouldn't the use of history counters also be worthless for move ordering?

Not sure. I don't use history counters any longer.

The effect was never very large for me, and over the past couple of years, it became a pretty-much break-even thing, so I took it out.

With regard to SEE and move ordering, my intuition disagrees with my experience. This is what I have found:

• For captures, it is best to search the winning and equal captures before the losing captures, and to prune losing captures in the quiescence search. This makes perfect sense. However, among the winning and equal captures, MVV/LVA move ordering performs better than SEE move ordering, which is counter-intuitive to me. After some thought, I think I have an explanation: If there there is a winning capture in the position, this winning capture will usually still be available after the exchange of some more valuable piece. Exchanging strong pieces before capturing the hanging piece reduces the subtree size, because both sides will have fewer legal moves after the exchange (on average).

I have never seen that kind of result with MVV/LVA vs SEE. You can find old discussions on this topic on r.g.c.c back in the early 90's. I ran a bunch of tests and even distributed a version of Crafty where one could choose between SEE and MVV/LVA for q-search move ordering, and others ran lots of tests as well. The net outcome was that SEE produced a tree roughly 10% smaller over a large test set. But when SEE was augmented with the "cull losing captures in q-search idea" then the difference went up dramatically, reducing the size of the tree by 50% (after that original 10% reduction). Numerically, if MVV/LVA searched a tree of size 100,000,000 nodes, SEE would search 90,000,000 nodes. But if SEE was used to eliminate losing q-search captures completely, the tree size was reduced to 45,000,000 nodes.

I've _never_ seen MVV/LVA out-perform SEE, except for the occasional pathological case (atypical).

[*]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.
[/list]

Are you searching tactical positions? If so, losing captures before non-captures would make sense. Otherwise, to me, it does not at all.

It is very frustrating that I haven't found a way to use SEE to improve the ordering of non-captures, because calling the SEE for every move doesn't slow me down noticably. Perhaps I can find some other way to use the SEE values (pruning or reduction decisions, maybe).

Tord

[hgm]

I have never seen that kind of result with MVV/LVA vs SEE. You can find old discussions on this topic on r.g.c.c back in the early 90's. I ran a bunch of tests and even distributed a version of Crafty where one could choose between SEE and MVV/LVA for q-search move ordering, and others ran lots of tests as well. The net outcome was that SEE produced a tree roughly 10% smaller over a large test set. But when SEE was augmented with the "cull losing captures in q-search idea" then the difference went up dramatically, reducing the size of the tree by 50% (after that original 10% reduction). Numerically, if MVV/LVA searched a tree of size 100,000,000 nodes, SEE would search 90,000,000 nodes. But if SEE was used to eliminate losing q-search captures completely, the tree size was reduced to 45,000,000 nodes.

I've _never_ seen MVV/LVA out-perform SEE, except for the occasional pathological case (atypical).

Strange how you seem to stop reading at the very point were you encounter the acronym MVV/LVA. That also happened in the thread the other month, where you went on fighting at nauseam what no one was actually claiming.

Tord does not say that MVV/LVA outperforms SEE. He says that it is better to order the good captures that way. To know what good captures are, SEE must already have been done on them. How else would you know what good captures are? You would not consider this MVV/LVA, as that has a very specific meaning since etcetcetc. But he does order the good captures such that those with the most valuable victim goes first, and amongst equal victims the least valuable attacker goes first, even if you don't want to call that MVV/LVA...

Pure SEE order is in general inferior, as about every one I talked to seems to know. I have also measured this myself, where you can beat the pure SEE ordering by about 30% by the more clever move ordering that Tord suggest.

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.

Now that I can recognize threats from the null-move search I even refined this a little bit: I do not only replace MVV/LVA by SEE/LVA if victim<capturer, but also if victim<piece under threat. In addition I add the amount that the null-move score was below eval (the threat value) to captures that might solve the threat (i.e. captures of the attacker, or captures with the piece under threat). And I slip in that single non-capture safe withdrawal amongst the captures, with as sort key the threat value.

[bob]

I have never seen that kind of result with MVV/LVA vs SEE. You can find old discussions on this topic on r.g.c.c back in the early 90's. I ran a bunch of tests and even distributed a version of Crafty where one could choose between SEE and MVV/LVA for q-search move ordering, and others ran lots of tests as well. The net outcome was that SEE produced a tree roughly 10% smaller over a large test set. But when SEE was augmented with the "cull losing captures in q-search idea" then the difference went up dramatically, reducing the size of the tree by 50% (after that original 10% reduction). Numerically, if MVV/LVA searched a tree of size 100,000,000 nodes, SEE would search 90,000,000 nodes. But if SEE was used to eliminate losing q-search captures completely, the tree size was reduced to 45,000,000 nodes.

I've _never_ seen MVV/LVA out-perform SEE, except for the occasional pathological case (atypical).

Strange how you seem to stop reading at the very point were you encounter the acronym MVV/LVA. That also happened in the thread the other month, where you went on fighting at nauseam what no one was actually claiming.

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? Or maybe are you the one that did the misreading this time around???

I reacted specifically to the above sentence. Which, on the surface, contradicts everything I have ever found when comparing the two ordering strategies...

Tord does not say that MVV/LVA outperforms SEE. He says that it is better to order the good captures that way. To know what good captures are, SEE must already have been done on them. How else would you know what good captures are? You would not consider this MVV/LVA, as that has a very specific meaning since etcetcetc. But he does order the good captures such that those with the most valuable victim goes first, and amongst equal victims the least valuable attacker goes first, even if you don't want to call that MVV/LVA...

So you think he uses SEE to get a _real_ estimate of whether a capture wins or not, and then orders winning captures using MVV/LVA, adding more overhead? Even if that is what was implied, it seems contradictory to me. I have two captures to make:

QxR (wins a pawn because of RxQ RxR, two rooks for a queen)
RxN (wins a knight).

And somehow searching QxR first is going to be better? I don't think so.

Pure SEE order is in general inferior, as about every one I talked to seems to know. I have also measured this myself, where you can beat the pure SEE ordering by about 30% by the more clever move ordering that Tord suggest.

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.

Now that I can recognize threats from the null-move search I even refined this a little bit: I do not only replace MVV/LVA by SEE/LVA if victim<capturer, but also if victim<piece under threat. In addition I add the amount that the null-move score was below eval (the threat value) to captures that might solve the threat (i.e. captures of the attacker, or captures with the piece under threat). And I slip in that single non-capture safe withdrawal amongst the captures, with as sort key the threat value.

You can say that all you want, but pure SEE is not an inferior way to order captures. One can avoid SEE overhead here and there, since RxQ is good whether it is SEE evaluated or MVV/LVA evaluated, generally (there are exceptions to that obviously).

I certainly find it impossible that the MVV/LVA piled on top of SEE is a 30% improvement. However, I can run this test here easily enough on a few thousand positions, and see what it does. More to follow. But I doubt I am going to be surprised here...

[BubbaTough]

Ed,

you said piece-square stuff helps you. How do you combine this with the history heuristic? Or do you not use that?

-Sam

[hgm]

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.

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.

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

[Tord Romstad]

• 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

[Tord Romstad]

So you think he uses SEE to get a _real_ estimate of whether a capture wins or not, and then orders winning captures using MVV/LVA, adding more overhead?

Yes, that is precisely what I do. The additional overhead isn't a problem at all. My program is so slow from the outset that I can add almost anything I want (including doing a full SEE for all moves, including non-captures) without noticing a slowdown. Being a bad programmer has some advantages.

Even if that is what was implied, it seems contradictory to me.

I also found it a little bit surprising at first, although not nearly as much as the fact that losing non-captures are apparently worse (on average) than losing captures. At least, in the case of SEE vs MVV/LVA move ordering for winning and equal captures, there is a logical explanation of why MVV/LVA works better in practise (at least for some of us): See HGM's post.

Tord

[Tord Romstad]

- And skip minor promotions in QS as well, it helps too -

Yes, I do this as well. I simplified things a little in my post.

Add a quick piece-square evaluation to your move generator, it helps a lot. Description: http://www.top-5000.nl/authors/rebel/ch ... 20ORDERING

I have tried that, unfortunately without success. It performs better than no move ordering at all, but worse than history move ordering. In a certain sense, of course, history tables are a form of piece square tables, except that they are based on experience from the current search rather than being precomputed.

I have also tried a more complicated version of your approach: Making every move and evaluating the resulting position, and using the evaluations to order the moves. This also didn't work, even when combined with SEE values.

Tord