Can a Computer Check Every Possible Chess Game?

Use the tree above.

• a.Press One move deeper a few times. Count the dots in each row: how many choices does each move have?
• b.Watch the numbers on the left. After how many moves are there more ways than grains of rice in a 25 kg sack? Than people in Nepal?
• c.Now switch to Tic-tac-toe and play to the end. How many rows can its tree ever have?

The numbers on the left of the chess tree are real counts. Chess programmers count every way the first moves can go, as a test of their programs: if the count is wrong, the program’s rules are wrong somewhere. The count is called perft (“performance test”); the widget’s own chess rules were tested the same way.

Times 2, times 30

The rice doubles: each square holds 2 times the square before. Watch how slowly it starts and how fast it ends.

A game multiplies in the same way, but by more. Think of every game as a path down the tree: one dot in each row. White has 20 first moves. For each of them, Black has 20 replies, so the first two moves can go 20 × 20 = 400 ways. For each of those 400, White has about 20 to 22 moves again: 8,902 ways for three moves. The ways after some moves are all the choices multiplied together.

Multiplying by the same number again and again is called exponential growth: the number of ways is 30 to the power of the number of moves, 30ⁿ. You met it in Grade 9 as the work that grows fastest of all Grade 9: Exponential: every group, and in Grade 6, where each extra bit doubles the patterns Grade 6: More bits, more patterns.

Shannon’s guess for a whole game

In 1950 Claude Shannon, an engineer at Bell Telephone Laboratories in the USA, published a famous paper on programming a computer to play chess. He began by working out why it couldn’t play by checking every game. In a typical position there are about 30 legal moves, he wrote, so a move for White and a reply from Black give about 30 × 30 ≈ 1,000 possibilities. A typical game lasts about 40 such pairs of moves. That makes 1,000 multiplied by itself 40 times: 10¹²⁰, a 1 followed by 120 zeros.

How big is that? Scientists estimate that the whole universe we can see holds about 10⁸⁰ atoms, a 1 followed by 80 zeros. Shannon’s number isn’t just a bit bigger than that: it is 10⁴⁰ times bigger: for every atom in the universe, ten thousand billion billion billion billion games.

With blocks: past the people on Earth

The blocks below play Shannon’s game of exactly 30 choices a move. They multiply the ways by 30, one move at a time, until there are more ways than the 8 billion people on Earth, counting the moves as they go.

It says 7 moves and 21,870,000,000 ways. Real chess took 8 moves to pass 8 billion. Why one more? Because real chess starts slowly: the first two moves have only 20 choices each, not 30. Shannon’s 30 is about right later in a game.

In Python (from Grade 8): more games than atoms

The same loop in Python is a while loop (Grade 8, Repeating with while). Python’s whole numbers can be as big as you like, so it can go much further than the blocks: all the way past the atoms in the universe. 10 ** 80 is 10 to the power 80.

atoms = 10 ** 80          # atoms in the universe we can see, roughlyways = 1moves = 0while ways <= atoms:    ways = ways * 30    moves = moves + 1print('After', moves, 'moves there are more ways than atoms.')print('That number of ways has', len(str(ways)), 'digits.')

After 55 moves there are more ways than atoms.That number of ways has 82 digits.

(len(str(ways)) turns the number into text and counts its digits.) A game of 40 moves each is 80 moves long. So the ways pass the atoms in the universe at move 55, long before an ordinary game is over.

How long would checking take?

Suppose a very fast computer checks a billion (1,000,000,000) games every second. This program takes the real counts from the tree and works out how long checking each would take. The function how_long turns seconds into minutes, hours, days or years, whichever reads best.

counts = [20, 400, 8902, 197281, 4865609, 119060324, 3195901860,          84998978956, 2439530234167, 69352859712417,          2097651003696806, 62854969236701747, 1981066775000396239,          61885021521585529237, 2015099950053364471960] def how_long(seconds):    minute = 60    hour = 60 * minute    day = 24 * hour    year = 365 * day    if seconds < 0.001:        return 'under a thousandth of a second'    elif seconds < 2 * minute:        return f'{seconds:.3f} seconds'    elif seconds < hour:        return f'{seconds / minute:.0f} minutes'    elif seconds < day:        return f'{seconds / hour:.0f} hours'    elif seconds < year:        return f'{seconds / day:.0f} days'    else:        return f'{seconds / year:,.0f} years' for moves in range(1, 16):    ways = counts[moves - 1]    print(f'Up to move {moves}: {how_long(ways / 1_000_000_000)}')

Up to move 1: under a thousandth of a secondUp to move 2: under a thousandth of a secondUp to move 3: under a thousandth of a secondUp to move 4: under a thousandth of a secondUp to move 5: 0.005 secondsUp to move 6: 0.119 secondsUp to move 7: 3.196 secondsUp to move 8: 84.999 secondsUp to move 9: 41 minutesUp to move 10: 19 hoursUp to move 11: 24 daysUp to move 12: 2 yearsUp to move 13: 63 yearsUp to move 14: 1,962 yearsUp to move 15: 63,898 years

(ways / 1_000_000_000 is the seconds needed; the _ in a number is only there to make it easy to read. :,.0f rounds to a whole number and puts commas in it.) The tree’s readout under the board says the same, rounded.

A whole game

Fifteen moves is not even a fifth of a game. Now take Shannon’s whole game, 10¹²⁰ ways, and the same billion a second. A year has 365 × 24 × 60 × 60 seconds, and the universe is about 13.8 billion years old.

