Tuesday, August 21, 2007

Draughts has been solved



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.

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, for which, 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.

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.

Originally cited by BBC. I beat Ben and Jerry's checkers all the time! There is a better place to play and that is Chinook the mighty and unbeatable checkers engine!

In the chess world Kasparov has been known to think 3 moves per second, computers can now think over two hundred thousand moves per second! staggering to say the least.

3 comments:

Anonymous said...

Who is Ben & Jerry?

Steven Nicholls said...

You have never eaten the BEST ice cream in the world, so it seems! Google Ben and Jerry ice cream!

Sreven said...

Try Chinook itself you will not beat it!
http://www.cs.ualberta.ca/~chinook/play/
Steven