A game between two such mental giants,
Mr. A and Mr. B, would proceed as follows.
They sit down at the chessboard, draw for colours,
and then survey the pieces for a moment.
Then either
(1) Mr. A says, "I resign" or
(2) Mr. B says, "I resign" or
(3) Mr. A says, "I offer a draw,"
and Mr. B replies, "I accept."
Programming a Computer for Playing Chess, 1950
Claude E. Shannon

Making a Chess Engine with Claude E. Shannon

Exploring Minimax, Alpha-Beta Pruning, and MVV-LVA

In this post, we will examine a chess program following a proposal by Claude E. Shannon.

The algorithm at the core of the program, minimax, was first established by John Von Neumann in 1927. Shannon proposed a program that uses minimax to play chess in 1950. Alan Turing wrote an algorithm, Turochamp, and played a match in 1952, executing its step manually, using himself as the computer. I hope, to anyone who is interested in AI, seeing these names altogether would bring at least some level of excitement, and hints at the rich history of programs playing games.

The program uses minimax as its core as proposed by Shannon. The above implementation also has alpha-beta pruning, and MVV-LVA move ordering to help with pruning branches earlier.

You can turn off alpha-beta pruning to play against the exact program (Type A) Shannon described. The only thing changing from the user's perspective is increased thinking time without any change in the program's strength.

Code for this engine was written in Rust and compiled to WebAssembly for performance. The Rust implementation can be found here:

Throughout the post I'll show simple implementation of concepts mentioned in Python. The complete Python implementation can be found here:

Evaluating a Chess board

If we had an exact function to evaluate a board position, we could simply check the result for every legal move, on average about 35, and choose the one with the highest score. However, no such computable function exists today. While modern engines like AlphaZero use deep neural networks to approximate this, Shannon's paper proposes a much simpler approach. Assigning a fixed value to each piece:

K, Q, R, B, N, and P are the numbers of White kings, queens, rooks, bishops, knights, and pawns on the board, and the primed letters are the same values for Black.

# Shannon proposes to encode the pieces like this
E = 0	# Empty

WP = 1	# White Pawn
WN = 2	# White Knight
WB = 3	# White Bishop
WR = 4	# White Rook
WQ = 5	# White Queen
WK = 6	# White King

BP = -1	# Black Pawn
BN = -2	# Black Knight
BB = -3	# Black Bishop
BR = -4	# Black Rook
BQ = -5	# Black Queen
BK = -6	# Black King

def get_fresh_board():
    board = [
        [WR, WN, WB, WQ, WK, WB, WN, WR],
        [WP, WP, WP, WP, WP, WP, WP, WP],
        [E,  E,  E,  E,  E,  E,  E,  E],
        [E,  E,  E,  E,  E,  E,  E,  E],
        [E,  E,  E,  E,  E,  E,  E,  E],
        [E,  E,  E,  E,  E,  E,  E,  E],
        [BP, BP, BP, BP, BP, BP, BP, BP],
        [BR, BN, BB, BQ, BK, BB, BN, BR]
    ]
    return board

PIECE2POINT = {
    WP: 1, WN: 3, WB: 3, WR: 5, WQ: 9, WK: 200,
    BP: -1, BN: -3, BB: -3, BR: -5, BQ: -9, BK: -200,
    E: 0
}

def evaluate_board(board):
    total_point = 0
    for row in board:
        for piece in row:
            total_point += PIECE2POINT[piece]
    return total_point

White's aim is to maximize this score and the Black's is to minimize.

Using an evaluation function to choose a move

Having an approximate evaluation function, we can now start to make moves that are not completely random.

Let's assume we are the White player. The simplest way to use this function is to play out every legal move, resulting in about 35 different positions, and choose the move that leads to the highest score. If you set the depth on the engine above to 1, this is the program you will be playing against (though it will be a very bad opponent).

To make this opponent slightly stronger, we can look one step deeper. Instead of evaluating the board immediately after our move, we consider all possible responses available to Black. Since Black aims to minimize the score, we must assume they will choose the response with the lowest value. Therefore, we assign this minimum value as the actual score for our candidate move.

If you set the depth to 2, this is the program you will be playing against. With this setting, we are running our evaluation function on around 35² moves. You can verify this number in the engine above. The number of legal moves changes throughout the game: it starts at 20, peaks during the middle game, and decreases as pieces are captured or when checks restrict the available responses. Turn off "Pruning" for now to see the numbers we are expecting with this method.

We can keep increasing the depth for this method as much as we want and get more accurate evaluations. But the number of board positions we will have to evaluate will increase exponentially as well. You can try playing with different depth settings and see the increase in time yourself.

