Welcome to NRICH.

 
Analysis of Chess
By Alexander Maryanovsky<</B>:

I've seen a mathematical proof that chess is a game with a forced win for white in one of the Technion magazine ("Etgar") editions. I was wondering if you know of an article regarding that matter online (or maybe can prove this yourself, hehe, or give me some pointers on how to "solve" games) ?

Thanks a lot, Alexander Maryanovsky.

By Anonymous on Thursday, November 25, 1999 - 02:27 pm:

Chess has not been solved mathematically, it is not a forced win for white, you've been had.

By Anonymous on Thursday, November 25, 1999 - 03:05 pm:

I really hate posts like that. If I say I have seen a proof of it, then I have! And the Technion is one of the leading universities in Sciences in the world, so they would not publish something unchecked.

By Alex Barnard (Agb21) on Thursday, November 25, 1999 - 06:07 pm:

Look --- both these posts are not that helpful. The second doesn't give any information about how you know it hasn't been solved or why it might even be likely that it hasn't. As for the third 'if I say I have seen a proof of it, then I have!' doesn't hold much water unless you have understood it. Don't believe that something published must be true (there are MANY examples of mistakes in publications even from the best journals) and also if you have not understood the proof yourself then you may not have understood what was being proved. If you can find the paper again and send details I'd be most grateful.

Now for some facts:

Chess is a game with extremely complicted rules - most solved games only have one or two and generally all the pieces look and move similarly. However chess has loads of different rules and nasty things like promotion, en-passant, move limit for draws, etc.

After only around 10-20 moves of chess the number of positions is vastly larger than the number of atoms in the universe. So a computational proof is just not possible at the moment. Again it might be possible to mathematically reduce it to a size that can be hit with a computer but see above for why this is unlikely.

Draughts (or chequers) has not been solved and it is a game that is vastly less complicated than chess. Only recently nine-mens-morris has been solved by computer and this is extraordinarily less complicated than chess.

If someone had published a proof of chess it would be absolutely enormous. Every university in the world would have heard, Technion would have it plastered all over their web page, it would have made national press and people I know working on game theory would have heard. None of these have happened so it is EXTREEMLY unlikely to have been proved.

Someone may have proved that chess is not a second player win (notice this is not the same as being a first player win) but the same reaction would have been felt. So again unlikely.

Now for some possible other things this paper could have said. The paper may have been a proof of first player win from some specialised situations. Or some numerical evidence that it could be likely that chess is a first player win. Etc...

I spent a long time this afternoon looking at electronic citation systems for maths/computing journals and there are no papers on chess being a first player win. Again it is possible that this journal is not in the lists but I'd be shocked.

Okay that is enough about the specific case of chess --- if I find out any more I'll write back.

Now, if you want some books on how to do game theory then the best ones I can recommend are:

  • Winning ways parts I+II by Conway
  • On numbers and games also by Conway
The first is much more fun and has loads of examples and pictures. The second is much more high level and mathematical.

AlexB.
By Dan Goodman (Dfmg2) on Friday, November 26, 1999 - 01:33 am:

No offence intended, but is it necessarily true that if you can't explicitly list (or compute) the entire tree of chess then you can't say whether or not white can always win? I don't think so. It seems perfectly reasonable to suppose that there could be an argument that could show that (in principle) there is an algorithm (which could easily involve practically impossible computations) which would result in a definite win for white. This sort of argument is what makes mathematics different from computer science for instance. In the former, showing the existence of something can be enough. In the latter, you would actually have to work it out. For instance, we know 1010000000+7 has a prime factorisation, although we can't find it in practice.

By Anonymous on Thursday, November 25, 1999 - 10:16 pm:

Ok, well, first, thanks for the info...now that I think about it, I become more skeptic too. You are right, I didn't understand the proof, as I was 13-14 years old at the time and didn't know much math.
About the complexity of games - though some game may be very complex and have many many rules, a certain "rule" or "feature" of the game may decide the outcome regardless of the other rules.
Regarding Technion plastering it all over their webpage - I'm not sure when the Technion put up their site, but the proof I saw quite a while ago, about 4-5 years ago. Also, I think they haven't updated their site for about a year or so.
After reading your post, I do feel more skeptical now, but I still know that I did read something extraordinary about proving chess, and the proof itself was quite long, several pages.
Do you know if perhaps Technion puts old issues of "Etgar" on the net? Because I wasn't able to find anything like that, if not, I guess I will HAVE to go through their library next time I am in Haifa.

