[AI] Computers crack famous board game

Vikas Kapoor dl.vikas at gmail.com
Mon Jul 23 10:07:03 EDT 2007

      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, Canada, 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, 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. 
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

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.


Vikas Kapoor,
MSN Id:dl_vikas at hotmail.com, Yahoo+Skype Id: dl_vikas,
Mobile: (+91) 9891098137.

More information about the AccessIndia mailing list