Per-square MVV/LVS: it's nice but it doesn't work

[mcostalba]

Suppose you have the following

[d] 7k/8/2p1p3/3p4/2P1P1B1/8/8/K7 w - - 0 1

In this simplified position the MVV/LVA algorithm returns the following move ordering:

1 - cXd5
2 - dXc5
3 - BXe6

Note that SEE is non-negative for all the captures.

Of course a better ordering (in this case) would be

1 - cXd5
2 - BXe6
3 - dXe5

The first one is a MVV/LVA, the second one is a per-square MVV/LVA. It works as follow:

Captures are MVV/LVA ordered for each square. First the best (according to MVV/LVA) move is done. If the moves fails we jump to the next best move that attacks a different square

The rationale is that if the best move that attacks a given square fails there is little gain to attack the same square with a lower move, better change target square and try attacking something else.

I have developed a quite cheap implementation of this scheme...but the results are not better then a standard MVV/LVA, actually are slightly worst. I still don't know if it is due to my implementation or to the underlying idea.

Comments? Already tried ?

Thanks
Marco

[hgm]

I don't see the logic of changing target. If capturing the highest victim with a low piece fails to gain material, it must mean either the opponent has a threat against one of your pieces higher that that with which you capture, or the capture itself made such a counter-strike possible (i.e. the attacker was pinned on a higher piece). In the latter case trying to capture with another piece that was not pinned make very much sense. In the former case, trying another capture is even more unlikely to help.

If you don't want to use SEE, it would be useful to look what move did refute your MVV/LVA capture. If it is not the re-capture, but captures of another high piece of yours, it would indeed be better to first try captures with this piece, or even save it with a non-capture (if you are not in QS).

[bob]

Suppose you have the following

[d] 7k/8/2p1p3/3p4/2P1P1B1/8/8/K7 w - - 0 1

In this simplified position the MVV/LVA algorithm returns the following move ordering:

1 - cXd5
2 - dXc5
3 - BXe6

Note that SEE is non-negative for all the captures.

Of course a better ordering (in this case) would be

1 - cXd5
2 - BXe6
3 - dXe5

The first one is a MVV/LVA, the second one is a per-square MVV/LVA. It works as follow:

Captures are MVV/LVA ordered for each square. First the best (according to MVV/LVA) move is done. If the moves fails we jump to the next best move that attacks a different square

The rationale is that if the best move that attacks a given square fails there is little gain to attack the same square with a lower move, better change target square and try attacking something else.

I have developed a quite cheap implementation of this scheme...but the results are not better then a standard MVV/LVA, actually are slightly worst. I still don't know if it is due to my implementation or to the underlying idea.

Comments? Already tried ?

Thanks
Marco

Let me say it again: _nobody_ says MVV/LVA is a _good_ way to order captures. It is not. It was developed by Ken Thompson for the Belle chess machine circa 1979. The issue was he did the entire search for that machine (other than the first 2 plies) in hardware. He used a finite state machine design, and SEE is not something that can be implemented in a reasonable FSM, because it has a variable run-time depending on how many pieces are participating. MVV/LVA is constant, he had a "find victim" operation for his chess board hardware, and a "find aggressor" to find attackers. Once cycle of each and he had a decent capture ordering.

For software, SEE is better. And it gives you more information as well so that you can use SEE to discard bad captures while you can not for MVV/LVA...

[mcostalba]

For software, SEE is better. And it gives you more information as well so that you can use SEE to discard bad captures while you can not for MVV/LVA...

Yes it is.

Actually the best captures ordering alghortim so far for Glaurung/Stockfish is the following:

1 - Calculate SEE for each capture

2- Discard bad captures (SEE < 0)

3- Order the remaining moves with MVV/LVA

This hybrid approach works better then a pure SEE ordering. It was a Tord finding and I have redone all the tests and confirmed the same results.

Now I am trying to improve with the following:

1 - Calculate SEE for each capture

2 - Discard bad captures (SEE < 0)

3 - Order the remaining moves with per-square MVV/LVA


