Creating a Chess AI Part 3: Move Ordering

Move Ordering: Guiding the Search

The last post went over NegaMax and Alpha-Beta pruning. I explained that Alpha-Beta pruning lets the chess engine skip evaluating moves that are impossible to be the best option.

However, something to note with Alpha-Beta pruning is that its efficiency relies heavily on the order in which the moves are searched. If we search the best move first, Alpha-Beta pruning can prune away a lot of branches immediately. If we search the worst moves first, Alpha-Beta pruning does nearly nothing so we end up searching nearly as many moves as without it.

To solve this we go through a process called move ordering.

What is Move Ordering

Move ordering is just guessing which moves are most likely to be good and searching them first. We don't need to perfectly rank every single move, we just need something fast and a good enough representation.

A common thought process when thinking about move ordering is why not use this time to search moves? The answer to this is just that the time spent ordering moves is so small compared to the millions of moves being searched so the benefit vastly outweighs the cost.

It becomes a lot faster to spend this small amount of time before searching to then search less moves in the future.

The Sorting Driver

This system works by a driver function that iterates through the legal moves and sorts them.

C# has a function called Array.Sort. This sorts the numbers in ascending order from lowest to highest. Because we want our highest scoring moves first, we can store the scores as a negative number and then we can use Array.Sort and it will work as intended.

public void OrderMoves(Move[] moves, int count, Bitboards board)
{
    for (int i = 0; i < count; i++)
    {
        //scored as negative due to Array.Sort sorting in ascending order
        _moveScores[i] = -GetMoveScore(moves[i], board);
    }

    Array.Sort(_moveScores, moves, 0, count);
}

note: in my code I have my own custom list implementation that I use, so my code is slightly different to this one shown.

MVV-LVA (Move Valuable Victim, Least Valuable Attacker)

When predicting which moves to look at first, the best place to look is captures. To sort them we use a heuristic called MVV-LVA. This simply means that capturing a queen with a pawn will be searched before capturing a pawn with a queen.

Here is how that can be done.

if (move.IsCapture) {
	Piece attacker = board.GetPieceOnSquare(move.StartingPos);
	Piece victim = Piece.None;

	//account for en passant
	if (move.Flag == MoveFlag.EnPassantCapture)
        victim = board.GetTurn() ? Piece.BlackPawn : Piece.WhitePawn;
	else
        victim = board.GetPieceOnSquare(move.EndingPos);

	//offset of 10,000 makes sure all captures are searched first
	// * 10 ensures that more weight is given to the victims value
	score = 10000 + (GetPieceValue(victim) * 10) - 
		   GetPieceValue(attacker);
}

Pawn Promotions

Pawn promotions are also often very good moves, for this reason we can also prioritise searching these moves.

if (move.IsPromotion)
{
	score += 20000 + GetPieceValue(move.PromotionPieceType);
}

Conclusion

By using simple, fast checks for captures and promotions, our alpha-beta pruning engine the ability to prune off a lot more moves. It's important to remember the speed of this is increased a lot by our binary move representation, as it allows us to check for captures or promotions faster.

This can be made even faster by also sorting all the quiet moves, as sometimes they are the best move. This can be done through killer moves, or the history heuristic but I wont go into detail on them in this blog series.