Checkers game solved by computer
-
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?"