Computers Solve Checkers ... very interesting

[pokerzen]

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.

[GodlikeRoy]

Connect 4 has also been solved!

[emmasdad]

Tic-tac-toe anyone?

[GodlikeRoy]

LOL @ ED.

Tic-tac-toe will never be solved.

[stickdude]

When they've solved Go, let me know.

[pokerzen]

[Xaston]

[NorthView]

[Pok 7's]

[antneye]

[GodlikeRoy]

[Zmej]

[pokerzen]

[pokerzen]

[redhouse]

HU LHE is halfway solved. It should be done in another 3-5 years.