Strangely enough, it’s this argument that I’m the most interested in, and the one I want to talk about. What seems at first to mean simply that he made an uncharacteristic blunder (which he did) actually has a very deep and altogether different meaning behind it. Because I think he means it literally.
Well, if Deep Blue didn’t win it, who—or what—did?
This is the question that starts to take us into the really weird and interesting territory.
How a Chess Program Is Built
To answer it, we need to get into some briefly technical stuff about how chess computers work;2 hopefully I can demystify a few things without going into soul-crushing detail.
Almost all computer chess programs work essentially the same way. To make a chess program, you need three things: (1) a way to represent the board, (2) a way to generate legal moves, and (3) a way to pick the best move.
Computers can only do one thing: math. Fortunately for them, a shockingly high percentage of life can be translated into math. Music is represented by air pressure values over time, video is represented by red, blue, and green intensity values over time, and a chessboard is just a grid (in computer jargon: “array”) of numbers, representing what piece, if any, is on that square.3 Compared to encoding a song, or a film: piece of cake. As is often true in computer science, there are nifty tricks you can do, and clever corners you can cut, to save time and space—in some cases, astonishingly much—but those don’t concern us here.
Once the computer has a chessboard it can understand in its own language (numbers), it figures out what the legal moves are from a given position. This is also simple, in fact, rather boringly straightforward, and involves a process like: “Check the first square. If empty, move on. If not empty, check what kind of piece it is. If a rook, see if it can move one square left. If yes, check to see if it can move another square left, and so on. If not, see if it can move one square right …” Again, there are some clever and ingenious ways to speed this up, and if you’re trying to take down a world champion, they become important—for example, Deep Blue’s creator, IBM electrical engineer Feng-hsiung Hsu, designed Deep Blue’s thirty-six-thousand-transistor move generator by hand—but we are not touching that level of detail with a ten-foot pole. If shaving off microseconds doesn’t matter to you, then anything that tells you the moves will do the trick.
Okay, so we can represent the board and we can figure out what moves are possible. Now we need an algorithm to help us decide what move to make. The idea is this:
1. How do I know what my best move is? Simple! The best move is the one that, after you make the best countermove, leaves me in the best shape.
2. Well, but how do I know what your best countermove is? Simple! It’s the one that, after my best reply, leaves you in the best shape.
(And how do we know what my best reply is? Simple! See step one!)
You’re starting to get the sense that this is a rather circular definition. Or not circular, exactly, but what computer scientists call recursive. A function that calls itself. This particular function, which calls itself, you might say, in reverse—what move makes things best, given the move that makes things worst, given the move that makes things best, etc.—is called a minimization-maximization algorithm, or “minimax algorithm,” and it crops up virtually everywhere in the theory and the AI of games.
Well, if you’re writing a program for tic-tac-toe, for instance, this isn’t a problem. Because the game only has nine possible first moves, eight possible second moves, seven possible third moves, and so on. So that’s nine factorial: 9! = 362,880. That may seem like a big number, but that’s kid stuff to a computer. Deep Blue, and this was fifteen years ago, could look at 300,000,000 positions per second.4
The idea is that if your “search tree” goes all the way to the end, then the positions resolve into win, loss, and draw, the results filter back up, and then you move. The thing about chess, though, is that the search tree doesn’t bottom out. Searching the whole thing (1090 years was Claude Shannon’s famous estimate) would take considerably longer than the lifetime (a paltry 13.73 × 109 years) of the universe.
So you have to pull it up short. There are very sophisticated ways of doing this, but the easiest is just to specify a maximum search depth at which point you just have to call off the dogs. (Calling off the search in some lines before you call it off in others is called pruning.) So how do you evaluate the position if you can’t look any further ahead and the game’s not over? You use something called a heuristic, which—barring the ability to consider any further moves or countermoves—is a kind of static guesstimate of how good that position seems, looking at things like who has more pieces, whose king is safer, and things like that.5
That’s it: represent the board, find moves and search through the replies, evaluate their outcomes with a heuristic, and use minimax to pick the best. The computer can then play chess.
The Book
There is, however, one other major add-on that top computer programs use, and this is what I want to talk about.
Computer programmers have a technique called “memoization,” where the results of frequently called functions are simply stored and recalled—much like the way most math-savvy people will, when asked, respond that 12 squared is 144, or that 31 is prime, without actually crunching the numbers. Memoization is frequently a big time-saver in software, and it’s used in chess software in a very particular way.
Now, every time Deep Blue starts a game, from that standard initial position of chess, it gets cranking on those 300 million positions a second, looks around for a while, and makes its choice. Because it’s a computer, and unless it has randomness specifically programmed in, it’s likely to be the same choice. Every time.
Doesn’t that seem like a lot of effort? A waste of electricity, from the environmental perspective alone?
What if we just calculated it once and memoized it, that is, wrote down what we decided—and then we simply always did that?
Well—and what if we started doing this game after game, position after position?
And what if we were able to upload databases of hundreds of thousands of grandmaster games and write them down, too?
And what if we looked at every professional game ever played by Garry Kasparov and did some 300 million positions/second analysis ahead of time of the best responses to the positions likely to come up against him? What if we did, in fact, several months of analysis ahead of time? And, while we’re at it, what if we employed a secret team of human grandmasters to help the process along?
This is hardly “cheating” since that is the way chess masters play.
–CLAUDE SHANNON, “PROGRAMMING A
COMPUTER FOR PLAYING CHESS”
But I’m making it sound more sinister than it was. First of all, Kasparov knew it was happening. Second, it’s what all professional chess players do before all professional chess games: all the top players have “seconds,” slightly weaker professional players who prepare analysis—personalized for the opponent—before a match or tournament. This, in addition to the massive repertoire of openings and opening theory that all top players know. That’s how the game is played. And this corpus of pre-played positions, untold thousands, if not millions, of them, this difference between discovery and memory, is called the book.
The Two Ends: Openings and Endings
All chess games begin from the exact same position. Because there are only so many moves you can make from that starting position, games will naturally take a while to differentiate themselves. Thus, a database of, say, a million games will have a million examples of a player making a move from that initial configuration; all other configurations will be a diminishing fraction of that. The more popular lines6 maintain that “density” of data longer, sometimes beyond 25 moves, whereas the more unpopular or offbeat lines might peter out much more quickly. (The world’s top computer program in recent years, Rybka, supposedly has certain lines in the Sicilian “booked” up to 40
moves, or longer than many games—for instance, only one game in the Kasparov–Deep Blue rematch went to move 50.)
At the other side: once enough pieces have been taken off the board, you begin to arrive at situations where the computer can simply preprocess and record every single possible configuration of those pieces. For example, the simplest endgame would perhaps be king and queen vs. king—three pieces on the board. That makes for, let’s see, 64 X 63 X 62 = 249,984 positions (minus some illegal ones, like when the kings are touching), and if you factor in the horizontal and (in this case) vertical symmetry of the board, you’re down to at most 62,496. Very manageable. Once you start adding pieces, it gets progressively hairier, but all positions involving six or fewer pieces have already been “solved.” This includes positions like some rook-and-knight versus two-knight endings, where, for instance, every move leads to a draw with perfect play except one—with which the strong side can, with inhumanly perfect and unintuitive play, force a checkmate in 262 moves.7 That used to be the record, actually; but now programmers Marc Bourzutschky and Yakov Konoval have found a seven-piece endgame with a forced mate in 517.
Positions like this seem to me to be vaguely evil—there’s absolutely nothing you can say about them to make them make sense. No way to answer the question, “Why is that the best move?” other than by simply pointing to the move tree and saying, “I don’t know, but that’s what it says.” There is no explanation, no verbal translation, no intuition that can penetrate the position. “To grandmasters, it may turn out that the dismaying message of the latest computer analysis is that concepts do not always work in the endgame” (emphasis mine), the New York Times wrote in 1986, and quoted U.S. Chess Federation administrator, and grandmaster, Arthur Bisguier: “We’re looking for something esthetic in chess—logic is esthetic. This bothers me philosophically.”8
Maybe, as a person who is always, always theorizing, always, always verbalizing, this is what disturbs me, too: there is no such thing to be done. Computers’ lightning-fast but unintuitive exploration of the game tree is known as the “brute force” method to game AI. This is what the “brute” in “brute force” means to me; this is what’s brute about it. No theory. No words.
Anyway, these tables are known as “endgame databases” or “endgame tables,” or “tablebases” or “telebases,” but we’re fairly safe in calling them “books.” The principle—look up a position and play the prescribed move—is the same.
So: there’s an opening book, and an ending book.
The middle game—where the pieces have moved around enough so that the uniform starting position is a distant memory, but there’s enough firepower on the board so that the endgame is still far off—is where games are most different, most unique.
“The whole strategy in solving a game is to shrink that middle part until it disappears, so your beginning game and your endgame connect,” says Rutgers University computer scientist Michael Littman.
“Fortunately,” says Kasparov, “the two ends—opening research and endgame databases—will never meet.”
The Two Ends: Greetings and Closings
Letter writing is a great example of how “opening book” and “endgame book” occur in human relations. Every schoolchild learns the greetings and closings of a letter. They’re so formalized, ritualized, that, well, computers can do them. If I end a paragraph in MS Word, and begin a new paragraph “Your,” I immediately see a tiny yellow box with “Yours truly” in it. If I hit return, it auto-completes. If I type “To who,” the “m it may concern” auto-completes. “Dear S” gives me “ir or Madam,” “Cord,” “ially,” etc.
We’re literally taught this “opening book” and “ending book” in schools. Then we go through life with our ears out—whether we know it or not—for subtle trends and indications of connotation, of context, of fashion. “What’s up” originally felt awkward to me as a kid, imitative and unnatural, inauthentic—I couldn’t say it, I found, without some kind of quotation marks—but it became as natural to me as “Hi.” Then I watched, a few years later, the same process happen to my parents: their first few “What’s up’s” seeming like pitiful attempts to be “hip,” and then increasingly I found I barely noticed. Abbreviations and truncations like “What up” and “Sup,” which seemed poised to take over the hip-greeting spot among the cool kids of my middle school, never quite made it. When I started negotiating the tricky formal-yet-informal, subordinate-yet-collegial space of email correspondence with my professors in college and then graduate school, my instinct was to close with “Talk to you soon,” but gradually I began to wonder if that didn’t feel like a coded demand for promptness on their part, which could be read as impolite. I observed, imitated, and quickly warmed to the closing “Best,” which then over some months started to feel curt; at some point I switched to “All the best,” which is my old standby these days. Etiquette is a bit like fashion: you never quite stop wising up to it.
And, I should add, it’s a bit like fashion in that you should be careful where you get your advice from: this afternoon I idly Googled “business letter closings,” and the top hit is a list that includes “Adios” and “Ta ta.” I don’t think so.
When I started translating poetry, and began an email correspondence with a Venezuelan writer in Spanish—which I do not use conversationally very much, and certainly had never written emails to native speakers in before—I quickly learned and began mimicking the author’s “Estimado amigo” opening and “Salud y poesía!” or “Recibe un abrazo fraterno” closings. I remember looking up websites that showed traditional Spanish greetings and closings, but couldn’t trust them: you never know what sounds too stiff or too casual, too old-fashioned or too newfangled—not to mention the effects of all the national and regional deviations among the Spanish-speaking world. This is seriously tricky territory. I want to personalize my own openings and closings, but it’s a delicate thing: without a broader sample of what gets used, I’m hopelessly out of my depth. So I repeat back the few greetings and closings I know.
Try starting or, even worse, ending a conversation with a non-stock phrase. It feels almost unmanageably awkward, abrupt. You can barely think of something non-stock to say; if you do think it up, you can barely bring yourself to say it. The ritual tugs hard at us.
It’s pretty clear that if you want to get a flavor for a conversation by sampling, say, one or two sentences at random, you don’t sample from the beginning or the end; you sample from the middle.
It’s odd, in a way, how much etiquette and social ritual—which is not the same thing as formality, as, for instance, the long and elaborately choreographed handshakes you used to see in the 1980s and ’90s go to show—threaten, and it is a threat of sorts, to lengthen those “books.”
“Of course, the culture writes … first, and then we write …,” says playwright Charles Mee.
And when I write a letter, my culture gets the first word and, other than my name, the last.
I can express myself through my choice of openings/greetings, but, in some sense, the words aren’t mine. It isn’t me saying them.
Fortunately the two ends will never meet, says Kasparov. But I think we’ve all—haven’t we?—had that experience, the conversation that plays itself entirely out, the conversation where the formalities of the greeting reach all the way to meet the formalities of the closing, the conversation that at some level, as Kasparov puts it, “doesn’t even count” because it has probably been had, verbatim, before.
As it turns out, this is the conversation that the bots want to have in a Turing test. The conversation that the confederates are, in a fairly tangible way, fighting against (if keystrokes can be blows). The statistical, cultural, ritual regularities of human interaction are the weaknesses that these machines exploit.
In the Gaps
Grandmaster games are said to begin with a novelty, which is the first move of the game that exits the book. It could be the fifth, it could be the thirty-fifth. We think about
a chess game as beginning with move one and ending with checkmate. But this is not the case. The game begins when it gets out of book, and it ends when it goes into book. Like electricity, it only sparks in the gaps.9
The opening book, in particular, is massive. The game may end before you get out, but it doesn’t begin until you do. Said differently, you may not get out alive; on the other hand, you’re not alive until you get out.
Who Sacked My Knight? The Metaphysics of Book
My point is this. What would prevent—Mike, maybe you can answer this question. What would prevent Deep Blue from seeing the e6 pawn and just taking it if Garry leaves it there so that it can get close to redressing the material imbalance? After all, this sacrifice it played was not played on its own, on its own volition, it was programmed in. Maybe by now Deep Blue is thinking, when the new moves started on the board, Who sacked my knight? (Audience laughter.)
–GRANDMASTER MAURICE ASHLEY, COMMENTATOR DURING GAME 6
Like many people in the competitive chess world, both Deep Blue’s developers and Garry Kasparov subscribe to a kind of metaphysics of the book: the book isn’t the person. Deep Blue’s lead engineer, Feng-hsiung Hsu, has quotations about wanting to play “the World Champion, not his home preparation against our openings”; Kasparov says the same thing about the machine.
So the book is not the person—and the book is not the game: “Today’s game doesn’t even count as a game because probably it has been published before elsewhere.” An extremely strong statement: a game of chess that fails to get out of book is not a game of chess at all.
A “real” game or no, here it is, with some of the original live commentary: Deep Blue (white) v. Kasparov (black), 1997, Game 6.
The Most Human Human Page 12