Sorting Captures

[ZirconiumX]

@Matthew

You are doing something wrong then...

What is confusing is that you don't subtract the two!!

MVV - LVA The hypen(-) doesn't mean subtraction!

Uh... That's exactly what it means.

Let say you have two captures;

A. Queen is captured by Queen
B. Rook is captured by Pawn

Based on MVV - LVA:
"A" should be your first selection.

Actually no, it shouldn't. QxQ is at best an equal trade, so it gets a score of 0. PxR is a winning trade, so it gets searched first. Why would you search equal captures before winning captures?

An easy way to score this is what we do in SF.
Use the PieceValue for MVV
And index for LVA.

Where index = (P= 1, N = 2, B=3, R=4, Q=5 K=6)
Since your index is much smaller than PieceValue you then can do subtraction.

This doesn't work, because dorpsgek has king = 0. Also, just because something works for stockfish doesn't mean it works for everybody. Junior doesn't do null move, for example.

Example above:
A: qxq = 900(Queen Value) - 5 = 895
B: pxr = 500 (Rook Value) - 1 = 499


Edit:
You can sort by just pieceValues by:
MVV * F - LVA

Where F is a factor greater than your Queen Value (Largest Value).
Just be careful not to do an integer overflow.

I hope this helps you out.
GL!

So if you have F as 10, you get what I tested:

Code: Select all

Score of New vs Old: 404 - 626 - 124  [0.404] 1154
ELO difference: -68
SPRT: llr -2.96, lbound -2.94, ubound 2.94 - H0 was accepted
Finished match
Press any key to continue . . .

[kbhearn]

@Matthew

You are doing something wrong then...

What is confusing is that you don't subtract the two!!

MVV - LVA The hypen(-) doesn't mean subtraction!

Uh... That's exactly what it means.

Let say you have two captures;

A. Queen is captured by Queen
B. Rook is captured by Pawn

Based on MVV - LVA:
"A" should be your first selection.

Actually no, it shouldn't. QxQ is at best an equal trade, so it gets a score of 0. PxR is a winning trade, so it gets searched first. Why would you search equal captures before winning captures?

1) QxQ is not at best an equal trade - the queen may be hanging, you may be able to win the piece that captures it back if it's not hanging, you have to go to SEE to find out if it's expected to be equal or better than equal

2) MVV-LVA or MVV/LVA or however you want to write it just means most valuable victim and then least valuable attacker to most people, not a mathematical operation.

3) As for why it may be more valuable than SEE which predicts winning captures
- getting the high value enemy pieces off generally means less captures on the next ply of QS and a smaller subtree. also note that if you do futility pruning in QS then after QxQ only the captures that will take the queen back may need to be checked, not the captures of knights, rooks, etc elsewhere on the board.
- usually inserting a QxQ PxQ move pair before PxR will still result in a quick refutation
- the one case i can think of where it could be a downside is where an otherwise hanging piece is allowed to recapture the queen - if this is good enough to cut anyways it may have the side effect of a much larger subtree when taking the hanging piece first may result in more null moves and a smaller subtree to prove the cut and as long as the queen trade is a cut anyways the free piece capture will never be tried. I expect this specific case to be rather rare though.

[theturk1234]

Is there any particular reason for the 64 * MVV? What I mean is, does the number 64 have any meaning or can I use any number instead?

David Cimbalista

[bob]

Is there any particular reason for the 64 * MVV? What I mean is, does the number 64 have any meaning or can I use any number instead?

David Cimbalista

All you want is a number big enough so that when you subtract the capturing piece it won't screw the order up. I do it this way myself:

const int MVV_LVA[7][7] = {
{0, 5<<21, 4<<21, 4<<21, 3<<21, 2<<21, 1<<21},
{0, 10<<21, 9<<21, 9<<21, 8<<21, 7<<21, 6<<21},
{0, 15<<21, 14<<21, 14<<21, 13<<21, 12<<21, 11<<21},
{0, 15<<21, 14<<21, 14<<21, 13<<21, 12<<21, 11<<21},
{0, 20<<21, 19<<21, 19<<21, 18<<21, 17<<21, 16<<21},
{0, 25<<21, 24<<21, 24<<21, 23<<21, 22<<21, 21<<21},
{0, 30<<21, 29<<21, 29<<21, 28<<21, 27<<21, 26<<21}};

That array is indexed by [captured][capturing]

I do the shifting so I can stick that on the front of the move and sort the thing as a single 32 bit value.

Critical factor is that MVV has to overwhelm LVA. Some of the above can't really be used effectively since there is no capturing piece "0", and you really can't capture piece "6" (a king) either. But it is simple and fast.

