Computing a chess game's end

The game was down to six pieces. Former world chess champion Anatoly Karpov, playing white, had a king, a bishop and two knights, whereas current world champion Gary Kasparov had only a king and a rook. In the end, the two combatants played to a draw. But was that the only possible outcome? Was there a way for Karpov to win?

Whereas chess experts would find themselves hard-pressed to answer such questions with any degree of certainty, a new, sophisticated computer program specifically designed for analyzing six-piece endgames can now provide the answers. Developed by Lewis Stiller, a graduate student in computer science at Johns Hopkins University in Baltimore, the program systematically works out the combinations of moves that produce various outcomes when given the identities and initial positions of six chess pieces, none of which is a pawn.

In this example, Stiller's program, running on a multiprocessor computer known as The Connection Machine, provided the answer in about 90 minutes. The program demonstrated that unless Kasparov made a mistake, Karpov could do nothing that would give him even a chance to win. This particular game, played at a tournament last month, was fated to end in a draw. Based on conventional chess wisdom, that's not really surprising, Stiller says. But computer analyses have in the past produced a number of counterintuitive results. "There's no way anybody can be sure until we actually solve the position," he says.

Stiller's most dramatic result so far concerns an endgame involving a king, a rook and a bishop versus a king and two knights. Chess experts generally assumed that the rook and bishop could not force a win. However, Stiller's program uncovered a winning line of attack 223 moves long, starting with the pieces in the position shown in the diagram. This represents by far the longest sequence of moves needed to win ever established in a chess endgame.

In performing such analyses, the computer program starts by constructing a huge, carefully laid out table with roughly 8 billion entries, each corresponding to a particular chess position involving a given set of six pieces. The program first finds and marks any entries showing positions in which the white pieces have already achieved a win. Then it works backward step by step to determine which combinations of moves lead to those winning positions, keeping track of each position unveiled during these moves by appropriately marking the requisite table entries. Once the table is fully annotated and summarized, Stiller can study particular sets of moves.

Stiller's method isn't completely foolproof. The computer program itself may still contain errors, and other errors can slip into the data and the computer-generated tables. "Based on my experience, I feel very confident that the results are accurate," he says. "On the other hand, it's such a large database that even if there's only a one in billion chance that a byte is wrong, already you would have a problem."

Besides the potential usefulness of the novel techniques required for writing the chess program, Stiller says, "I think there is scientific value in showing that there are so many surprises and such incredible depth in even a simple-seeming problem." He describes his program in the current JOURNAL OF SUPERCOMPUTING (Vol.5, No.2).

COPYRIGHT 1991 Science Service, Inc.
COPYRIGHT 2004 Gale Group