www.canada.com/topics/tec.../story.html
Published: Friday, July 20, 2007
EDMONTON - A team of scientists at the University of Alberta has reached a milestone in artificial intelligence by using computers to "solve" the game of checkers.
The feat essentially means the team's checkers-playing program, Chinook, can never be beaten at the game. It can only be tied - and only when its opponent plays a perfect game.
To date, checkers is the largest, non-trivial game of skill to be solved. It is more than a million times more complex that the previous AI standard, Connect Four.
"This is not a small leap. This is not something that anyone is going to duplicate tomorrow," said team leader Jonathan Schaeffer.
Schaeffer began working on the checkers project more than 18 years ago, in 1989. By the mid-1990s, Chinook was sophisticated enough to consistently beat the top human players in the world.
But Schaeffer pressed on, working to get the program to the point where it could never be defeated.
To solve the game, the team had to sift through an astronomical number of checkers positions and analyse the best way to move the pieces. Almost continuously since 1989, dozens of computers have been working on the problem, constantly updating Chinook's database with more and more positions.
The total number of potential positions in the game is about 500 billion billion.
To put that in perspective, "let's say the surface of the Earth is represented by that number," Schaeffer said.
"Then take a square inch and break it into 1,000 pieces, take one of those pieces and that's one checker position. Your foot would represent maybe a million positions, so the question then is, how long would it take you to cover the entire surface of the Earth in footprints?"
The team's research is set to be published in the academic journal Science.
www.canada.com/topics/tec.../story.html
Published: Friday, July 20, 2007
EDMONTON - A team of scientists at the University of Alberta has reached a milestone in artificial intelligence by using computers to "solve" the game of checkers.
The feat essentially means the team's checkers-playing program, Chinook, can never be beaten at the game. It can only be tied - and only when its opponent plays a perfect game.
To date, checkers is the largest, non-trivial game of skill to be solved. It is more than a million times more complex that the previous AI standard, Connect Four.
"This is not a small leap. This is not something that anyone is going to duplicate tomorrow," said team leader Jonathan Schaeffer.
Schaeffer began working on the checkers project more than 18 years ago, in 1989. By the mid-1990s, Chinook was sophisticated enough to consistently beat the top human players in the world.
But Schaeffer pressed on, working to get the program to the point where it could never be defeated.
To solve the game, the team had to sift through an astronomical number of checkers positions and analyse the best way to move the pieces. Almost continuously since 1989, dozens of computers have been working on the problem, constantly updating Chinook's database with more and more positions.
The total number of potential positions in the game is about 500 billion billion.
To put that in perspective, "let's say the surface of the Earth is represented by that number," Schaeffer said.
"Then take a square inch and break it into 1,000 pieces, take one of those pieces and that's one checker position. Your foot would represent maybe a million positions, so the question then is, how long would it take you to cover the entire surface of the Earth in footprints?"
The team's research is set to be published in the academic journal Science.
www.canada.com/topics/tec.../story.html
posted by:
|
Nevada
|
-
Re: Canadian scientists crack Checkers code
Wed, November 28, 2007 - 7:42 AMsweet, too bad computers still suck at Go. ~; )
Also, perhaps I am reading this wrong, but doesn't this mean that they've only solved the game because they have explored all of the 500 billion billion positions? That sounds more like computational brute force rather than learning the ideal strategy. Now, if they could reduce that massive database to a series of algorithms which would always produce the same results, seemingly that would imply a greater level of understanding: synthesis and reduction of large data into usable 'thought' patterns. -
-
Real "AI" is not so easy
Sun, December 23, 2007 - 10:16 PMI agree with you.
And this post reminds me of this news:
Creating a better Go Program (an article by IEEE)
Cracking GO By Feng - Hsiung Hsu
First Published October 2007 < www.spectrum.ieee.org/oct07/5552 >
Brute-force computation has eclipsed humans in chess, and it could soon do the same in this ancient Asian game
In 1957, Herbert A. Simon, a pioneer in artificial intelligence and later a Nobel Laureate in economics, predicted that in 10 years a computer would surpass humans in what was then regarded as the premier battleground of wits: the game of chess. Though the project took four times as long as he expected, in 1997 my colleagues and I at IBM fielded a computer called Deep Blue that defeated Garry Kasparov, the highest-rated chess player ever.
You might have thought that we had finally put the question to rest—but no. Many people argued that we had tailored our methods to solve just this one, narrowly defined problem, and that it could never handle the manifold tasks that serve as better touchstones for human intelligence. These critics pointed to weiqi, an ancient Chinese board game, better known in the West by the Japanese name of Go, whose combinatorial complexity was many orders of magnitude greater than that of chess. Noting that the best Go programs could not even handle the typical novice, they predicted that none would ever trouble the very best players.
Ten years later, the best Go programs still can't beat good human players. Nevertheless, I believe that a world-champion-level Go machine can be built within 10 years, based on the same method of intensive analysis—brute force, basically—that Deep Blue employed for chess. I've got more than a small personal stake in this quest. At my lab at Microsoft Research Asia, in Beijing, I am organizing a graduate student project to design the hardware and software elements that will test the ideas outlined here. If they prove out, then the way will be clear for a full-scale project to dethrone the best human players... (full story at the above website)
-
