SEE on non-capture moves in main search

[hgm]

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

Well, so I left out the "anymore", obviously there has been a time when MVV/LVA was quite popular, and perhaps considered top-of-the-bill. We could argue if Hydra counts as a serious engine. I would say it is an oddity. Comparing hardware implementations with PC software is comparing apples and oranges. Anyway, if people are still using pure MVV/LVA, it is not because they are not aware that better orderings exist, but do it for other reasons, such as code size (uMax), educational reasons (TSCP), hardware limitations (Hydra). That was my point.

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

Well, even pure MVV/LVA is certainly a viable technique that reliably suppresses search explosion in QS. But I doubt that amongst the orderings that do not take into account if pieces are defended, it would be the best ordering. Similar schemes that push HxL captures a bit down the line, seem hardly more difficult to implement in hardware. (E.g. sorting not on VV but on VV-0.5*AV only requres an extra 3-bit adder) Do you also have performance data on such 'improved' MVV/LVA schemes? It would be interesting to know by how much these outperform pure MVV/LVA

Furthermore, keeping track of if pieces are defended or not does not seem so awfully difficult in hardware. (Not to say almost trivial. A cross-bar like 64x64 array of AND-OR ripple-carry propagators in 8 directions would suffice.) So using BLIND in stead of MVV/LVA seems also an option.

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

One can always come up with such a 'what if'. The NxR with a SEE of +2 obviously has the Rook defended, or it would have a SEE of +5. The probability that it would be exactly this Rook that is defending the Q is not a-priori any larger than the probability that the Q would be defending the R. In that case starting with QxQ would up the score of the second capture to +5.

In the absence of hard statistcs, I consider it likely that arguments of this type (i.e. dependence of the various exchanges through sie effects) weaken your case more than they advance it. Exchanges make pieces disappear from the board, and (especially when heavy pieces disappear) this might alter the attack/defence status in many places on the board. This is generally in the avantage of the side that has the inititive, i.e. he who started the exchange, as he has first pick.

You have given me one idea, though: there is one case of obvious depenence that is also very easy to detect. This is where more captures are available to the same piece. Obviously, if you have the choice between QxQ (defended, SEE=0) and QxB (undefended, SEE=+3), it seems wise to try the QxB first. Although from a defensive point of few, the QxQ is safer. Who knows what that Q was attacking that had to remain defended by your Q. But this is not a-priori clear, it would have to be tested. To completely specify the new algorithm: if a HxL capture with a piece P has a positive SEE, go back to all LxH and ExE captures of that same piece, (which were ranked before it in the list based on their higher victim), to calculate their SEE as well, and let it replace the VV in their sort key.

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.

The point is that if you can do QxQ, he can do it to. You cannot escape a QxQ being searched. It is either yours, of which you know the outcome (SEE=0), and to which he will have only one non-futile reply, or it is his in a side branch to the immediate recapture of the winnig exchange. Because he will be in an all node, and capturing something as big as Q will not be futile. And the SEE gives you no clue as how that might end, except that it can only end worse (as QxQ is at least equal).

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.

So are you testing Tord's way (SEE only to weed losing captures out of the MVV/LVA ordering) or my way (replace victim value by SEE score for all LxH captures in the sort key), or both?

[bob]

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.

Then please cite a solution to the following problem. A hardware chess implementation is a finite state machine with a static cycle-time. So how are you going to implement a SEE that can do its thing in one cycle that is a constant-time thing? You can't. Either you stretch the cycle time out horrendously to allow for the max SEE run-time when there are lots of pieces bearing on the square, or you end up with a SEE that can't complete in the synchronous timing required by the hardware.

That is _the_ reason MVV/LVA was developed. Because it is a constant-time algorithm that lends it self well to hardware implementations...

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

