Dr. Dobb's Journal - September 2008 - (Page 16)

D09LEAD_p1ds.qxp 7/11/08 11:47 AM Page 16 Strategic Vision by Jack Woehr A Conversation With Erik Demaine Erik Demaine took his bachelor’s at the age of 14 and at 20 became the youngest professor in the history of MIT. Erik received a MacArthur fellowship in 2003, which cited him as a “computational geometer tackling and solving difficult problems related to folding and bending—moving readily between the theoretical and the playful, with a keen eye to revealing the former in the latter” Erik is one of this year’s Katayanagi Prize winners. His website (erikdemaine.org) . includes Demaine’s work in Computational Origami, and highlights the great beauty found in mathematics. Erik’s recent book (with collaborator Joseph O’Rourke) is Geometric Folding Algorithms: Linkages, Origami, Polyhedra (www.gfalop.org)—read the theory, proof, and algorithm and then copy ’em, fold ’em and cut ’em! Within two minutes of our conversation with Erik, the conversation had arrived by its own inscrutable logic at game theory and veered off from there towards epistemology, biology, parenting, and origami. DDJ: You are noted for your work in folding geometry. Is there a folding geometric solution to the game of chess? ED: There is no good solution to chess. DDJ: How can there not be? ED: It’s a matter addressed in the study of computational complexity. DDJ: The pieces’ moves are regular, the board is regular, and there is a certain large number of possible checkmates and many symmetric reflections of them around the board. The Knight’s Tour is algorithmically solved since the 18th century, why isn’t the game solvable? ED: The game is harder. You can prove you need exponential time to solve the game. You need to brute-force search through all possible moves. DDJ: I’ve been familiar with that assessment since the 1970s. I just can’t believe it! It seems to me that if you, say, had an infinite number of origami cranes you folded just right, you could describe chess that way. ED: That’s probably true, but that relationship is not size preserving. You would need a huge number of cranes, or bits, or whatever you want to think about, in order to represent the full game of chess. So even though chess positions can be very succinctly described, the whole game, the tree of possible states, is “gi-normous” . The 8x8 game is trivial. It’s not interesting from a theoretician’s point of view. I assume it will eventually be solved. Checkers was solved last year. DDJ: Checkers was pretty much solved by human beings by the mid20th century. 16 Dr. Dobb’s Journal l www.ddj.com l September 2008 ED: The solution is not geometric, and I don’t know how algorithmic it is, but it is exhaustive and provably correct. They do some tricks to show that certain moves need not be considered because they’re guaranteed not to be useful plays. And from the initial position, they’ve tried everything. DDJ: Computers can exhaustively examine every move. But is there a mathematical answer, like, “Considered in 15 dimensions a king looks like this, a queen looks like this, starting from a certain position, ergo…” ED: Computational complexity theory tells you there is no clean answer for games like Chess, Checkers, and Go. If you believe in the perspective of complexity theory, it tells you that all you can do is sit there and do the bookkeeping and exhaust the exponential possibilities. DDJ: But there’s an algorithimic solution to Nim. ED: Yes and computational complexity theory says that Nim is “easy.” There’s an easy algorithm for Nim. You can prove that there is no easy one for Chess, and by that I mean an nxn chessboard. Complexity theory only applies to certain scalable problems. But the problem of Chess as it is played is not theoretically interesting…we know the answer. DDJ: What is “interesting”? ED: The problems we don’t know the answer to. Finding the answer, or proving that there isn’t one. That’s the name of the game in algorithms: Find an interesting problem that no one has solved before, nor shown that it’s unsolvable. DDJ: Epistemologically, is it really that there is an Ideal against which you can compare a problem, or is it just that, “Our scaffolding http://erikdemaine.org http://www.gfalop.org http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - September 2008

Dr. Dobb's Journal - September 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook A Conversation With Erik Demaine Application Lifecycle Management Meets Model-Driven Development Building a Robust Development Environment Real Users Really Matter Matching Wildcards: An Algorithm The Android Mobile Phone Platform Managing Application Thread Use Signalling Integer Overflows in Java .NET Development & the IBM WebSphere Portal Server The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - September 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.