Sorting Captures

[theturk1234]

Hi,
In which order should I search captures? Starting with pawn promotion captures, or good captures, or what? Also how do you determine "good" and "bad" captures? I've been thinking about it and the only way I could come up with is literally a 2-ply search in alpha-beta. But that would be pretty expensive, right?

Thanks,
David Cimbalista

[brtzsnr]

Variations of MVV-LVA is the easiest/standard solution. https://chessprogramming.wikispaces.com/MVV-LVA

MVV -> most valuable victim
LVA - > least valuable attacker.

Some use MVV/LVA. I use 64*MVV - LVA. The later usually produces small search trees because it reduces the mobility of the other player.

[ZirconiumX]

Variations of MVV-LVA is the easiest/standard solution. https://chessprogramming.wikispaces.com/MVV-LVA

MVV -> most valuable victim
LVA - > least valuable attacker.

Some use MVV/LVA. I use 64*MVV - LVA. The later usually produces small search trees because it reduces the mobility of the other player.

I tried 10*MVV-LVA, but it was worse than plain MVV-LVA scoring. Both did better than SEE sorting though. SEE should probably just be for pruning bad captures.

[jdart]

I order by MVV/LVA but then as moves are chosen from the move generator each capture is checked by SEE. Then those with negative SEE are put in an array to be searched much later in the "losing captures" phase.

--Jon

[voyagerOne]

@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!


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.


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.

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!

[bob]

Hi,
In which order should I search captures? Starting with pawn promotion captures, or good captures, or what? Also how do you determine "good" and "bad" captures? I've been thinking about it and the only way I could come up with is literally a 2-ply search in alpha-beta. But that would be pretty expensive, right?

Thanks,
David Cimbalista

MVV/LVA.

Most Valuable Victim (captured piece) first, ties broken by Least Valuable Attacker (capturing piece).

[bob]

Variations of MVV-LVA is the easiest/standard solution. https://chessprogramming.wikispaces.com/MVV-LVA

MVV -> most valuable victim
LVA - > least valuable attacker.

Some use MVV/LVA. I use 64*MVV - LVA. The later usually produces small search trees because it reduces the mobility of the other player.

I tried 10*MVV-LVA, but it was worse than plain MVV-LVA scoring. Both did better than SEE sorting though. SEE should probably just be for pruning bad captures.

That _IS_ MVV/LVA order, you just converted MVV/LVA into a single integer. I do something similar but use a table lookup instead. In your case, if MVV is 1-5 (pawn through queen) and LVA is 1-6, then that will give perfect MVV/LVA ordering and I can't imagine why you would see a difference since there isn't any.

[bob]

Variations of MVV-LVA is the easiest/standard solution. https://chessprogramming.wikispaces.com/MVV-LVA

MVV -> most valuable victim
LVA - > least valuable attacker.

Some use MVV/LVA. I use 64*MVV - LVA. The later usually produces small search trees because it reduces the mobility of the other player.

I have seen this stated twice. 64 * MVV - LVA is EXACTLY MVV/LVA order.

assume MVV = Q = 5, and LVA = 1 You get 64 * 5 - 1 for PxQ, and you get 64 * 4 - 2 for NxR. That is exactly MVV/LVA order. Whether you multiply by 10, or 1000, it doesn't matter so long as the multiplier is at least as large as the largest piece number.

[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!


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.


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.

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!

I don't follow. MVV/LVA means first sort by most valuable captured piece (victim), then tie-break with least valuable capturing piece.

10*MVV - LVA does that perfectly.

Suppose you can play NXQ and QxQ where we use the traditional 1 2 3 4 5 for pawn through knight.

For both, the victim = 5 so both get an initial score of 50, then for the knight, you subtract 2, giving 48, and for the second capture you get 50 - 5, which is 45. You try the 48 first which is perfect MVV/LVA order...

[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!


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.


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.

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!

I don't follow. MVV/LVA means first sort by most valuable captured piece (victim), then tie-break with least valuable capturing piece.

10*MVV - LVA does that perfectly.

Suppose you can play NXQ and QxQ where we use the traditional 1 2 3 4 5 for pawn through knight.

For both, the victim = 5 so both get an initial score of 50, then for the knight, you subtract 2, giving 48, and for the second capture you get 50 - 5, which is 45. You try the 48 first which is perfect MVV/LVA order...

Your approach has a potential flaw if bishop and knight have different values (which is pretty common).

if B=325 and knight=300,

you would tend to play QXB before NXB.

QXB = 325 - 5, NXB = 300-2. QXB goes first and that is NOT MVV/LVA ordering.