How Does a Computer Play Chess?

Chess on a small board

The board above plays Gardner’s minichess, after Martin Gardner, a writer of mathematical puzzles, who suggested chess on a 5 × 5 board in 1969. Each side has the pieces of a real game without the three on the king’s side: rook, knight, bishop, queen and king, with five pawns in front. The pieces move as in chess, except that a pawn moves only one square forward, even on its first move, and there is no castling. On this board a pawn that reaches the far row always becomes a queen (in chess you may choose another piece). You win by checkmate. It is a draw after a stalemate (no legal move, but not in check), with only the two kings left, when the same position comes up a third time, or after 25 moves each with no capture and no pawn move.

In this topic, a move means one player’s turn: White’s move and Black’s reply are two moves (chess players call each a half-move). So Looks 1 tries each of its own moves and stops; Looks 2 also tries each of your replies; Looks 3 also tries its own answer to each reply.

What one more move of looking does

Play Looks 1 a few times. Leave a piece where Black can take it, even a pawn that another of your pieces guards. Then do the same against Looks 2.

Now let the computers play each other. The board below plays 20 games and swaps the colors after each game, so each player is White in 10 of them.

Counting what the computer looks at

Go back to the first board, and watch the numbers under it. Positions looked at is the number of boards the computer made in its head, by trying moves, before it chose. At the very start of a game, Black’s first move needs:

(The numbers depend on your first move, and the last column on the order the computer happens to try its moves in.) Each extra move of looking multiplies the positions by about 9 or 10, because each side has about that many moves to choose from. The last column is the same search with a trick called alpha–beta, below: it finds exactly the same move after looking at far fewer positions.

Why the computer can’t look to the end

The tic-tac-toe player looked at every game to the end: 255,168 of them. Claude Shannon, an engineer at Bell Telephone Laboratories in the USA, worked out in 1950 what that would mean for chess. A typical position has about 30 legal moves, so a move by White and a reply by Black give about 30 × 30 ≈ 1,000 possibilities. A game lasts about 40 moves each, so there are roughly 1,000 multiplied by itself 40 times ways for a game to go: 10¹²⁰, a 1 followed by 120 zeros. Checking a million of them a second would take over 10⁹⁰ years. Even looking just three moves ahead for each side means about a billion (10⁹) positions: at a million a second, more than 16 minutes for every move.

So no computer plays chess by seeing to the end. It does what Shannon proposed:

• a.Look a few moves ahead: try every move, every reply, and so on, for a fixed number of moves. This is minimax, exactly as in tic-tac-toe, cut off after a few moves.
• b.Guess a score for each position where it stops: is White better or worse there, and by how much? A function that does this is an evaluation function.
• c.Pass the scores back up the tree, the largest where White chooses and the smallest where Black does, and play the move with the best score.

The guess is the new part. A finished game has an exact score; a position in the middle of a game doesn’t. Shannon started from the values chess players already use: a pawn is worth 1, a knight 3, a bishop 3, a rook 5 and a queen 9. Add up White’s pieces and take away Black’s: that is the material score, the guess the page’s computers use.

Skipping what can’t matter: alpha–beta

Take a small game tree (the widget below draws it). White has three moves; after each, Black has three replies, and the scores where the search stops (from White’s side: high is good for White) are 3, 12 and 8 after White’s first move, 2, 4 and 6 after the second, and 14, 5 and 2 after the third.

Plain minimax looks at all 9 scores. But think like White, checking its moves from the left. The first move is worth 3, the smallest of 3, 12 and 8, since Black will choose the reply worst for White. In the second move, Black’s first reply scores 2. White can stop looking at this move at once: Black can already hold it to 2 or less, and White already has 3. Whatever the other two replies score, White will never play this move.

That is alpha–beta pruning. The search keeps two numbers: alpha, the score White is already sure of, and beta, the score Black is already sure of. As soon as alpha is at least beta, the rest of the moves in that branch can’t change the choice, and the search skips them. Step through it:

