Will computers ever solve chess?

Sort:
Avatar of adamny

Yes. Is the answer.

 

The combinations and possibilities are astronomical, true....

But soon quantum computing will arive and the game will be over, 

Those who limit the possibility of a quantum computer are deluding themselves.

Avatar of Nathanhof
s23bog wrote:

I wonder if a device is set up to solve chess, regardless of time limits ... would anyone even care when it finally is solved?

That's an interesting question. I sure hope it would solve it before the universe ends (either due to natural causes or because your god thinks it's time).

Let me put it this way: if I build a tower, first story is 10/1 meters high, the second is 10/2 the next 10/3 etc. etc. In some time I'll build an infinitely high tower, but it'll be of very little use and I don't think anybody would be impressed by a tower of 90 meters high.

Avatar of zborg

Ah, to be youthful and to let you imagination run roughshod over your better judgement.

What a thrill.  So engaging.  Anything you can imagine MUST be possible, eventually.

Neat trick to your thinking.

Once you look at it, a bit more closely.  All those infinite monkeys typing away on those infinite number of typewriters will eventually recreate all of Shakespeare's works.

What have you been smoking, kind sir?

 

Avatar of Elroch

Recurrent neural networks can do a passable attempt at writing in the style of Shakespeare, being provided with nothing but the ASCII text of his complete works.

Avatar of Elroch
vickalan wrote:
Nathanhof wrote:
You are literally proposing to have a computer do more work than counting all the atoms in the universe at the very least 10^29 times... That is, recounting every. single. atom.
100000000000000000000000000000 times over.

 

Not correct. The entire game-tree of chess does not have to be searched to find a forced mate.

 

I think I see your point: it is that in a given position, a lot of black replies will permit a forced mate. Each bad move the opponent makes either permits a mate or makes a mate quicker, and each such move reduces the computation needed on a branch.

The problem is that even if typically a player has a small number (2 or 3, say) of moves that do not harm the theoretical result, this still means there are a heck of a lot of branches in a tree 100 moves deep. My suspicion is that with play of this quality, 200 move games might be the norm.

An extension to your idea is that white can play simplifying moves to approach a forced draw more quickly. I am not sure how much this helps the computation, but it is of some use.

Avatar of Elroch
bb_gum234 wrote:
vickalan wrote:
Nathanhof wrote:
You are literally proposing to have a computer do more work than counting all the atoms in the universe at the very least 10^29 times... That is, recounting every. single. atom.
100000000000000000000000000000 times over.

 

Not correct. The entire game-tree of chess does not have to be searched to find a forced mate.

If you were able to find a forced win, yes, but since chess is almost certainly a draw with best play, you will likely have to find a forced draw, I suppose by finding all (well, most anyway) forced mates associated with that draw.

And lets say we find out 1.e4 is a draw... but we can't say for sure 1.d4 isn't a win, so next we have to find a forced draw there too, etc.

But yes, finding a forced win from the starting position would greatly simplify the storage requirements for the solution. maybe only a planet sized storage device would be needed instead of  a device of galactic mass, or universe scale, or more 

 I was thinking along similar lines to you, but I think the relevance of vickalan's  comment is that presuming perfect play leads to a draw, for a large fraction of black's responses, forced mates will be available to white.  If inferior moves follow inferior moves, the forced mates get shorter.

Even moves that say lose 50 centipawns in a computer assessment mean that a following move which is similarly inaccurate (in an imprecise sense) may well leave the game lost (i.e. a forced mate). This does reduce computation, but IMO not enough to make a solution anything like feasible.

Avatar of ProfessorPownall

The idea that White possibly has a forced win because he moves 1st a fallacy. In fact, Computers understand counter-attacking motifs, sacrificing a pawn that White must accept or face annihilation. It is Black that Computers will prove to have a forced win ! 

Avatar of universityofpawns

How would we know if chess was actually "solved"? Didn't humans think chess was solved several times in the history of chess?

Avatar of vickalan
Elroch wrote:
vickalan wrote:
Nathanhof wrote:
You are literally proposing to have a computer do more work than counting all the atoms in the universe at the very least 10^29 times... That is, recounting every. single. atom.
100000000000000000000000000000 times over.

 

Not correct. The entire game-tree of chess does not have to be searched to find a forced mate.

 

I think I see your point: it is that in a given position, a lot of black replies will permit a forced mate. Each bad move the opponent makes either permits a mate or makes a mate quicker, and each such move reduces the computation needed on a branch.

The problem is that even if typically a player has a small number (2 or 3, say) of moves that do not harm the theoretical result, this still means there are a heck of a lot of branches in a tree 100 moves deep. My suspicion is that with play of this quality, 200 move games might be the norm.

An extension to your idea is that white can play simplifying moves to approach a forced draw more quickly. I am not sure how much this helps the computation, but it is of some use.

I agree that any search of the game-tree can still be huge, even if only searching for forced mates. It still might be outside the bounds of today's computing power, but considering there are big projects using tons of computer power looking for extra-terrestrials, I wouldn't be surprised if some group takes up the probably simpler (and more mundane) task of solving chess.

For clarity I made a diagram below to help show how solving chess doesn't necessarily require checking the entire game-tree. If either side can force a mate (left branch) then nothing in the orange needs to be check. This concept can apply from the very first move of the game (if 1.e4 leads to a forced win no need to check other 19 openings). It also applies to intermediate and very small branches all over the game-tree.

null

As for why some people believe chess is a draw, I don't know where that conclusion comes from. It's possible, but where's the analysis? Using data from human games and engines doesn't mean much because we don't yet know perfect play.

