most recent 30 from http://mathoverflow.net 2013-05-23T22:58:05Z http://mathoverflow.net/feeds/question/50711 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50711/how-long-is-the-longest-path-in-the-game-tree-of-chess Zirui Wang 2010-12-30T09:23:14Z 2010-12-30T21:05:56Z

<p>I can only think of an upper bound, which consists of all configurations and so has length 5⁶⁴. 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.</p> <p>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.</p>

http://mathoverflow.net/questions/50711/how-long-is-the-longest-path-in-the-game-tree-of-chess/50720#50720 Bhalchandra D Thatte 2010-12-30T12:40:49Z 2010-12-30T12:40:49Z

<p>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.</p>

http://mathoverflow.net/questions/50711/how-long-is-the-longest-path-in-the-game-tree-of-chess/50725#50725 Joel David Hamkins 2010-12-30T13:41:40Z 2010-12-30T13:41:40Z

<p>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. </p> <p>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.</p>

http://mathoverflow.net/questions/50711/how-long-is-the-longest-path-in-the-game-tree-of-chess/50727#50727 sleepless in beantown 2010-12-30T13:56:20Z 2010-12-30T14:25:01Z

<p>A long comment, too long and painstakingly difficult to keep re-editing in the comment boxes:</p> <p>If you don't <strong>require</strong> 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. </p> <p>It may be the concept of {white pawn, white other, black pawn, black other, empty}$^{64}$, which has a set size of $5^{64}$. </p> <ul> <li><p>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.</p></li> <li><p>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. </p></li> <li><p>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.</p></li> </ul>

http://mathoverflow.net/questions/50711/how-long-is-the-longest-path-in-the-game-tree-of-chess/50759#50759 Ross Millikan 2010-12-30T21:05:56Z 2010-12-30T21:05:56Z

<p>In <a href="http://www.tomshardware.com/forum/48906-13-longest-chess-game" rel="nofollow">this post</a> 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. </p>