The checkers challenge: a checker-playing computer program contends for the world title.

Like many chess players, computer scientist Jonathan Schaeffer had a condescending attitude toward the game of checkers. Its childishly simple rules and its image as a sedate pastime for elderly gentlemen put checkers deep in the shadow of chess, it smore prestigious rival.

It was natural, then, for computer programmers to ignore checkers and to focus instead on the challenge of creating machines that could master chess. Schaeffer himself spent many years perfecting a chess program named Phoenix. In 1986, this program tied for first place at the world computer chess championship.

Despite that success, Schaeffer felt frustrated. Without ready access to enormous computing power, and ill-equipped to build a computer specifically designed for playing chess, he found he could make little further progress.

Early in 1989, he abruptly changed the direction of his research. Responding to a casual query concerning progress in computer checkers, he discovered that programming a computer to play checkers had been largely neglected for decades, partly because many computer scientists and artificial-intelligence experts already believed -- erroneously -- that for all practical purposes, the game had been solved.

"I was quite surprised that nearly everybody had been ignoring checkers," Schaeffer says. "So we decided to do something about it."

Today, the checker program he and his colleagues developed ranks among the top 10 checker players in the world. This computer program, called Chinook, stands ready to challenge the top human player for the world title -- if the game's sanctioning organizations ever relent and approve the match.

At the same time, computer scientists are finding that checkers -- like chess -- provides a handy platform on which to develop and test new programming concepts that may eventually prove useful in other applications.

Schaeffer, of the University of Alberta in Edmonton, started out by taking a close look at the pioneering work of Arthur Samuel, an IBM researcher who began to program checkers in 1952. Samuel gradually improved his checker-playing programs to the point where one of those programs, in the early 1960s, won a game against a master-level human player, albeit under special circumstances.

Schaeffer noted that although Samuel had worked with the fastest computers and the most advanced programming techniques avalable at the time, his program lacked many of the features that contribute to the remarkable performance of present-day chess programs.

"He had to labor under the limitations of the technology," Schaeffer says. "Today's machines run hundreds of times faster, and today's algorithms allow us to search much more efficiently."

Working with two computer science faculty members and two undergraduate students, Schaeffer began to put together the program that became Chinook. "Our first priority was to get a functional program that played a halfway decent game," Schaeffer says.

Simultaneously, the Alberta team began to develop a set of databases that involved computing every possible position that can be reached when there are fewer than a certain number of pieces on the checkerboard. With such databases at its disposal and with a game down to the last few pieces, Chinook could then look up all possible outcomes for a given position and select an appropriate strategy to ensure a win or to delay a loss, they reasoned.

"It was an enormous task computationally," Schaeffer says. "We knew it would take years to get it done."

About two months of frenetic programming prepared Chinook for its first major challenge: a computer-against-computer olympiad, held in London, England, in August 1989. "The program was brand new," Schaeffer recalls. "There were obviously lots of things wrong with it, and lots of things we had yet to try."

Written in the computer language C, running on a workstation and with only a four-piece database available for checking outcomes at the end of games, Chinook nevertheless won first place, defeating a number of other checker-playing computers.

After the competition, work on Chinook began in earnest. The next 10 months saw a vast improvement in Chinook's play. Much of that progress resulted from the addition of an expert checker player to the Alberta team.

"The lack of checker knowledge was our bottleneck for the first six months," Schaeffer says. None of the original team members had ever played the game seriously, and they had to rely on books and other sources to get a handle on its strategy.

Then Schaeffer remembered receiving an inquiry three years before from someone interested in checker programs. On impulse, he tracked the individual down and came up with Normal Treloar, then an unemployed astrophysicist and a first-rate checker player with time on his hands.

"Treloar was a tremendous asset to the project," Schaeffer says. "Very quickly, he was able to figure out what a computer can and can't do, and he was able to describe the checker knowledge that he thought should be in the program in terms that we could actually implement on a computer."

By June 1990, the computer program, equipped with a five-piece end-game database, was good enough to win one game out of 20 from a humam checker player who was ranked among the top players in the world.

A month later, Schaeffer took Chinook to Tupelo, site of the Mississippi State Open Checker Tournament. This time, the program had a six-piece end-game database to help it along.

"Much to the surprise of everybody, including myself, we won the tournament," Schaeffer says.

This provided just a forestate of the future. The U.S. National Open -- the premier event in international checker play -- took place the following week, attracting nine of the top 10 human players in the world, including world champion Marion Tinsley, a semiretired mathematician from Tallahassee, Fla.

In the tournament, each contestant played eight matches against eight opponents, with each match consisting of four games. The rules specified that each player had to complete 22 moves per hour to keep the games going at a reasonable pace.

