Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I can only think of an upper bound, which consists of all configurations and so has length 564. If the true value is intractable, we may give up solving chess. But if it's small, there still could be a fast algorithm to solve chess.

I say give up because I'm still thinking of traversing the game tree. But this may not be required on a second thought. Anyway I think this question is still interesting theoretically.

share|improve this question
1  
What about the game tree for when white has all 16 pieces and black has just 4 or 5 pieces (or even just a king). That might be huge as well but I'm sure fast algorithms exist. –  Aaron Meyerowitz Dec 30 '10 at 10:07
1  
You might want to explain why $5^{64}$ is (an upper bound of) the number of all configurations. –  Did Dec 30 '10 at 11:24
5  
Why the down-votes without comments or explanations? It's an interesting question, even if it is poorly formed and not rigorously defined, and does not explain the question asker's belief and reasoning behind why he posits that $5^{64}$ is the upper bound on "all configurations"? It's easy to think of reasons to criticize the question; so I find it sad that people are down-voting without taking the effort to leave a comment. And why not leave feedback allowing the original poster to edit and improve the question? There's no reason to pile on down-votes indiscriminately –  sleepless in beantown Dec 30 '10 at 14:05
3  
@sleepless: you have given several sufficient reasons for a downvote. Here are two more: (i) the only tag on the question is "chess", which seems to indicate that it is borderline off-topic for the site. (ii) as you say, exactly what the OP means to ask is not so clear, but I think the question is equivalent to "What is the longest possible game of chess?" This is not a new question or an especially mathematically interesting one. Moreover it depends upon the precise rules, but if you take FIDE rules many sources give the answer 5949. –  Pete L. Clark Dec 30 '10 at 14:34
3  
P.S.: As a former tournament chess player, I am quite confident that this question has nothing to do with solving the game of chess: Joel's answer explains why. –  Pete L. Clark Dec 30 '10 at 14:36
show 10 more comments

4 Answers 4

The longest path in the game tree very likely arises from the two players cooperating merely to make a very long game, rather than trying to win, and therefore seems little related to finding a winning strategy.

Very long games, for example, could arise if each player should simply move their knights around the board as much as possible, not capturing anything, but staying within the bounds of the triple repetition stalemate rule (and the 50 move rule for moving a pawn or capturing, if you intended that rule to be included). Such a strategy would produce very long games, but there seems little reason to expect that this way of playing has much to do with winning.

share|improve this answer
    
But in calculating a winning strategy, especially the perfect strategy, you need to be comprehensive. You can't be short sighted. Even the cooperative behaviour could lead to a win. You need to check that out. –  Zirui Wang Jan 1 '11 at 14:09
    
My point was that we expect that either player would gain winning advantage by ending the cooperation. –  Joel David Hamkins Jan 26 '11 at 13:39
add comment

A long comment, too long and painstakingly difficult to keep re-editing in the comment boxes:

If you don't require a draw to be declared, there are multiple scenarios in which king vs. king or (king+queen) vs. (king+queen) can play on infinitely; in that case, the game tree of chess is unbounded. There must be a strict rule for when to prune a branch in the game tree. @Didier-Piau, the upper-bound concept as posited by the poster of this question appears to have 3 mistakes in it.

It may be the concept of {white pawn, white other, black pawn, black other, empty}$^{64}$, which has a set size of $5^{64}$.

  • This makes the mistake of lumping all of the pieces into $4$ categories. Even if you define the pieces to be {Black, White} $\times$ {Pawn, Queen, King, Rook, Knight, Bishop}, and allow for an empty space, then $13^{64}$ would be a better (but still grossly overlarge) upper-bound on the number of chess board configurations as it included multiple implausible configurations with an impossible count of pieces. A better guess might be the combinatorial (64 choose 32) + (64 choose 31) + ... (64 choose 1), and that can be pruned in many ways such as if the last board position has only one piece in it, then that last piece could only be the winning side's king, etc.

  • It makes the mistake of conflating the number of possible positions or "boards" of a chess game with the number of paths through these possible boards; this is equivalent to the error of confusing the number of vertices in a directed graph with the number of paths leading out from a starting vertex.

  • And it makes the error of not being rigorously defined: for example, defining the tree correctly, as the tree starts out from a fixed board position.

share|improve this answer
    
I meant to say "the total number of paths which being at a fixed starting vertex" which can be much much larger than the number of vertices, not "the number of paths leading out from a starting vertex" which sounds like it is limited to "the outdegree of the starting vertex". Alas, poor rigour in my own statements. –  sleepless in beantown Dec 30 '10 at 14:10
    
@sleepless: thanks for your answer, which explains (and refutes) the mysterious (to me) number $5^{64}$ mentioned by the OP. A comment: the tree of chess is finite. This is due, inter alia, to the so-called 50-moves-rule (also mentioned by Joel David), which stipulates that after 50 moves during which no piece was taken nor any promotion of a pawn occurred, the game must be declared a draw. –  Did Dec 30 '10 at 14:10
    
@Didier-Piau, I'm only guessing as to the original poster's intent or thoughts, but considering the confusion in the question between paths on a directed graph and the number of vertices, I surmised that the mistake came from something like that. Thanks for pointing out the specific branch-pruning rule; I like Joel's comment about how it's possible for two colluding (or clueless) players to keep the game going longer pointlessly. –  sleepless in beantown Dec 30 '10 at 14:23
    
In my comment above, "promotion" should be "move". –  Did Dec 30 '10 at 14:49
add comment

In this post a claim of 11799 is made, assuming the 50 move rule is interpreted as forcing a draw, and then the moment there is not sufficient mating material the draw is called.

share|improve this answer
1  
I must clarify that some people define a move as a single move by one player and most chess players define a move as a single move by both players. Your link considers the first definition. To get the same rough number as other sources just divide this number by 2. –  Orange Dec 31 '10 at 15:17
    
@Orange: you are correct. The 11799 will correspond to the depth of the tree, as each layer of the tree is one ply, or one half-move. –  Ross Millikan Dec 31 '10 at 21:18
add comment

Just a speculative thought: The density of the end positions may be of theoretical interest, and may be quite high. One estimate could be obtained by placing black/white king in one corner mated by just a couple of pieces, and then counting the configurations of the remaining pieces, which suggests that the density may be quite high, and there may be lots of end positions within a short distance from almost any position, which further suggests that chess may be quite easy at least in practice. Moreover, if there are sufficiently many end positions near the starting position, then it may be possible to solve the game looking at a subtree.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.