Alpha–beta never changes the move chosen; it only skips work, and how much depends on the order the moves are tried in. In the second move the 2 came first, and two replies were skipped; in the third it came last, and all three had to be looked at.

Step 1: the rules

The page has the rules of minichess written in Python, in a file called minichess.py, which every program in this topic imports. You can use it without reading it. A board is a list of 5 strings, one for each row, from Black’s side (rank 5) down to White’s (rank 1): capital letters for White’s pieces, small letters for Black’s, and . for an empty square. A move is four numbers: the row and column it starts from, and the row and column it ends on.

This program shows the starting position and White’s moves:

from minichess import START, moves, name, show show(START)first = moves(START, 'white')print(len(first), 'moves:', [name(m) for m in first])

5 r n b q k4 p p p p p3 . . . . .2 P P P P P1 R N B Q K  a b c d e7 moves: ['a2-a3', 'b2-b3', 'c2-c3', 'd2-d3', 'e2-e3', 'b1-a3', 'b1-c3']

Now count the futures, as Step 2 of the tic-tac-toe topic did, but only a few moves ahead: how many positions can the game reach in 1, 2, 3 and 4 moves?

from minichess import START, moves, play, other def count(board, side, depth):    if depth == 0:        return 1    total = 0    for m in moves(board, side):        total = total + count(play(board, m), other(side), depth - 1)    return total for depth in [1, 2, 3, 4]:    print(f'{depth} ahead: {count(START, "white", depth)} positions')

1 ahead: 7 positions2 ahead: 53 positions3 ahead: 506 positions4 ahead: 4775 positions

Each move multiplies the count by about 9. Continue the pattern to a game of 30 moves each, 60 moves in all: 9⁶⁰ is about 10⁵⁷. Even this small board is far too big to search to the end.

Step 2: look ahead, then guess

Here is the look-ahead, with material as its guess. value(board, side, depth) is minimax from the tic-tac-toe topic with one change: when depth reaches 0 it stops and returns evaluate(board), unless the side to move is checkmated (an exact score, a big number). best_move tries each move and keeps the best; looked counts the positions made.

On this board, White’s queen can take the pawn on a4, but Black’s rook on a5 guards it.

from minichess import moves, play, other, in_check, name, show VALUES = {'P': 1, 'N': 3, 'B': 3, 'R': 5, 'Q': 9, 'K': 0} def evaluate(board):    score = 0    for row in board:        for piece in row:            if piece != '.':                if piece.isupper():                    score = score + VALUES[piece]                else:                    score = score - VALUES[piece.upper()]    return score looked = 0 def value(board, side, depth):    global looked    if in_check(board, side) and not moves(board, side):        return -1000 if side == 'white' else 1000    # checkmate    if depth == 0:        return evaluate(board)                       # stop and guess    options = moves(board, side)    if not options:        return 0                                     # stalemate: a draw    results = []    for m in options:        looked = looked + 1        results.append(value(play(board, m), other(side), depth - 1))    if side == 'white':        return max(results)    return min(results) def best_move(board, side, depth):    global looked    best = None    for m in moves(board, side):        looked = looked + 1        v = value(play(board, m), other(side), depth - 1)        if best is None or (side == 'white' and v > best_v) or (side == 'black' and v < best_v):            best = m            best_v = v    return best, best_v board = ['rnbqk',         'p.ppp',         '.....',         'PP.PP',         'RNBQK']show(board)for depth in [1, 2]:    looked = 0    m, v = best_move(board, 'white', depth)    print(f'Looks {depth}: {name(m)}, score {v}, after {looked} positions')

5 r n b q k4 p . p p p3 . . . . .2 P P . P P1 R N B Q K  a b c d eLooks 1: d1-a4, score 1, after 9 positionsLooks 2: d1-c2, score 0, after 84 positions

Looks 1 takes the pawn: in the positions it sees, White has a pawn more, a score of 1. Looks 2 also tries Black’s replies, finds the rook taking the queen (−8 for that move) and plays a quiet move worth 0 instead: one move further changed the move, for about nine times as many positions.