In round seven, Chinook faced Tinsley. All four games -- replete with tension and excitement -- ended as draws. "That result stunned everybody," Schaeffer says.

Overall, Chinook placed second in the tournament, winning four matches and drawing four. With five wins and three draws, Tinsley took first place. But Chinook's astonishing performance had earned it the right to challenge for the world title.

In Tinsley, Chinook faces a formidable opponent. Now 63, Tinsley first won the world championship in 1956. He resigned his title in 1958 and retired from checkers to pursue other interests; in 1975, he resumed play and promptly regained the championship. Since then, Tinsley has lost only three of the thousands of games he has played in tournaments and exhibition matches.

"He is as close to protection as you can imagine in a human checker player," Schaeffer says.

Tinsley visited Edmonton last December and played a friendly match against Chinook. He won one game, and the remaining 13 games ended in draws.

From Tinsley's point of view, Chinook plays like a precocious youngster. "He [Chinook] really hasn't developed much in the way of judgment and makes strange moves, but then gets down and just fights like the very devil after getting into trouble," Tinsley says. "It's exciting to play him."

Playing against Chinook and watching the computer respond to particular positions has also brought human competitors new insights and fresh approaches to the game. In one instance, Chinook examined a particularly difficult opening developed by Tinsley and found a novel, alternative defense.

"Without any doubt, this is going to contribute a lot to checkers," Tinsley says. "I'm amazed how well they've done."

Human players could even use a checker-playing computer like Chinook as an assistant to analyze tough situations and suggest possible courses of action. "A good checker player could use his own maturity and experience to direct Chinook to work along certain lines, and then turn the computer loose all night to work out the moves," Tinsley notes.

"For people who want to study the game and find the best moves, a program like Chinook is beautiful," says Herschel F. Smith, who recently retired from IBM and now directs the International Checker Hall of Fame in Petal, Miss. "I have a computer that runs [a copy of] Chinook, and I play with it night and day. I've not beaten it yet."

Chinook doesn't have the electronic field entirely to itself. Two other programs play at the master level. Checkers Experimental, developed by Gil Dodgen of Garden Grove, Calif., tied for sixth place in the U.S. National Open after losing only three matches to human players. A British program named Colossus also ranks high.

At the University of Rochester in New York, graduate student Brian Marsh and his colleagues are even using checker play as part of a project designed to investigate ways of integrating computer programs written in different languages. In this context, the Rochester team has developed a checker-playing robot that not only works out a strategy but also "sees" the board, makes the moves and even comments on the play.

Combining such varied functions as vision, motion, voice and reasoning requires the integration of several different styles of computing. The techniques Marsh has developed allow researchers to choose the computer language best suited for a given task instead of compromising on a single, less-than-optimal language for all the functions.

Chinook, however, ranks at the top in the digital checkers world. Although Schaeffer's considerable experience in developing efficient search techniques for computer chess makes an important contribution to Chinook's prowess, he says the computer's prime advantage lies in the end-game databases that it can bring to bear in matches.

Indeed, Chinook can now check 2.3 billion positions attainable with six or fewer pieces, and the Alberta researchers are in the midst of computing the 35 billion possible positions for seven pieces. "We believe that if we could reach the eight-piece database, which includes 400 billion positions, we would be virtually unbeatable," Schaeffer says.

Chinook continues to improve, but now there's uncertainty about whether it will ever contend for the world title -- even though it won the right to do so at the U.S. National Open.

Both the American Checker Federation and the English Draughts Association have refused to sanction a title match between Chinook and Tinsley. In May, Tinsley resigned his title, in part to protest this move.

"Their decision grieves me greatly," he says. "So I'm trying to put some pressure on."

Meanwhile, Tinsley may visit Edmonton to play another friendly match against Chinook. And a 40-game exhibition match between them in London, England, is in the works for later this year.

At this stage, Schaeffer doubts that Chinook can beat Tinsley in a 40-game match. But the time may come.

Schaeffer's ultimate goal is to solve the game of checkers -- to develop a computer program that knows all the possible outcomes of any given position. "We believe we can come up with a program that can play perfect checkers," he says.

That's conceivable in checkers, where the number of possible positions is [10.sup.20]. In chess, the number is [10.sup.44]; in the ancient Chinese game of Go, it's [10.sup.120]. "We can realistically consider solving checkers, but we could never contemplate solving chess or Go," Schaeffer says. "They're just too big."

The former chess programmer has also developed a new appreciation of checkers. "Having gotten involved in the game, I have a lot more respect for it than I had before," Schaeffer admits. "The game is in fact inordinately complex. It's much more subtle and much more elegant than most people ever give it credit for."