Sorting Captures

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.
theturk1234
Posts: 52
Joined: Tue Jul 12, 2016 3:28 am

Sorting Captures

Post by theturk1234 » Wed Aug 03, 2016 2:39 pm

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
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: Sorting Captures

Post by brtzsnr » Wed Aug 03, 2016 2:58 pm

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
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Sorting Captures

Post by ZirconiumX » Wed Aug 03, 2016 3:02 pm

brtzsnr wrote: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.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

jdart
Posts: 3835
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Sorting Captures

Post by jdart » Wed Aug 03, 2016 6:31 pm

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
Posts: 154
Joined: Tue May 17, 2011 6:12 pm

Re: Sorting Captures

Post by voyagerOne » Wed Aug 03, 2016 6:34 pm

@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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Sorting Captures

Post by bob » Wed Aug 03, 2016 7:35 pm

theturk1234 wrote: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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Sorting Captures

Post by bob » Wed Aug 03, 2016 7:37 pm

ZirconiumX wrote:
brtzsnr wrote: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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Sorting Captures

Post by bob » Wed Aug 03, 2016 7:41 pm

brtzsnr wrote: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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Sorting Captures

Post by bob » Wed Aug 03, 2016 8:46 pm

voyagerOne wrote:@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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Sorting Captures

Post by bob » Wed Aug 03, 2016 8:49 pm

bob wrote:
voyagerOne wrote:@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.

Post Reply