By Alex Barnard (Agb21) on Friday, November 26, 1999 - 11:19 am:

In response to Dan:

Nowhere did I say that there isn't a proof not involving computers. But I did give lots of reasons why chess is very likely to be too complicated for this type of arguement. It does not currently seem reasonable that there is a mathematical arguement on the game of chess due to its rule complexity. There are great difficulties when a game rule can depend on the previous rule (ie. en passant) or even worse in chess on the previous 40 (ie. endgame draw). Again I look forward to being proved wrong (because solving chess would be a fantastic feat) but I'm very dubious at the moment.

In response to Alexander. I guess that a proof would be vastly more than a couple of pages (it would take about that long to contain the abstract and definitions). There are algorithms that computers use to play chess (called, I think, alpha and beta trimming) which allow one to quickly eliminate branches from a tree search and so concentrate more on the correct ones. This paper could have been one on this subject --- infact it may well have been the paper which invented one of these methods or another that I don't know about. I haven't found any copies of Etgar on the web but it should have had its articles in the citation index I was using. If you could let us know what you find out from the library - I would be VERY interested.

Finally, you are right about a rule or feature deciding the game of chess. I believe that the current best idea in the area is that the rules on drawing (move limit / position repeating) will mean that chess is actually a draw. I think there is some evidence from current matches and the IBM Deep Blue. Not that empirical evidence means much...

AlexB.

By Alexander Maryanovsky on Friday, November 26, 1999 - 03:44 pm:

I'm a programmer, and I write chess programs, so I do know what AlphaBeta algorithm is, the article was not about algorithms to improve and deepen the search tree. I think for the purpose of solving chess, we could easily drop the 50 moves rule, the en passant move, perhaps even castling. The 3-fold repetition rule is irrelevant here, because if we prove there is a winning line, there will not be repetitions in it.
Again, in order to solve a game, you don't need to consider all its rules, one rule may give you the outcome and all the others may prove to be quite irrelevant.
I don't believe that any empirical results in the chess world can give us any kind of sign of the outcome. These are just humans that play a game. As for computers, I hope I'm not mistaken, but Deep Blue calculated 18-19 plies in the middlegame (again, I could be wrong), not nearly enough to give an estimate.
I will try to look up that issue of "Etgar", I'm supposed to go to the Technion in about a week and a half, and I will try to sneak away into the library :-)

By Alex Barnard (Agb21) on Friday, November 26, 1999 - 05:10 pm:

The three repeat rule is not irrelevant. It may just be possible that the second player can play so as to force a loop and therefore draw. But it is very unlikely.

I do agree that one rule may be dominant - but you have to admit that it doesn't look likely in chess that the way one of the pieces move solely determines the outcome of the game!!

Empirical results normally give indications as to what may or may not be true. If the vast majority of games of chess played end in a first player win then people would believe that it was probably a first player win. The fact that we aren't playing perfectly doesn't stop this information making it more believable that the outcome is a certain way. Mathematicians believe things like the Riemann hypothesis because the first 10^40 cases have been checked. This is as nothing compared to the infinite number that need to be checked - but it hints that the result is possibly true.

Don't underestimate experimentation... most results in mathematics come first from empirical data. Things are much easier to prove if you have some evidence which way you should look!

AlexB.

By Alexander Maryanovsky on Friday, November 26, 1999 - 11:53 pm:

Ok, one thing I still don't understand, why is the 3-fold repetition move relevant? If there is a winning sequence (or rather a tree), then each move will make a progress towards the victory, thus repeating will never happen since we assume there is a finite number of moves in that sequence.

By Jonathan Kirby (Pjk30) on Saturday, November 27, 1999 - 08:19 pm:

I think that the 3-fold repetition move is not relevant to whether or not
there is a forced win, but it is relevant to whether or not it is a forced draw.
It may be the case that white can force a postion in which, with the
repetition rule, black can force a draw, but without it can only force an
infinite cyle, and that if black breaks the cycle then white can force a win.
This is not technically a forced win for white, but it might be a solution to the
problem.

Jonathan Kirby