Game over

By Tom Whipple

In the years following the publication of J. Sturge’s canonical “Guide to the Game of Draughts” in 1800, the world of serious players was wracked by argument. Number 105 of Sturge’s “140 Striking Situations” had asked readers to demonstrate that with the pieces in a given position white could always win. An expert claimed in a rival publication that Sturge was wrong: the position was a draw. Another countered that it was a win for white – but not for the reasons Sturge suggested. Arguments would continue for the entire reign of Queen Victoria until a consensus was finally reached: it was a win for white.

This most controversial conundrum in the history of draughts became known as the Hundred Years Problem. The name was a little premature.

In 1997, a grandmaster showed the Hundred Years Problem to Jonathan Schaeffer, professor of computer science at the University of Alberta, who is by his own admission a rather mediocre player. Minutes later, Schaeffer announced that the result was a draw. This time, there was no controversy, because although Schaeffer is a mediocre draughts player he is an excellent computer scientist who had spent the previous decade working on a program, Chinook, designed to “solve” draughts.

It so happened that in the same year the computer Deep Blue defeated Gary Kasparov at chess – an event that Newsweek dubbed, “The Brain’s Last Stand”. In the battle of man versus machine, machine had won a great victory.

In draughts, though, the brain’s defeat has been much more comprehensive. By 1994 Chinook was already good enough to draw a championship match 6-6 with the world number one draughts player, Marion Tinsley. Three years later, it conquered the Hundred Years Problem. Ten years after that, it defeated the game itself: a paper published in the journal Science showed that Schaeffer’s program could play a “perfect” game of draughts. Whatever its opponent did, it would respond with the strongest possible play. While in theory a better computer program than Deep Blue could come along, the best any future human or computer could hope to do against Chinook was to draw. The game contained no further mysteries.

To many players, Chinook’s victory was the game’s loss. Before a game is solved a skilled player can be considered an artist, driven by inspiration and creativity as much as by cold logic. Afterwards the player is a fallible human – imperfectly striving to do what a computer has already done. The success of Chinook was as if overnight portrait painters had to cope with the invention of photography, calligraphers with the printing press.

Tinsley was untroubled. He said the program made him feel young again: for decades he had been unbeatable and at last he had a worthy opponent. But some draughts players took it badly. “They said I was going to destroy the game, to ruin it – that no one was going to play,” says Schaeffer. He received hate mail. Some players argued that the computer’s ability to draw on a database of moves, rather than computing best play each time, was cheating. Others considered Schaeffer had besmirched the name of Tinsley, who over a 40-year career lost fewer than ten games. In particular, they objected to the fact that the program won against him by default, because he discovered he had terminal cancer halfway through. “Chinook couldn’t hold a candle to Tinsley,” complained one angry player in a letter to Schaeffer. Another accused him of “trumpeting an unjustified victory against a sick old man”, a third of “engaging in intellectual dishonesty”. A fourth just called him “despicable”.

This upset Schaeffer, who in the course of developing the program had formed a friendship with Tinsley. “He was as close to perfection as you could imagine a human being. What some human players were upset about is we now were better than him.” Schaeffer uses the collective noun a couple of times when referring to him and Chinook. “He was truly outstanding, but he wasn’t quite perfect. He would make a mistake. It may have been only once every 10-15 years, but he would make a mistake.”

Schaeffer is one of a small group around the world trying to solve the world’s games. Last year, a colleague of his published a paper in which he solved a simplified version of poker. It ended by quoting Alan Turing: “It would be disingenuous of us to disguise the fact that the principal motive which prompted the work was the sheer fun of the thing.”

There are around 26,830 days in the average life. If you walked 26,830 miles you would cover the entire circumference of the equator, and still have enough distance left to go from Paris to Moscow. There are also 26,830 possible permutations in the first major game to be solved by a computer. That sounds like a lot, but this is a game so simple that in America there is a family of animal trainers that raises chickens to play it against humans as a casino attraction: noughts and crosses.

Most humans have solved noughts and crosses, and the solution is a draw. Writing a program to play a perfect game of noughts and crosses is now a basic undergraduate assignment.

A bigger number is 4,531,985,219,092. There have been roughly 4.5 trillion seconds since humans evolved. When Victor Allis, a computer-science student, contemplated the number in 1988, he realised it was too big for any computer to handle. It is, however, the number of possible permutations in Connect 4. “Computers then were pretty small,” says Allis.

Allis now runs Quintiq, a large Dutch software company. But he still enjoys talking about Connect 4. Unlike Schaeffer and draughts, he is also rather good at playing it. When he analysed why he normally won he realised it was because of “odd and even threats”: to win you need to have three in a row threatening completion on an odd row if you are the colour that goes first, and on an even one if you go second. That knowledge, plus a few other basic strategies and some clever computing helped him to reduce 4.5 trillion to something more manageable – and to solve Connect 4.

When it was launched, Connect 4 was marketed as “vertical checkers” – the American term for draughts. It was a slogan about as sensible as marketing walking as “horizontal climbing”, for the games are different.

From a computer scientist’s point of view, draughts is 100m times more complex – with 500 billion billion games. For many people, though, it is more about emotion. It is like the difference between rounders and baseball, or pool and snooker. People play Connect 4 for fun; they devote their lives to draughts. That was why when Allis solved Connect 4 it was an interesting curiosity, but when Schaeffer solved draughts it was, for some, cataclysmic.

Given how much emotion was generated by the solution of a game that has always been seen as chess’s less serious cousin, one can only imagine the response when chess finally falls. Luckily for Schaeffer’s mailbag, he is unlikely to be around to see that. “We are certainly not going to solve chess in my lifetime,” he says. “It will need a real change in technology.”

We are used to exponential improvement in computing. After all, in two decades the hardest game solved by a computer increased in complexity by 100m. So why is Schaeffer pessimistic about chess?

Five hundred billion billion is big. But the number of atoms in the Earth is unimaginably big. The number of atoms in the universe is an unimaginably big number times an unimaginably big number. Chess is so complex that no one is certain how complex it is – estimates range between these two numbers.

“Very simply expressed, the problem of playing a perfect chess game is that there are too many possible chess games,” says David Levy, president of the International Computer Games Association – a body that, despite its title, has very little to do with Grand Theft Auto – and a lot to do with chess and draughts. “Remember, the pieces are not all the same. In checkers there are two pieces – the man and the king. In chess there are six pieces. That is a huge difference. The game of checkers – I don’t want to use the word ‘simple’ – but it is simple enough.”

It is hard not to feel there is something marvellous about this. At some point, more than 1,000 years ago, a game was developed by pre-scientific people – maybe in China, probably in India – that developed into something confined to a board eight squares by eight squares, but turned out to be as complicated as the planet we are on. In the centuries since, almost all other games devised by humans have been solved by humans – but it has held firm. Levy won’t go so far as to say it will never be solved. “Never is a very long time,” he says. “Who knows what might one day be possible? It could be a DNA computer that will solve it, or an optical computer.” Others have suggested quantum computers – even more exotic machines that harness the behaviour of subatomic particles. But it is clear that no computer using silicon chips will ever do it.

The question is, if such a computer is devised, and chess at last falls, does that count as a victory for human ingenuity? Or a defeat? Or maybe, in the end, like Turing we should just accept it has always been about “the sheer fun of the thing”.■

illustration Brett Ryder