My testing so far (running slowly as I have other tests running as well) has SEE + MVV/LVA as producing _larger_ trees than SEE alone. The range (so far) has been from a max of 5% to a min of 2%. But as I mentioned, all my testing is not done. This is probably the range I would expect, since I already had done hundreds of hours of testing comparing plain SEE to plain MVV/LVA 15+ years ago... The 2-5% is pure node counts, and does not take into account the minor added overhead of adding in MVV/LVA after SEE has already been done. Note also that I am doing this everywhere, within the tree and in the q-search...

[bob]

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

Well, so I left out the "anymore", obviously there has been a time when MVV/LVA was quite popular, and perhaps considered top-of-the-bill. We could argue if Hydra counts as a serious engine. I would say it is an oddity. Comparing hardware implementations with PC software is comparing apples and oranges. Anyway, if people are still using pure MVV/LVA, it is not because they are not aware that better orderings exist, but do it for other reasons, such as code size (uMax), educational reasons (TSCP), hardware limitations (Hydra). That was my point.

MVV/LVA was _never_ considered "top of the bill". It was done purely for hardware implementations because of the synchronous nature of a FSM-implemented hardware search. Dark Thought used it because they did bitboards more like chess 4.x and didn't take the attack bitmaps and unroll them into a move list for sorting. If you don't sort, MVV/LVA is about the best you can do to pick a single capture from a set since you can't use SEE without sorting.

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

Well, even pure MVV/LVA is certainly a viable technique that reliably suppresses search explosion in QS. But I doubt that amongst the orderings that do not take into account if pieces are defended, it would be the best ordering. Similar schemes that push HxL captures a bit down the line, seem hardly more difficult to implement in hardware. (E.g. sorting not on VV but on VV-0.5*AV only requres an extra 3-bit adder) Do you also have performance data on such 'improved' MVV/LVA schemes? It would be interesting to know by how much these outperform pure MVV/LVA

You really don't implement algorithms like that in hardware. The issue is synchronous execution with a fixed-length clock. Each "thing" you do needs to finish in a fixed period of time. The longer that time, the longer the overall clock cycle time since all clocks have to be the same length.

That's why you don't find killer moves and such in hardware, although there is probably a way to do that with some work and a lot of logic.

Furthermore, keeping track of if pieces are defended or not does not seem so awfully difficult in hardware. (Not to say almost trivial. A cross-bar like 64x64 array of AND-OR ripple-carry propagators in 8 directions would suffice.) So using BLIND in stead of MVV/LVA seems also an option.

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

One can always come up with such a 'what if'. The NxR with a SEE of +2 obviously has the Rook defended, or it would have a SEE of +5. The probability that it would be exactly this Rook that is defending the Q is not a-priori any larger than the probability that the Q would be defending the R. In that case starting with QxQ would up the score of the second capture to +5.

In the absence of hard statistcs, I consider it likely that arguments of this type (i.e. dependence of the various exchanges through sie effects) weaken your case more than they advance it. Exchanges make pieces disappear from the board, and (especially when heavy pieces disappear) this might alter the attack/defence status in many places on the board. This is generally in the avantage of the side that has the inititive, i.e. he who started the exchange, as he has first pick.

Some actual data. I have lots of test positions queued up to run, but they are interacting with other tests I have set up on the cluster and they run rather infrequently, slowing this testing down. But so far, SEE + MVV/LVA is producing node counts (same positions searched to the same depth) that are 2-5% larger than my SEE-only node counts. There are probably some interactions with LMR since changing the ordering changes the history values and such which changes the pruning in odd ways. But all I am changing is see or see+mvv/lva. I am doing this at internal nodes and in the q-search. The tests are about 1/4 done so far, I'll report final results when all are completed. But, at the moment, adding MVV/LVA on top of SEE is certainly not helping my program...

You have given me one idea, though: there is one case of obvious depenence that is also very easy to detect. This is where more captures are available to the same piece. Obviously, if you have the choice between QxQ (defended, SEE=0) and QxB (undefended, SEE=+3), it seems wise to try the QxB first. Although from a defensive point of few, the QxQ is safer. Who knows what that Q was attacking that had to remain defended by your Q. But this is not a-priori clear, it would have to be tested. To completely specify the new algorithm: if a HxL capture with a piece P has a positive SEE, go back to all LxH and ExE captures of that same piece, (which were ranked before it in the list based on their higher victim), to calculate their SEE as well, and let it replace the VV in their sort key.

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.

