When the possible moves are searched by an Alpha Beta algorithm to find the best move to play, more branches of the search tree are pruned if the moves are first ordered into an educated guess of the best order. Move Ordering will substantially reduce the number of branches searched.
MVV/LVA stands for Most Valuable Victim/Least Valuable Attacker. As it says, we order the potential captures by the most valuable piece captured taken by the least valuable attacker.
We give each piece, as listed in the Pieces Representation, a value. The precise values used are irrelevant, they merely indicate that one piece is more valuable than another.
enum class Pieces { empty, P, N, B, R, Q, K, p, n, b, r, q, k, offboard, enpassant };
int mvvLvaValue[13] = { 0,100,200,300,400,500,600,100,200,300,400,500,600 };
We create an array to hold our evaluations.
int mvvLvaScores[14 * 14];
The function InitMvvLva populates the array with an evaluation for each combination of Attacker and Victim. The index of the array is [victim * 14 + attacker] giving us space to store all of the combinations of victim and attacker.
void MoveGen::initMvvLva() //Most Valuable Victim, Least Valuable Attacker
{
int attacker = 0;
int victim = 0;
for (attacker = static_cast <int>(Defs::Pieces::P);
attacker <= static_cast <int>(Defs::Pieces::k);
++attacker)
for (victim = static_cast <int>(Defs::Pieces::P);
victim <= static_cast <int>(Defs::Pieces::k);
++victim)
mvvLvaScores[victim * 14 + attacker] =
mvvLvaValue[victim] + 6
- static_cast<int>(mvvLvaValue[attacker]) / 100);
}
So if a pawn takes a queen, the evaluation is 500 +6 – (100/100) = 505
If a pawn takes a rook, the evaluation is 400 +6 – (100/100) = 405
If a bishop takes a queen, the evaluation is 506 – (300/100 ) = 503
If a bishop takes a rook, the evaluation is 400 +6 – (300/100) = 503
Captures of queens all start 500, captures of bishops all start 400 etc.
Captures by pawns will all end in 0, captures by bishops will all end in 3 etc.
We will order by highest scoring captures, which equates to the most valuable victim and the least valuable attacker.
We hold a field, score, on the Move Representation, to hold the MVV/LVA score, populated when we add moves, calling the getCaptureScore function . 1 million is added to score to allow room for later ordering algorithms. En passant captures, pawn taking pawn, always score 105.
int MoveGen::getCaptureScore(int from, int to, Gameboard& Board, int ply)
{
int victim = static_cast<int>(Board.getPiece(to));
int captureScore = 0;
if (victim > 0)
{
int attacker = static_cast<int>(Board.getPiece(from));
//enpassant capture
if (victim == static_cast<int>(Defs::Pieces::enpassant)
&& (attacker == static_cast<int>(Defs::Pieces::p)
|| attacker == static_cast<int>(Defs::Pieces::P)))
{captureScore = 1000000 + 105;} //Pawn taked Pawn is 105
else
{captureScore = getMvvLvaScores(victim * 14 + attacker) + 1000000;}
}
return captureScore;
}
