Skip to content

Playing against a machine: minimax and alpha-beta pruning

How a machine that never loses plays: minimax assumes the opponent's worst and alpha-beta pruning gives the same move by looking at less. AI course, 0.6.

Ramón Invarato
Un peón de cristal negro en el centro, rodeado de copias translúcidas de sí mismo en otras casillas, unidas a él por líneas finas, como todas las jugadas posibles a la vez; sobre un suelo negro y ante un fondo azul oscuro con una franja de luz cálida

To find a path on a map, all it takes is a good choice of the order in which to look at the cells, as Finding a path explains. In a game there is something more: an opponent who also chooses, and who is not going to let you win. Classic search solves it with minimax, which always assumes the worst from the opponent, and with alpha-beta pruning, which reaches the same move while looking at far fewer positions.

Try this first

Open the Game tab of the Search tool, on Tic-tac-toe. Press Let the machine start. It puts its X in a corner, and below it counts what it had to look at to decide: 34,203 positions looked at, with pruning, against the 549,946 it would have looked at without pruning, “×16 less work, and the same move”.

Tic-tac-toe in the Search tool after the machine starts: above the board, in orange, "Values for the machine: what each move got it"; its X in the top left corner and "draw" on every free cell. Below, boxed, 34,203 positions looked at with pruning, 549,946 the ones it would have looked at without pruning, ×16 less work, and the same move, and 13,124 branches cut

How to read the board. It is an ordinary game of tic-tac-toe, with one difference: the tool shows what the machine is thinking. On each free cell it writes what playing there is worth if both of you play perfectly: who wins, if that is certain; draw if it ends in a tie; and a number when it is only an estimate (higher is better). A label above the board says whom those values are for. With no hints, in orange, “Values for the machine”: those are the ones it worked out to choose its move, which is why they say it wins or it loses. Those are the “draw” values of each free cell in the screenshot: the machine played in the corner, but any other first move also ended in a tie. When you play against a person, you cannot see what they are thinking; here you see what the machine has thought and why it chooses that move.

Now open the same game with the hints (the Show what each move is worth on my turn box) and press Let the machine start again. The label turns green, “Values for you”, and each free cell says what that move is worth to you if both of you play perfectly: all of them say you lose, except the center, which says draw and is boxed as what would be your best move. In this example, only the center saves you from losing.

The same game with the hints: above the board, in green, "Values for you: what each move gets you"; all the free cells say "you lose" except the center, boxed, which says "draw"

What just happened

A game can be drawn as a tree, like the one in the figure a little further down: at the top, the current position; below it, all the possible moves of whoever is to move; below each one, all the opponent’s replies. Each turn is a level of the tree, and so on until the game ends in a win, a loss or a draw. In tic-tac-toe, the whole tree has 255,168 distinct games (Game complexity, on Wikipedia), and the tool counts 549,946 positions if everything is looked at from the empty board (many are the same board reached by different paths: there are 5,478 distinct boards).

Minimax goes through that tree from the bottom up. The final positions are worth “win”, “loss” or “draw”. On its turn, the machine takes the move that is worth the most to it; on yours, it assumes you choose the one that is worth the least to it, that is, the best for you. That is how the value rises to the current position. The machine keeps the move that suits it best even if you always reply with what is best for you: of all its moves, the one that hurts it least. That is why it never loses at tic-tac-toe: it has looked at all the possible replies to each move.

See it in an endgame: it is just the bottom tip of the tree, because above it would be all the levels of the earlier moves. In the figure, start at the top: that board is the current position, the one the machine has in front of it. It is its turn (it plays X), and the three cells at the bottom are free. The opponent, who plays O, has two marks on the diagonal that goes down from the top right corner, and needs the one at the bottom left. If the machine blocks there (move A), the opponent has two replies left, and both end in a draw: A is worth “draw”. If it plays in either of the other two cells (B or C), the opponent completes the diagonal and wins: they are worth “loses”. Minimax keeps A.

Tree of a tic-tac-toe endgame. At the top, the board with X X O, O O X and the bottom row empty, "Machine to move (X)", worth "draw". Below, its three moves: A blocks the diagonal and is worth "draw", with two replies from O that end in a tie; B and C leave the diagonal open and are worth "loses": in each, O's first reply completes the diagonal and wins, and the other reply, in gray, says "not looked at". At the bottom: in B and in C, O's first reply is enough, because it is already worse than the draw A secures, so the other one is pruned

Alpha-beta pruning saves work without changing the result. The idea can be understood without a tree: if you already have a move that secures you a draw, and in the next one you look at, the opponent can beat you with their first reply, there is no need to look at the rest of their replies, because you are not going to choose that move anyway. In the tree, when looking at B, the opponent’s first reply already wins, and the other one, in gray, is left unlooked: with that first reply, B is already worse than the draw it gets with A, and looking at the rest is pointless. With C the same happens. On the first move from the empty board, the machine cut 13,124 branches this way, and looked at 16 times fewer positions to arrive at the same X in the corner.

You do not have to imagine that tree: the tool shows it. Open tic-tac-toe, press Let the machine start and scroll down to The tree the machine looked at. Every possible move comes up with what it is worth and how many positions it looked at below it. If you click one, the opponent’s replies unfold, and the branches that pruning did not get to look at appear separately, with their value worked out only to show you. Follow the line it expects goes through the game the machine believes will be played.

