Computer ingenuity solves old chess puzzle

Alex Dominguez
The Associated Press

The Denver Post
Tuesday, October 29, 1991


BALTIMORE -- A 25-year-old graduate student solved an ancient chess puzzle by taking a computer to places no computer has gone before.

The double feat by Lewis Stiller, a computer scientist at Johns Hopkins University, not only settled an old chess conundrum, but also opened the door for analysis once considered too complicated for even the fastest computers.

"It's very important. Sort of like discovering that there's a new element," said Hans Berliner, a computer scientist at Carnegie-Mellon University in Pittsburgh.

By performing one of the largest computer searches ever conducted, Stiller found a king, a rook and a bishop can defeat a king and two knights in 223 moves, ending argument over whether the position is a draw.

Stiller, who works in Hopkins' artificial intelligence lab, made the search by writing a new program that tapped the power of a massively parallel computer at the Los Alamos National Laboratories in New Mexico.

The computer is actually thousands of processors working side by side on parts of a program. Unlike most computers, the Los Alamos machine has 65,536 processors instead of one. That enables it to break a problem into many smaller problems and solve them simultaneously.

Stiller devised a way to avoid bogging down the computer with communications between the processors while it worked his 10,000 line program.

The computer solved the chess problem in five hours last summer after considering 100 billion moves by retrograde analysis - working backward from a winning position. His findings were reported in November's Scientific American.

The prod to push the computer came from Noam Elkies, a Harvard mathematics professor Stiller met on a computer bulletin board. The two were discussing computers and chess when Elkies suggested the six-piece endgame.

Elkies said the solution goes beyond the gameboard.

"This is an idea that can be used for a much greater generality of problems than just chess games," Elkies said in a recent interview. "The new thing he was able to figure out was some important ways to allow the parallel computer to work on the problem.

The program can solve a five-piece endgame in about a minute and a six-piece endgame in four to six hours, said Stiller.

Kenneth Thompson of Bell Laboratories was the first to use retrograde analysis to solve chess endgames, the last portion of the game, proving a king and queen can defeat a king and two bishops.

Stiller, who plays down his achievement, said it wasn't important for the chess world.

"The actual significance of this for full chess is minimal because the position is very rare," he said.