games = 1000 ** 40          # Shannon: about 1,000 ways for each pair of moves, 40 pairsper_second = 1_000_000_000  # a billion games checked every secondyear = 365 * 24 * 60 * 60   # seconds in a yearuniverse = 13_800_000_000   # the universe's age in years years = games // per_second // yearprint('Years needed: a number with', len(str(years)), 'digits')print('Ages of the universe: a number with', len(str(years // universe)), 'digits')

Years needed: a number with 104 digitsAges of the universe: a number with 94 digits

(// divides and drops what is left over, so the answers stay whole numbers.) A number with 94 digits is about 10⁹³. Checking every game would take the whole age of the universe, over and over, 10⁹³ times.

Every atom a computer

A faster computer, then? Imagine the fastest you can: every atom in the universe turned into a computer checking a billion games a second, all of them working since the Big Bang.

games = 1000 ** 40atoms = 10 ** 80per_second = 1_000_000_000seconds = 13_800_000_000 * 365 * 24 * 60 * 60   # since the Big Bang checked = atoms * per_second * secondsprint(f'Games checked: a number with {len(str(checked))} digits')print(f'Checked: one game in every {games // checked:,}')

Games checked: a number with 107 digitsChecked: one game in every 22,978,110,133,162

• Seven or eight moves pass the people on Earth. Times 30 a move, the blocks passed 8 billion at move 7; real chess, which starts with only 20 choices, at move 8.
• 55 moves pass the atoms in the universe, long before an ordinary game of about 80 moves is over.
• The deepest count anyone has made, 15 moves, would take 63,898 years at a billion a second. A whole game, 10¹²⁰ ways, would take a 104-digit number of years.
• Even a universe of computers isn’t enough. Every atom checking a billion games a second since the Big Bang would have checked about one game in every 23 trillion.

So the answer to the title is no, and not because today’s computers are slow. Multiplying beats any speed. A computer a million times faster than another can check a million times as many games in the same time, but 30 × 30 × 30 × 30 = 810,000: a million times more work buys only about four more moves of looking ahead. This is why chess programs don’t check every game. They look a few moves ahead and then guess how good the position is, the way Shannon proposed in the same paper. The topic How does a computer play chess? shows how.

Games or positions? The 400 ways to play the first two moves of chess end in 400 different positions. But play 1. Nf3 and then 2. Nc3, or 1. Nc3 and then 2. Nf3 (with the same Black replies), and you reach the same board by two different games. Deeper in the tree this happens all the time, so there are far fewer positions than games. The computer scientist John Tromp estimated that chess has about 4.8 × 10⁴⁴ legal positions: still unthinkably many, but a 45-digit number instead of a 121-digit one. Shannon made a rougher estimate in 1950, about 10⁴³. Chess programs use this: a position already looked at is remembered, not looked at again. Challenge ★★★ counts tic-tac-toe’s positions and finds how much smaller that number is than its games.

Other games. Change the 30 in the atoms program to 2 (a coin tossed each move), or to 9. How many moves does each take to pass 10⁸⁰? Why does a game with only 2 choices a move still get there?

An open question. Is chess a draw if neither player ever makes a mistake, like checkers? Most strong players think so, and the strongest programs draw so many games against each other that their tournaments make them start from chosen, unbalanced openings, to get fewer draws. But nobody has shown it, and with 10¹²⁰ games, no computer can simply check.

★ Past any number (blocks)

Finish the program so that it says how many moves it takes until the ways pass the number typed: more than it, not just equal. Each move has the typed number of choices. (For 30 choices and 8,000,000,000 it says 7.) Then press Test.

★★ How many choices a move? (Python, from Grade 8)

The tree’s counts hide how many choices each move had on average. If 400 ways became 8,902 at the next move, each of the 400 had on average 8,902 ÷ 400 ≈ 22.3 choices. Write choices(counts): given a list of counts for 1, 2, 3… moves, give back a list of the average choices at each move, each rounded to one decimal place with round(x, 1). The first move’s choices are just the first count.

def choices(counts):    # counts[0] is the ways for 1 move, counts[1] for 2 moves, ...    return [] print(choices([20, 400, 8902, 197281]))

★★★ How many different boards? (Python, from Grade 8)

After 3 moves of tic-tac-toe there are 504 ways the game can have gone. But many of them end on the same board: X in two squares and O in one, played in a different order. Write boards_after(n): how many different boards there can be after exactly n moves (X moves first; a game with three in a row stops there). The function won(board) is given. A board is a string of 9 characters, 'X', 'O' or ' ', row by row from the top left.

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)] def won(board):    for a, b, c in LINES:        if board[a] != ' ' and board[a] == board[b] == board[c]:            return True    return False def boards_after(n):    return 0 print(boards_after(3))

• Grade 8, Repeating with while: loops that go on until a condition is true, like the one that passed the atoms.
• Grade 9, How the work grows: why exponential work is the hardest of all.
• How many moves to move 64 disks? Another puzzle that doubles: the same number as the grains on the whole chessboard.
• How many ways round Bhaktapur’s temples? Another way a number of choices runs away from any computer.
• How does a computer play chess? (Grades 9–12): looking a few moves ahead and guessing, as Shannon proposed.
• How can a computer never lose at tic-tac-toe? (Grades 9–12): a game small enough to check every game, and play perfectly.