Marco

[hgm]

Actually I have seen several people claiming here that MVV/LVA-like schemes not using SEE were performing better than SEE-based ordering.

What works even better for me than the Glaurung ordering is:

1) Determine the victim value for each capture.
2) Discard all captures with unworthy victims (futility)
3) Upgrade the victim value of captures with the threatened piece or of the piece threatening it by the opponent's SEE score on this piece.
4) Replace this adjusted victim value by SEE score when (adjusted) victim < attacker or victim < highest threatened piece.
5) use this victim value / SEE score to sort the moves
6) in case of equality, lowest attacker goes first.

Step 3 or 4b are only relevant in nodes where the null move failed low because it was refuted by a good capture of the opponent. Usually this is not the case.

So QxQ with SEE=0 will be tried before PxN with SEE=+2 (like Glaurung does).

An additional advantage of this ordering is that you don't use SEE as often as with the Glaurung scheme.

[pijl]

If you're calculating SEE anyway, I'd recommend ordering by SEE/LVA. MVV is just a measure of potential gain (which is better estimated by SEE already). LVA is a measure of risk with which you can improve the choice of the capture/move you want to make.

Richard.

[hgm]

The explanation of why SEE/LVA usually performs worse than MVV-based ordering, is that in most positions you reap the benefits of a positive SEE on a lower-valued piece anyway after first trading the high material. Profitable captures on lower-vaued victims won't go away, as the opponent has to recapture the high piece. By taking his highest piece you shrink the tree by eliminating all captures he has with this piece. In addition, you make the largest possible number of his captures with other pieces futile, by taking the highest possible lead in material eval. Remember: if you can do QxQ, he can do it as well...

[mcostalba]

3) Upgrade the victim value of captures with the threatened piece or of the piece threatening it by the opponent's SEE score on this piece.
4) Replace this adjusted victim value by SEE score when (adjusted) victim < attacker or victim < highest threatened piece.

Sorry, but I fail to understund points 3 and 4.

Could you please write the alghorithm as a (simplified) pseudo-code ?

Thanks a lot
Marco

[bob]

For software, SEE is better. And it gives you more information as well so that you can use SEE to discard bad captures while you can not for MVV/LVA...

Yes it is.

Actually the best captures ordering alghortim so far for Glaurung/Stockfish is the following:

1 - Calculate SEE for each capture

2- Discard bad captures (SEE < 0)

3- Order the remaining moves with MVV/LVA

This hybrid approach works better then a pure SEE ordering. It was a Tord finding and I have redone all the tests and confirmed the same results.

Now I am trying to improve with the following:

1 - Calculate SEE for each capture

2 - Discard bad captures (SEE < 0)

3 - Order the remaining moves with per-square MVV/LVA


Marco

I have tried that in the past, but never found any benefit. You have a _better_ score using SEE, yet you use a weaker algorithm (MVV/LVA) to order what SEE says are non-losing captures. Why would it be better to try a move like NxR (winning an exchange) before trying QxB winning a whole bishop?

I'll try to run this test this week as I can get some _very_ accurate resolution on whether it is better or worse and by how much.

[bob]

The explanation of why SEE/LVA usually performs worse than MVV-based ordering, is that in most positions you reap the benefits of a positive SEE on a lower-valued piece anyway after first trading the high material. Profitable captures on lower-vaued victims won't go away, as the opponent has to recapture the high piece. By taking his highest piece you shrink the tree by eliminating all captures he has with this piece. In addition, you make the largest possible number of his captures with other pieces futile, by taking the highest possible lead in material eval. Remember: if you can do QxQ, he can do it as well...

The reason this fails however, is that now you can choose either NxR winning an exchange, or QxB winning a piece. MVV/LVA goes for the exchange which is wrong. We ran lots of comparison tests years ago in a long discussion with Hsu...

I don't see how this can be better, but will test for confirmation... Probably will take a _ton_ of games to differentiate but I'll bet that plain SEE is better overall in real games, how much better is the only question in my opinion... not if. Just how much...