Also, if there is a forced mate for one side, I don't know if there is a reason why it would be longer than an average game. There may be a huge number of paths in the tree that lead to a forced mate. If chess is solved, we will probably find a normal length forced-mate first (40 moves or so) and then discover longer ones later.happy.png

Avatar of SmyslovFan

Repeatedly saying you don't know where the conclusion that chess is a draw comes from simply shows that you haven't bothered to read or study what the experts of the game (grandmasters), have said, and what the engines are demonstrating. 

Avatar of vickalan

Using data from humans and engines doesn't mean anything because we (humans) and engines don't play perfect chess. You can't say "chess cannot be solved" and at the same time say that humans have solved it.happy.png

Avatar of SmyslovFan
vickalan wrote:

Using data from humans and engines doesn't mean anything because we (humans) and engines don't play perfect chess. You can't say "chess cannot be solved" and at the same time say that humans have solved it.

You aren't quoting me. 

I have said many times that not only can chess be solved, we are close to solving it and may solve it in our lifetimes. 

I reject the notion that we must map out every single possible move to claim that the game is solved. All we need to do is create a chess playing program that can never be beaten, even by its clone. That's how checkers was solved, and how chess will be solved in the next 20-30 years.

We are already close to having perfect chess playing engines. The current computer world chess championship is 100 games. Stockfish won the final match, and lost a total of 8 games against Komodo. Both are rated +3200.

Avatar of DiogenesDue

Checkers was solved:

 

"Draughts, English (Checkers)This 8×8 variant of draughts was weakly solved on April 29, 2007 by the team of Jonathan Schaeffer, known for Chinook, the "World Man-Machine Checkers Champion". From the standard starting position, both players can guarantee a draw with perfect play.[10] Checkers is the largest game that has been solved to date, with a search space of 5×1020.[11] The number of calculations involved was 1014, which were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50.[12]"

 

Chess will not be.  10^46 is quite a bit more difficult than 10^14.  Over a billion billion billion times more difficult.  Eighteen years won't cut it.

 

Avatar of Nathanhof
vickalan wrote:
Elroch wrote:
vickalan wrote:
Nathanhof wrote:
You are literally proposing to have a computer do more work than counting all the atoms in the universe at the very least 10^29 times... That is, recounting every. single. atom.
100000000000000000000000000000 times over.

 

Not correct. The entire game-tree of chess does not have to be searched to find a forced mate.

 

I think I see your point: it is that in a given position, a lot of black replies will permit a forced mate. Each bad move the opponent makes either permits a mate or makes a mate quicker, and each such move reduces the computation needed on a branch.

The problem is that even if typically a player has a small number (2 or 3, say) of moves that do not harm the theoretical result, this still means there are a heck of a lot of branches in a tree 100 moves deep. My suspicion is that with play of this quality, 200 move games might be the norm.

An extension to your idea is that white can play simplifying moves to approach a forced draw more quickly. I am not sure how much this helps the computation, but it is of some use.

I agree that any search of the game-tree can still be huge, even if only searching for forced mates. It still might be outside the bounds of today's computing power, but considering there are big projects using tons of computer power looking for extra-terrestrials, I wouldn't be surprised if some group takes up the probably simpler (and more mundane) task of solving chess.

For clarity I made a diagram below to help show how solving chess doesn't necessarily require checking the entire game-tree. If either side can force a mate (left branch) then nothing in the orange needs to be check. This concept can apply from the very first move of the game (if 1.e4 leads to a forced win no need to check other 19 openings). It also applies to intermediate and very small branches all over the game-tree.

 

As for why some people believe chess is a draw, I don't know where that conclusion comes from. It's possible, but where's the analysis? Using data from human games and engines doesn't mean much because we don't yet know perfect play.

Also, if there is a forced mate for one side, I don't know if there is a reason why it would be longer than an average game. There may be a huge number of paths in the tree that lead to a forced mate. If chess is solved, we will probably find a normal length forced-mate first (40 moves or so) and then discover longer ones later.

And how do you propose to know beforehand which route to take?

Why do you think we'll find a forced mate within 40 moves when we already have computers that calculate that deep and cannot find a position even close to a mate?

Avatar of ponz111

Not to mention you will never find a forced mate as chess itself is a draw.

Avatar of anselan
ponz111 wrote:

Not to mention you will never find a forced mate as chess itself is a draw.

 

It has not even been proved that chess is not a win for Black.

Avatar of camter
NelsonMoore wrote:

The opening position could be zugzwang.

 

You have stolen my joke.

But, the advantage of White is, if we really knew what it meant, the initiative.

If anyone can explain the initiative, I will be very grateful. 

Avatar of anselan
 
If anyone can explain the initiative, I will be very grateful. 

Combinatorial game theory quantifies the notion of initiative precisely with a concept called "temperature". Roughly, hot positions are those where you would want to have the next move, cold positions are those where you would want the opponent to move first. Snooker is a good example of a game with both hot and cold positions. Chess is a little more complicated to apply this theory, but still there are non-trivial insights possible. See for example the beautiful paper by Noam Elkies: library.msri.org/books/Book29/files/elkies.pdf

Avatar of camter
s23bog wrote:

The initiative is seizing the moment to do what is right and best.

I thank you for that.

Anyone has something to agree or disagree with that.

Avatar of camter

As to the original question, I believe that the problem is soluble if the computer has enough storage space and time.

Whether there will ever be enough of that to achieve that even in a million years of design and building before the machine can be even turned on is very debateable.