A smarter MVV/LVA

[thevinenator]

i'm playing around with a "smarter" replacement for the usual MVV/LVA scheme.

Assuming the following values for each piece (from Chess 4.5 and others)

#define PAWN_VALUE 100
#define KNIGHT_VALUE 325
#define BISHOP_VALUE 350
#define ROOK_VALUE 500
#define QUEEN_VALUE 900

I created a 2D array indexed by attacker (down) and victim (across)

Code: Select all

      P     N     B     R     Q     K
P - 6002 20225 20250 20400 20800 26900
N - 4775  6004 20025 20175 20575 26675
B - 4750  4975  6006 20150 20550 26650
R - 4600  4825  4850  6008 20400 26500
Q - 4200  4425  4450  4600  6010 26100
K - 3100  3325  3350  3500  3900 26000

King capture moves have the highest value (for non-legal move generation) so they sort to the top.
The values above 20000 are "good captures", 6000 range are equals, and anything lower is a bad capture.
The idea is to base the ordering on the difference between the values of the pieces, this comes to light esp. for knights and bishops. If you value a bishop higher than a knight, then NxB will be a good capture and BxN will not. the piece values are also used for the material calculation, so it follows that what is considered a good capture should be aligned with the evaluation. PXR scores the same as RxQ since the delta between their values is the same. As Bruce Moreland pointed out in his Programming Pages, MVV/LVA scores RxR ahead of PxB. That doesn't happen here. if you want ties to be broken, say to make RxQ sort higher than PxR, then just modify the value of the Queen to be 901, for example.

If your QSearch only does "good" captures and not "good/equal", then the selection only needs to look at moves with a score above 20000, otherwise, those above 6000. QxQ will be looked at before RxR.

This table is generated at compile time based on the values given to the pieces, so if they are tweaked, the table is automatically adjusted.

One can always tune the values by hand, but there are only a few places where it might matter.

comments/criticisms always welcome.

[H.G.Muller]

A lot of research has been performed on move ordering, and this has clearly shown that it is quite important to search RxR before PxB. Several factors contributeto this. For one, the Rook can be unprotected (and usually is), so RxR gains on average more material than PxB. Playing RxR is almost always a better move than PxB, because in the unfavorable case that the Rook was protected, you still gain a Rook if the opponent does not recapture. And if he does recapture, you play the PxB after all. The probability that the recapture spoiled the PxB (e.g. because the Bishop performed the recapture) is quite small. If, OTOH, you start with PxB, the opponent will retaliate RxR, and you lost the exchange in the first two ply, and might now have to work a lot harder (i.e. seach a larger tree) to get out ahead. If you can get out ahead at all; your own Rookmight have been unprotected, and gone forever.

So equal captues of high pieces should be searched before Low x High captures of lower pieces. The only case where there is something to gain is High x Low captures. Without additional information it is still much better to search QxR before PxB, because after PxB the Rook might escape, or worse, play RxQ. The additional information is whether the involved pieces are protected or not. (Or better yet, the SEE value of exchange on the same square, to make sure that you will still try RxB on a B attacked by 2 Rooks and protected by only N.) When you then see that the victim of a High x Low capture is (sufficiently) protected, (and does not attack you back) you can postpone (or even prune) that capture until after search of the capture of lower pieces.