Will computers ever solve chess?

Sort:
Prometheus_Fuschs
waffllemaster escribió:

This has been asked and talked about before.  The answer is no.

 

ifoody wrote:

Sadly yes. It may take some years, but the technology advances all the time, and if today's computer need 200 years to solve chess completley, in 10 years the will need 50 years, and maybe in some time solving games like chess will be something that every 8 years old kid can do with his personal computer at home.

But the answer is for sure, yes.

The problem with that logic is they currently need an absurd number like 10^50 years.  So in the future, when it gets 100x faster, they'll only need 10^48 years, and in the very far far far future, only 10^40 years.

And then there's the impracticality (more like impossibility) of storing the solution.

e.g. a little quiz.  If every position + its evaluation only took 1 bit of storage space, and every bit could be stored in the size of an atom, then how big would the storage device be?

A) Bigger than the moon.
B) Bigger than the sun.
C) More atoms than our solar system.
D) More atoms than our galaxy.

 

D)

 

troy7915
lfPatriotGames wrote:
pawn8888 wrote:

Perhaps a perfect game would be for white to use it's slight opening advantage and play for a win, not making any mistakes. Black couldn't play a perfect game for a win because white would have to make a mistake first which would mean the game wasn't perfect. Maybe black's perfect game would be a draw.  

If blacks perfect game is a draw, wouldn't that mean whites perfect game is a draw too? I'm assuming in all cases both sides play with no mistakes. If white starts out with an advantage and plays for a win and black can't stop it, then blacks perfect game is always a loss and never a draw.

 

  But by the same token, the slight advantage at the beginning of the game for White ( which we don’t know for sure, but assume for a moment it’s a fact) may be insufficient for a win with best play by both sides, so that it ends in a draw no matter what.

 Or there was no advantage at the start of the game for either side. It’s like the hyper-modern openings. It used to be believed that occupying the center was the best method to control it, and thus if you didn’t make any physical maneuvers to get there you’d be at a serious disadvantage. 

 But then came the understanding that you might as well control it from afar, like in KID, and there was no disadvantage by not physically having the army in the center, at least up to a point ( where Black starts moving in with either ...e5 or ...c5–or else he appears to lose).

 

 So about the initial advantage, who really knows? It might be insufficient for a win or there may be no advantage at all and it ends up in a draw no matter what. Or if the initial position is a Zugzwang , the advantage is with Black and he wins with best play every  single time.

 

 

 

 

lfPatriotGames
troy7915 wrote:
lfPatriotGames wrote:
pawn8888 wrote:

Perhaps a perfect game would be for white to use it's slight opening advantage and play for a win, not making any mistakes. Black couldn't play a perfect game for a win because white would have to make a mistake first which would mean the game wasn't perfect. Maybe black's perfect game would be a draw.  

If blacks perfect game is a draw, wouldn't that mean whites perfect game is a draw too? I'm assuming in all cases both sides play with no mistakes. If white starts out with an advantage and plays for a win and black can't stop it, then blacks perfect game is always a loss and never a draw.

 

  But by the same token, the slight advantage at the beginning of the game for White ( which we don’t know for sure, but assume for a moment it’s a fact) may be insufficient for a win with best play by both sides, so that it ends in a draw no matter what.

 Or there was no advantage at the start of the game for either side. It’s like the hyper-modern openings. It used to be believed that occupying the center was the best method to control it, and thus if you didn’t make any physical maneuvers to get there you’d be at a serious disadvantage. 

 But then came the understanding that you might as well control it from afar, like in KID, and there was no disadvantage by not physically having the army in the center, at least up to a point ( where Black starts moving in with either ...e5 or ...c5–or else he appears to lose).

 

 So about the initial advantage, who really knows? It might be insufficient for a win or there may be no advantage at all and it ends up in a draw no matter what. Or if the initial position is a Zugzwang , the advantage is with Black and he wins with best play every  single time.

 

 

 

 

I dont disagree with any of that. That's why I said if. I was only considering that if white plays for a win (who doesn't) that it doesn't seem possible to have whites perfect result be a win but blacks perfect result be a draw. If blacks perfect game is a draw, then whites perfect result has to be a draw too. Or, if whites perfect game is a win, then blacks perfect result has to be a loss.

