Checkers game solved by computer
-
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
-
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...
This goes back to the oldest question fo what defines intelligence, is intelligence simply finding the right answer (as this does when provided with every possible question and answer. Or is intelligence the process fo finding the best answer when provided with an incomplete dataset. Fro example an artificial intelligence would be able to take the information collected from expierience (previous games, not every possible game) and examine the best course of action looking ahead a modest number of moves. the decision reached would be an intelligent one, but not definitively the right one. To me thats the difference between artificial intelligence and an expert system. Expert systems always make the right decisions as long as they know the answer. A chess AI would that had practiced ona normal chess board would be able to play equally as well on an abnormal chess board (I've seen some shaped in an infinity symbol, or the trekky fall back of "3-d" chess) the priniciples would be the same for deciding, while an expert system would say "huh?"