Click on any of the pages above to open a PDF viewer
with sample pages from the published book.
Click on any of the pages above to open
a PDF excerpt of the book.
chapter two
THE ROAD NOT TAKEN
A foolproof way to escape a maze is to comprehensively test every path, keeping track of where you are and where you’ve been. You walk down a path, make note of every available option, and then continue forward until you either escape or hit a dead end. If you do hit a dead end, no problem; because you have kept track of all the remaining options, you can retrace your steps and try one of those. As it turns out, this is a promising approach for more than just mazes. If you are playing sudoku, for instance, there might be several numbers that could plausibly be placed in a given square. How to pick? Choose one tentatively, see if you can from there fill in the rest of the grid without hitting a dead end, and then retrace your steps if the original choice doesn’t work. This chapter formalizes this wandering approach and then marvels at the countless puzzles it can effectively solve.
chapter one
GUESS WRONG ANSWERS
You are playing Wordle, and you know that the hidden word ends with the letters a-b-l-e. Is table the best next guess? Cable? Sable? Fable? A well-trained computer will tell you not to guess any of these but instead to guess the obviously incorrect word scarf. This chapter explains why, unpacking one of the best algorithms to use when your goal is to find a needle in some significant haystack.
The prior chapter considers strategies where the computer picks its move by literally playing out every possible future response. That turns out to be a wildly effective but frustratingly slow approach. To exhaustively play out a game of tic-tac-toe, for example, the computer would need to test something on the order of half a million game interactions just to make its first move. Do the same thing for Connect Four and the computer is stuck evaluating untold trillions. And chess? Forget about it. This chapter takes a first step toward addressing this problem by limiting the extent to which the computer looks ahead. The computer might look two or three moves ahead, but in this chapter the computer is no longer allowed to play every possible game to its definitive conclusion.
chapter five
MOVE FASTER
chapter six
PRUNING THE TREE
We can do even better, however. Our best algorithm so far still wastes a lot of time considering completely implausible moves. For instance, even if the computer realizes that its opponent will win the game unless the computer blocks a particular spot, our current algorithm records that information but then continues to consider other options. A human player would do nothing of the sort. Once a human player finds what looks to be the best move, the human player makes it. This chapter looks at strategies that empower the computer to similarly cut wasteful analysis, saving time for more difficult choices.
When researchers are evaluating the efficacy of a medication, they don’t test the drug on every patient. Instead, they test a few patients, then generalize the results to fit the population. Computers, it turns out, can do something very similar. For instance, instead of analyzing two potential moves rigorously, a computer can randomly simulate fifty games using the first option, randomly simulate fifty more games using the second option, and then pick the move with the better average performance. The power of this technique might surprise you, in that it can be both remarkably fast and surprisingly accurate.
chapter seven
THROWING DARTS
chapter eight
AIMING DARTS
The prior chapter demonstrates the power of random sampling. This chapter takes the next step, shifting from random sampling to strategic sampling. For instance, if after fifty random simulations it is clear that one move is terrible while three others are plausible, a purely random approach would continue to explore all four options. A better strategy, however, would take those results and adjust, focusing all remaining simulations on the three still-plausible moves while ignoring the move that is pretty clearly a dud.
Let’s not hurt anyone here, folks. But the two previous chapters apply random strategies to what are, in essence, one-player games. Here, we upgrade the algorithm so that it can be used to simulate two-player interactions. The chapter ends with a showdown: the two-player algorithms from chapters 4, 5, and 6 pitted against the two-player algorithms developed in chapters 7, 8, and 9. Get your popcorn ready.
chapter nine
AIMING DARTS AT OTHERS
chapter ten
ROCK, PAPER . . . PAPER
Random? Please. When playing rock-paper-scissors, you might try to make your choices randomly, but odds are you suffer from some idiosyncratic hiccup that throws off your game. Maybe you are reluctant to play scissors twice in a row, even though a purely random player would do exactly that surprisingly often. Maybe you subconsciously favor rock, or you absent-mindedly change your choice after a loss but keep it the same after a win. Because of this, rock-paper-scissors isn’t really a game of random chance; it’s a game of random chance plus pattern recognition. And who, dare I ask, is the king of pattern recognition? Yes, you guessed it: your computer.
In every chapter thus far, I have been explicit about exactly what the computer is doing and why it works. At the cutting edge of computer science, however, are black-box strategies where these details are almost completely hidden from view. The programmer provides training data, which in our case will be some large number of already-played sample games. And the programmer builds flexible data structures and supportive functions that empower the computer to test different strategies against the data. But from there the computer finds its own way, learning from the past to create its own strategic future.
chapter eleven
BLACK BOXES
People learn by interacting with their environment. Toddlers, for instance, figure out the details of walking not by listening to detailed instructions from their caregivers but by paying attention to their own bumps and bruises. Computers, too, can learn as they go. Thus, this chapter concludes our work by exploring one such learning algorithm: the computer plays the game, looks back to see where it might have made a better move, and quantifies that regret in order to gradually develop an even more promising solution strategy.
chapter twelve
MINIMIZING REGRET
chapter four
WHOSE TURN IS IT ANYWAY?
When you play any two--player game, you presumably pick your move based on what you think will happen in the moves to follow. In chess, for instance, as you think about moving your left-most pawn, you probably think ahead to what your opponent will do in response to that move, what you will do in response to your opponent’s response, and so on, perhaps several moves deep. Computers can play games using this exact approach but with a huge advantage: while you have the memory and organizational powers of a human, the computer has the memory and organizational firepower of . . . well, a computer!
chapter three
ONE STEP AT A TIME
If your car’s navigation system applied the approach introduced in the previous chapter, you would from time to time be sent on a ridiculous journey. Your car would be parked in (say) Los Angeles, California; you would ask for directions to a nearby restaurant; and the computer would correctly tell you that one workable path would be to drive from California to Alaska, to Texas, to Ohio, and then back to that Los Angeles restaurant. Admittedly, you would ultimately arrive, but you would be hungry. This chapter therefore considers a competing algorithm that does not simply promise to find a winning path, but more powerfully promises to find the shortest one.
