SCIENCE FORUM

Checkered in a billion billion moves?

The game of English draughts, or American checkers, is more complex than it may seem at first sight. Rashida Ahmad takes a look at what it takes to solve a game with 500 billion billion variations

We have a good claim to having invented chess in this part of the world, which is perhaps why the game of English draughts, or American checkers, is seen somewhat as the poorer cousin in the subcontinent. After all, the rules of draughts could hardly be simpler, could they? But, that's not to say we should look on it as a simplistic game. Draughts has roughly 500 billion billion (5x1020) possible positions, which means "solving the game" is no mean task. In fact one computer program has been trying to do so almost continuously for nearly two decades.

Now, computer scientists at the University of Alberta in Canada have announced that draughts has finally been solved. But what exactly does that mean? Well, solving a game like draughts means "determining the final result in a game with no mistakes made by either player," according to professor of computer science, Jonathan Schaeffer and his team. Their paper, published last month in the journal Science, claims that "perfect play by both sides leads to a draw."

The computer program that allows them to make this claim is called Chinook, and was first developed in 1989 by Dr Schaeffer to try and beat the world's best draughts players. Running on as many as 200 computers simultaneously at times, it first began beating champion players in 1994. But Schaeffer and his team of computer scientists claim that no one can possibly beat Chinook at draughts today -- the best human player can only ever draw.

Simply put, the program reduces draughts to something resembling a vast game of noughts and crosses, for which the perfect strategy for a win or draw (that is, for never losing) can be explained to a child. But draughts, with its 500 billion billion possibilities compared with only 765 in noughts and crosses, is the most complex game that has been solved to date. Even for Chinook, however, it would have been impossible in practical terms to process moves for all 5x1020 board positions.

"It's a computational proof," says Schaeffer. "It's certainly not a formal mathematical proof."

That means there is no set of equations that can be applied for every possible play, and at the same it would be impossible to check every calculation Chinook might make. Chinook did not in fact need to go through every single one of the 500 billion billion possible moves -- not all losing plays needed to be analysed, for example. In the end, only 1/5,000,000 of the moves needed to be computed.

The solvability of a board game generally depends on two factors: the number of possible positions, or "state-space complexity," and the difficulty of deciding on the best move, or "decision complexity." Noughts and crosses is simple on both counts. Checkers is complex in both regards.

As for chess, it is obviously harder to solve than checkers, with a state-space complexity of 1046. Decision complexity in chess is difficult to quantify, but it is clearly very high. Artificial intelligence has created game-playing programmes, such as DEEP BLUE for chess. But solving a game means achieving perfection in chess. Until recently this was thought to be impossible, as mathematicians and programmers considered chess to be an "infinite game." But Chinook is now considered a significant step towards finding such a solution. Nevertheless, Schaeffer says new tools are needed before that can happen.

"Chess and Go cannot be solved with the type of technology that we have today," he says. The game of Go, played on a 19 by 19 grid, is considered by many to be the hardest conventional game to crack, with approximately 10100 possible positions.

In fact Dr. Schaeffer is taking a shot at cracking poker next -- a whole new game in which opponents' positions are not openly revealed. His program Polaris is currently taking on world champion poker players in Texas Hold 'Em poker. What the stakes might be is anyone's guess!

Man beats machine
World champion and professor of mathematics Marion Tinsley had won every tournament he had played in since 1950, when he fought Chinook in 1992. Dr. Tinsley won, four games to two with 33 draws. Chinook's two wins were only the sixth and seventh games Dr. Tinsley had lost in over 40 years. In a 1994 rematch, Tinsley had to withdraw in poor health after six draws. He died of cancer seven months later. Though Chinook beat other human opponents with ease, the unfinished battle with Dr. Tinsley raised questions over Chinook's claim to be the best draughts player of all time. Alexander Moiseyev, the current world champion, has never faced Chinook. He uses computers to analyse games but does not play against them, readily conceding that people are no longer a match for computers.

Fur your own good
Primates spend much of their time going through one another's fur to relax and cement social relationships all round. A common conception is that those who are on the receiving end benefit. But a recent study of 'Barbary apes' finds that grooming benefits the groomers even more than the groomed. Primatologists from Roehampton University in London followed a group of macaques on the Rock of Gibraltar over 2 months, recording grooming behaviour and collecting faeces to analyse the stress hormone cortisol. The animals who tended others the most had as little as half the cortisol levels as those who spent less time grooming others. And, surprisingly, there was no correlation between cortisol levels and being groomed. The study suggests that more active groomers are less stressed because they have stronger social support networks.

Planetary waves speeding up

Gigantic ocean waves, spanning hundreds of kilometres from crest to crest, are speeding up due to global warming, a new model by Canadian scientists suggests. Geophysicists at the University of Victoria, British Columbia, predict that as the ocean surface warms these so-called planetary waves will further speed up according to a model tracking changes to ocean wave patterns over the 20th and 21st centuries. Although global warming has already increased the speed of the waves, no one has noticed because satellites have not been monitoring their speeds for long enough. The model also shows that by the end of the 21st century, the waves will be a further 20 to 40 per cent faster compared with pre-industrial speeds. The faster planetary waves will in turn have an effect on global weather.

Loopy universe
While the mathematics appears to show that the universe started with a Big Bang , few cosmologists actually believe this to be the case! Now, a new mathematical model, based on the theory of "Loop Quantum Gravity," purports to show that space-time did not begin with a singularity 13.7 billion years ago. Instead, the model suggests that a universe pretty much like the one we live in today existed before, except it was contracting instead of expanding. The gravitational energy grew so large as the previous universe contracted that it ignited the current expansion, making a "Big Bounce" rather than a Big Bang. If ever proven, the idea could force a complete rethinking of the origins of the cosmos and perhaps even open a doorway to an endless future.

Treeless wonder
Planting trees, to 'off-set' carbon dioxide emissions, is seen as a way to reduce global warming. However, trees also change the earth's albedo, or its ability to reflect sunshine. American climatologist, Govindasamy Bala set off an environmental storm recently by comparing a deforested world with a standard world in a climate model that measured the global carbon cycle. A totally treeless world would be 0.3 C cooler by 2100, he claimed. Although this world would have higher carbon dioxide in the atmosphere and oceans, it would reflect more sunlight, thereby lowering the temperature. The scientist advises against deforestation to mitigate global warming, however because of "the many economic and environmental benefits of forests"!

Science Forum is written and edited by Rashida Ahmad.