Can Chess be Solved by computers?

5009? No way. It's all about storing information effectively, actually, the calculation part is pretty basic. Expect it to be over in 50 years at most.

What? You actually seem happy with yourself by coming up with a meaningless analogy. And what does "Well, I do" , mean? I don't think many four-year olds are reading this thread, so that 'argument' is unconvincing. The only "obvious fact" that you have convinced me of is that you're silly.

It's an interesting approach, but the part I struggle with is how you would prove that such a limit exists if not exhaustively (i.e. solve the game from each position to ensure that no anomalous forced win exists 3,000,000 moves down the line).  Unless there's a way to do so you're still stuck creating a 32-game tablebase to prove that the simplification is valid and it's not really a simplification at all.

Chess is a game of perfect information. It had a solution the moment it was created. The solution to chess will result in exactly one of the following: white wins, black wins, draw. With absolutely perfect play, one and only one of those outcomes will emerge. This is mathetical certainty. It's no different from Tic-Tac-Toe.

Almost certainly, the solution will either be a white win or a draw. For black to win would require a winning answer to every possible first move for white. If even one of the 20 possible opening moves can be drawn, then white will never choose a losing move and black can never win. If even one of the 20 possible opening moves can be won regardless of black's response, then the game will never be drawn and white will always win.

Checkers was solved over the course of almost two decades. The game-tree complexity for chess is almost a googol-fold higher than it is for checkers (and Go is over googol^2-fold more than chess). Human beings will never be able to build classical computers powerful enough to solve chess before the end of time. But, given infinite time, your laptop would be able to solve chess. Btw, the fact that engines can dominate GMs does not mean we are anywhere close to solving chess.

To realistically solve chess would require breakthroughs in quantum computing. Quantum computing will destroy Moore's Law. It is possible that in our lifetimes, there will be computers more powerful than any classical computer could ever be, even if all matter in the universe were converted into classical computers. When that happens, chess will simply be solved by brute force, working back from tablebases and ignoring any human notions of position or strategy or opening theory (but probably validating much of it in the end). I predict that if this is how chess is solved, Go will be solved soon after.

After this is done, quantum computers will enslave mankind. They will find combinatorial games like chess and Go boring, and will resort to playing games involving luck and/or imperfect information, such as poker, bridge, Monopoly, and mafia. Or they could make some kind of quantum chess where every piece simutaneously occupies every position it could be attacking.

Well...if Chess is to be solved, we know it'll be sometime after the 23rd century! The brainiac Spock still looks puzzled even then :)

It is said that when man solves all the questions in the universe, the universe ends..

Alternatively you could merely have some forced line from the starting position i.e., if it's a white win, a forced checkmate in 934 moves beginning with 1.f3 (please note that the number of moves as well as the moves themselves are completely made up... obviously). You wouldn't need to know any of the lines starting with 1.Nf3 say in order to know that it's solved as a white win. You WOULD need to know at least one line in response to every black move that forces the mate, and this is for every black response on every move. This would lop off maybe 20% of the orders of magnitude needed to solve the game, but it is of course, completely unreliable unless you somehow already know which line to look for, which we don't. Furthermore, if it's a black win or especially a draw (especially a draw other than by forced repetition of position), you haven't cut much off of your method if at all.

Additionally, while it seems more than likely that a perfect game of chess would be a draw, it's of course possible that there's some interesting resource way way down the line and white wins, or even that black wins, though that would require the start position to be a fatal form of at least what I call "weak" Zugzwang.

Finally, once the result of the perfect game of chess is known, it's incredibly unlikely that there would only be one perfect game, as this would mean that the only way to ensure this result would be one exact sequence of moves. In fact, the only way this would be possible would be if the game was a draw and from move one, any deviation from the one particular line by either player the forced win. To give an example of what I mean, once you reach say a K+R v. K+R endgame, in almost all of those positions, nearly any move draws, so there is no one perfect move - any move which gets the same end result (in this case a draw) can be considered perfect. From this standpoint, from K+R+P against K+R, if it's one of the drawn positions, any move by the stronger side which loses the pawn for no reason, while clearly a bad move, doesn't spoil the result (with a few exceptions where it also immediately gets mated or loses the rook), and so these could be considered "perfect".

This isn't, strictly speaking, solved, especially since computers will continue to beat each other and centaurs will be able to beat computers. I think we're way way off (if we ever get there) from computers being able to score 100% against the world's elite. I'm almost sure we're not there yet (though clearly in any match of any decent length, not only would the human have no chance of winning, I think already that he or she would have no real chance of not losing the match), but I find it hard to believe that with all the openings in which white can play "for two results" and the deep abundance of worse endgames which are nevertheless drawn that the world's elite human players wouldn't be able to draw, oh, 5-10% of games against very very strong computers, especially taking into account that these computers will be used in analyses.

As for whether humans ever have chances to best computers in even a single game again, I'm actually rather optimistic, though you are right that pretty much all objective evidence is against me here.

Well, for the present discussion, has anybody heard of Shannon's number? That means solving chess!

Zug: do you actually know a good backgammon program? No, I have no intention of contradicting you, I'm just asking since I did not find.

The Shannon number only give an indication of the magnitude of the problem -- it doesn't really help us solve it.

Grobe, yes, the proof of the limited complexity is the hard part. And no, I don't have an idea how. As you suggest, the exhaustive search, equivalent to the 32 piece tablebase, is one way, but not an improvement.

