TITLE: Old Dreams Live On AUTHOR: Eugene Wallingford DATE: September 14, 2009 10:53 PM DESC: ----- BODY:

"Only one, but it's always the right one."
-- Jose Raoul Capablanca,
when asked how many moves ahead
he looked while playing chess

When I was in high school, I played a lot of chess. That's also when I first learned about computer programming. I almost immediately was tantalized by the idea of writing a program to play chess. At the time, this was still a novelty. Chess programs were getting better, but they couldn't compete with the best humans yet, and I played just well enough to know how hard it was to play the game really well. Like so many people of that era, I thought that playing chess was a perfect paradigm of intelligence. It looked like such a wonderful challenge to the budding programmer in me. I never wrote a program that played chess well, yet my programming life often crossed paths with the game. My first program written out of passion was a program to implement a ratings system for our chess club. Later, in college, I wrote a program to perform the Swiss system commonly used to run chess tournaments as a part of my senior project. This was a pretty straightforward program, really, but it taught me a lot about data structures, algorithms, and how to model problems. Though I never wrote a great chessplaying program, that was the problem that mesmerized me and ultimately drew me to artificial intelligence and a major in computer science. In a practical sense, chess has been "solved", but not in the way that most of us who loved AI as kids had hoped. Rather than reasoning symbolically about positions and plans, attacks and counterattacks, Deep Blue, Fritz, and all of today's programs win by deep search. This is a strategy that works well for serial digital computers but not so well for the human mind. To some, the computer's approach seems uncivilized even today, but those of us who love AI ought be neither surprised nor chagrined. We have long claimed that intelligence can arise from any suitable architecture. We should be happy to learn how it arises most naturally for machines with fast processors and large memories. Deep Blue's approach may not help us to understand how we humans manage to play the game well in the face of its complexity and depth, but it turns out that this is another question entirely. Reading David Mechner's All Systems Go last week brought back a flood of memories. The Eastern game of Go stands alone these days among the great two-person board games, unconquered by the onslaught of raw machine power. The game's complexity is enormous, with a branching factor at each ply so high that search-based programs soon drown in a flood of positions. As such, Go encourages programmers to dream the Big Dream of implementing a deliberative, symbolic reasoner in order to create a programs that plays the game well. The hubris and well-meaning naivete of AI researchers have promised huge advances throughout the years, only to have ambitious predictions go unfulfilled in the face of unexpected complexity. Well-defined problems such as chess turned out to be complex enough that programs reasoning like humans were unable to succeed. Ill-defined problems involving human language and the interconnected network of implicit knowledge that humans seem to navigate so easily -- well, they are even more resistant to our solutions. Then, when we write programs to play games like chess well, many people -- including some AI researchers -- move the goal line. Schaefer et al. solved checkers with Chinook, but many say that its use of fast search and a big endgame databases is unfair. Chess remains unsolved in the formal sense, but even inexpensive programs available on the mass market play far, far better than all but a handful of humans in the world. The best program play better than the best humans. Not so with Go. Mechner writes:
Go is too complex, too subtle a game to yield to exhaustive, relatively simpleminded computer searches. To master it, a program has to think more like a person.
And then:
Go sends investigators back to the basics--to the study of learning, of knowledge representation, of pattern recognition and strategic planning. It forces us to find new models for how we think, or at least for how we think we think.
Ah, the dream lives! Even so, I am nervous when I read Mechner talking about the subtlety of Go, the depth of its strategy, and the impossibility of playing it well in by search and power. The histories of AI and CS have demonstrated repeatedly that what we think difficult often turns out to be straightforward for the right sort of program, and that what we think easy often turns out to be achingly difficult to implement. What Mechner calls 'subtle' about Go may well just be a name for our ignorance, for our lack of understanding today. It might be wise for Go aficionados to remain humble... Man's hubris survives only until the gods see fit to smash it. We humans draw on the challenge of great problems to inspire us to study, work, and create. Lance Fortnow wrote recently about the mystique of the open problem. He expresses the essence of one of the obstacles we in CS face in trying to excite the current generation of students about our discipline: "It was much more interesting to go to the moon in the 60's than it is today." P versus NP may excite a small group of us, but when kids walk around with iPhones in their pockets and play on-line games more realistic than my real life, it is hard to find the equivalent of the moon mission to excite students with the prospect of computer science. Isn't all of computing like Fermat's last theorem: "Nothing there left to dream there."? For old fogies like me, there is still a lot of passion and excitement in the challenge of a game like Go. Some days, I get the urge to ditch my serious work -- work that matters to people in the world, return to my roots, and write a program to play Go. Don't tell me it can't be done. -----