If your pieces go from 1 (pawn) to 6 (king) then multiplying by 6 is good enough. Anything bigger will work equally well. But if you go smaller you will violate MVV/LVA.

[bob]

@Matthew

You are doing something wrong then...

What is confusing is that you don't subtract the two!!

MVV - LVA The hypen(-) doesn't mean subtraction!

Uh... That's exactly what it means.

Let say you have two captures;

A. Queen is captured by Queen
B. Rook is captured by Pawn

Based on MVV - LVA:
"A" should be your first selection.

Actually no, it shouldn't. QxQ is at best an equal trade, so it gets a score of 0. PxR is a winning trade, so it gets searched first. Why would you search equal captures before winning captures?

He was correct there. You ALWAYS capture the most valuable piece (in this case the queen). That's the key for MVV/LVA ordering.

An easy way to score this is what we do in SF.
Use the PieceValue for MVV
And index for LVA.

Where index = (P= 1, N = 2, B=3, R=4, Q=5 K=6)
Since your index is much smaller than PieceValue you then can do subtraction.

This doesn't work, because dorpsgek has king = 0. Also, just because something works for stockfish doesn't mean it works for everybody. Junior doesn't do null move, for example.

Example above:
A: qxq = 900(Queen Value) - 5 = 895
B: pxr = 500 (Rook Value) - 1 = 499


Edit:
You can sort by just pieceValues by:
MVV * F - LVA

Where F is a factor greater than your Queen Value (Largest Value).
Just be careful not to do an integer overflow.

I hope this helps you out.
GL!

So if you have F as 10, you get what I tested:

Code: Select all

Score of New vs Old: 404 - 626 - 124  [0.404] 1154
ELO difference: -68
SPRT: llr -2.96, lbound -2.94, ubound 2.94 - H0 was accepted
Finished match
Press any key to continue . . .

[Daniel Anulliero]

In Isa , I do the move ordering like this :

Code: Select all

int move_ordering(int type, int dep, int arr)
{
    int val = 0;

    if(type == PROMO_DAME)
        val = 4000000;
    else if&#40;type >= PROMO_CAVALIER && type < PROMO_DAME&#41;
        val = &#40;2000000 + valeur_piece&#91;type&#93;);
    if&#40;probe_move_ordering&#40;dep, arr, prof&#41;)
        val += 1000000;
    if&#40;type == CAPTURE&#41;
        val = &#40;3000000 + &#40;valeur_piece&#91;piece&#91;arr&#93;&#93; - valeur_piece&#91;piece&#91;dep&#93;&#93;));
    else
    &#123;
        if&#40;killer1&#91;prof&#93;.from == dep && killer1&#91;prof&#93;.dest == arr&#41;
            val +=  2000000;
        else if&#40;killer2&#91;prof&#93;.from == dep && killer2&#91;prof&#93;.dest == arr&#41;
            val += 1500000;
        else
            val += history&#91;dep&#93;&#91;arr&#93;;
    &#125;

    return val;
&#125;

You can see the promotions are ahead , then the hash move , then MVV / LVA with pieces values , no index (wrong?)
Then killer 1 and 2
Then history value

I use high values because the max value of history is 999999
So , with my scheme , q x q = 3000000 and pxr = 3000400
Ok I'm certainly doing something wrong

[tttony]

Here the code from Vice:

Code: Select all

const int VictimScore[13] = { 0, 100, 200, 300, 400, 500, 600, 100, 200, 300, 400, 500, 600 };
static int MvvLvaScores[13][13];

void InitMvvLva() {
	int Attacker;
	int Victim;
	for &#40;Attacker = wP; Attacker <= bK; ++Attacker&#41; &#123;
		for &#40;Victim = wP; Victim <= bK; ++Victim&#41; &#123;
			MvvLvaScores&#91;Victim&#93;&#91;Attacker&#93; = VictimScore&#91;Victim&#93; + 6 - &#40;VictimScore&#91;Attacker&#93; / 100&#41;;
		&#125;
	&#125;
&#125;

[cdani]

Just to illustrate that move ordering can be quite ellaborated far from the standard ways, in Andscacs all the different move ordering and move picking functions are more than 400 lines of code. I have a function for ordering captures and promotions, one that does the same but is specialized for quiescence, one to order quiets that is like 150 lines long, and a move pick function with 15 different phases.

[cdani]

This is another way of ordering captures:
https://github.com/official-stockfish/S ... d9a2062f32

[cdani]

In quiescence promotion ordering I review only queen promotion, and for knight promotion only when it is check.