The bot tournament

All through the book we have written exact recipes for the machine, and it has carried them out, fast and without a thought. Even in the last chapter we wrote every rule of defense ourselves: check the bounds here, escape that, don’t let this in. The machine decided nothing on its own. Can it make choices without a step-by-step recipe from us? We’ll test it on a game: we’ll teach the machine to play. A sequence of moves written down in advance is no use here, because across the board sits an opponent who also thinks, and thinks against you.

That is what sets a game apart from the problems of earlier chapters: the outcome doesn’t depend on you alone. An array puts up no resistance while you sort it, but in a game every move you make draws a reply designed to hurt you. A good move is one that stays good after the opponent’s nastiest answer. The chapter is laid out as a tournament. First you’ll write a tic-tac-toe bot that never loses, then a bot for Connect Four, a game too big to count out to the end, and you’ll enter both in the tournament table.

The arena: tic-tac-toe

A bot is a function: it gets the position on the board and whose turn it is, and it returns a move. Everything else is a matter of how the function decides. We’ll start in the smallest arena, tic-tac-toe on a three-by-three grid. The board is a list of nine cells ('X', 'O' or '.'), numbered 0 to 8 from left to right and from top to bottom. Here is the referee: it pairs up two bots and plays the game out to the end.

Two bots that move at random draw about one game in eight, and of the rest the first player wins more often, since it gets the extra move. The random bot is a weakling: it notices neither its own win in one move nor the opponent’s threat. To play in earnest you have to look ahead, which means searching: what if I go here, and the opponent answers there, and then I go here. What comes out is a tree.

Stockholm, 1974: the first world champion

Behind all the machines from Kaissa to Deep Blue stands a single idea, and tic-tac-toe is enough to understand it completely: picture the game as a tree and choose a move in it, assuming that the opponent always replies in the best possible way.

The game tree

Take a position and draw every way it can go on. The root is the current board. Branches lead from it, one for each possible move; from every position they reach, more branches, one for each reply of the opponent, and so on to the end of the game, where somebody has won or it’s a draw. This is the game tree. Its leaves are finished games, and for each one it is obvious at once how it ended. The levels alternate: on one level one player moves, on the next the other. One such level, a move by one player, is called a ply.

How big is this tree? On an empty board the first player picks one of 9 cells, the second one of 8, and so on. That puts an upper limit of $9!$ on the number of games, but many branches stop early: a game ends as soon as someone completes a line. A full traversal gives the exact number of leaves.

There are 255,168 leaves, fewer than $9! = 362\,880$, because a game in which a line was completed before the ninth move branches no further. A computer gets through a quarter of a million leaves in a fraction of a second, so tic-tac-toe can be counted out to the end, and for any position we can find out how it ends with correct play. What remains is to work out how to pick a move from the tree when the opponent is no friend of ours.

Minimax: expect the worst

Give the leaves numbers from our point of view: our win is $+1$, a loss is $-1$, a draw is $0$. We want the largest number and the opponent wants the smallest (our loss is their win). So as we go down the tree, on our own levels we’ll pick the branch with the largest value, and on the opponent’s levels we have to assume that they pick the smallest. That gives the rule: the value of a node where we move is the maximum of its children’s values, and where the opponent moves it is the minimum. This is minimax. It answers the question “what outcome can I guarantee if the opponent plays perfectly?”

Folding a tree by maximum and minimum is older than computers. In 1928 the mathematician John von Neumann proved the minimax theorem for two-person zero-sum games, and in 1950 Claude Shannon carried the idea over to the machine in his paper Programming a Computer for Playing Chess. Around the same time Alan Turing and David Champernowne designed a chess program, and in 1952 Turing played it by hand, on paper, because there was no machine to run it on. These works started the computer study of games. We’ll write minimax for tic-tac-toe with one convenient convention: a value is always taken from the point of view of whoever moves now, and a child’s value is taken with a minus sign (what’s good for them is bad for us). This way of writing it is called negamax.

The starting position is worth zero: with accurate play, tic-tac-toe always ends in a draw. That is why a bot built on best_move never loses: it picks a move after which even the opponent’s best play brings them no win. It sees threats too. Faced with two O’s in a row, X takes the third cell, because every other move leads to a loss, and for value a loss is worse than a draw. In the task minimax-ttt you’ll write such a bot, and the checker will try to beat it in every possible game, without success. In the widget below, try to catch your opponent with a fork, two threats at once: the near-sighted bot falls for it, and the perfect one won’t let you set it up.

Alpha-beta: skip what can’t matter

Minimax visits the whole tree. Yet whole branches can often be skipped, because they can no longer change the answer. Say you are choosing between two moves. You have worked out the first: it guarantees a draw, zero. You start on the second, and in the opponent’s first reply you see that they can beat you: minus one. They will pick that reply (they play for the minimum), so the second move is worth at most minus one and already loses to the draw you found. There is no need to look at the opponent’s other replies to the second move: whatever they hold, we have already rejected it. The branch is pruned.

This is how alpha-beta pruning works. The search carries two numbers along: α, how much is already guaranteed to the player who maximizes, and β, how much is guaranteed to the opponent. As soon as it becomes clear at some node that it falls outside these bounds, the search over its children is cut off. The answer is the same one minimax gives; only branches that can’t matter are thrown away. On the tic-tac-toe tree we can count how many nodes plain minimax visits and how many it visits with pruning.

