Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Exact number of possible chess games

  1. Dec 29, 2013 #1
    I've googled this and it appears that there doesn't seem to be an exact number of games. Assume that no illegal moves are allowed, peices must start in their correct squares and each game lasts a total of 40 moves.

    Is there a way to work out exactly how many 40 move games exist? There are a few different upper bounds but they include illegal moves, pawns on the first rank and kings on adjacent squares ect.

    Any particular reason why there are only estimations on the number of games? I guess it's pretty difficult to work out exactly how many games exist...
     
  2. jcsd
  3. Dec 29, 2013 #2

    Pythagorean

    User Avatar
    Gold Member

    Technically, two people could get into a loop and repeat the same moves over, or go back and forth, or return to a previous board state some other way. So it's essentially recursive (potentially infinite).
     
  4. Dec 29, 2013 #3
    I agree for an unlimited number of moves, but with a 40 move limit it certainly appears finite.
     
  5. Dec 29, 2013 #4

    Nugatory

    User Avatar

    Staff: Mentor

    If the same position is reached three times (the definition of "same position" is not completely trivial, but it's there and unambiguous) the game is a draw, so there are a finite number of chess games.
     
  6. Dec 29, 2013 #5
    Your requirement that each game lasts a total of 40 moves is strange, I guess you meant no more than 40?

    I agree with Pythagorean, although regarding loops note the rule making a draw claimable upon three-fold repetition of a position. I don't think you can avoid the requirement to analyse each new position you generate for legality, to see whether it has already occurred twice, or to see whether it's checkmate or stalemate and terminates the game prematurely. To do all this from the opening position is probably beyond us at present, considering our tablebases are only at seven right now: http://en.wikipedia.org/wiki/Tablebase

    http://mathworld.wolfram.com/Chess.html has some links to relevant literature, though I guess you probably found this already.
     
  7. Dec 29, 2013 #6

    Nugatory

    User Avatar

    Staff: Mentor

    That's why there are only estimates: It's pretty difficult to work out an exact answer. Indeed, there is no known way of calculating it that is appreciably less work than systematically enumerating all possible games, and that's a rather computationally daunting problem.
     
  8. Dec 29, 2013 #7
    Yes I did mean that no game can go on past the 40th move otherwise the game is a stalemate. Also I guess you could have 2 players loop the same two moves but it doesn't matter because upon the 40th move the game is a stalemate.
     
  9. Dec 30, 2013 #8

    jbriggs444

    User Avatar
    Science Advisor

    The actual rule appears to be that a draw may be claimed after 50 moves without a capture or the movement of a pawn.

    There being 16 pawns able to move 6 spaces each and 30 pieces that can be captured, it is possible for legal games to continue to thousands of moves, even if the players declare a draw at the first opportunity.
     
  10. Dec 30, 2013 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The answer to the original question is that the number of legal moves in any position varies depending on the position. So, you can only estimate this for more than a few moves ahead.

    There are just too many factors governing the number of legal moves in any position: how many pawns are blocked, how many pieces have been taken, whether there's a check.

    All you can do is estimate the average or maximum number of moves and raise that to the power of 80 or whatever.

    To get an exact figure you would have to go through every possible game.
     
  11. Dec 31, 2013 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's not hard to calculate the longest legal game. Each player would play 50 moves before a pawn is moved or a piece taken: athough, in order to get the pawns past each other, they have to capture. Half the pawns have to do this, so that's 8 pieces that need to be captured.

    Each pawn could then move 6 times: 96 moves. That leaves 22 more pieces to be captured. So, the longest game is about 50*118 moves each.

    I make it 0.5 + 49.5*118 to be exact. The game would end at that point, as you don't have to play out 50 moves with two Kings.

    So, the game would end on white's 5,842nd move!

    But, of course, the 50-move rule only allows either player to claim a draw. In practice, two players could go on playing beyond this.
     
    Last edited: Dec 31, 2013
  12. Jan 3, 2014 #11
    No, there's no good way of doing this besides having a computer enumerate all the possibilities. This is actually a common test that chess engine programmers use to verify correctness of their move-generation routines. From the initial position people have used computers to answer your question for games of up to 13 half-moves: see http://chessprogramming.wikispaces.com/Perft+Results. Apparently the number of possible games of 13 half-moves is 1,981,066,775,000,396,239.
     
  13. Mar 16, 2014 #12
    Actual maximum number of possible moves in a chess game

    Assuming the 50-move rule is enforced, every 50th move would have to be either a pawn move or capture. This would make move #5900 the final move.
    But there is an exception to the 50-move rule in certain endgame positions. For example, a King, Rook & Bishop can force checkmate against a King & Rook. However, computers have calculated that even with perfect play against perfect defense, it cannot be accomplished in fewer than 54 moves. In these special situations, players are allowed 100 moves. So for the absolutely greatest number of moves in a chess game, it would be Black either checkmating, stalemating or drawing by the 50-move rule on his 5,950th move.
     
  14. Mar 17, 2014 #13

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's 49.5 moves not 50, because white and black have to alternate the pawn and capture moves. Also, FIDE has removed to 50+ rule as computers were finding more and more such positions.
     
  15. Mar 17, 2014 #14
    Don't BOTH players have to complete 50 full moves before a draw can be called? In other words, would it NOT be a draw, if for example:
    1. ... ...
    50. ... a6
    100. a3 ...
    150. ... b6
    200. b3 ...
    etc. ?

    Also, what is the exact FIDE rule concerning this?
     
  16. Mar 17, 2014 #15
    Try this:
    http://en.wikipedia.org/wiki/Threefold_repetition

    You're not going to be able to solve it using pen and paper. The problem is a computational one and you're going to be looking to use the current state of the board as a way to merge branches to reduce complexity by taming the exponential growth.

    If you're familiar with a programming language, you could try to solve it. It's an interesting challenge. I'd start by working out a way to create an efficient hash of the current disinguishable state of the board. This part is an interesting challenge in itself. Then branch on each move checking to see if you've seen that state before, either in this match, in which case you will use it to test for a termination condition, or in another match in which case you can prune the current branch. You'll need to store sufficient data for each board state to facilititate the pruning.

    I suspect that the problem has now been solved using super-computers, but the amount of computational power required is beyond the device that you're currently using, within any reasonable timescale.

    If you manage to do it, then you've pretty much 'solved' the game of chess. All that remains is to stay on a branch that gives at least one successful or neutral outcome and you're unbeatable.
     
    Last edited: Mar 17, 2014
  17. Mar 17, 2014 #16

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Either player could claim a draw after White's 150th move above. As both players have then played 50 moves each without a pawn move or capture.
     
  18. Mar 17, 2014 #17

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    ... however, I realise that there's no need to lose half a move every time. Instead, black could play as many moves as possible first: on moves 50, 100, 150 etc. Eventually, White would have to make a pawn move, but then White would keep playing the key moves for as long as possible, before Black would take over again.

    It's tricky to work out exactly how often they need to change over (losing half a move in the process), so the answer is close to 5,900, but a few moves short.
     
  19. Mar 17, 2014 #18
    In response to my own post, it doesn't look like its a solveable problem any time soon.


    The number of different possible game states is going to be:

    64!/32!/8!/8!/2/2/2/2/2/2 * (32*32+32)/2 = 2.4471357e+45

    This includes a black/white symmetry and bishops on same colour squares, which is possible. There is no left/right symmetry due to castling. It also includes a number of invalid pawn positions. If we removed those we could reduce it a little. Then some of those remaining states are going to be unreachable within 50 moves, so sparse storage would help, but it isn't going to make the problem solveable, with current technology.

    We could partition based upon irreverisble pawn structure, but even the case with no pawns would involve game states equal to:

    64!/48!/2/2/2/2/2/2 * (16*16+16)/2 = 2.1720361e+28

    So it's doubtful that it would even be suitable for a distributed computation problem.
     
    Last edited: Mar 17, 2014
  20. Mar 18, 2014 #19
    After some analysis, it looks like the minimum number of changes is three, so the longest game (assuming 50-move rule is always applied) ends on white's 5899th move.
     
  21. Jun 30, 2015 #20
    As per FIDE Rules, three repetition of moves will make a drawn game or even if repetition is tried to be made in a long tree, it is 50 moves limit after which a game is drawn if no piece is captured or no pawn is advanced therein.

    Hence, that's not potentially infinite.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Exact number of possible chess games
  1. X-O game and chess! (Replies: 5)

  2. Is chess a futile game? (Replies: 27)

Loading...