The point is that if you can do QxQ, he can do it to. You cannot escape a QxQ being searched. It is either yours, of which you know the outcome (SEE=0), and to which he will have only one non-futile reply, or it is his in a side branch to the immediate recapture of the winnig exchange. Because he will be in an all node, and capturing something as big as Q will not be futile. And the SEE gives you no clue as how that might end, except that it can only end worse (as QxQ is at least equal).

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.

So are you testing Tord's way (SEE only to weed losing captures out of the MVV/LVA ordering) or my way (replace victim value by SEE score for all LxH captures in the sort key), or both?

[Tord Romstad]

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

Clearly not.

Then please cite a solution to the following problem. A hardware chess implementation is a finite state machine with a static cycle-time. So how are you going to implement a SEE that can do its thing in one cycle that is a constant-time thing? You can't. Either you stretch the cycle time out horrendously to allow for the max SEE run-time when there are lots of pieces bearing on the square, or you end up with a SEE that can't complete in the synchronous timing required by the hardware.

That is _the_ reason MVV/LVA was developed. Because it is a constant-time algorithm that lends it self well to hardware implementations...

I'm sorry, I misread your first sentence quoted above. You wrote "MVV/LVA is the only viable solution when using special-purpose hardware", which my brain somehow managed to read as "MVV/LVA is only a viable solution when using special-purpose hardware".

My testing so far (running slowly as I have other tests running as well) has SEE + MVV/LVA as producing _larger_ trees than SEE alone. The range (so far) has been from a max of 5% to a min of 2%. But as I mentioned, all my testing is not done. This is probably the range I would expect, since I already had done hundreds of hours of testing comparing plain SEE to plain MVV/LVA 15+ years ago... The 2-5% is pure node counts, and does not take into account the minor added overhead of adding in MVV/LVA after SEE has already been done.

Actually, I think the overhead for using pure SEE is probably slightly bigger. If you use pure SEE, you have to call the SEE for every capture you search (perhaps even for the captures you end up not searching because you may have to do an SEE for all moves before you can order them). With a hybrid SEE/MVV/LVA, you can postpone the SEE computation until just before the moment you want to search the move. You can even omit it completely if the value of the capturing piece is lower than or equal to the value of the captured piece.

But in any case, the difference in overhead is likely to be tiny, and the node count is the really important thing. With regard to node count, our programs clearly behave differently, for whatever reason.

Note also that I am doing this everywhere, within the tree and in the q-search...

So do I.

Tord

[Tord Romstad]

There are probably some interactions with LMR since changing the ordering changes the history values and such which changes the pruning in odd ways.

Yes. For this reason, I think it is best to disable LMR while doing move ordering tests.

Tord

[gladius]

Well there was certainly some lively discussion generated from this . It's very interesting to read how others have used SEE and battled with move ordering.

Currently, I'm sorting moves in q-search by (captured value) - (attacker value), then non-winning captures have SEE applied to them. Then I can quit Q-search when a losing capture is the best, and don't have to SEE everything (and since my SEE is quite expensive, this is quite a gain).

