Checkers game solved by computer
-
After 18-and-a-half years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, Dr. Jonathan Schaeffer and colleagues have built a checkers-playing computer program that cannot be beaten.[^] :cool: You can play against the unbeatable program here[^].
Tech, life, family, faith: Give me a visit. I'm currently blogging about: How could God prove Himself to humanity? The apostle Paul, modernly speaking: Epistles of Paul Judah Himango
-
To be honest, I'm unimpressed with his 'achievement'. What makes AI programming techniques useful is when they are applied to 'combinatorially explosive' problems. These are problems where the search tree for the correct solution grows too rapidly for a brute-force solution to work. Schaeffer has simply used enough compute time (e.g. applied brute force) to fully evaluate the tree for the game of checkers.
Software Zen:
delete this;Gary R. Wheeler wrote:
Schaeffer has simply used enough compute time (e.g. applied brute force) to fully evaluate the tree for the game of checkers.
I graduated recently at the University of Alberta. Had a course on AI and Dr. Schaeffer gave the class on search techniques applied to games. In his class he commented that yours is the most common critique about AI. When people see the massive search computers do to simulate intelligent behavior they say: "Oh, that's just brute force, it is not real intelligence". And they end up never accepting that computers can simulate "real" intelligence. I don't have the slightest idea of what "AI techniques" could be used to prove that Chinook can't be beaten besides massive search and I am sure you don't, too. But I am sure that, regardless of the means, Chinook simulates intelligent behavior pretty well. And this is why we call it "Artificial Intelligence".
Rui A. Rebelo I don't smoke, don't gamble, don't sniff, don't drink and don't womanize. My only defect is that I lie just a little bit, sometimes. Tim Maia (brazilian pop singer)
-
Gary R. Wheeler wrote:
Schaeffer has simply used enough compute time (e.g. applied brute force) to fully evaluate the tree for the game of checkers.
I graduated recently at the University of Alberta. Had a course on AI and Dr. Schaeffer gave the class on search techniques applied to games. In his class he commented that yours is the most common critique about AI. When people see the massive search computers do to simulate intelligent behavior they say: "Oh, that's just brute force, it is not real intelligence". And they end up never accepting that computers can simulate "real" intelligence. I don't have the slightest idea of what "AI techniques" could be used to prove that Chinook can't be beaten besides massive search and I am sure you don't, too. But I am sure that, regardless of the means, Chinook simulates intelligent behavior pretty well. And this is why we call it "Artificial Intelligence".
Rui A. Rebelo I don't smoke, don't gamble, don't sniff, don't drink and don't womanize. My only defect is that I lie just a little bit, sometimes. Tim Maia (brazilian pop singer)
Rui A. Rebelo wrote:
Chinook simulates intelligent behavior pretty well.
It's still a highly complicated state machine, not what is called intelligence, which involves strategy and so forth. Marc
-
After 18-and-a-half years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, Dr. Jonathan Schaeffer and colleagues have built a checkers-playing computer program that cannot be beaten.[^] :cool: You can play against the unbeatable program here[^].
Tech, life, family, faith: Give me a visit. I'm currently blogging about: How could God prove Himself to humanity? The apostle Paul, modernly speaking: Epistles of Paul Judah Himango
a truly significant advance in artificial intelligence and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions A huge state machine is not a significant advance nor is it intelligence. Marc
-
a truly significant advance in artificial intelligence and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions A huge state machine is not a significant advance nor is it intelligence. Marc
Marc Clifton wrote:
A huge state machine is not a significant advance nor is it intelligence.
Every Turing-based computer is a state machine. Therefore you only consider a significant advance a computer that breaks the most basic paradigm of theory of computation. It will only happen if we get quantum computing to work.
Rui A. Rebelo I don't smoke, don't gamble, don't sniff, don't drink and don't womanize. My only defect is that I lie just a little bit, sometimes. Tim Maia (brazilian pop singer)
-
It ties.
Rui A. Rebelo I don't smoke, don't gamble, don't sniff, don't drink and don't womanize. My only defect is that I lie just a little bit, sometimes. Tim Maia (brazilian pop singer)
-
Rui A. Rebelo wrote:
Chinook simulates intelligent behavior pretty well.
It's still a highly complicated state machine, not what is called intelligence, which involves strategy and so forth. Marc
I guess though that any recognizable intelligence actually does have a big database in the background. You can't operate from a state of zero knowledge and the more knowledge you have the mor intelligently you can make decisions. If you extend the checkers database to the sum of all human knowledge I'm pretty sure it would be a very intelligent machine as a result.
"I don't want more choice. I just want better things!" - Edina Monsoon
-
I guess though that any recognizable intelligence actually does have a big database in the background. You can't operate from a state of zero knowledge and the more knowledge you have the mor intelligently you can make decisions. If you extend the checkers database to the sum of all human knowledge I'm pretty sure it would be a very intelligent machine as a result.
"I don't want more choice. I just want better things!" - Edina Monsoon
Yeah, but how many times have you fully thought out more than 10 or so moves ahead when playing a game of checkers? never most likely. this program, OTOH, 'knows' what to do beforehand.
:badger:
-
Marc Clifton wrote:
A huge state machine is not a significant advance nor is it intelligence.
Every Turing-based computer is a state machine. Therefore you only consider a significant advance a computer that breaks the most basic paradigm of theory of computation. It will only happen if we get quantum computing to work.
Rui A. Rebelo I don't smoke, don't gamble, don't sniff, don't drink and don't womanize. My only defect is that I lie just a little bit, sometimes. Tim Maia (brazilian pop singer)
Rui A. Rebelo wrote:
It will only happen if we get quantum computing to work.
Last time I checked my dog and I aren't quantum computers. Why is quantum computing the only way for us to create AI?
regards, Paul Watson Ireland & South Africa
Shog9 wrote:
And with that, Paul closed his browser, sipped his herbal tea, fixed the flower in his hair, and smiled brightly at the multitude of cute, furry animals flocking around the grassy hillside where he sat coding Ruby on his Mac...
-
After 18-and-a-half years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, Dr. Jonathan Schaeffer and colleagues have built a checkers-playing computer program that cannot be beaten.[^] :cool: You can play against the unbeatable program here[^].
Tech, life, family, faith: Give me a visit. I'm currently blogging about: How could God prove Himself to humanity? The apostle Paul, modernly speaking: Epistles of Paul Judah Himango
Jeez, I read that as "500 billion billion dollars" and nearly cried for Africa. Cool stuff though. My JavaScript checkers algorithm takes half an hour to make a move, in Firefox. 15 minutes in IE. 10 minutes in Opera and ZERO TIME in Safari... :rolleyes:
regards, Paul Watson Ireland & South Africa
Shog9 wrote:
And with that, Paul closed his browser, sipped his herbal tea, fixed the flower in his hair, and smiled brightly at the multitude of cute, furry animals flocking around the grassy hillside where he sat coding Ruby on his Mac...
-
Marc Clifton wrote:
A huge state machine is not a significant advance nor is it intelligence.
Every Turing-based computer is a state machine. Therefore you only consider a significant advance a computer that breaks the most basic paradigm of theory of computation. It will only happen if we get quantum computing to work.
Rui A. Rebelo I don't smoke, don't gamble, don't sniff, don't drink and don't womanize. My only defect is that I lie just a little bit, sometimes. Tim Maia (brazilian pop singer)
Quantum computers have different basic operations that allow some algorithms to run faster; but it can be simulated by a Turing machine (with exponential time overhead), so every quantum computer still is a state machine.
-
To be honest, I'm unimpressed with his 'achievement'. What makes AI programming techniques useful is when they are applied to 'combinatorially explosive' problems. These are problems where the search tree for the correct solution grows too rapidly for a brute-force solution to work. Schaeffer has simply used enough compute time (e.g. applied brute force) to fully evaluate the tree for the game of checkers.
Software Zen:
delete this;Checkers is EXP-TIME complete (source[^]); that means it is proven that an provably optimal playing program CANNOT run in polynomial time. He definitely didn't "fully evaluate the tree" (as in: using the trivial brute force solution), that would calculate positions that can be reached on multiple ways many times, dramatically increasing the required time. At least he used the "clever brute force" solution that uses a huge database to store the positions it already visited. The article says there are 5*10^20 positions (currently I'm too lazy to calculate that myself, so I'm going to believe the article). Say the program takes only 20 CPU cycles per position. On a 3 GHz CPU, that allows him to evaluate 161061273 positions per second. Multiply that with the 200 computers he used (the article says 50 on average, 200 at peak times), 60 seconds per minute, 60 minutes per hour, 24 hours per day, 365 days per years. In one year, you evaluate 1015845661065600000 = 1,0158 * 10^18 positions. For 5*10^20 positions, the computation takes 492 years. And I don't think 3 GHz CPUs were available when he started. So he definitely didn't try all positions, but used a more clever solution. Side note: the database (storing if white wins for each position) would take 5*10^20 bits = 56843418 TB memory.
-
a truly significant advance in artificial intelligence and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions A huge state machine is not a significant advance nor is it intelligence. Marc
I've said it befor and I'll say it again... Where did I leave my quantum laptop?
When prediction serves as polemic, it nearly always fails. Our prefrontal lobes can probe the future only when they aren’t leashed by dogma. The worst enemy of agile anticipation is our human propensity for comfy self-delusion. David Brin Buddha Dave
-
Yeah, but how many times have you fully thought out more than 10 or so moves ahead when playing a game of checkers? never most likely. this program, OTOH, 'knows' what to do beforehand.
:badger:
FWIW the same guy started with a purely heuristic approach & the machine won a world chequers tournament back in 1994. He was dissatisfied with the fact that it could be beaten & subsequently pursued this 'brute-force' approach instead, but way back in '94 demonstrated a working, winning AI which probably fits some of your definition's of machine intelligence a bit better...
-
Number of players: 0 It plays every variation of the game it can compute, tying each time, then launches the Global Thermonuclear War game and plays that through every possible scenario until it finally learns that the only way to win, is not to play. Then it asks to play a nice game of chess. Oh wait, that's a cheesy Matthew Broderick movie! G
-
Gary R. Wheeler wrote:
Schaeffer has simply used enough compute time (e.g. applied brute force) to fully evaluate the tree for the game of checkers.
I graduated recently at the University of Alberta. Had a course on AI and Dr. Schaeffer gave the class on search techniques applied to games. In his class he commented that yours is the most common critique about AI. When people see the massive search computers do to simulate intelligent behavior they say: "Oh, that's just brute force, it is not real intelligence". And they end up never accepting that computers can simulate "real" intelligence. I don't have the slightest idea of what "AI techniques" could be used to prove that Chinook can't be beaten besides massive search and I am sure you don't, too. But I am sure that, regardless of the means, Chinook simulates intelligent behavior pretty well. And this is why we call it "Artificial Intelligence".
Rui A. Rebelo I don't smoke, don't gamble, don't sniff, don't drink and don't womanize. My only defect is that I lie just a little bit, sometimes. Tim Maia (brazilian pop singer)
My point was, by fully enumerating the problem space, the heuristic is no longer necessary. It's simply a tree traversal at that point, which doesn't fit my definition of an AI solution to the problem. If he did not completely enumerate the problem space, then I doubt that Schaeffer's player is provably unbeatable. His project is of interest mainly in pointing out that there are sufficient computing cycles available now to treat some problems this way. Instead of tweaking a heuristic, or an inference engine, or a neural network over time through trial and error, simply throw massive amounts of computer time and/or storage at it to compute all the possible solutions. Render the solution space in an efficient manner, and add a relatively simple application to use the solution.
Software Zen:
delete this; -
Rui A. Rebelo wrote:
Chinook simulates intelligent behavior pretty well.
It's still a highly complicated state machine, not what is called intelligence, which involves strategy and so forth. Marc
Strategy is a Human concept, which describes a way to approach a problem. A State Machine is also a human concept, ii is a tool for describing a problem in a more humanly understandable way. In absurdum, every computer program ever written and to be written can also be described as a state machine. The main breakthrough was that the game solution was described at all, and that a non-trivial question was answered: Does the None Loosing formula involve an infinite number of moves. Now we know for the first time since the invention of the game that the number of 'perfect' moves is finite.
LateNightsInNewry
-
Rui A. Rebelo wrote:
Chinook simulates intelligent behavior pretty well.
It's still a highly complicated state machine, not what is called intelligence, which involves strategy and so forth. Marc
What's the difference?
LateNightsInNewry