#6901
My point is that quantum computers are faster than conventional computers and much so and thus more likely to solve chess.
If you deny that then why would IBM sell quantum computers?
For applications that quantum computers are going to be good for...?
Probably the best way to solve chess is to work backwards. Since every game has and ending all a computer has to do is to store all the games and reuse them knowing how it ends.
#6904
Yes, that is how endgame table bases were generated: from 3 men to 4 men to 5 men to 6 men to 7 men. Work on 8 men is in progress.
However, this is not feasible to continue all the way down to 32 men.
So the most promising approach is a two prong method of calculating from the initial position towards a sufficiently large endgame table base. That is how checkers was solved.
Probably the best way to solve chess is to work backwards. Since every game has and ending all a computer has to do is to store all the games and reuse them knowing how it ends.
Congratulations, and welcome to 1965.
Interesting that that idea came from the Bellman I am familiar with from Bellman equations in reinforcement learning (and inventor of dynamic programming). This sort of thing is used in applications like self-driving cars.
@johntromp has today published a set of work that drops the number of possible positions from 10^46.7 to 10^44.7...
https://github.com/tromp/ChessPositionRanking
https://www.chess.com/forum/view/general/on-the-number-of-chess-positions?page=1
This has yet to be poked or prodded much, so feel free to help him out by kicking the tires...there's a bounty of up to $256 for finding something.
#6899
This includes a vast majority of non sensible positions with more than 2 queens, rooks, bishops, or knights per side. The number of sensible positions with maximum 2 queens, rooks, bishops, knights per side is estimated at a factor of 1 million less.
#6899
This includes a vast majority of non sensible positions with more than 2 queens, rooks, bishops, or knights per side. The number of sensible positions with maximum 2 queens, rooks, bishops, knights per side is estimated at a factor of 1 million less.
There's no "sensibility" determination involved in solving chess. But even if there were, and even if your million factor were to be true, 10^38.7 is still unreachable by any reasonably foreseeable technology. You posited that chess could be solved by burning the candle at both ends because we could drop the number of positions to 10^20, which is why you'll take anything you can grasp...but even allowing for 10^38.7, you've got 1,000,000,000,000,000,000 times more positions to go.
#6901
Take a look at the sample positions from John Tromp: at first glance it is clear that none of these results from a real game, i.e. none has any relevance. In a real game underpromotions to knight, rook, or even bishop do happen occasionally, but are very rare. In no real game anybody will underpromote to a 3rd rook or a 3rd bishop or a 3rd knight. Promotion to a second queen does happen rarely, but 3 or more queens per side are fantasy.
Hence to solve chess only sensible and legal positions need consideration.
Legal means: possible to reach from the initial position.
As sensible I propose: possible with one chess set of 32 pieces and an additional spare queen of each color.
Now not all possible, sensible, legal positions need to be visited to solve chess.
Of the 5 x 10^20 possible positions, Schaeffer needed to evaluate only 10^14 to prove that checkers, played perfectly, results in a draw.
#6901
Take a look at the sample positions from John Tromp: at first glance it is clear that none of these results from a real game, i.e. none has any relevance. In a real game underpromotions to knight, rook, or even bishop do happen occasionally, but are very rare. In no real game anybody will underpromote to a 3rd rook or a 3rd bishop or a 3rd knight. Promotion to a second queen does happen rarely, but 3 or more queens per side are fantasy.
Hence to solve chess only sensible and legal positions need consideration.
Legal means: possible to reach from the initial position.
As sensible I propose: possible with one chess set of 32 pieces and an additional spare queen of each color.
Now not all possible, sensible, legal positions need to be visited to solve chess.
Of the 5 x 10^20 possible positions, Schaeffer needed to evaluate only 10^14 to prove that checkers, played perfectly, results in a draw.
You can contort all you want to, but you will never get 10^40+ down to 10^20. Ain't gonna happen. Chess is not checkers.
One thing that has to happen is that each side has to make a move that is the best move to be played, otherwise he loses. There might be a couple of sensible moves at the beginning, usually one best move toward the end, so I don't see a lot of possibilities.
Nope.
Said it before. Sometime the simple and correct answer to the OP’s question is worth restating.
no
Yes, before the end of this century.
Not in our lifetimes.
#6916
That depends on your age.
In 1970 it was unthinkable that a chess engine would ever beat a human grandmaster, or that we would know exactly how to play 7 men endgames.
Maybe IBM will do it like they made Deep Blue.
Maybe Google will do it like they made AlphaZero.
Maybe the Lomonosov University will do it like they made 7 men table bases.
Maybe a loner like Ken Thomson will do it like he made 5 men table bases.
Maybe a loner like Schaeffer will do it like he solved checkers.
#6916
That depends on your age.
In 1970 it was unthinkable that a chess engine would ever beat a human grandmaster, or that we would know exactly how to play 7 men endgames.
Maybe IBM will do it like they made Deep Blue.
Maybe Google will do it like they made AlphaZero.
Maybe the Lomonosov University will do it like they made 7 men table bases.
Maybe a loner like Ken Thomson will do it like he made 5 men table bases.
Maybe a loner like Schaeffer will do it like he solved checkers.
None of those are going to happen. Also, it was not remotely unthinkable that a chess computer would eventually outplay humans...it's almost an inevitability, in fact.
Beating a human GM is like a grain of sand compared to the beach of solving chess.
You can say nay all day, but whether you like it or not, sooner or later chess will be solved.
#6895
"in the first move, there are a total of 400 diferent board combinations"
Most of those 400 positions most are irrelevant.
It is pointless to investigate 1 e4 g6 2 Qh5, 1 d4 g6 2 Bh6, 1 e4 e5 2 Ba6 etc.
Once it is proven that the Berlin draws, then it is not necessary to investigate if the Petrov, Sveshnikov, Najdorf, French, Caro-Kann draws as well or not.
Once it is proven that the Grünfeld draws, then it is unnecessary to investigate if the Queens's Gambit declined, Slav Defence, Queen's Gambit Accepted, Nimzo-Indian Defence draw as well or not.
Once it is proven that black can draw after 1 e4, 1 d4, 1 c4, 1 Nf3, then it is unnecessary to prove that black can also draw against 1 Nh3, 1 f3, 1 a4...
So the 400 possible positions after move 1 boil down to 4 relevant positions.
"To compute that many combinations would take a lot of time, space, and energy, all spent on what?" It would be a good factory acceptance test for a quantum computer: run the same program on two quantum computers and verify that the results concur to demonstrate that the Shor autocorrection successfully handles any quantum decoherence caused by cosmic radiation.
#6901
My point is that quantum computers are faster than conventional computers and much so and thus more likely to solve chess.
If you deny that then why would IBM sell quantum computers?