6
$\begingroup$

I can only think of an upper bound, which consists of all configurations and so has length $5^{64}$. 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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Aaron Meyerowitz Dec 30 '10 at 10:07
  • 3
    $\begingroup$ You might want to explain why $5^{64}$ is (an upper bound of) the number of all configurations. $\endgroup$ – Did Dec 30 '10 at 11:24
  • 7
    $\begingroup$ 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 $\endgroup$ – sleepless in beantown Dec 30 '10 at 14:05
  • 5
    $\begingroup$ @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. $\endgroup$ – Pete L. Clark Dec 30 '10 at 14:34
  • 5
    $\begingroup$ 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. $\endgroup$ – Pete L. Clark Dec 30 '10 at 14:36
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Zirui Wang Jan 1 '11 at 14:09
  • 1
    $\begingroup$ My point was that we expect that either player would gain winning advantage by ending the cooperation. $\endgroup$ – Joel David Hamkins Jan 26 '11 at 13:39
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – sleepless in beantown Dec 30 '10 at 14:10
  • $\begingroup$ @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. $\endgroup$ – Did Dec 30 '10 at 14:10
  • $\begingroup$ @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. $\endgroup$ – sleepless in beantown Dec 30 '10 at 14:23
  • $\begingroup$ In my comment above, "promotion" should be "move". $\endgroup$ – Did Dec 30 '10 at 14:49
4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Orange Dec 31 '10 at 15:17
  • 1
    $\begingroup$ @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. $\endgroup$ – Ross Millikan Dec 31 '10 at 21:18
4
$\begingroup$

Apparently to avoid perpetual check, a rule was initially set such that a sequence of moves that repeats three times will be declared a draw.

A recent nice video by James Grime and Rune Friborg notes that in the 1920's mathematician and chess grandmaster Max Euwe showed that players can engage to create a set of moves corresponding to the Thue-Morse sequence, such that no sequence of moves will be repeated three times.

For example:

  • call "white moves a left piece, black moves a left piece" $0$;
  • call "white moves a right piece, black moves a right piece" $1$;
  • have the players play a set of moves such as $0110100110010110...$ according to the Thue-Morse sequence.

Thus there would never be a sequence of moves that repeats three times. Cooperative play would never accidentally lead to a win. Indeed there might be a position wherein the best move for white is to check black with either a left ($a-d$ file) or right ($e-h$ file) rook, and for black to respond by checking white with either a left or right knight.

However, of course there would be a position that repeats three times, even if players cooperate - hence the the change in the rules.

$\endgroup$
  • $\begingroup$ There is also the 50 move rule. If 50 moves by each side have been played without a pawn move or capture either player may claim a draw. The idea is that pawn moves and captures represent irreversible changes, avoiding the infinite string you describe.The rule is voluntary, but I think it is in the spirit of the question to require the draw at that point. $\endgroup$ – Ross Millikan Feb 10 at 19:15
  • $\begingroup$ @RossMillikan indeed, I guess we can say "throw a bunch of black and white pieces onto an $8\times 8$ board, and have them move randomly according to the rules of chess. What is the mean recurrence time?" I suspect it is much more than $50$. $\endgroup$ – Mark S Feb 11 at 0:43
  • $\begingroup$ I don't think that matters. When the rule was made (I am guessing) it was assumed that if you can't make progress in $50$ moves you can't make progress at all. There are a number of endgames known where it takes more than $50$ moves to make the capture you need. For a number of years there was a loophole that if the position was known to require more than $50$ moves you got more, but it got too complicated and was removed. There are positions that would be won for one side without the $50$ move rule that are draws by the official rules of chess. $\endgroup$ – Ross Millikan Feb 11 at 4:39
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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