Quantum Chess!
September 8, 2010 4:43 PM Subscribe
"Computers can search all possible outcomes of all possible moves in conventional chess and beat even top human players, so Akl wanted to make the computation more difficult." The result? Quantum chess! [via]
At least no cats die in this example.
posted by ALongDecember at 4:52 PM on September 8, 2010 [1 favorite]
posted by ALongDecember at 4:52 PM on September 8, 2010 [1 favorite]
Can you program the computer to "accidentally" knock the board over if it's losing?
posted by The Card Cheat at 4:57 PM on September 8, 2010
posted by The Card Cheat at 4:57 PM on September 8, 2010
To my knowledge, even the best computer programs do not search every move, which would still take a prohibitive amount of time. Instead they use a database of known positions, heuristics, and general strategy, combined with deep move search, to arrive at their move.
posted by JHarris at 4:58 PM on September 8, 2010 [3 favorites]
posted by JHarris at 4:58 PM on September 8, 2010 [3 favorites]
Computers can search all possible outcomes of all possible moves in conventional chess
I'm pretty sure this is a false statement. At least, it's not true that this HAS been done. It's been done for checkers, but not for chess.
posted by Salvor Hardin at 5:02 PM on September 8, 2010
I'm pretty sure this is a false statement. At least, it's not true that this HAS been done. It's been done for checkers, but not for chess.
posted by Salvor Hardin at 5:02 PM on September 8, 2010
ALongDecember: At least no cats die in this example.
You're playing it wrong.
Or are you?
posted by MCMikeNamara at 5:05 PM on September 8, 2010
You're playing it wrong.
Or are you?
posted by MCMikeNamara at 5:05 PM on September 8, 2010
I played and reviewed this earlier today.
tl;dr summary: I can live with taking away castling and en passant, but take away check and checkmate and I'm sorry but that's not chess any more. It's a whole new game that inherits some rules from chess and uses a chess board and chess pieces, but it isn't chess.
posted by motty at 5:07 PM on September 8, 2010
tl;dr summary: I can live with taking away castling and en passant, but take away check and checkmate and I'm sorry but that's not chess any more. It's a whole new game that inherits some rules from chess and uses a chess board and chess pieces, but it isn't chess.
posted by motty at 5:07 PM on September 8, 2010
It is an embarrassingly false statement.
It is not true.
posted by Joe Beese at 5:31 PM on September 8, 2010
It is not true.
posted by Joe Beese at 5:31 PM on September 8, 2010
To be clear...
Although computers now can beat world champions in tournament conditions, their doing so requires a great deal more than simply simulating every possible sequence of moves - which it is computationally unable to do more than several moves out.
posted by Joe Beese at 5:34 PM on September 8, 2010
Although computers now can beat world champions in tournament conditions, their doing so requires a great deal more than simply simulating every possible sequence of moves - which it is computationally unable to do more than several moves out.
posted by Joe Beese at 5:34 PM on September 8, 2010
My dad and my brother and I once made up a game which was sort of like a cross between battleship and chess. Each player had his own board hidden from the other, and would announce when moving a piece what that piece was, and where it was departing from, but not where it was moved to. It's status remained unknown until it was moved again, and then it might collide with pieces which had been moved after it had been moved. I had written up the rules and put them up on geocities ages ago. We never really came up with a proper name for that game, but we considered calling it "quantum chess."
posted by smcameron at 5:39 PM on September 8, 2010 [8 favorites]
posted by smcameron at 5:39 PM on September 8, 2010 [8 favorites]
Metafilter: in a quantum superposition of two piece type states: a primary type and a secondary type.
posted by blue_beetle at 5:45 PM on September 8, 2010
posted by blue_beetle at 5:45 PM on September 8, 2010
I win! Playing without reading the rules, the first time, was terribly confusing.
posted by Michael Roberts at 5:46 PM on September 8, 2010
posted by Michael Roberts at 5:46 PM on September 8, 2010
Ugh, where'd that extra apostrophe come from?
Your grammatical wave-function collapsed after preview.
posted by device55 at 6:10 PM on September 8, 2010 [1 favorite]
Your grammatical wave-function collapsed after preview.
posted by device55 at 6:10 PM on September 8, 2010 [1 favorite]
Yeah, the search space for chess positions is huge. Crazy huge. I don't remember if it's more-than-the-number-of-atoms-in-the-universe huge, but it's damned big. Checkers is a solved problem; chess is just a problem that we've built really good computers to take approximate shots at. (And, yes, Go is just completely out of reach.)
posted by cortex at 6:14 PM on September 8, 2010 [2 favorites]
posted by cortex at 6:14 PM on September 8, 2010 [2 favorites]
Checkers is a solved problem; chess is just a problem that we've built really good computers to take approximate shots at. (And, yes, Go is just completely out of reach.)
Do any mathematicians/physicists/etc. have any idea if there is a significant difference in complexity for chess and Go? I'm just curious at the mathematical differences between chess and Go's gameplay. Thanks!
posted by kurosawa's pal at 7:07 PM on September 8, 2010 [1 favorite]
Do any mathematicians/physicists/etc. have any idea if there is a significant difference in complexity for chess and Go? I'm just curious at the mathematical differences between chess and Go's gameplay. Thanks!
posted by kurosawa's pal at 7:07 PM on September 8, 2010 [1 favorite]
Googling suggest that the total permutations of chess positions are 2E+46. More than the number of stars in the observable universe, less than the number of atoms. About 100 million times as hard as brute-forcing a 128-bit key.
Which is to say, there's probably a machine in the basement of NSA that's solved chess by backwards induction.
posted by ROU_Xenophobe at 7:10 PM on September 8, 2010
Which is to say, there's probably a machine in the basement of NSA that's solved chess by backwards induction.
posted by ROU_Xenophobe at 7:10 PM on September 8, 2010
Do any mathematicians/physicists/etc. have any idea if there is a significant difference in complexity for chess and Go? I'm just curious at the mathematical differences between chess and Go's gameplay. Thanks!
Complexities of some well-known games
posted by kmz at 7:20 PM on September 8, 2010 [1 favorite]
Complexities of some well-known games
posted by kmz at 7:20 PM on September 8, 2010 [1 favorite]
Do any mathematicians/physicists/etc. have any idea if there is a significant difference in complexity for chess and Go?
They do! I'm just an armchair complexity nerd so I can't point you to the state of the art or anything, but as a rough point of scale you can look at raw board states as a point of comparison: chess is a 8*8 matrix, Go is 19*19. A really, really rough napkin calculation might take those numbers and throw them as exponents into a value like 2n to get a basic sense of scale:
chess as 264 = 1.84467441 × 1019
Go as 2361 = 4.69708517 × 10108
Those are both huge numbers, but the size of the raw Go space makes chess look like tic-tac-toe.
Non-silly approaches to the complexity of the problems are a lot more complex than this; aside from just restricting the board states we consider to actual legal states (as opposed to every possible configurations of pieces on the board), there's a lot of symmetry and subdivision that can with care be done to the board states themselves to further reduce just how many distinct configurations we need to deal with. But so far even all that cleverness applied to either game has only helped reduce somewhat the still-overwhelming burden.
And whereas world-class chess computers can now compete with and beat world-class human players, no existing Go computer yet built can stand up to even reasonably solid players, let alone grandmasters.
posted by cortex at 7:22 PM on September 8, 2010 [1 favorite]
They do! I'm just an armchair complexity nerd so I can't point you to the state of the art or anything, but as a rough point of scale you can look at raw board states as a point of comparison: chess is a 8*8 matrix, Go is 19*19. A really, really rough napkin calculation might take those numbers and throw them as exponents into a value like 2n to get a basic sense of scale:
chess as 264 = 1.84467441 × 1019
Go as 2361 = 4.69708517 × 10108
Those are both huge numbers, but the size of the raw Go space makes chess look like tic-tac-toe.
Non-silly approaches to the complexity of the problems are a lot more complex than this; aside from just restricting the board states we consider to actual legal states (as opposed to every possible configurations of pieces on the board), there's a lot of symmetry and subdivision that can with care be done to the board states themselves to further reduce just how many distinct configurations we need to deal with. But so far even all that cleverness applied to either game has only helped reduce somewhat the still-overwhelming burden.
And whereas world-class chess computers can now compete with and beat world-class human players, no existing Go computer yet built can stand up to even reasonably solid players, let alone grandmasters.
posted by cortex at 7:22 PM on September 8, 2010 [1 favorite]
The initial branching factor for chess is 20, which quickly escalates and reaches an average observed branching factor of about 35.
The number of distinct chess positions after N moves are:
After each player makes 1 move: 400
After 2 moves apiece: 72,084
After 3 moves apiece: over 9 million
After 4 moves apiece: over 318 billion
The estimated number of positions after the first 10 moves apiece is:
169,518,829,100,544,000,000,000,000,000 =~ 1029.229
By the way, the longest theoretically possible chess game is 5,949 moves.
Let's take a 40 move game with a branching factor of 35 = 35^(2*40)=10120 different possible games. This is the Shannon number, an estimated lower bound of the number of variations needed to be examined in order to calculate a chess solution. This is commonly compared to the number of hydrogen atoms in the universe, 3*1079.
There's good news: a recent upper bound on the number of possible positions has been determined to be:
45193640626062205213735739171550309047984050718 =~1046.65
Which is much smaller and won't take as long.
The age of the universe (according to the Big Bang Model) is about 4.3*1017 seconds. So, a supercharged nanillion-hertz iPad (10,000 times faster than a mere yottahertz knockoff, and with a more reliable battery) working on this problem since the beginning of time would be just about finished exhausting the search space now. So it's definitely possible.
But wait! Where are you going to put your answer, of what move to make every turn? (You don't want to repeat this search this every time you play, do you?). Let's assume that your solution only needs one atom to store the winning response to each position. Realistically, it won't have to store a move for *every* position, but realistically it will need more than one particle per position so let's accept this as a lower bound. The good news is that with 1046.65 positions to encode, there are more than enough atoms available in the universe to store the entire solution with this method, with enough matter left over to form a physical board, pieces, and maybe an opponent.
However, large, nonrotating masses over the Chandrasekhar limit of approximately 2.85*1030kg, or about 1.4 solar masses, will suffer gravitational collapse into a neutron star. If the mass is greater than the Tolman-Oppenheimer-Volkoff limit, between 1.5 and 3.0 solar masses, it will collapse into a black hole. So, not only do we not have enough time to calculate the solution, storing the complete solution is impossible with our current understanding of matter.
*All figures from google/wikipedia. For entertainment purposes only.
posted by ceribus peribus at 7:53 PM on September 8, 2010 [26 favorites]
The number of distinct chess positions after N moves are:
After each player makes 1 move: 400
After 2 moves apiece: 72,084
After 3 moves apiece: over 9 million
After 4 moves apiece: over 318 billion
The estimated number of positions after the first 10 moves apiece is:
169,518,829,100,544,000,000,000,000,000 =~ 1029.229
By the way, the longest theoretically possible chess game is 5,949 moves.
Let's take a 40 move game with a branching factor of 35 = 35^(2*40)=10120 different possible games. This is the Shannon number, an estimated lower bound of the number of variations needed to be examined in order to calculate a chess solution. This is commonly compared to the number of hydrogen atoms in the universe, 3*1079.
There's good news: a recent upper bound on the number of possible positions has been determined to be:
45193640626062205213735739171550309047984050718 =~1046.65
Which is much smaller and won't take as long.
The age of the universe (according to the Big Bang Model) is about 4.3*1017 seconds. So, a supercharged nanillion-hertz iPad (10,000 times faster than a mere yottahertz knockoff, and with a more reliable battery) working on this problem since the beginning of time would be just about finished exhausting the search space now. So it's definitely possible.
But wait! Where are you going to put your answer, of what move to make every turn? (You don't want to repeat this search this every time you play, do you?). Let's assume that your solution only needs one atom to store the winning response to each position. Realistically, it won't have to store a move for *every* position, but realistically it will need more than one particle per position so let's accept this as a lower bound. The good news is that with 1046.65 positions to encode, there are more than enough atoms available in the universe to store the entire solution with this method, with enough matter left over to form a physical board, pieces, and maybe an opponent.
However, large, nonrotating masses over the Chandrasekhar limit of approximately 2.85*1030kg, or about 1.4 solar masses, will suffer gravitational collapse into a neutron star. If the mass is greater than the Tolman-Oppenheimer-Volkoff limit, between 1.5 and 3.0 solar masses, it will collapse into a black hole. So, not only do we not have enough time to calculate the solution, storing the complete solution is impossible with our current understanding of matter.
*All figures from google/wikipedia. For entertainment purposes only.
posted by ceribus peribus at 7:53 PM on September 8, 2010 [26 favorites]
And whereas world-class chess computers can now compete with and beat world-class human players, no existing Go computer yet built can stand up to even reasonably solid players, let alone grandmasters.
In the last few years, Go programs have made it to dan level, largely through the discovery of new Monte Carlo-based techniques. Zen19, for example, is currently holding down a 3d rating on KGS. So I think they finally have made it to the point where they're standing up to reasonably solid players. It will still be a while before they can compete on even terms with pros, though.
posted by dfan at 8:35 PM on September 8, 2010
In the last few years, Go programs have made it to dan level, largely through the discovery of new Monte Carlo-based techniques. Zen19, for example, is currently holding down a 3d rating on KGS. So I think they finally have made it to the point where they're standing up to reasonably solid players. It will still be a while before they can compete on even terms with pros, though.
posted by dfan at 8:35 PM on September 8, 2010
Dearest ceribus peribus,
Thank you so much for cementing my faith in Metafilter.
Yours truly,
posted by kurosawa's pal at 9:19 PM on September 8, 2010
Thank you so much for cementing my faith in Metafilter.
Yours truly,
posted by kurosawa's pal at 9:19 PM on September 8, 2010
Some fun further dorking in this thread from 2007, though more conversational than computational in nature.
In the last few years, Go programs have made it to dan level, largely through the discovery of new Monte Carlo-based techniques.
Neat! I am out of date.
posted by cortex at 9:31 PM on September 8, 2010
In the last few years, Go programs have made it to dan level, largely through the discovery of new Monte Carlo-based techniques.
Neat! I am out of date.
posted by cortex at 9:31 PM on September 8, 2010
smcameron - that sounds a bit like Kriegspiel, but without having to have a referee.
posted by labberdasher at 10:14 PM on September 8, 2010
posted by labberdasher at 10:14 PM on September 8, 2010
"As an online discussion of chess grows longer, the probability of a comparison involving the computational complexity of Go approaches 1." -- Go wins law
posted by logopetria at 2:10 AM on September 9, 2010 [3 favorites]
posted by logopetria at 2:10 AM on September 9, 2010 [3 favorites]
Thank you ceribus peribus, that was very interesting!
posted by Sutekh at 5:51 AM on September 9, 2010
posted by Sutekh at 5:51 AM on September 9, 2010
I don't think we've exhausted the checkers search space, either. Chinook is the best checkers player. It has apparently been proved mathematically that you cannot beat Chinook under any circumstances. But it didn't do this by exhausting the search space. There's a bunch of known play programmed in. The creator of Chinook wrote a book about it. I started to read it once.
Apparently, everybody thought that Checkers was "solved" in the 1950s because of boasts by Claude Shannon. It turned out that he had started the science of computer games-playing AI, and made a Checkers program that could beat a reasonable player, but this stuff got overhyped to the point where everybody thought it was all over for human checkers players.
posted by Galaxor Nebulon at 7:57 AM on September 9, 2010
Apparently, everybody thought that Checkers was "solved" in the 1950s because of boasts by Claude Shannon. It turned out that he had started the science of computer games-playing AI, and made a Checkers program that could beat a reasonable player, but this stuff got overhyped to the point where everybody thought it was all over for human checkers players.
posted by Galaxor Nebulon at 7:57 AM on September 9, 2010
I don't understand how removing check changes anything more than the quantum concept already does. If you have to touch a piece and collapse its waveform in order to make check, you can then proceed to move it to the king's square on the same turn. The rules don't appear to provide for leaving pieces in a classical state in between turns, with the exception of the King.
posted by LogicalDash at 10:56 AM on September 9, 2010
posted by LogicalDash at 10:56 AM on September 9, 2010
The board consists of the usual 64 squares of alternating black and white... with the usual misplacing of a white square on the player's left.
Each player’s pieces are initially positioned as in traditional chess, on the first two rows,... with the traditional swapping of King and Queen positions. (See board, above)
posted by MtDewd at 11:01 AM on September 17, 2010
Each player’s pieces are initially positioned as in traditional chess, on the first two rows,... with the traditional swapping of King and Queen positions. (See board, above)
posted by MtDewd at 11:01 AM on September 17, 2010
« Older I honestly think you ought to sit down calmly... | Mostly Maui Waui man, but it's got some Labrador... Newer »
This thread has been archived and is closed to new comments
posted by Blazecock Pileon at 4:48 PM on September 8, 2010 [1 favorite]