vickalan

Some mathematician (Ernst Zermelo) actually studied this. It sounds pretty simple, but his work was considered notable because it had some interesting conclusions. Basically, if White can force a win then Black cannot. And vice-versa. Or if neither can force a win, then both can force a draw.

So either chess is a draw, or one player can force a win. Sounds pretty simple.

It's funny that this thread is getting close to 4500 comments and nobody has solved it. And mathematicians haven't figured it out yet either. A crazy problem in game-theory!null

Elroch

I tell you something, after today's play, regardless of whether computers ever solve chess, I know I won't.

Zermelo's result from game theory that every finite deterministic 2-player game of perfect information (including chess) has a value is basically trivial.

Elroch
troy7915 wrote:
Elroch wrote:
troy7915 wrote:

 The length of the games matters in deciding what a perfect game is. If White wins in 55.000 moves with perfect opposition, then winning in 55.014 moves with perfect resistance by Black, means that somewhere he slipped up!

Not if you count 1 point for a win. There are no bonus points for being 14 moves quicker. According to the rules of chess, optimality is a matter of getting the right result, not the quickest way to that result.

 

  The point is that if you play a longer game you allow more chances for your opponent, by giving yourself more room for error. The longer the game lasts the more resistance  your opponent puts up with perfect play and the less perfect your moves are.

  We are talking about perfection here. Like the road from A to B, it is the most direct route between two points. It is even more obvious when the difference between the number of moves is reduced dramatically, to a reasonable number that can be played in a normal game, like from 55.000 to 79 moves.

 

 But that being said, I can see your point as well, where only the final result counts, and so a move would be perfect regardless of how it gets the job done.

We respect this principle all the time. If you miss a mate in 3 in your game and go into a winning ending to win 20 moves later, it is not a blunder, it is merely imprecise play. In fact sometimes you could easily argue that the longer route was easier, and it might be the correct one to play with limited time (if the other route would require a lot of analysis to get right). This is an example of where you choose an alternative metric to number of moves ("thinking time").

troy7915
vickalan wrote:

Some mathematician (Ernst Zermelo) actually studied this. It sounds pretty simple, but his work was considered notable because it had some interesting conclusions. Basically, if White can force a win then Black cannot. And vice-versa. Or if neither can force a win, then both can force a draw.

So either chess is a draw, or one player can force a win. Sounds pretty simple.

It's funny that this thread is getting close to 4500 comments and nobody has solved it. And mathematicians haven't figured it out yet either. A crazy problem in game-theory!

 

  Haha! ‘If White can force a win then Black cannot.’ Really? You need to study this as a mathematician to see it? 

 Of course if White can force a win from move one then Black cannot. And vice versa: if Black can force a win from move one then White cannot. And if neither can then what’s left? A draw, obviously. That doesn’t say much, unfortunately. 

troy7915
lfPatriotGames wrote:
troy7915 wrote:
lfPatriotGames wrote:
pawn8888 wrote:

Perhaps a perfect game would be for white to use it's slight opening advantage and play for a win, not making any mistakes. Black couldn't play a perfect game for a win because white would have to make a mistake first which would mean the game wasn't perfect. Maybe black's perfect game would be a draw.  

If blacks perfect game is a draw, wouldn't that mean whites perfect game is a draw too? I'm assuming in all cases both sides play with no mistakes. If white starts out with an advantage and plays for a win and black can't stop it, then blacks perfect game is always a loss and never a draw.

 

  But by the same token, the slight advantage at the beginning of the game for White ( which we don’t know for sure, but assume for a moment it’s a fact) may be insufficient for a win with best play by both sides, so that it ends in a draw no matter what.

 Or there was no advantage at the start of the game for either side. It’s like the hyper-modern openings. It used to be believed that occupying the center was the best method to control it, and thus if you didn’t make any physical maneuvers to get there you’d be at a serious disadvantage. 

 But then came the understanding that you might as well control it from afar, like in KID, and there was no disadvantage by not physically having the army in the center, at least up to a point ( where Black starts moving in with either ...e5 or ...c5–or else he appears to lose).

 

 So about the initial advantage, who really knows? It might be insufficient for a win or there may be no advantage at all and it ends up in a draw no matter what. Or if the initial position is a Zugzwang , the advantage is with Black and he wins with best play every  single time.

 

 

 

 