# get_legal_moves returns an array of moves
# each move is a tuple of (current position, target position, piece)
# each position is a tuple if integers representing rank and file
# make_move makes a move on the board and 
# returns a piece if any piece was capured
# undo_move takes the move back and puts back the captured piece

def minimax(board, color, depth):
    if depth == 0:
        return evaluate_board(board)
    best_point = float("-inf") if color == "white" else float("inf")
    legal_moves = get_legal_moves(board, color)
    for move in legal_moves:
        prev_piece = make_move(board, move)
        point = minimax(board, get_opponent(color), depth - 1)
        undo_move(board, move, prev_piece)
        if color == "white":
            best_point = max(best_point, point)
        else:
            best_point = min(best_point, point)
    return best_point

Type A and Type B programs

Shannon divides the types of programs that can play chess into two classes, called Type A and Type B.

Type A programs are programs that look at every possible sequence up to a certain depth and choose the best move. If the game of chess was technically to be called "solved", this is the type of program we would need. In chess there are 35 legal moves per turn on average, this is our branching factor. Assuming an average of 40 turns (40 moves per player) it would be around 35⁸⁰ ≈ 10¹²⁰ positions. In the best case scenario alpha-beta pruning reduces the branching factor to the square root of the original number, so (35^0.5)⁸⁰ = 35 ⁴⁰ ≈ 10⁶¹ board positions to evaluate.

If we calculated on an extremely optimistic speed of 10⁹ board positions per second, we would still need 10⁵² seconds to evaluate every possible position. The world is expected to be engulfed by the sun well within 10¹⁰ years, and the universe is expected to be dominated by black holes within 10⁴⁰ years, entering The Black Hole Era. To be able to "solve" chess, we would need to make a computer that can withstand the decay of the universe, harvesting energy from the Hawking radiation of these black holes.

Shannons mentions two improvements to the strategy above:

1 ) Examine variations out as far as a quasi-stability has been established.
Meaning don't stop exploring the branches in the middle of a trading sequence.
2 ) Select the variations to be explored so to not waste time in pointless variations.
This would require a policy function which ranks the moves to be explored.

Shannon calls a strategy with these two improvements type B strategy.

A type A program

The complete program for a type A strategy consists of nine sub-programs which we designate T₀, ₁, ..., T₈ and a master program T₉. The basic functions of these programs are as follows:

• T₀ – Makes move (a, b, c) in position P to obtain the resulting position.
• T₁ – Makes a list of the possible moves of a pawn at square (x, y) in position P.
• T₂, ..., T₆ – Similarly for other types of pieces: knight, bishop, rook, queen and king.
• T₇ – Makes list of all possible moves in a given position.
• T₈ – Calculates the evaluating function f(P) for a given position P.
• T₉ – Master program; performs maximizing and minimizing calculation to determine proper move.

With a given position P and a move (a, b, c) in the internal memory of the machine it can make the move and obtain the resulting position by the following program T₀.

Programming a Computer for Playing Chess, 1950

We have already implemented T₈ in the code block "Evaluating the board in Python". Also in the code block "Minimax in Python" we referenced a function called `make_move` which is our T₀. T₁ is also relatively simple.

def get_pawn_legals(board, color, position):
    legal_moves = []
    rank, file = position
    if color == 'white':
        if rank == 7:
            return []
        if board[rank+1][file] == 0:
            # Pawn going 1 square forward
            legal_moves.append((rank+1, file))
        if rank == 1 and board[rank+1][file] == 0 and board[rank+2][file] == 0:
            # Pawn going 2 squares if it's in the initial position
            legal_moves.append((rank+2, file))
        if file > 0 and board[rank+1][file-1] < 0:
            # Capturing a piece on diagonal square
            legal_moves.append((rank+1, file-1))
        if file < 7 and board[rank+1][file+1] < 0:
            # Other side diagonal
            legal_moves.append((rank+1, file+1))
    else:
        if rank == 0:
            return []
        if board[rank-1][file] == 0:
            legal_moves.append((rank-1, file))
        if rank == 6 and board[rank-1][file] == 0 and board[rank-2][file] == 0:
            legal_moves.append((rank-2, file))
        if file > 0 and board[rank-1][file-1] > 0:
            legal_moves.append((rank-1, file-1))
        if file < 7 and board[rank-1][file+1] > 0:
            legal_moves.append((rank-1, file+1))
    return legal_moves

Basic implementation for T₂, ..., T₆ can be found in the repository:

T₇ just uses the T₁, ..., T₆ to make a list of all legal moves.