Step 3: your own idea of a good position

Material is a poor guess early in the game, when nothing has been taken. Shannon’s paper suggested more: among them, that the side with more moves available, more mobility, usually has the better game, since its pieces are free and the other side’s are hemmed in. He gave each move a tenth of a pawn.

Here is that evaluation: material, plus 0.1 for each legal move White has, minus 0.1 for each Black has.

from minichess import START, moves VALUES = {'P': 1, 'N': 3, 'B': 3, 'R': 5, 'Q': 9, 'K': 0} def evaluate(board):    score = 0    for row in board:        for piece in row:            if piece != '.':                if piece.isupper():                    score = score + VALUES[piece]                else:                    score = score - VALUES[piece.upper()]    mobility = len(moves(board, 'white')) - len(moves(board, 'black'))    return score + 0.1 * mobility print(evaluate(START))print(evaluate(['rnbqk', 'p.ppp', '.....', 'PP.PP', 'RNBQK']))

0.00.1

The board below plays with your evaluate, as you have it in the program just above (press Edit to change it): its search looks two moves ahead, exactly like Looks 2, but scores the positions where it stops with your function. Looks 2 scores them by material alone. So the only difference between the two players is the evaluation.

Step 4: alpha–beta, and what it saves

Now the trick from the small tree, in the real search. value gets two more arguments, alpha and beta, and stops trying moves as soon as alpha >= beta. This program searches the start of the game both ways, 1 to 4 moves ahead, and prints the move chosen and the positions looked at.

from minichess import START, moves, play, other, in_check, name VALUES = {'P': 1, 'N': 3, 'B': 3, 'R': 5, 'Q': 9, 'K': 0} def evaluate(board):    score = 0    for row in board:        for piece in row:            if piece != '.':                if piece.isupper():                    score = score + VALUES[piece]                else:                    score = score - VALUES[piece.upper()]    return score looked = 0 def value(board, side, depth, alpha, beta, prune):    global looked    if in_check(board, side) and not moves(board, side):        return -1000 if side == 'white' else 1000    if depth == 0:        return evaluate(board)    options = moves(board, side)    if not options:        return 0    if side == 'white':        best = -10000        for m in options:            looked = looked + 1            best = max(best, value(play(board, m), 'black', depth - 1, alpha, beta, prune))            alpha = max(alpha, best)            if prune and alpha >= beta:                break    else:        best = 10000        for m in options:            looked = looked + 1            best = min(best, value(play(board, m), 'white', depth - 1, alpha, beta, prune))            beta = min(beta, best)            if prune and alpha >= beta:                break    return best def best_move(board, depth, prune):    global looked    alpha = -10000    best = None    for m in moves(board, 'white'):                  # White to move        looked = looked + 1        v = value(play(board, m), 'black', depth - 1, alpha, 10000, prune)        if best is None or v > best_v:            best = m            best_v = v        if prune:            alpha = max(alpha, best_v)    return best for depth in [1, 2, 3, 4]:    looked = 0    plain = best_move(START, depth, False)    without = looked    looked = 0    pruned = best_move(START, depth, True)    print(f'{depth} ahead: {name(plain)} after {without} positions,',          f'with alpha-beta {name(pruned)} after {looked}')

1 ahead: a2-a3 after 7 positions, with alpha-beta a2-a3 after 72 ahead: a2-a3 after 60 positions, with alpha-beta a2-a3 after 353 ahead: a2-a3 after 566 positions, with alpha-beta a2-a3 after 2494 ahead: a2-a3 after 5341 positions, with alpha-beta a2-a3 after 812

The same move every time, from far fewer positions: four moves ahead, alpha–beta skipped 85 out of every 100. (The counts under the first board are made the same way.) With the moves in the best possible order, alpha–beta looks at only about the square root of what plain minimax does, so in the same time it can look about twice as far ahead.

