Game over: International draughts, a variant of draughts (or checkers) played on a 10 x 10 playing board. Computer scientist ran an AI enhanced program for 18 years to solve the game.
Credit: Wikipedia
SYDNEY: In a milestone for artificial intelligence, computer scientists have created the first checkers-playing computer program that cannot be beaten.
After running for 18 years – on dozens of computers equipped with state-of-the-art AI techniques – the Chinook program has 'solved' draughts (called checkers in the U.S), say researchers.
It can be played to a draw, but can never lose.
AI testbed
“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,” said Jonathan Schaeffer, lead scientist behind the project at the University of Alberta in Canada.
“With Chinook, we’ve pushed the envelope about one million times more than anything that’s been done before,” he said.
With a history dating back to 3,000 BC, draughts is an internationally popular board game, involving two players. Battled out on an 8 x 8 board, the game consists of diagonal moves of pieces. Enemy pieces are captured by jumping over them with a player's own pieces. The game has been used as testbed for research into artificial intelligence.
As detailed today in the U.S. journal Science, the University of Alberta's artificial simulation has attempted every possible move – a staggering 500 billion, billion (5x1020) positions since 1989.
The researcher's found that, if black moves first, and the opponents execute perfect play, the game ends in a draw.
“We’ve taken the knowledge used in artificial intelligence applications to the extreme, by replacing human-understandable heuristics [or approximations] with perfect knowledge,” said Schaeffer. “It’s an exciting demonstration of the possibilities that software and hardware are now capable of achieving.”
"Incredible achievement"
Software engineer Frederic Maire from the Queensland University of Technology in Australia said that Schaeffer's team has made an “incredible achievement” in a search space of 5x1020 states. “This is definitely a milestone in AI. It demonstrates again that computer-aided proofs can enable researchers to answer questions that a mathematician equipped with pen and paper would not be able to work out,” he said.
“Chinook achieved its goals employing a combination of both cutting-edge hardware and software. A [previous] 'mediocre' program could only have accomplished the same result given huge futuristic computing resources,” added computer scientist Andrew Chiou of Central Queensland University. “The bottom line is that Chinook solved it using what is currently available."
Although games with a relatively small 'search space' can be solved with computers by examining every possible set of moves from a set starting position, Schaeffer says researchers won’t yet attempt to solve chess yet as the number of possible moves is much greater.
“We have shown what leading edge artificial intelligence technology can do and on a scale more massive than has ever been done before. Perhaps the biggest contribution will be in how people build on our work and apply it to other (non-games) applications,” said Schaeffer.
Not international draughts, English checkers
The image indeed shows international draughts, but that is not what has been solved. Chinook plays English checkers only. Since international draughts is played on 50 squares instead of 32, and the complexity (very roughly) doubles with every square it will be a long time until that game is solved in the same way.
Um
I'm glad out all the rest of the things the world could be doing with this type of dedication, they choose to figure out how to make a game impossible to beat.
*sigh* Such is the whims of human existence.
Comp vs. Comp
They should pit this program against a clone of itself. It would be the draughts game of the century!
Mwhahahaha!