I dont disagree with any of that. That's why I said if. I was only considering that if white plays for a win (who doesn't) that it doesn't seem possible to have whites perfect result be a win but blacks perfect result be a draw. If blacks perfect game is a draw, then whites perfect result has to be a draw too. Or, if whites perfect game is a win, then blacks perfect result has to be a loss.

 

  Obviously, if White’s perfect play is a win then Black’s perfect play is always a loss, not a draw. 

 But move ‘perfection’ to move two on the White side, and Black might have a chance to draw or win.

troy7915
Elroch wrote:

I tell you something, after today's play, regardless of whether computers ever solve chess, I know I won't.

Zermelo's result from game theory that every finite deterministic 2-player game of perfect information (including chess) has a value is basically trivial.

 

  It is trivial in its own context, but not trivial in the context of the big picture, which here implies ‘solving chess’ , regardless of the findings of one person who cannot see the big picture and also speculates ( Zermelo speculates that the game cannot end in a draw, in order for either side to have a chance at winning—but that is a speculation as well, even if the first one is a fact, which is not).

Toxo94
[COMMENT DELETED]
troy7915

No need to be formal. Go right ahead.

troy7915
CP6033 wrote:

 in the next 30-40 years no, 100-200 who cares? i mean none of us will be alive then.

 

  In 30 years some of will, but that is highly unlikely.

Elroch
troy7915 wrote:
vickalan wrote:

Some mathematician (Ernst Zermelo) actually studied this. It sounds pretty simple, but his work was considered notable because it had some interesting conclusions. Basically, if White can force a win then Black cannot. And vice-versa. Or if neither can force a win, then both can force a draw.

So either chess is a draw, or one player can force a win. Sounds pretty simple.

It's funny that this thread is getting close to 4500 comments and nobody has solved it. And mathematicians haven't figured it out yet either. A crazy problem in game-theory!

 

  Haha! ‘If White can force a win then Black cannot.’ Really? You need to study this as a mathematician to see it? 

 Of course if White can force a win from move one then Black cannot. And vice versa: if Black can force a win from move one then White cannot. And if neither can then what’s left? A draw, obviously. That doesn’t say much, unfortunately. 

I said Zermelo's theorem was trivial, and our experience of the game of chess does make it seem so, but such things do need to be made precise and formally proven. To quote the wiki article:

"In game theory, Zermelo’s theorem, named after Ernst Zermelo, says that in any finite two-person game of perfect information in which the players move alternatingly and in which chance does not affect the decision making process, if the game cannot end in a draw, then one of the two players must have a winning strategy (i.e. force a win). It can alternately be stated as saying that in such a game, either the first-player can force a win, or the second-player can force a win, or both players can force a draw."

One reason it is worth treating it seriously is that every part of the assumptions is necessary. For the theorem to hold for a game, the game needs to be:

  • finite
  • two player
  • of perfect information
  • has alternate moves
  • is deterministic

Without any one of these assumptions, the theorem (or anything similar) won't hold.

prusswan

Humans will solve chess with the help of computers.

troy7915

To 4448:

 

Yes, I’d read that already and based my reply on it.

 

 The problem is that he begins with speculations:

 If the game cannot end in a draw...Then he is speculating about a winning strategy. If chess is solved, it’s just a matter of crunching numbers, that is a tactical matter , if, after , say, 10.000 best moves one side wins a piece... And finally, he speculates about both parties having a chance to force a win, without having the final picture. 

How can you prove all that? After all, when you start with a speculation (‘the game cannot end in a draw’ was one of the ifs) then the final result is bound to be a speculation as well. 

 

 This is like in math: 

 

 You can prove that 2+2=4, which is a theorem, but you cannot prove that 1+1=2, which is an axiom! 

 

 In other words, if you don’t accept the axiom as being true, then the theorem cannot be demonstrated.

chessspy1

 but you cannot prove that 1+1=2, which 

I think this statement is incorrect:

You are thinking of the Principia Mathematica, written by Alfred North Whitehead and Bertrand Russell. Here is a relevant excerpt: As you can see, it ends with "From this proposition it will follow, when arithmetical addition has been defined, that 1+1=2

Elroch

