Computers crack famous board game
Game of draughts (Eyewire)
Draughts has about 500 billion billion potential positions
It could be a case of game over for draughts - scientists say the ancient board game has finally been solved.

A Canadian team has created a computer program that can win or draw any game, no matter who the opponent is.

It took an average of 50 computers nearly two decades to sift through the 500 billion billion possible draughts positions to come up with the solution.

Writing in the journal Science, the team said it was the most challenging game solved to date.

Jonathan Schaeffer, lead author on the paper and chair of the department of computer science at the University of Alberta, told the BBC News website: "This was a huge computational problem to solve - more than a million times bigger than anything that had ever been solved before."

Trial and error

Professor Schaeffer, who admits he is "awful" at draughts (also known as checkers), began his attempts to solve the board game in 1989.

He consulted champion players to find out more about their game tactics and then fed this information into a computer program called Chinook.


I think we've raised the bar - and raised it quite a bit - in terms of what can be achieved in computer technology and artificial intelligence
Professor Schaeffer

Chinook looked at solving problems much like a human does by using trial and error to find out what appeared to be the best solutions. This is called a heuristic approach.

However, Professor Schaeffer said that although the program was extremely successful - it won the World Checkers Championship in 1994 - it was not perfect and occasionally lost games.

So the computer scientists tried another non-heuristic tack, where, over a number of years, hundreds of computers ran through game upon game of draughts to work out the sequences that would lead to winning, losing and drawing.

Eventually, the new program gathered so much information that it "knew" the best move to play in every situation. This meant that every game it played led to a certain win, or, if its opponent played perfectly, a draw.

Chess pieces
Chess may prove more tricky to solve

Professor Schaeffer said: "I think we've raised the bar - and raised it quite a bit - in terms of what can be achieved in computer technology and artificial intelligence."

With the vast number of playing possibilities, draughts is the most complex game to have been solved to date - it was about a million times more complicated to solve than Connect Four.

Researchers are now hoping to move on to even bigger problems, however it seems that grand master of the board games - chess - may remain unsolved for some time.

It has somewhere in the range of a billion billion billion billion billion possible positions, meaning that computers, with their current capacity, would takes aeons to solve it.

I can still beat Chess on my Apple on hardest difficulty with good consistancy sometimes 2 or three in a row.

I'm somewhat proud of myself for it.

Would not it have been more productive to spend that brain power and computer time on something slightly more rewarding like curing cancer?

I was thinking something along the same lines.

__________________
It is a truism that almost any sect, cult, or religion will legislate its creed into law if it acquires the political power to do so. Robert A. Heinlein


09 Jetta TDI
1985 300D