MVV/LVA. Or should it be LVV/MVA?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
hgm
Posts: 23792
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

MVV/LVA. Or should it be LVV/MVA?

Post by hgm » Tue Mar 31, 2009 5:57 pm

I am trying to improve move ordering. To this end I let the engine print positions where it achieve a beta cutoff by another move then the first, plus the list of moves that it considered before, selected by remaining depth. Just to evaluate manually what type of positions it typically has to judge, and if there is an identifiable source of error that could be cured.

One frequent mistake is that it has the choice between capturing two different undefended Rooks, one with a Rook, the other with a lower piece. Of course it tries the lower piece first. (For this it does not matter if you sort MVV/LVA or by SEE value.) And that often backfires, because the R on R attack was of cource reciprocal, so when I capture the Rook with the low piece, his other Rook captures mine, which sometimes is undefended.

So lacking the geneal information on existing threats against my pieces (which I might perhaps obtain from analysing the null-move reftation, but not in QS), it is often predictably better to capture with a higher-valued attacker first, if that attacker is attacked back by its would-be victim, while the other attacker attacks another victim of the same value. Even if the first victim is defended, it is in general better to take it first, to resolve the reciprocal threat in a forcing manner, and cash the good capture wth the lower attacker later.

Another frequent error in the order I use now (basically MVV based) occurs if the same piece can capture a high defended piece or a lower undefended piece. Going for the highest victim first would lose you the possibility to gobble up the low piece later. So where in general it is better to first trade the MVV before cashing in on a lower victim with better SEE, it would pay to check in case of a defended MVV of the piece you are going to take it with has alternative targets with better SEE (typically ndefended ones).

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: MVV/LVA. Or should it be LVV/MVA?

Post by bob » Tue Mar 31, 2009 6:33 pm

hgm wrote:I am trying to improve move ordering. To this end I let the engine print positions where it achieve a beta cutoff by another move then the first, plus the list of moves that it considered before, selected by remaining depth. Just to evaluate manually what type of positions it typically has to judge, and if there is an identifiable source of error that could be cured.

One frequent mistake is that it has the choice between capturing two different undefended Rooks, one with a Rook, the other with a lower piece. Of course it tries the lower piece first. (For this it does not matter if you sort MVV/LVA or by SEE value.) And that often backfires, because the R on R attack was of cource reciprocal, so when I capture the Rook with the low piece, his other Rook captures mine, which sometimes is undefended.

So lacking the geneal information on existing threats against my pieces (which I might perhaps obtain from analysing the null-move reftation, but not in QS), it is often predictably better to capture with a higher-valued attacker first, if that attacker is attacked back by its would-be victim, while the other attacker attacks another victim of the same value. Even if the first victim is defended, it is in general better to take it first, to resolve the reciprocal threat in a forcing manner, and cash the good capture wth the lower attacker later.

Another frequent error in the order I use now (basically MVV based) occurs if the same piece can capture a high defended piece or a lower undefended piece. Going for the highest victim first would lose you the possibility to gobble up the low piece later. So where in general it is better to first trade the MVV before cashing in on a lower victim with better SEE, it would pay to check in case of a defended MVV of the piece you are going to take it with has alternative targets with better SEE (typically ndefended ones).
I do not believe pure MVV/LVA is that good. I've run way too many tests and you can find long discussions back in the early 90's in r.g.c.c with myself, Hsu, and others.

However, the current trend seems to be to recognize safe/good captures with traditional means, but then use the MVV/LVA to sort _those_ moves. And it is a compromise that works well for most cases, but not for all. This does solve the problem of trying QxR where R is defended, before you try PxN where this wins material outright. But given the option of an even capture for a queen or for a knight, you try the queen first.

Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: MVV/LVA. Or should it be LVV/MVA?

Post by Daniel Shawul » Tue Mar 31, 2009 6:56 pm

I think that kind of problem will not be solved by MVV/LVA or a SEE. In the past I tried to "see" not just on a single square but for every square where there is a piece (not pawns). This is an idea I took from Ed where he computes attack tables in the evaluation. The SEE value can be calculated cheaply (infact precalculated at startup). That information can be used anywhere in the quiescence search for move ordering. But the problem for me was i could not do lazy evaluation to use that for "seeing". Calculating the attack tables is so slow I am contemplating to write a different eval nowadays. However if you have that then you can do many "sees" and other curious evaluation I guess.

User avatar
hgm
Posts: 23792
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: MVV/LVA. Or should it be LVV/MVA?

Post by hgm » Tue Mar 31, 2009 8:23 pm

bob wrote:I do not believe pure MVV/LVA is that good. I've run way too many tests and you can find long discussions back in the early 90's in r.g.c.c with myself, Hsu, and others.
Well, I am not using pure MVV/LVA, I only said that my current move ordering was MVV based. I do frown at HxL captures: I do not do a full SEE on those (yet), but if I encounter one in the MVV/LVA ordering, I do test if the victim is defended. If it is defended by a piece that is also lower than the attacker, I discard it immediately as a bad capture: it is then sorted with the non-captures. (Note that this is a Xiangqi engine, and that in Xiangqi 2 lower pieces are always worth less than a single higher one.) If the piece was undefended I immediately take it. But if it was lower, but defended by something that was equal or higher, I postpone it until after every Low x High, Equal x Equal or Any x Undefended capture has been tried.

In d=0 nodes this gives already 97% cut rate on the first move for the nodes that are cut by a move (and not by stand pat). This includes cuts by the hash move, but usually there is no hash moves at the leaves, and non-captures are not accepted as hash moves in QS anyway.

But from looking at the other 3% it seems thee are some easy tricks that could make it better. E.g. upgading reciprocal captures. And when you have the choice of two equal targets, it might be more important to take the one that is positioned better (accordig to the PST) first than to capture with the lowest attacker or the highest SEE first. The LVA ordering is really only useful in choosing how to capture the same victim. If you have captures on two different equal-valued victims, and neither of them is HxL, it is not obvious at all why it would be preferable to start with the lowest attacker, or with the highest SEE.

The biggest problem seems to occur at d>0: there the cut-rate on my first move is only ~80% (not counting null move). Sorting al moves, including captures, by history seems to work better than trying captures first. Especially when I keep separate history for captures and non-captures.

Dann Corbit
Posts: 10207
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: MVV/LVA. Or should it be LVV/MVA?

Post by Dann Corbit » Tue Mar 31, 2009 8:48 pm

One way to resolve this sort of thing is (for every square on the board) to count the types and colors of all attackers.

This is best done incrementally.

Then, when you have the complete list of attackers, whenever you update the board, tag each square as:
1. King safe for black
2. Queen safe for black
3. Rook safe for black
4. Knight/Bishop safe for black
5. Pawn safe for black
6. Pawn safe for white
7. Knight/Bishop safe for white
8. Rook safe for white
9. Queen safe for white
10.King safe for white

Whenever you move a chessman, you pick up its influence and re-add its influence. It should also consider x-rays. It sounds like a lot of work, but you can precompute everything.

If a square is knightsafe, you can attack it with a knight or bishop.
If a square is pawnsafe, you can attack it with a pawn but not a knight.

Just one way of doing it.

Post Reply