I did end up using the SEE on non-capture moves in the main tree, but not applied to the sort order, so I only have to run it when I actually play the move in the tree. If the SEE returns that the non-capture move is hanging the piece, I give it a one ply search penalty (if it hasn't been extended somehow), which seems to have been good for some ELO.

[hgm]

Then please cite a solution to the following problem. A hardware chess implementation is a finite state machine with a static cycle-time. So how are you going to implement a SEE that can do its thing in one cycle that is a constant-time thing? You can't. Either you stretch the cycle time out horrendously to allow for the max SEE run-time when there are lots of pieces bearing on the square, or you end up with a SEE that can't complete in the synchronous timing required by the hardware.

That is _the_ reason MVV/LVA was developed. Because it is a constant-time algorithm that lends it self well to hardware implementations...

Perhaps this hard-ware business is a bit off topic, but nevertheless very interesting. You seem to argue from the assumption that there exists nothing else but SEE and pure MVV/LVA. "SEE is too difficult, so the only viable solution is MVV/LVA."

Well, MVV/LVA has obvous shortcomings w.r.t. the HxL captures, and there are plenty of ways to improve on that even within the restictions of fixed-length algorithms. BLIND is one of them (reduce the victim value to zero or one for pieces that are defended, before applying MVV/LVA sorting). Especially in hardware, where basing a decision on extra information often does ot require any additional time at all, as the extra information can be computed in parallel. (Of course there is a trade-off here as well, as transistors or gates are also not an unlimited resource.)

For the balancing of process time of different units, one generally uses pipe-lining. I have no experience at all in designing hard-ware Chess machines. (Looks like fun, though, so who knows? Micro-Max seems simple enough to implement in hardware. Perhaps I will return with a matchbox-size version of it some day after all! ) Seems to me, though, that a cleverly designed hardware move generator can just as easily generate moves for both sides at once as just for the side to move, so that the information which squares are defended is freely available.

You still did not answer my question about what exactly you are testing now. It would be a pity if your conclusion was based on a theoretically sub-optimal alternative ordering. And within the assumptions where SEE is a mainingful quantity (which is that none of the moves has any side effects w.r.t. captures on other squares) the sorting on

(Victim<Attacker ? (SEE&1 || SEE<=0 ? SEE : Victim) : Victim) - 0.01*Attacker

is provably better than the others in singling out the move with the best score.

Of course there are situations where your first priority is not to get the best move in front, but just a good-enough one. (If beta is not much above eval.) There you might want to go for the cut-score SEE with the shortest sequence. So if window-dependent ordering is an option, further improvement is still possible.

[Rob]

This is true for non-PV nodes, but not for PV nodes. Try to measure the relative frequency of the first, second, third (...) move being the best at PV nodes. Unless you are much better than me, the result will be rather depressing. The last time I measured, the first move was the best only about 65% of the time (IIRC). It was quite common that the best move occurred near the end of the move list.

Isn't this inherent in the chess game, where the best move is often not what you expect?

I mean, normal move ordering heuristics are fine for the junk part of the tree but PV nodes typically require a real good move.

[bob]

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

Clearly not.

Then please cite a solution to the following problem. A hardware chess implementation is a finite state machine with a static cycle-time. So how are you going to implement a SEE that can do its thing in one cycle that is a constant-time thing? You can't. Either you stretch the cycle time out horrendously to allow for the max SEE run-time when there are lots of pieces bearing on the square, or you end up with a SEE that can't complete in the synchronous timing required by the hardware.

That is _the_ reason MVV/LVA was developed. Because it is a constant-time algorithm that lends it self well to hardware implementations...

I'm sorry, I misread your first sentence quoted above. You wrote "MVV/LVA is the only viable solution when using special-purpose hardware", which my brain somehow managed to read as "MVV/LVA is only a viable solution when using special-purpose hardware".

My testing so far (running slowly as I have other tests running as well) has SEE + MVV/LVA as producing _larger_ trees than SEE alone. The range (so far) has been from a max of 5% to a min of 2%. But as I mentioned, all my testing is not done. This is probably the range I would expect, since I already had done hundreds of hours of testing comparing plain SEE to plain MVV/LVA 15+ years ago... The 2-5% is pure node counts, and does not take into account the minor added overhead of adding in MVV/LVA after SEE has already been done.

Actually, I think the overhead for using pure SEE is probably slightly bigger. If you use pure SEE, you have to call the SEE for every capture you search (perhaps even for the captures you end up not searching because you may have to do an SEE for all moves before you can order them). With a hybrid SEE/MVV/LVA, you can postpone the SEE computation until just before the moment you want to search the move. You can even omit it completely if the value of the capturing piece is lower than or equal to the value of the captured piece.

I don't do that. For moves like PxN and RxQ, I just assume the gain is +2 or +4 respectively and don't do a see at all. That eliminates a bunch of SEE calls for the many cases where a smaller piece can capture a bigger piece and the safety of doing so doesn't matter at all since it is a guaranteed winner with respect to captures just on that square...

But in any case, the difference in overhead is likely to be tiny, and the node count is the really important thing. With regard to node count, our programs clearly behave differently, for whatever reason.

Note also that I am doing this everywhere, within the tree and in the q-search...

So do I.

Tord

[bob]

Then please cite a solution to the following problem. A hardware chess implementation is a finite state machine with a static cycle-time. So how are you going to implement a SEE that can do its thing in one cycle that is a constant-time thing? You can't. Either you stretch the cycle time out horrendously to allow for the max SEE run-time when there are lots of pieces bearing on the square, or you end up with a SEE that can't complete in the synchronous timing required by the hardware.

That is _the_ reason MVV/LVA was developed. Because it is a constant-time algorithm that lends it self well to hardware implementations...

Perhaps this hard-ware business is a bit off topic, but nevertheless very interesting. You seem to argue from the assumption that there exists nothing else but SEE and pure MVV/LVA. "SEE is too difficult, so the only viable solution is MVV/LVA."

Not quite. What I am saying is that MVV/LVA is the only (so far) viable algorithm for a FSM-type implementation, which is what we need for a hardware implementation, at least implementations that look like belle/deep thought/Hydra. No one has proposed any other type of implementation due to the clock cycle time having to be the same every cycle.

Well, MVV/LVA has obvous shortcomings w.r.t. the HxL captures, and there are plenty of ways to improve on that even within the restictions of fixed-length algorithms. BLIND is one of them (reduce the victim value to zero or one for pieces that are defended, before applying MVV/LVA sorting). Especially in hardware, where basing a decision on extra information often does ot require any additional time at all, as the extra information can be computed in parallel. (Of course there is a trade-off here as well, as transistors or gates are also not an unlimited resource.)

That would stretch the clock cycle time for _everything" since the clock cycle time has to be long enough for the most complex circuit in the thing to settle. MVV/LVA requires two minor cycles in a hardware implementation. First cycle is find the most valuable attacked piece (victim), second cycle is to find the least valuable piece defending that piece. If you add another "thing" then you increase the basic clock cycle time by 50% which is murderous for speed.

For the balancing of process time of different units, one generally uses pipe-lining. I have no experience at all in designing hard-ware Chess machines. (Looks like fun, though, so who knows? Micro-Max seems simple enough to implement in hardware. Perhaps I will return with a matchbox-size version of it some day after all! ) Seems to me, though, that a cleverly designed hardware move generator can just as easily generate moves for both sides at once as just for the side to move, so that the information which squares are defended is freely available.

That kind of information is not in a usable form. You still have to extract the parts that are pertinent to the current capture, and that takes time. MVV/LVA just answers the question in two easy steps. More steps = slower cycle time.

You still did not answer my question about what exactly you are testing now. It would be a pity if your conclusion was based on a theoretically sub-optimal alternative ordering. And within the assumptions where SEE is a mainingful quantity (which is that none of the moves has any side effects w.r.t. captures on other squares) the sorting on

I have taken current Crafty, and for non-losing captures (as proven by SEE) I then re-order them using MVV/LVA. I do this everywhere I would normally sort captures by SEE. I did not try to make it as efficient as possible since I am not (currently) worried about the time cost. I am only looking at tree sizes for identical fixed-depth searches, one using my normal SEE ordering, one using the MVV/LVA ordering for non-losing captures...

(Victim<Attacker ? (SEE&1 || SEE<=0 ? SEE : Victim) : Victim) - 0.01*Attacker

is provably better than the others in singling out the move with the best score.

Of course there are situations where your first priority is not to get the best move in front, but just a good-enough one. (If beta is not much above eval.) There you might want to go for the cut-score SEE with the shortest sequence. So if window-dependent ordering is an option, further improvement is still possible.