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
Sorting Captures
Moderators: hgm, Rebel, chrisw
-
- Posts: 433
- Joined: Fri Jan 16, 2015 4:02 pm
Re: Sorting Captures
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.
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.
zurichess - http://www.zurichess.xyz
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Sorting Captures
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.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.
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: Sorting Captures
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
--Jon
-
- Posts: 154
- Joined: Tue May 17, 2011 8:12 pm
Re: Sorting Captures
@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!
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!
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Sorting Captures
MVV/LVA.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
Most Valuable Victim (captured piece) first, ties broken by Least Valuable Attacker (capturing piece).
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Sorting 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.ZirconiumX wrote: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.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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Sorting Captures
I have seen this stated twice. 64 * MVV - LVA is EXACTLY MVV/LVA order.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.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Sorting Captures
I don't follow. MVV/LVA means first sort by most valuable captured piece (victim), then tie-break with least valuable capturing piece.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!
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...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Sorting Captures
Your approach has a potential flaw if bishop and knight have different values (which is pretty common).bob wrote:I don't follow. MVV/LVA means first sort by most valuable captured piece (victim), then tie-break with least valuable capturing piece.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!
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...
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.