Hopkins chess buff computes an end to ancient riddle

October 24, 1991|By Douglas Birch

Lewis B. Stiller, a 25-year-old Johns Hopkins graduate student who describes himself as not a full-fledged expert in the game, has proved that a centuries-old maxim of chess masters is dead wrong.

Combining a new processing technique on an advanced computer and a 10,000-line program, the soft-spoken Roland Park man looked at a type of pawnless endgame that the game's leading players believed always ended in a draw. An endgame is a point late in many contests where a small number of pieces maneuver around the board without being captured.

He found that, after an unheard of number of moves, some of these endgames could result in wins.

Over the past several years, Mr. Stiller, who received an undergraduate degree from Hopkins at age 16 and "sort of skipped" high school, has spent more than 50 sleepless nights writing his program. It explores these chess problems more deeply than they have ever been studied.

Running the program on supercomputers, he recently found these winning solutions. And his most intriguing discovery came this summer, while he was studying at the Los Alamos National Laboratory in New Mexico. Around midnight, the lanky young scientist, who has a weakness for Bach and late-evening pizzas, sat down at a terminal in a windowless room at the laboratory.

He ran his program on a six-piece endgame in which the white king has a rook and bishop and the black king has two knights, using the lab's Thinking Machines Corp. supercomputer. The machine uses parallel processing to break up a problem in to pieces and work on several of those pieces at the same time.

Five hours, 32 trillion operations and 223 moves later, the computer reached a position where white was guaranteed to capture a black knight and eventually take the game. The longest previous endgame studied, he said, was less than 100 moves long.

The sequence of moves doesn't fit any of the classic patterns of the world's most extensively studied game.

"They really didn't seem to be making any sense," he said, pointing to a series of moves in a 16-page summary. "If you look here, white seems to be moving randomly. And that's very, very interesting."

Mr. Stiller's approach was to try to find all possible endgames involving a given set of pieces -- which, in the world of computer chess, is called an exhaustive search.

He did this by having the computer work backward from all known winning positions for the pieces to the supposed "draw."

The task was enormous. "It would have been difficult, maybe impossible, to tackle without massively parallel [computer] techniques," he said.

Mr. Stiller, who works in Hopkins' artificial intelligence lab, tackled the problem as an exercise in parallel programming.

"He found some very clever programs for doing this," said Burton Wendroff, a mathematician at Los Alamos National Laboratory, who helped Mr. Stiller. Noam Elkies, a math professor at Harvard, also helped him with the work.

Mr. Wendroff said he was not surprised by the length of the endgame, since he was familiar with Mr. Stiller's work on the problem in recent years.

"We could sort of see it coming, I think," he said. "With six pieces, it [the endgame] is very complicated. It's probably beyond humans to figure out."

Mr. Stiller, whose findings were reported in November's edition of Scientific American, said it's not likely any grandmasters will bother studying his 223-move endgame as they might other classic sequences of moves. "These positions don't actually occur very often in real chess," he said.

Mr. Stiller, who plays occasionally at The Chess Story on Park Avenue, said bigger challenges are still out there: endgames involving eight pieces, which could easily surpass 223 moves.

"It sounds very simple, but it gets very hairy, it really does," he said.

Baltimore Sun Articles
Please note the green-lined linked article text has been applied commercially without any involvement from our newsroom editors, reporters or any other editorial staff.