January 27, 2010

How Many Moves Ahead?

Famous chess players often get asked the same thing by reporters: "How many moves can you see ahead?" The query crept up, inevitable as the sunrise, in Time's interview with 19-year-old Magnus Carlsen. (He responded, "Sometimes 15 to 20 moves ahead—but the trick is evaluating the position at the end of those calculations.") Thing is, it's sort of an odd and not very well-defined question.

In an endgame, with just a few pieces left on the board, sure, a good player will plot out where things are heading down to the bitter end. But in the middle of a game? There are about 40 possible moves in the average chess position, so analyzing all the possibilities even just two moves out would involve looking at 2.5 million positions. No human brain can pull that off. Instead, recognizing patterns and assessing positions is the far more crucial skill, which is basically what Carlsen was saying, if you read his quote carefully. In The Inner Game of Chess, Andrew Soltis argues that most grandmasters don't usually gaze more than two moves ahead—they don't need to. And then there's Garry Kasparov's take on this question, in his fascinating New York Review of Books essay on computer chess:
As for how many moves ahead a grandmaster sees, Russkin-Gutman makes much of the answer attributed to the great Cuban world champion José Raúl Capablanca, among others: "Just one, the best one." This answer is as good or bad as any other, a pithy way of disposing with an attempt by an outsider to ask something insightful and failing to do so. It's the equivalent of asking Lance Armstrong how many times he shifts gears during the Tour de France.

The only real answer, "It depends on the position and how much time I have," is unsatisfying. In what may have been my best tournament game at the 1999 Hoogovens tournament in the Netherlands, I visualized the winning position a full fifteen moves ahead—an unusual feat. I sacrificed a great deal of material for an attack, burning my bridges; if my calculations were faulty I would be dead lost. Although my intuition was correct and my opponent, Topalov again, failed to find the best defense under pressure, subsequent analysis showed that despite my Herculean effort I had missed a shorter route to victory. Capablanca's sarcasm aside, correctly evaluating a small handful of moves is far more important in human chess, and human decision-making in general, than the systematically deeper and deeper search for better moves—the number of moves "seen ahead"—that computers rely on.
Speaking of computer chess, I wanted to bring up one of my favorite points: that, even though your average laptop chess program can now whip any grandmaster, computers still have trouble mastering the game of Go—even the most advanced programs get crushed by skilled children. Except that, it turns out, this talking point's now a few years obsolete. According to a recent Wired report, AI Go players are starting to beat ranking human players using the Monte Carlo method. Just another step down the path to robot domination, I guess.

(Flickr photo credit: Boered)
-- Brad Plumer 10:10 AM || ||