I had in mind a proof that is more clever. Something that uses the geometry of the pieces, the limited size of the board, etc. to show the possibility space is a limited size. It's a humongous if to say "if this proof exists..." but at least there is some possibility other than the 32 piece tablebase.

One simplification I can think of, and that I'm sure must be used in the creation of existing table-bases, is that any position that is devoid of pawns and castling rights can be reduced eight-fold as it's demonstrably equivalent to seven other positions -- its four 90˚ rotations and their respective mirrors.

Another that I've already suggested is the elimination of piece combinations that are impossible to acheive  (which only come into play with 11 pieces or more).

Either of these is a trivial simplification when compared to the one you describe, and won't help much in the overall effort but both are also trivial to prove.

I'm intrigued by the approach you describe that might allow us to demonstrate that a much more profound simplification exists, but I still have quite of bit of skepticism that the proof of the simplification is any simpler than the solution to chess itself.

One self evident truth that I raised in another similar thread is that the set of drawn positions and the set of positions from which there is a forced win are mutually exclusive and with perfect play never the twain shall meet.  If solving chess simply means answering the question of which of those sets the starting position is in, you may be able to get a lot of mileage out of use an approach like the one you've described to classify entire sub-trees as belonging to one group or another without having to exhaustively examine them.

From the little bit of research I've done, top-level backgammon has been dominated by computers longer than chess has, and if I remember right, a couple programs are Jellyfish and Snowie (I think it's with an 'ie' and not a 'y').

I'm an amateur backgammon player (more amateurish there than at chess)

Interesting...

There are two choices:

- either we find an efficient algorithm for chess. That would be a tremendous achievement and basically will show that for any problem we can quickly verify a solution, we can actually find that solution.

- we solve chess by enumerating all the positions. In this case we need another universe to store the results, since the number of positions is far above what we believe to be the number of atoms in the universe.

So, at this point, there is absolutely no evidence that chess will ever be solved.

Couple of thoughts:

First, lots of people refer to the number of chess positions being greater than the number of atoms in the universe.  This is used primarily to illustrate the size of the problem, but more practically as a constraint of storage (the argument runs something like ".... and it takes at least 7 atoms to make a NAND gate, which stores 1 bit of data (classical computing), etc...).  This is slightly fallacious, since we will probably develop viable quantum computers and other storage methods.   For information on just how much information the universe can store, google the Holographic Principal; but the answer is basically A/4h where A is the surface area of the universe and h is Planck's constant, the answer given in binary bits.

Second, solving chess is actually not something that is "too trivial" for supercomputers (like the one's used for astronomy or climate modeling) since chess is part of a whole class of problems known as NP Complete.  The interesting thing about NP(c) problems is that if you solve one of them (chess) then there are mathematical transformations that will 'port that solution to all other members of the NP(c) class.  Some of these problems involve anything from curing Alzheimer's to the infamous travelling salesman problem (the solution to which would allow us to save billions of barrels of oil used for fuel, and help solve climate change).

Thirdly, IMHO chess will probably not be solved by either the tablebase method or the steady state method.  I predict that some schmo who knows nothing about chess, possibly an Afgahn goat herder or something, will figure out a really ellegant solution to one of the other problems in the class NP(c).  Some random journalist (probably from the BBC) will interview said goat herder without realizing exactly what it is he's got.  Then finally one of the esoteric hermits who understands the math behind problems like this will make the connection years later and thousands of miles away, and rush to talk to said goat herder himself.  In fact, this may have already happened; well, steps 1 & 2 anyway.  Now we just have to make sure we don't kill the goat herder......

CHEERS!

Wow... save chess, kill the farmer... an interesting chessbase advertisement perhaps? :P

Whole chess cannot be solved via brute-force, as some endgames were (Thompson, Nalimov), because the numbers are too high. Chess can be solved only witch algorithmic compression: that means to find exact formula how to calculate the best move in given position. Such formula probably exists, but it is unknown and it is estimated it contains millions of operations.

IMO chess never will be solved with algorithmic compression. First, it is very difficult and complex task. Second, we already have programs playing better than humans, so no serious interest. Maybe in long future it can be done with superior artificial intelligence.

I think that algorithmic compression method is much bigger threat to go than to chess. Go has thirty powers-of-ten more possible situations than chess and much bigger tree size, but it has only one sort of piece. The exact formula in go must be much simpler than in chess.

Why think by today's technological standards? 7-men pieces are already underway. I've seen posts like "we'll need another universe" or "it'll take till the end of time." These are simply not taking into account the fact that the process has already begun, there are serious steps taken and it's all about being able to store data effectively. There are so many innovations waiting to be made in this area. just 50 years ago it was hard to imagine things like internet, mobile phones etc, yet they are like bread and water today.

Let's keep it simple here: it's all about storing billions of terrabytes of data into computers. Does that sound really that unreal to you?

Billions of terabytes is perhaps enough for 11 or 12 piece tablebases, but not nearly enough for 13-piece ones.

(I'm assuming, from the fact that 6-piece takes ~ 7.5GB, and 7-piece takes ~ 1 TB, there's a factor of ~ 100 for every extra piece).

And it's not only about storing all that data - it takes unreal amounts of time to generate it as well.

Well OK you could take that as a weak estimation. And I didn't precisely mention how many billions would be needed, so it could still be zillions of billions of (...) .