PIECE2FUNC = {
        WP: get_pawn_legals,
        BP: get_pawn_legals,
        WN: get_knight_legals,
        BN: get_knight_legals,
        WB: get_bishop_legals,
        BB: get_bishop_legals,
        WR: get_rook_legals,
        BR: get_rook_legals,
        WQ: get_queen_legals,
        BQ: get_queen_legals,
        WK: get_king_legals,
        BK: get_king_legals,
}
def get_legal_moves(board, color):
    all_legal_moves = []
    for rank in range(8):
        for file in range(8):
            piece = board[rank][file]
            if piece == E:
                continue
            piece_color = "white" if piece > 0 else "black"
            if piece_color != color:
                continue
            if piece in PIECE2FUNC:
                legals = PIECE2FUNC[piece](board, color, (rank, file))
                for legal in legals:
                    all_legal_moves.append(((rank, file), legal, piece))

    return all_legal_moves

And T₉ brings everything all together.

def minimax_player(board, color, depth):
    legal_moves = get_legal_moves(board, color)
    points_w_moves = []
    for move in legal_moves:
        prev_piece = make_move(board, move)
        point = minimax(board, get_opponent(color), depth - 1)
        points_w_moves.append((point, move))
        undo_move(board, move, prev_piece)
    # choose_random_best_move just chooses a random move among the highest scored ones
    best_point_w_move = choose_random_best_move(points_w_moves, color)
    make_move(board, best_point_w_move[1])

Alpha-beta Pruning

There is a way to help our Type A program by pruning some branches of the search tree without changing the algorithm's strength. If you look at Fig 1, we ran our evaluation function on all 9 terminal positions. However, if we assume we evaluate these sequentially, up to bottom, we can see that some evaluations were unnecessary because they could not possibly affect White's final decision.

After evaluating the first possible move, White knows that the best it can do so far is +2. When looking at the second White possible move, as soon as we see a score that is lower than +2, which is -2 in the figure above, we can stop looking at the rest of the Black moves.

Since Black plays to minimize the score, once they have the option to force the game to -2, the value of this entire branch becomes at most -2. Because White can already guarantee a +2 from the first move, White will never choose this second branch.

This means the +2 we found becomes our lower bound. Any time we see a response resulting in a score lower than this lower bound, we can be sure that we will not go with that branch and we can stop looking at the other sub-branches. As White keeps exploring, it could find branches resulting in scores higher than +2, and we would increase the lower bound with these new values.

Just keeping track of a lower bound allows us to only prune one side's moves. We also need to keep track of the upper bound of the score for Black. We keep track of these scores by adding two new variables to our existing minimax implementation. The lower bound is kept track in a variable called Alpha and the upper bound in Beta.

def minimax(board, color, depth, alpha=float("-inf"), beta=float("inf")):
    if depth == 0:
        return evaluate_board(board)
    best_point = float("-inf") if color == "white" else float("inf")
    legal_moves = get_legal_moves(board, color)
    for move in legal_moves:
        prev_piece = make_move(board, move)
        point = minimax(board, get_opponent(color), depth - 1, alpha, beta)
        undo_move(board, move, prev_piece)
        if color == "white":
            best_point = max(best_point, point)
            alpha = max(alpha, point)
            if beta <= alpha:
                break
        else:
            best_point = min(best_point, point)
            beta = min(beta, point)
            if beta <= alpha:
                break
    return best_point

The idea was conceived by John McCarthy during the famous 1956 Dartmouth conference.

"McCarthy thought of the method during the Dartmouth Summer Research Conference on Artificial Intelligence in 1956, when Bernstein described an early chess program which didn't use any sort of alpha-beta." An Analysis of Alpha-Beta Pruning, 1975
Donald E. Knuth, Ronald W. Mooree

This is the very same conference where the term "Artificial Intelligence" was first coined. The proposal for this historic gathering was co-authored by John McCarthy, Marvin Minsky, Nathaniel Rochester, and Claude E. Shannon.

MVV-LVA

The efficiency of alpha-beta pruning relies heavily on the order we examine moves. If we examine the best moves first, we can prune the remaining bad branches much earlier. Since we don't know the true "best" move yet, we use heuristics to guess which moves are likely to be good.

A popular method for sorting captures is called MVV-LVA(Most Valuable Victim - Least Valuable Aggressor).

• Most Valuable Victim (MVV): If we have a choice of pieces to capture, we look at capturing the most valuable one first, for example: capturing a queen is likely to be better than capturing a pawn.
• Least Valuable Aggressor (LVA): If we can capture a piece with multiple different pieces, we start with the least valuable attacker, capturing with a pawn is likely to be safer than capturing with a queen.

To illustrate the impact of these improvements, we can look at the number of positions the engine above evaluates to find a response to the opening move 1. e4 at depth 6:

• Minimax: 309,392,030 positions
• Alpha-Beta Pruning: 3,000,909 positions
• With MVV-LVA Ordering: 1,175,609 positions