Pruning shrinks the search tenfold and more, here about thirtyfold, and the answer doesn’t change in a single position. The deeper the tree, the bigger the gain. If moves are tried in a good order, the strongest first, alpha-beta at best visits about $\sqrt{b^d}$ nodes instead of $b^d$, where $b$ is the number of moves in a position and $d$ is the depth. Taking a square root halves the exponent, so in the same time the search can look twice as deep and see eight moves ahead instead of four. Many people found the idea independently. It was in the air from the mid-1950s (John McCarthy proposed something similar as early as 1956), in 1963 the Soviet mathematician Alexander Brudno published it, and in 1975 Donald Knuth and Ronald Moore gave a rigorous analysis. In the task alphabeta you’ll write the pruning yourself, and the checker will hold you to a limit on the number of leaves examined.

When you can’t count to the end

Tic-tac-toe is over in nine moves, and its tree has a quarter of a million leaves. Chess won’t yield like that. Back in 1950 Shannon estimated the number of different chess games at around $10^{120}$. This is now called the Shannon number, and it is larger than the number of atoms in the universe: no pruning will get you through a tree like that. Connect Four, on a 7×6 board, is more modest, but it still has over $4.5 \cdot 10^{12}$ positions, far too many to count out in the time of a single move.

Shannon also proposed the way out: stop at a fixed depth, short of the leaves, and estimate the unfinished position with a number. That number comes from an evaluation function. In chess it counts material and the placement of the pieces; in Connect Four, whose threes and twos, still able to become a four, outnumber the other side’s. The search runs minimax with pruning a few plies ahead and takes the estimate in place of the unreachable leaves. The deeper you look, the stronger the play, and here alpha-beta comes to the rescue again by doubling the depth within reach.

Here is a bot for Connect Four. The board is a list of seven columns, each holding its pieces from the bottom up. The evaluation is simple: go over every group of four cells in a line where a four can still be made. Your own three with room for a fourth piece earns a lot of points, a two fewer, and the same for the opponent count with a minus sign. There is no need to reward the center separately: more lines pass through the central cells, so they collect more points on their own. The bot does try moves from the center outward, though, because that way pruning kicks in sooner.

The bot that looks four plies ahead wins all twelve games against the random one. It doesn’t count to the end of the game: it stops at the fourth ply and trusts the evaluation to say who is closer to a four. In the task connect4-bot you’ll write a bot like this, and it will face reference bots in a tournament: a simpleton that always plays the leftmost column, and a tactician that takes a win and blocks threats. You have to fit into the time allowed: deeper is stronger, but slower too.

Too many branches: Monte Carlo

An evaluation function works when it is clear what matters in a position. In chess that has been known for centuries: material, the center, the king’s safety. For Go, played on a 19×19 board, nobody could come up with a working evaluation for a long time. A position that looks lost turns out to be won twenty moves later, and no simple formula catches that. On top of this, every position offers hundreds of moves, and the tree branches so wildly that even alpha-beta drowns.

The way out was the randomness of Chapter 26. To evaluate a position you can do without a formula: play many games out from it to the end with random moves and see how often you win. The share of wins becomes the estimate. And instead of spending the random games evenly on every move, you hand them out sensibly: more to the branches that look best so far, but a few to the rest too, in case you misjudged them. This method is called Monte Carlo tree search. It came together in 2006: Rémi Coulom described how to search a tree with random games and gave the method its name, and Levente Kocsis and Csaba Szepesvári gave a formula for dividing the trials between exploiting the best and exploring the rest.

This is what AlphaGo grew out of when it beat Lee Sedol in 2016: Monte Carlo search in which the choice of branches was guided by a neural network trained on human games, while a second network judged positions alongside the random playouts (how networks learn is the subject of the next chapter). The promised 37th move of the second game was a rare “shoulder hit,” a move that, according to commentators, most professional players would not have considered. The program played it against the advice of its own network trained on human games: it was that network that rated the move as one a human almost never plays. The decision came from the search and from a judgment of positions that had grown out of millions of games the program played against itself, not from a formula written by people.

Solved games

If the game tree can be traversed to the end, even if it takes years of computing, you can find out how the game ends when neither side makes a mistake. Such games are called solved. Tic-tac-toe is a draw, as we have seen. Connect Four was solved independently in 1988 by James Allen and Victor Allis: with perfect play the first player wins, provided the first move goes into the center column. Checkers held out longest. In 2007 Jonathan Schaeffer’s group at the University of Alberta, after eighteen years of computation, proved that checkers played without mistakes on either side ends in a draw. Their paper in Science bore the title Checkers Is Solved. Checkers has about $5 \cdot 10^{20}$ positions, and without the methods that cut the tree down to a manageable size, the whole history of humanity would not have been enough to go through them.

A solved game is still worth playing: people make mistakes, and the game stays alive. “Solved” only means that the perfect line is known in full. In games too big to traverse to the end, search with evaluation and pruning can only come closer to that line.

The tournament: tasks

Three bots, from an unbeatable one on a small board to a fighter for a big one. The checker doesn’t read your code: it runs it and judges by results, by the games played, by the number of leaves examined, by the time taken.

What next

Our machine can play now: perfectly where the tree can be traversed, and very strongly where it can’t. Deep Blue beat the world champion with the same kit: fast search, alpha-beta pruning and an evaluation function. But look closely at where the intelligence sits in this machine. Search and pruning are pure mechanics, and everything about them can be proved. What counts as a good position, though, the evaluation, was written for Deep Blue by people: for years its programmers, together with a grandmaster consultant, tuned how much a passed pawn or an open file is worth.

For chess such an evaluation was somehow assembled by hand; for Go it couldn’t be done, because nobody knew how to write down a formula for which position on the big board is better. What if a person can’t write the evaluation? Can the machine work it out for itself, from examples and games played, the way AlphaGo eventually did? That question opens the next chapter, and with it everything that goes by the name of machine learning today.