The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel.
Also, next pandemic, let's approve the vaccines faster!
This entry was posted
on Friday, July 20th, 2007 at 10:09 am and is filed under Nerd Interest, Procrastination.
You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.
I couldn’t see if is 8×8 or 10×10, but … uh… “guess” is 8×8. And I don’t know if the rules are yahoo games’ or the rules I play in Brazil… I “guess” they are not. I wonder if they are harder or easier.
The quote “From my point of view, thank God it’s over,” almost made me feel bad for thinking “but how about general m x n boards?” when I started reading the article.
I think it still relies on very large computation power, though their chess-playing algorithm has been improved. It is still far different from human intelligence.
I think it still relies on very large computation power, though their chess-playing algorithm has been improved. It is still far different from human intelligence.
Amir – read the articles. The code and proofs are freely available. In its very basics the proof is kind of like what happened with the 4 color conjecture. A whole bunch of special cases were found to cover the entire search tree for the game. 10^14 of them I guess. They then crunched through them for 18 years. What kind of confidence should you give this? As much as you give a somewhat hard standard proof I would guess.
It is an achievement because we now know something we didn’t know before about a game millions have played. How big an achievement is up to the reader.
It sounds like the compression and searching of compressed tree techniques might be useful in other situations.
What I found amazing is that their analysis of the “greatest Checker Player ever”, Marion Tinsley, showed that he had only a double handful of “mistaken” moves in the 10’s of thousands of moves they had on file for him. That is almost unbelievable. He must have played hundreds of literally perfect games.
I wonder if AI researchers will now initiate a massive automated search for (simple) heuristics based on perfect play in Checkers. Such heuristics might be useful for other games/problems.
Yeah, when I was a grad student in 1994, I think, I went up the hill to an MSRI conference on combinatorial games. Someone from Chinook gave a talk, and while what he said about program was interesting, the most interesting part was what he said about Marion Tinsley. I’ve had a fascination (usually dormant) with him ever since.
How would you rank moves with knowledge of perfect play?
You might want to do this to test a human player’s ability earlier in the game so that you can decide whether to make risky moves later on that could result in a win rather than a draw.
I guess what I’d be curious about is, what proportion of the endpoints of the “perfect game” tree end in wins and what proportion end in draws? If you consider all possible games which could be played by opponents, I mean.
Schaeffer wrote a pretty entertaining nontechnical book on this subject a few years ago. The material in it about Tinsley was indeed very interesting (as well as anecdotes about other pro players; I believe there was one who tried to cheat against the computer).
” I have been asked many times when chess will be solved and I refuse to say anything other than it can’t be done for a very long time unless there is a fundamentally new breakthrough. The computing models that we have today — even if they are a billion times faster — won’t make a dent in chess. We need something *much* better. The answer might be quantum computing, but this technology is still in its infancy and remains unproven.”
Bram: Well, we know now that quantum computers give you a generic square-root speedup for games of alternation, thanks to the recent breakthrough of Farhi, Goldstone, and Gutmann. But we have no evidence that they give anything better than that in specific cases like chess.
(1) Checkers. My grandfather Alfred Vos was New Jersey State Checkers Champion (I’m not sure which years); it took me ages to learn the tactic called “winkling” from him.
(2) Checkers again. As I submitted to the Prime Curios web site, which will have the copyright:
“500995484682338672639
The total number of positions in all possible Checkers games has a smallest prime factor of 19, which curiously is the number of rows or columns in the more
complex board game Go.”
(3) Perfect game. That has an official definition in Major League Baseball. In Chess, however, I stated a theorem, and gave examples, early in my CS grad student days at UMass/Amherst, 1973-1977. I showed it to our resident International Master, Danny Kopec, who then went to be Chess Advisor to the AI programme at University of Edinburgh. SIGART had the Edinburgh professor (was he the same one who died this month in a car crash?) publish an article which failed to cite me as the original author of the theorem. Roughly speaking (I don’t have the notes in front of me):
If in a Chess game, you KNOW that your opponent is NOT a perfect player (i.e. makes at least one mistake per game), then there exist positions where your move yielding the greatest probability of your win is NOT the same as your optimal move (i.e. the move you would make against an opponent that you know to be a perfect player).
I gave examples (horizon effect was shown in SIGART) and classified situations with 1 error per game players, 2 errors per game players, and suggested a generalization with distributions.
Yes, it ws he who died a week ago: “Professor Donald Michie, 84, and his ex-wife, Dame Anne McLaren, 80, were in a car which left the motorway as they travelled from Cambridge to London. Prof Michie was a researcher in artificial intelligence who worked as part of the British code-breaking group at Bletchley Park during World War II.”
I am not accusing the late prof. Michie of plagiarism; it was probably accidental on his part, because perhaps Danny Kopec did not have the right contact information for me. At the time, I was writing the world’s first PhD dissertation on Nanotechnology and Artificial Life, neither of which fields were yet named.
I was calculating the channel capacity of metabolisms, which required me to solve perturbations in the Michaelis-Menten equations in Laplace transform space, and imprssed Marvin Minsky with my use of the Krohn-Rhodes semigroup decomposition theorem. The issue of complexity of dynamics of metabolisms is still open, but my solutions in the neighborhood of steady-state are stil the key, and have been publsihed several times in refereed venues.
That PhD dissertation is still listed as “incomplete” on my transcript, having never been either accepted nor rejected. Perhaps, Scott, you might give me a chance to speak about this at MIT after you’ve gotten established in the faculty. I did speak with Marvin Minsky most recently in June 2006 at the 6th International Conference on Complex Systems. He has given me good career advice since 1973. At ICCS-2006, I introduced him to someone expert in Japanese and said that he’d received the Emperor’s Prize. Marvin said: “More than that: I bought lunch for the Emperor!”
Scott, in that post you say that an exponent of 0.753 is optimal for the classical case (I assume that’s plain old alpha-beta pruning?) and that 0.5 is the best known for the quantum case. Shouldn’t we expect an exponent of 0.753 / 2 for it to be a true square root speed-up?
Bram: The 0.753 is only for games with branching factor of 2 (which don’t tend to be played a lot 🙂 ). As the branching factor increases, the classical exponent asymptotically approaches 1 while the quantum exponent remains 1/2. And for classical deterministic (as opposed to randomized) algorithms, the exponent is always 1.
Winkle. Based on the zoological “periwinkle” ( small, snail-like, marine molluscs, Littorina littorea), and the process of digging the small edible shellfish meat out of the shell with an appropriate tool, we get the transitive verb, winkle,: to pry, extract, or force from a place or position. Often used with out. chiefly British, as well as the derivations for winkled, winkling, winkles.
The verb winkle has 3 meanings:
Meaning #1: emit or reflect light in a flickering manner; of stars
(Synonyms: twinkle, scintillate);
Meaning #2: gleam or glow intermittently
(Synonyms: flash, blink, wink, twinkle)
Meaning #3: remove or displace from a position.
It is #3 that applies to the board game of checkers (a.k.a. darughts).
I’ve got three kings. You, poor bastard, have only two. You run each of them to a corner where you can shuttle back and forth between two diagonally connected squares.
I head into one corner and play a little parity game with you, as your king can only move back and forth with period 2, and I have more degrees of freedom.
Eventually, I can time it so that you get jumped, or unable to move, no matter what you do. Then I go and pry your final king out of its corner. You are doomed.
It is easy to handwave like this, a little more subtle to express algorithmically. My grandfather had to show me over and over. Anyone who knows the game well can show you. I have no book on hand to explain better.
My good friend jeremy Colton, back at PsS.#9 (Robert Fulton Elemntary School) had a father Sam Colton who owned and ran a spectacular used book store on Montague Street for a long time, which was a vast repository of ancient wisdom, and regular customers of eccentric intelligence and erudition. Sam was Philadelphia city wide checkers champion when he was 12 (1919).
In a sense, it’s a pity that the game is “proved.” But if someday Chess is proved, will people stop playing Chess?
Put it another way: cars drive faster than people can run. Have we stopped running?
Computers can do arithmetic many orders of magnitude faster than people. have we given up on Math?
Darn. I had hoped that my son would have finished Harry Potter 7 by now. Then my wife has to finish it, atsrtaing after the 100 pages she read while our son was asleep. I kind of wnat resolution before I have to go back to teaching Algebra 1 to frustrated teenagers.
“Why are you not looking at me when I speak at the whiteboard? I’m your teacher, not the guy behind you? I took a huge oay cut to be here. You need me to graduate.”
“Because, Professor Post, you goota keep an eye behind you in the ‘hood.”
If David Deutsch writes: “… my method of urging you to read the book [I Am a Strange Loop] will itself be paradoxical: I shall summarize why I find it ultimately unconvincing,” then are we helping or hurting the paradox by urging people to read his review? Will more people read the Douglas Hofstadter’s book if an even number of us refer to David Deutsch’s review, or an odd number? Please don’t refer to my comment on the review. I’m certainly not going to.
Most people overgeneralize from a single example. I surely do.
I saw an article on this a couple of days ago, and it’s not clear to me that checkers really is solved. They hedge it by saying something about being restricted to positions that usually arise in play.
“Solving” checkers or any other game with a large but finite number of positions or moves is a predictable result of increased computing power. I don’t think I’ll be at all surprised years from now when we see the headlines “Chess has been solved” and “Go has been solved.”
Poker is far more interesting from an AI perspective since it requires the program to adapt strategy to its opponent while varying its play to preclude an opponent from successfully adapting to it. There is also no possibility of “solving” the game since the outcome could vary even when dealing with the same opponents and cards.
I look forward to the world’s first combination poker tournament & Turing test, and I hope they plan to serve free drinks.
What’s your perspective Scott on the claims/hope that great advances in AI will help computers play GO better?
I have been thinking about what that would mean in complexity-theoretic terms. It is known of course that determining the winner of a arbitary GO position is hard. (In fact, very hard, harder than NP.) Is the hope that GO is easier on average than in the worst case? That you don’t need to evaluate positions to choose a move?
Johan: My understanding is that the problems of finding solutions to Checkers, Chess AND Go are all three in the same complexity class (wikipedia says that this is EXPTIME, but that in the case of Go this may depend on the Ko rule you choose to adopt).
In practical terms solving these games can offer different degrees of difficulty (i.e. since practical terms usually mean using a standard, finite-sized board); but in complexity-theoretic (asymptotic) terms there’s not really a difference there, since here we don’t really care about the structure of the decision tree, just the bounds on its size.
Go is far, far harder to solve via the standard search techniques used for Chess and Checkers, since it has a far higher branching factor. I think that saying “different degrees of difficulty” is an understatement since chess programs operate at the grandmaster level while Go programs operate at the weak AI level.
Also, this might be slightly off topic, but I’ve always had the opinion that AI is a field where complexity theory isn’t really very important, since essentially all interesting problems scale exponentially in the worst case. I think AI is more about finding pragmatic algorithms that can offer decent performance in the average case.
Scott said, “Bram: The 0.753 is only for games with branching factor of 2 (which don’t tend to be played a lot ). As the branching factor increases, the classical exponent asymptotically approaches 1 while the quantum exponent remains 1/2. And for classical deterministic (as opposed to randomized) algorithms, the exponent is always 1.”
Hmm, that seems odd. Is the optimal classical algorithm for other branching factors the same (evaluate one random subtree and then others until you can stop)?
Is the optimal classical algorithm for other branching factors the same (evaluate one random subtree and then others until you can stop)?
Great question! If all the branching factors are the same, then I think Saks-Wigderson analysis gives an affirmative answer (someone correct me if I’m wrong). If the branching factor can differ from one vertex to another, then I’d still conjecture the answer is yes, but it’s not known in general.
This week’s “Science News Weekly” had an article on the Checkers solution. Although this was the rare SNW that had an actual equation (fibonacci and lucas numbers recursion formula), little detail was provided.
SNW discussed how they worked on the problem from both ends. First, on the back end, they crunched all boards with n checkers, starting with n = 2 and making it to n = 10 in a decade or so. The work per board scaled as 10^n. This info was stored in a condensed form. Next they played openings, taking all branches until the game got to n = 10, and then looked up the solution. I am guessing some pruning was involved.
Here is what caught my attention: SNW stated that a condensed storage scheme was used that stored the n
This continues a comment about the report in Science News Weekly that was somehow cut short:
Here is what caught my attention:
SNW stated that a condensed storage scheme was used that stored the n
One more try. It appears that a “C-language less than or equal sign” cuts off messages in the “Leave a Reply” box.
Anyway, the SNW report stated that the n = 10 (and less) end game outcomes were stored in some unspecified data structure with an “average of 154 positions per byte”. Rather impressive. Does anyone have a guess how they could do that? The SNW report is at http://www.sciencenews.org/articles/20070721/fob4.asp
AFAIK Chinook endgame data uses fairly standard techniques in combination with domain dependent knowledge. They utilize symmetries and every unique position gets an index where the game value is stored. Capture and capture threat positions get special treatment to reduce. Then a version of run length encoding does the compression.
I couldn’t understand some parts of this article Checkers solved, but I guess I just need to check some more resources regarding this, because it sounds interesting.
“Babbage, in speaking of his analytical engine, has suggested that a machine might be made that would play a game of combination, such as draughts, provided the maker of the machine himself would work out perfectly the sequences of the game. Professor Fairman Rogers finds that the sequences of tit-tac-toe are easily tabulated, and hence an automaton may be made that will play the game as follows: The opponent to the automaton makes the first move in the game and in so doing causes a certain cylinder to change its position. This causes the automaton to make that play which the proper sequence of the game requires. The next play of the opponent moves another cylinder, and so on throughout the sequence. If the player plays perfectly, the game will be drawn; if the opponent makes a mistake, the automaton will take advantage of it and win the game.”
Follow
Comment #1 July 20th, 2007 at 12:55 pm
I couldn’t see if is 8×8 or 10×10, but … uh… “guess” is 8×8. And I don’t know if the rules are yahoo games’ or the rules I play in Brazil… I “guess” they are not. I wonder if they are harder or easier.
Comment #2 July 20th, 2007 at 1:40 pm
Standard checkers is 8×8.
Comment #3 July 20th, 2007 at 3:12 pm
The quote “From my point of view, thank God it’s over,” almost made me feel bad for thinking “but how about general m x n boards?” when I started reading the article.
Comment #4 July 20th, 2007 at 3:47 pm
So how do we know that Checkers is really solved? What sorts of assurances are given that the code used is correct?
Also, in what sense is this an achievement? Are the clever algorithms used applicable to other domains?
Comment #5 July 20th, 2007 at 4:01 pm
I think it still relies on very large computation power, though their chess-playing algorithm has been improved. It is still far different from human intelligence.
Comment #6 July 20th, 2007 at 4:07 pm
I think it still relies on very large computation power, though their chess-playing algorithm has been improved. It is still far different from human intelligence.
Sorry, I used a wrong pseudonym. 🙂
Comment #7 July 20th, 2007 at 4:10 pm
Amir – read the articles. The code and proofs are freely available. In its very basics the proof is kind of like what happened with the 4 color conjecture. A whole bunch of special cases were found to cover the entire search tree for the game. 10^14 of them I guess. They then crunched through them for 18 years. What kind of confidence should you give this? As much as you give a somewhat hard standard proof I would guess.
It is an achievement because we now know something we didn’t know before about a game millions have played. How big an achievement is up to the reader.
It sounds like the compression and searching of compressed tree techniques might be useful in other situations.
What I found amazing is that their analysis of the “greatest Checker Player ever”, Marion Tinsley, showed that he had only a double handful of “mistaken” moves in the 10’s of thousands of moves they had on file for him. That is almost unbelievable. He must have played hundreds of literally perfect games.
Comment #8 July 20th, 2007 at 4:24 pm
I wonder if AI researchers will now initiate a massive automated search for (simple) heuristics based on perfect play in Checkers. Such heuristics might be useful for other games/problems.
Comment #9 July 20th, 2007 at 4:26 pm
Yeah, when I was a grad student in 1994, I think, I went up the hill to an MSRI conference on combinatorial games. Someone from Chinook gave a talk, and while what he said about program was interesting, the most interesting part was what he said about Marion Tinsley. I’ve had a fascination (usually dormant) with him ever since.
Comment #10 July 20th, 2007 at 4:37 pm
How would you rank moves with knowledge of perfect play?
You might want to do this to test a human player’s ability earlier in the game so that you can decide whether to make risky moves later on that could result in a win rather than a draw.
Comment #11 July 20th, 2007 at 5:22 pm
I guess what I’d be curious about is, what proportion of the endpoints of the “perfect game” tree end in wins and what proportion end in draws? If you consider all possible games which could be played by opponents, I mean.
Comment #12 July 20th, 2007 at 8:22 pm
Schaeffer wrote a pretty entertaining nontechnical book on this subject a few years ago. The material in it about Tinsley was indeed very interesting (as well as anecdotes about other pro players; I believe there was one who tried to cheat against the computer).
Comment #13 July 21st, 2007 at 2:18 am
Scott, what do you think about professor Schaeffer’s comments about quantum computation?
http://www.chessninja.com/dailydirt/2007/07/checkered_past.htm
” I have been asked many times when chess will be solved and I refuse to say anything other than it can’t be done for a very long time unless there is a fundamentally new breakthrough. The computing models that we have today — even if they are a billion times faster — won’t make a dent in chess. We need something *much* better. The answer might be quantum computing, but this technology is still in its infancy and remains unproven.”
Comment #14 July 21st, 2007 at 2:35 am
Bram: Well, we know now that quantum computers give you a generic square-root speedup for games of alternation, thanks to the recent breakthrough of Farhi, Goldstone, and Gutmann. But we have no evidence that they give anything better than that in specific cases like chess.
Comment #15 July 21st, 2007 at 8:46 am
(1) Checkers. My grandfather Alfred Vos was New Jersey State Checkers Champion (I’m not sure which years); it took me ages to learn the tactic called “winkling” from him.
(2) Checkers again. As I submitted to the Prime Curios web site, which will have the copyright:
“500995484682338672639
The total number of positions in all possible Checkers games has a smallest prime factor of 19, which curiously is the number of rows or columns in the more
complex board game Go.”
(3) Perfect game. That has an official definition in Major League Baseball. In Chess, however, I stated a theorem, and gave examples, early in my CS grad student days at UMass/Amherst, 1973-1977. I showed it to our resident International Master, Danny Kopec, who then went to be Chess Advisor to the AI programme at University of Edinburgh. SIGART had the Edinburgh professor (was he the same one who died this month in a car crash?) publish an article which failed to cite me as the original author of the theorem. Roughly speaking (I don’t have the notes in front of me):
If in a Chess game, you KNOW that your opponent is NOT a perfect player (i.e. makes at least one mistake per game), then there exist positions where your move yielding the greatest probability of your win is NOT the same as your optimal move (i.e. the move you would make against an opponent that you know to be a perfect player).
I gave examples (horizon effect was shown in SIGART) and classified situations with 1 error per game players, 2 errors per game players, and suggested a generalization with distributions.
Yes, it ws he who died a week ago: “Professor Donald Michie, 84, and his ex-wife, Dame Anne McLaren, 80, were in a car which left the motorway as they travelled from Cambridge to London. Prof Michie was a researcher in artificial intelligence who worked as part of the British code-breaking group at Bletchley Park during World War II.”
I am not accusing the late prof. Michie of plagiarism; it was probably accidental on his part, because perhaps Danny Kopec did not have the right contact information for me. At the time, I was writing the world’s first PhD dissertation on Nanotechnology and Artificial Life, neither of which fields were yet named.
I was calculating the channel capacity of metabolisms, which required me to solve perturbations in the Michaelis-Menten equations in Laplace transform space, and imprssed Marvin Minsky with my use of the Krohn-Rhodes semigroup decomposition theorem. The issue of complexity of dynamics of metabolisms is still open, but my solutions in the neighborhood of steady-state are stil the key, and have been publsihed several times in refereed venues.
That PhD dissertation is still listed as “incomplete” on my transcript, having never been either accepted nor rejected. Perhaps, Scott, you might give me a chance to speak about this at MIT after you’ve gotten established in the faculty. I did speak with Marvin Minsky most recently in June 2006 at the 6th International Conference on Complex Systems. He has given me good career advice since 1973. At ICCS-2006, I introduced him to someone expert in Japanese and said that he’d received the Emperor’s Prize. Marvin said: “More than that: I bought lunch for the Emperor!”
Comment #16 July 21st, 2007 at 9:01 am
Scott, in that post you say that an exponent of 0.753 is optimal for the classical case (I assume that’s plain old alpha-beta pruning?) and that 0.5 is the best known for the quantum case. Shouldn’t we expect an exponent of 0.753 / 2 for it to be a true square root speed-up?
Comment #17 July 21st, 2007 at 10:01 am
Bram: The 0.753 is only for games with branching factor of 2 (which don’t tend to be played a lot 🙂 ). As the branching factor increases, the classical exponent asymptotically approaches 1 while the quantum exponent remains 1/2. And for classical deterministic (as opposed to randomized) algorithms, the exponent is always 1.
Comment #18 July 21st, 2007 at 12:00 pm
“winkling” ?
Mister Jonathan Vos Post… is there any place where I can read about that?
Comment #19 July 21st, 2007 at 6:54 pm
Off-topic, but FYI: David Deutsch’s review of Douglas Hofstadter’s I Am a Strange Loop.
Comment #20 July 21st, 2007 at 10:04 pm
Winkle. Based on the zoological “periwinkle” ( small, snail-like, marine molluscs, Littorina littorea), and the process of digging the small edible shellfish meat out of the shell with an appropriate tool, we get the transitive verb, winkle,: to pry, extract, or force from a place or position. Often used with out. chiefly British, as well as the derivations for winkled, winkling, winkles.
The verb winkle has 3 meanings:
Meaning #1: emit or reflect light in a flickering manner; of stars
(Synonyms: twinkle, scintillate);
Meaning #2: gleam or glow intermittently
(Synonyms: flash, blink, wink, twinkle)
Meaning #3: remove or displace from a position.
It is #3 that applies to the board game of checkers (a.k.a. darughts).
I’ve got three kings. You, poor bastard, have only two. You run each of them to a corner where you can shuttle back and forth between two diagonally connected squares.
I head into one corner and play a little parity game with you, as your king can only move back and forth with period 2, and I have more degrees of freedom.
Eventually, I can time it so that you get jumped, or unable to move, no matter what you do. Then I go and pry your final king out of its corner. You are doomed.
It is easy to handwave like this, a little more subtle to express algorithmically. My grandfather had to show me over and over. Anyone who knows the game well can show you. I have no book on hand to explain better.
My good friend jeremy Colton, back at PsS.#9 (Robert Fulton Elemntary School) had a father Sam Colton who owned and ran a spectacular used book store on Montague Street for a long time, which was a vast repository of ancient wisdom, and regular customers of eccentric intelligence and erudition. Sam was Philadelphia city wide checkers champion when he was 12 (1919).
In a sense, it’s a pity that the game is “proved.” But if someday Chess is proved, will people stop playing Chess?
Put it another way: cars drive faster than people can run. Have we stopped running?
Computers can do arithmetic many orders of magnitude faster than people. have we given up on Math?
Darn. I had hoped that my son would have finished Harry Potter 7 by now. Then my wife has to finish it, atsrtaing after the 100 pages she read while our son was asleep. I kind of wnat resolution before I have to go back to teaching Algebra 1 to frustrated teenagers.
“Why are you not looking at me when I speak at the whiteboard? I’m your teacher, not the guy behind you? I took a huge oay cut to be here. You need me to graduate.”
“Because, Professor Post, you goota keep an eye behind you in the ‘hood.”
“But this is not the hood. This is my classroom.”
*sigh*
Comment #21 July 21st, 2007 at 10:07 pm
Draughts. P.S. #8. Pay cut. Gotta.
Modulo spellchecking.
Comment #22 July 21st, 2007 at 10:35 pm
Chris W.: That’s a fantastic review!
Comment #23 July 22nd, 2007 at 12:58 am
If David Deutsch writes: “… my method of urging you to read the book [I Am a Strange Loop] will itself be paradoxical: I shall summarize why I find it ultimately unconvincing,” then are we helping or hurting the paradox by urging people to read his review? Will more people read the Douglas Hofstadter’s book if an even number of us refer to David Deutsch’s review, or an odd number? Please don’t refer to my comment on the review. I’m certainly not going to.
Most people overgeneralize from a single example. I surely do.
Comment #24 July 22nd, 2007 at 4:38 am
> (…) Meaning #3: remove or displace from a position. (…)
Thank you very much! I think I already saw something like this somewhere.
If you have time, I invite you to play at http://www.pocket-monkey.com
I’m registered there as Osias
Comment #25 July 22nd, 2007 at 11:15 am
I saw an article on this a couple of days ago, and it’s not clear to me that checkers really is solved. They hedge it by saying something about being restricted to positions that usually arise in play.
Comment #26 July 23rd, 2007 at 9:53 am
For another attempt at computerized opponents (this time for poker), check out this story:
http://wcbstv.com/watercooler/local_story_202200457.html
“Solving” checkers or any other game with a large but finite number of positions or moves is a predictable result of increased computing power. I don’t think I’ll be at all surprised years from now when we see the headlines “Chess has been solved” and “Go has been solved.”
Poker is far more interesting from an AI perspective since it requires the program to adapt strategy to its opponent while varying its play to preclude an opponent from successfully adapting to it. There is also no possibility of “solving” the game since the outcome could vary even when dealing with the same opponents and cards.
I look forward to the world’s first combination poker tournament & Turing test, and I hope they plan to serve free drinks.
Comment #27 July 23rd, 2007 at 12:49 pm
What’s your perspective Scott on the claims/hope that great advances in AI will help computers play GO better?
I have been thinking about what that would mean in complexity-theoretic terms. It is known of course that determining the winner of a arbitary GO position is hard. (In fact, very hard, harder than NP.) Is the hope that GO is easier on average than in the worst case? That you don’t need to evaluate positions to choose a move?
Comment #28 July 23rd, 2007 at 1:23 pm
Johan: My understanding is that the problems of finding solutions to Checkers, Chess AND Go are all three in the same complexity class (wikipedia says that this is EXPTIME, but that in the case of Go this may depend on the Ko rule you choose to adopt).
In practical terms solving these games can offer different degrees of difficulty (i.e. since practical terms usually mean using a standard, finite-sized board); but in complexity-theoretic (asymptotic) terms there’s not really a difference there, since here we don’t really care about the structure of the decision tree, just the bounds on its size.
Comment #29 July 24th, 2007 at 12:08 am
Go is far, far harder to solve via the standard search techniques used for Chess and Checkers, since it has a far higher branching factor. I think that saying “different degrees of difficulty” is an understatement since chess programs operate at the grandmaster level while Go programs operate at the weak AI level.
Also, this might be slightly off topic, but I’ve always had the opinion that AI is a field where complexity theory isn’t really very important, since essentially all interesting problems scale exponentially in the worst case. I think AI is more about finding pragmatic algorithms that can offer decent performance in the average case.
Comment #30 July 24th, 2007 at 4:16 pm
Scott said, “Bram: The 0.753 is only for games with branching factor of 2 (which don’t tend to be played a lot ). As the branching factor increases, the classical exponent asymptotically approaches 1 while the quantum exponent remains 1/2. And for classical deterministic (as opposed to randomized) algorithms, the exponent is always 1.”
Hmm, that seems odd. Is the optimal classical algorithm for other branching factors the same (evaluate one random subtree and then others until you can stop)?
Comment #31 July 24th, 2007 at 5:14 pm
Is the optimal classical algorithm for other branching factors the same (evaluate one random subtree and then others until you can stop)?
Great question! If all the branching factors are the same, then I think Saks-Wigderson analysis gives an affirmative answer (someone correct me if I’m wrong). If the branching factor can differ from one vertex to another, then I’d still conjecture the answer is yes, but it’s not known in general.
Comment #32 July 26th, 2007 at 12:13 pm
Computer vs Human in poker – and the winner is…
http://www.nytimes.com/2007/07/26/business/26poker.html?_r=1&adxnnl=1&oref=slogin&adxnnlx=1185480611-+7dAinwap+FN5OdyrmPjAQ
Comment #33 July 26th, 2007 at 9:08 pm
This week’s “Science News Weekly” had an article on the Checkers solution. Although this was the rare SNW that had an actual equation (fibonacci and lucas numbers recursion formula), little detail was provided.
SNW discussed how they worked on the problem from both ends. First, on the back end, they crunched all boards with n checkers, starting with n = 2 and making it to n = 10 in a decade or so. The work per board scaled as 10^n. This info was stored in a condensed form. Next they played openings, taking all branches until the game got to n = 10, and then looked up the solution. I am guessing some pruning was involved.
Here is what caught my attention: SNW stated that a condensed storage scheme was used that stored the n
Comment #34 July 30th, 2007 at 10:25 am
This continues a comment about the report in Science News Weekly that was somehow cut short:
Here is what caught my attention:
SNW stated that a condensed storage scheme was used that stored the n
Comment #35 July 30th, 2007 at 11:26 am
One more try. It appears that a “C-language less than or equal sign” cuts off messages in the “Leave a Reply” box.
Anyway, the SNW report stated that the n = 10 (and less) end game outcomes were stored in some unspecified data structure with an “average of 154 positions per byte”. Rather impressive. Does anyone have a guess how they could do that? The SNW report is at http://www.sciencenews.org/articles/20070721/fob4.asp
Comment #36 July 30th, 2007 at 12:53 pm
AFAIK Chinook endgame data uses fairly standard techniques in combination with domain dependent knowledge. They utilize symmetries and every unique position gets an index where the game value is stored. Capture and capture threat positions get special treatment to reduce. Then a version of run length encoding does the compression.
Comment #37 August 6th, 2007 at 6:38 am
I couldn’t understand some parts of this article Checkers solved, but I guess I just need to check some more resources regarding this, because it sounds interesting.
Comment #38 August 7th, 2007 at 12:15 am
Hmm:
“Babbage, in speaking of his analytical engine, has suggested that a machine might be made that would play a game of combination, such as draughts, provided the maker of the machine himself would work out perfectly the sequences of the game. Professor Fairman Rogers finds that the sequences of tit-tac-toe are easily tabulated, and hence an automaton may be made that will play the game as follows: The opponent to the automaton makes the first move in the game and in so doing causes a certain cylinder to change its position. This causes the automaton to make that play which the proper sequence of the game requires. The next play of the opponent moves another cylinder, and so on throughout the sequence. If the player plays perfectly, the game will be drawn; if the opponent makes a mistake, the automaton will take advantage of it and win the game.”
— Scientific American, May 1874