Every axiom is a theorem, just a very trivial one, so the claim "You can prove that 2+2=4, which is a theorem, but you cannot prove that 1+1=2, which is an axiom!" is not actually true.

To make it a theorem that is not an axiom, you just need to move your axioms a bit. wink.png

Chesseract557
CP6033 wrote:

 in the next 30-40 years no, 100-200 who cares? i mean none of us will be alive then.

But it's likely that your descendants will.

This "100-200 years who cares?" mindset is highly illogical. After all, chess is 1,500 years old. If all the chess grandmasters of the past had those same mindsets, it would be highly unlikely that chess would survive into the present day. If the people of India at the 6th century said: "Who cares about what happens 1,500 years later?" we wouldn't even be here in the first place because chess would either never have existed or would simply die out before the 15th Century or something.

And who knows? Maybe some day modern tech will find a way to make humans have 200-year lifespans.

troy7915
Elroch wrote:
troy7915 wrote:
Elroch wrote:
troy7915 wrote:

 The length of the games matters in deciding what a perfect game is. If White wins in 55.000 moves with perfect opposition, then winning in 55.014 moves with perfect resistance by Black, means that somewhere he slipped up!

Not if you count 1 point for a win. There are no bonus points for being 14 moves quicker. According to the rules of chess, optimality is a matter of getting the right result, not the quickest way to that result.

 

  The point is that if you play a longer game you allow more chances for your opponent, by giving yourself more room for error. The longer the game lasts the more resistance  your opponent puts up with perfect play and the less perfect your moves are.

  We are talking about perfection here. Like the road from A to B, it is the most direct route between two points. It is even more obvious when the difference between the number of moves is reduced dramatically, to a reasonable number that can be played in a normal game, like from 55.000 to 79 moves.

 

 But that being said, I can see your point as well, where only the final result counts, and so a move would be perfect regardless of how it gets the job done.

We respect this principle all the time. If you miss a mate in 3 in your game and go into a winning ending to win 20 moves later, it is not a blunder, it is merely imprecise play. In fact sometimes you could easily argue that the longer route was easier, and it might be the correct one to play with limited time (if the other route would require a lot of analysis to get right). This is an example of where you choose an alternative metric to number of moves ("thinking time").

 

  Forget about ‘analysis time’, for the time required to do all this is of astronomical 

proportions. In practice, you would have to do this:

 

 From White’s point of view, you would choose a move, any move. Then exhaust all Black’s replies and then White’s until the end—a huge number of possibilities. 

 But let’s just say that at move 10, you are examining the first move for White. Now you would have to thoroughly examine all the replies by Black and White all the way to end, to declare it a perfect game. That’s for White, which had the first move. Starting with another move, who knows? Black might have had a forced win—although that is not a perfect game, since White began with a losing move. 

 

But this is a perfect game for White. And no matter when you repeat that procedure, at move 10, 9, 8, or 22, all Black’s replies must be analyzed, along with all White’s replies to those replies, all the way to the end.

 

 One time it’s allowed, to not analyze all the moves, but from that move on all the permutations must be exhausted, in order to claim a perfect game.

 After the first random choice, all permutations must be tried on both sides. The analysis time for such a task, oh boy, I wouldn’t even know how to begin to express it!

 So one incomplete analysis is allowed: it doesn’t matter if , say, 10. Qh4 hasn’t been analyzed—if 10. Qh3 leads to a forced win then it’s a perfect game. But that is only permissible to White!

 

 Black is allowed no such incompleteness. 10. Qh4 must be analyzed as well, in order for Black to claim a perfect game.

 This includes the very first move, where missing one White move doesn’t yet allow Black to claim a perfect game, since there is still a possibility that White could have played better, on the very first move!

 As for draws to be considered perfect games (regardless of the number of moves), it first has to be ruled out that there are no forced wins on either side, which brings us back right where we started, analysis-wise!

troy7915
Elroch wrote:

Every axiom is a theorem

 

 

 Not quite. A theorem can be demonstrated, while an axiom is a statement accepted as a fact without demonstration.

 

 A theorem can be demonstrated. An axiom cannot.

 

  Which is why, without accepting the fundamental equation that 1+1=2 as true, you cannot demonstrate that 2+2=4, 3+3=6, and so on.