• a.No computer sees to the end. Your Step 1 counted 7, 53, 506 and 4,775 positions in 1 to 4 moves on a 5 × 5 board. Chess on a full board grows by about 30 a move, not 9: Shannon’s 10¹²⁰ games.
• b.Looking one move further changes the move. In Step 2, Looks 1 took a guarded pawn and Looks 2 didn’t, and in the match Looks 2 beat Looks 1 nearly every game.
• c.A better guess wins with the same look-ahead. Your evaluate with mobility, searching exactly as far as Looks 2, won more games than it lost against it.
• d.Alpha–beta skips most of the work without changing the move. In Step 4 it found the same moves after a fraction of the positions.

These are still the two parts of every strong chess program: a search (look ahead, minimax, alpha–beta) and an evaluation (a guess at who stands better). Deep Blue’s search was faster and its evaluation far more detailed, but it was built of these same two parts.

The horizon

A search sees nothing past where it stops, its horizon. Make it look three moves ahead from the poisoned-pawn board in Step 2 (for depth in [1, 2, 3]). Looks 3 plays a2-a3 and scores it +1, as if it wins a pawn. It doesn’t: whatever Black replies, White can take something with its third move, and the search stops right there, before Black takes back. Looking four moves ahead, the same move scores 0 again. Real programs fix this with a quiescence search: at the horizon, they keep following captures until the position is quiet, and only then guess. Shannon saw the problem in 1950: a machine that stops at exactly three moves, he wrote, stops “even though it or the opponent be in check”, and he proposed looking further wherever the position wasn’t quiet.

A question nobody can answer yet: is chess, like tic-tac-toe and minichess, a draw with perfect play? Most strong players think so, and games between the strongest programs from the normal starting position end mostly in draws, but no one has shown it, and with Shannon’s 10¹²⁰ no computer can simply search for the answer.

Three challenges, each checked on the page: write your function in the program above the checker (press Edit), then press Check my program. The examples show what your function should give; there are more tests you can’t see.

★ Read a position as chess programs write it

Chess programs write a position in a short form called FEN: the rows from Black’s side, separated by /, with a digit for a run of empty squares. The minichess start is rnbqk/ppppp/5/PPPPP/RNBQK. Write board_from_fen(fen), which gives back the board as this topic writes it, a list of 5 strings with . for each empty square.

def board_from_fen(fen):    # Give back a list of 5 strings, '.' for an empty square.    return [] print(board_from_fen('rnbqk/ppppp/5/PPPPP/RNBQK'))

★★ Minimax on any tree

A game tree can be written as nested lists: a number is a position where the search stops, with its score; a list is a position where someone chooses, with one item for each move. Write minimax(tree, white): the tree’s minimax score, when White chooses at the top if white is True and Black does if it is False, the two taking turns at each level down. The tree can be any number of levels deep.

def minimax(tree, white):    # Give back the best score with both sides playing their best.    return 0 print(minimax([[3, 12, 8], [2, 4, 6], [14, 5, 2]], True))

★★★ How much does alpha–beta skip?

Write alphabeta_looked(tree): the number of scores (numbers in the tree) that alpha–beta looks at, searching from left to right with White choosing at the top. Start with alpha as very low and beta very high, and stop trying the moves at a level as soon as alpha ≥ beta, exactly as the tree above did. For the tree on this page the answer is 7.

def alphabeta_looked(tree):    # Give back how many numbers alpha-beta looks at.    return 0 print(alphabeta_looked([[3, 12, 8], [2, 4, 6], [14, 5, 2]]))

• How Can a Computer Never Lose at Tic-Tac-Toe?: minimax to the very end of every game, and remembering positions.
• Who wins Bagh-Chal when nobody makes a mistake? Nepal’s own game, solved by computer, and a search with your own evaluation for the goats.
• Grade 11, Recursion: functions that call themselves, and how to be sure they stop.
• Grade 12, The Limits of Computing: problems that grow too fast to solve by trying everything.
• Grade 12, Algorithms for Hard Problems: when the best answer can’t be found in time, a good guess, a heuristic, like a chess program’s evaluation.