The tree the machine looked at in the Search tool, after it starts at tic-tac-toe. At the top, the empty board. At level 1, "The machine moves": its nine moves, all "draw", with the positions it looked at in each (2,788 in the top left corner, unfolded). At level 2, "You move": your eight replies to that corner; seven say "it wins in 7" and only the center, boxed in green as the best for you, says "draw"

With a bigger game, the tree is too big to look at whole: Connect 4 has about 4.5 trillion distinct positions (Connect Four, on Wikipedia), and going through them on every move would take too much time and too much memory. Open Connect 4 and let the machine start: now it looks only 6 moves ahead (the depth) and, where it cuts off, it estimates how much the position is worth with a score, which is what shows in the columns (numbers like −18 or 0) instead of “it wins” or “it loses”. That estimate plays the role of A*’s heuristic: a shortcut written by a person. Even so, pruning saves it a lot: 7,000 positions instead of 137,257. And the saving holds later in the game: in the screenshot, after four moves of yours, it looked at 6,567 positions instead of 130,558, and above each column it writes what it estimates playing there is worth to it.

Connect 4 in the Search tool halfway through a game, with red discs for the machine and yellow ones for you in the middle columns. At the top, in orange, "Values for the machine". Above each column, what the machine estimates: +8, +8, +20, +59 boxed, the one it chose, +8, −4 and +8. Below, boxed, 6,567 positions looked at with pruning, 130,558 the ones it would have looked at without pruning, ×20 less work, and the same move, and 1,115 branches cut

The classic mistake

You might think pruning is a gamble: that, by looking at less, the machine sometimes skips the best move. With alpha-beta pruning that does not happen. It only cuts the branches that, whatever they are worth, are not going to change the move it chooses, and it arrives at the same move as minimax looking at everything (Alpha–beta pruning, on Wikipedia). What does change the result is the depth: with a tree too big to look at whole, the machine plays only as well as its depth and its estimate allow.

Try it yourself

  • At tic-tac-toe, try to beat the machine. Before each move, look at the hints: is there any cell that says “you win”?
  • Start in a corner yourself and see what the machine does. Does it play in the center?

Test yourself

In Connect 4 looking 3 moves ahead, let the machine start. How many times less work does pruning save it? Repeat it with 7 moves.

With 3, pruning saves ×___; with 7, ×___.

Below the board: “less work, and the same move”.

See the answer

Answers: 2.7 and 60.

The deeper it looks, the more branches there are to cut, and pruning pays off more: with 7 moves it looks at 15,939 positions instead of 960,793. That is why a machine with pruning can look further in the same time.

Open the sticks: there are 13, each player takes 1 to 3 per turn and whoever takes the last one wins. Turn off Show the analysis and play before answering.

Test yourself

You start with 13 sticks. How many do you have to take so as not to lose?

You take [1 / 2 / 3].

Turn Show the analysis back on and look at the red numbers: they are the positions where the player to move loses.

See the answer

Answer: 1.

Whoever has to move with 0, 4, 8, 12… sticks loses: the multiples of 4. If you leave 12, whatever the other player takes, you make it up to 4 and leave them on 8, then on 4 and then on 0. The machine found that rule by searching, without anyone giving it to it, and with it there is no need to search any more.

Test yourself

Tick Whoever takes the last one loses (or open that variant) and start again with 13. Who wins now with perfect play?

The winner is [you / the machine]. The positions where the player to move loses are the ones that leave a remainder of ___ when divided by 4.

See the answer

Answers: the machine and 1.

Now whoever is left with the last stick loses, so the bad positions shift by one: 1, 5, 9, 13… With 13 you start on one of them, and the machine, which has searched to the end, does not let you out.

With several heaps the game is called Nim: on each turn you take as many sticks as you like, but from a single heap. Here the rule is no longer counting by 4s.

Test yourself

Open Nim with heaps of 3, 4 and 5 and look at the analysis. The tool writes each heap in binary and takes the “exclusive or” of each column: the nim sum. What is it worth here? Who wins if you start?

The nim sum is ___, and the winner is [you / the machine]. To win, you take ___ from the heap of 3.

With sum 0, whoever moves loses. Look for the move that leaves the sum at 0: check it with the heaps of 1, 4 and 5.

See the answer

Answers: 2, you and 2.

3, 4 and 5 in binary are 011, 100 and 101; column by column, the “exclusive or” gives 010, which is 2. If you take 2 from the heap of 3, 1, 4 and 5 are left (001, 100 and 101), and the sum is 0: any move by the other player spoils it, and you can always put it back at 0. It is the rule of Charles Bouton, from 1901 (Nim, on Wikipedia), and the machine arrives at the same thing by searching: it says so below the analysis.

Further reading

  • Alpha–beta pruning, on Wikipedia: how pruning works with a drawn example, and its history: John McCarthy proposed it at the Dartmouth workshop in 1956.
  • How far a machine looks, from the same course: what happens when the machine cuts off in the middle of an exchange of pieces (the horizon effect) and how engines decide by looking at less.
  • Finding a path, from the same course: the other half of classic search, when there is no opponent, with the same tool.
  • Learning from reward: a machine that learns to play by itself with rewards and punishments, with no rules for searching.

“Playing against a machine: minimax and alpha-beta pruning” by Ramón Invarato at jarroba.com, licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0. Registered at Safe Creative.

Ramón Invarato

I design and build data platforms and intelligent systems, and I enjoy sharing that experience here.

You may also like

Comments

Leave a comment


This site uses Akismet to reduce spam. Learn how your comment data is processed.