• Quick note - the problem with Youtube videos not embedding on the forum appears to have been fixed, thanks to ZiprHead. If you do still see problems let me know.

Solving Chess

In this case the part of me that adores chess is in conflict with the part of me that adores mathematics.
 
This was a homework problem back when I was studying quantum computing on Planet X. White wins in 58 moves against blacks's best defense.

IXP
 
Has anyone solved sex yet?
Similar to chess in many ways and, as Robinson said, most of the positions are bad ones.
 
plumjam said:
Has anyone solved sex yet?
Similar to chess in many ways and, as Robinson said, most of the positions are bad ones.
Click to expand...

You gotta admit people are quite more eager to actually solve it than Chess, and I honestly think it'll be solved first.

I didn't know that people enjoyed/discussed chess here. This kind of topic comes along often?
 
Arthur Denton said:
I believe it could, but solving chess is not really useful, is it? except, perhaps, if you're a crazy chess player who thinks that will save your soul in the end, or that maybe god, in its infinite anger will actually save you and burn the rest of the humans, because the rest of us would be whatever.
Click to expand...

Not necessarily. Solving chess would not be useful in itself, but as a computing and mathematics problem it could be very useful, since the tricks required to solve a problem like chess will almost certainly be applicable elsewhere. Deep Blue, for example, certainly wasn't useful in itself, but IBM obviously thought that the experience of building and programing it was worth the time, money and effort put into it.

A good example that I'm familiar with would be graphics cards. In general, they really have no use, they simply allow people to have games that look a bit better. But it's recently been realised that the techniques used to process games are very similar to those used in finite element analysis. There are now GPUs designed specifically for simulations, and seems quite likely that many future super computers will be built around GPUs rather than CPUs. Without the "useless" computer games industry, this would probably never have happened. We may not know what benefits would come from solving chess, but we can be pretty sure that there would be benefits.
 
SeanDamnit said:
I'm not too keen on how this all works, so forgive me if this sounds silly, but if bad positions are eliminated - positions that wouldn't come up given perfect play, or at least some level of competent playing - would we be able to reach statements like "Given perfect play, white (will always win, can force a draw, will always lose)"....
Click to expand...

If you are satisfied with that sort of a statement then you can conclude that given perfect play on the part of both white and black that one of the following statements is true

White will always win.
Black will always win.
The game will always end in a draw.

This is a general theorem from game theory. The problem is that the proof provides no means of deciding which of the three statements is correct.
 
I actually expect it to be a mix, something like:

If white opens with ___ , perfect play on both sides leads to tie.
If white opens with ___ , black can force a win.

Which technically makes the former really the only example of "perfect play".
 
Folly said:
Assuming chess has roughly 10^40 reachable positions, this would mean that the proof tree needed around 10^20 positions. This is "only" a million times larger than the checkers proof tree, which involved around 10^14 positions. Of course, the skeptic will cry "but the checkers proof was 10 thousand times larger than the square root! Why expect chess to be done in 10^20?!" And they would be entirely right. Barring some new clever ideas, or very large increases in computational power and storage space, chess is pretty much right out.
Click to expand...

Correction: a classical computer would be able to evaluate an N= 10^40 position game by evaluating only about (N)^0.75 = 10^30 positions. Eddie Farhi recently showed that a quantum computer could do it by evaluating only (N)^0.5 = 10^20 positions; IIRC he further showed that this was the best possible quantum algorithm.

http://arxiv.org/abs/quant-ph/0702144
http://scottaaronson.com/blog/?p=207

The only thing such a computer would tell you is "there exists/does not exist a guaranteed win for white/black." It doesn't tell you what the winning decision tree actually is.
 
SeanDamnit said:
Black always wins
Click to expand...
Nice one. Had that "delayed reaction" response.

Anyway, I can't wait for them to solve chess. I used to play and I'm sick of how much memorization there is in it. Random chess is a far superior game and apparently the universe will burn out before we could ever solve all the variations there.
 
ben m said:
Correction: a classical computer would be able to evaluate an N= 10^40 position game by evaluating only about (N)^0.75 = 10^30 positions. Eddie Farhi recently showed that a quantum computer could do it by evaluating only (N)^0.5 = 10^20 positions; IIRC he further showed that this was the best possible quantum algorithm.
Click to expand...

Nice!

Thanks - I didn't know about that. Eddie's a smart guy...
 
gnome said:
I actually expect it to be a mix, something like:

If white opens with ___ , perfect play on both sides leads to tie.
If white opens with ___ , black can force a win.

Which technically makes the former really the only example of "perfect play".
Click to expand...

My understanding is that most theoreticians expect chess to be a forced win for white. (Assuming, of course, that white makes one of her many optimal opening moves, at least one of which will be demonstrated in the course of the proof.) It is actually highly unlikely that every position will be analyzed in the course of generating such a proof -- precisely because if we learn that white has a win starting from 1. e4 ... , then there's no need to examine the positions arising from 1. a3 ... or 1. Na3 ....

Oddly enough, if chess is a draw, the proof is actually much harder, precisely because the proof will require looking at such "silly" lines of play on both sides.
 
drkitten said:
My understanding is that most theoreticians expect chess to be a forced win for white. (Assuming, of course, that white makes one of her many optimal opening moves, at least one of which will be demonstrated in the course of the proof.) It is actually highly unlikely that every position will be analyzed in the course of generating such a proof -- precisely because if we learn that white has a win starting from 1. e4 ... , then there's no need to examine the positions arising from 1. a3 ... or 1. Na3 ....

Oddly enough, if chess is a draw, the proof is actually much harder, precisely because the proof will require looking at such "silly" lines of play on both sides.
Click to expand...

From a theoretical perspective things will be a lot more interesting if a proof of any case can be found that proceeds by some technique other than an exhaustive evaluation of a gigantic tree of possible moves. Such a proof would give new insight into game theory.

A gigantic computer evaluation of a huge number of possibilities may solve the question for the game of chess but might not be all that illuminating. The technique will probably be of more interest than the actual result.

And if there turns out to be any sort of reasonably implementable algorithm it will kill the game. That is doubtful given the long history of the game, but not impossible. I would hate to see a wonderful game killed by a boring proof.
 
drkitten said:
My understanding is that most theoreticians expect chess to be a forced win for white.
...
if chess is a draw, the proof is actually much harder, precisely because the proof will require looking at such "silly" lines of play on both sides.
Click to expand...
Wouldn't it be more accurate then, to say that most theoreticians PRAY that chess is a forced win for white? :)

Especially if it's like tic tac toe and it's a forced win for black due to being able to choose a proper response to whatever move white begins with.
 
Tic Tac Toe isn't a forced win for the second player.

Either player can force a tie if they play correctly.
 
Chess is solvable in theory, even if we lack the computing power to do it. The comments earlier in the thread about how we'll never be able to do it remind me of those famous comments from the middle of the last century about the limitations of computing power. Like some of these.

But chess is solvable, which really makes it just a really complicated version of checkers, which really is in turn just a really complicated version of tic tac toe. Which is why backgammon is the better game.
 
You must log in or register to reply here.

Back
Top Bottom