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

I How many possible plays in first 10 moves of a game of Chess

  1. Apr 2, 2016 #1
    How many different sequences of plays (moves of pieces) are possible in the first ten moves of a chess game? I have seen numbers that range up to 30!, but I have no real idea how those numbers are derived or whether trhey are valid. In fact, I doubt if a factorial even has anything to do with it.

    Any ideas?

    Pete B
     
  2. jcsd
  3. Apr 2, 2016 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    https://www.quora.com/How-many-possible-moves-are-there-in-a-chess-game-which-lasts-n-turns [Broken]

    Above claims to be an answer - I think it is wrong. But using his idea, an upper limit would be [itex]218^n[/itex].
     
    Last edited by a moderator: May 7, 2017
  4. Apr 2, 2016 #3

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    In that article, he admits that many of those moves are illegal. He is giving an upper limit which is way above the true maximum. I don't think it would be possible to figure out the real answer without going crazy.
     
    Last edited by a moderator: May 7, 2017
  5. Apr 2, 2016 #4

    billy_joule

    User Avatar
    Science Advisor

    I guess the answer depends on what you consider valid moves? All legal moves?
    eg this series is legal for white as long as black isn't being repetitive also, but clearly nonsensical:
    Kf3
    Kg1
    Kf3
    Kg1
    Kf3
    Kg1
    Kf3
    Kg1
    Kf3
    Kg1
     
  6. Apr 2, 2016 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, all legal moves.
     
  7. Apr 3, 2016 #6
    I don't agree with the number of moves being (218)^n at all. Nor do I agree with his analysis, Chess is far more complex than that. Consider just how much complexity is introduced by the choice of whether to castle or not: choosing either way can determine a vastly different set of further possible moves for each choice, IOW it affects the entire remainder of the game.

    Nor are individual moves as simple as he states, because each move is dependent on how the piece is moved as well as whether it is a strategic or advantageous move or not, as in, say, sacrificing one piece to achieve an advantage for another subsequent move, or not doing so. As well, the skill levels of the players can have a huge impact on the progress of the game; to be extreme, for example, one player can deliberately have a game-ending impact at the very beginning of a game by simply exposing his King to being checked by an opponent with no further moves possible to evade the mate.

    I do not think there is any possible general answer that is true for all games, and even forecasting an individual, specifc game woulde entail projecting the gamut of possibilities presented after each and every move of the game; thus every game would have a unique analysis or move-by-move projection.

    In other words, I think this is an NP-Hard problem, perhaps :=), there just is not any possible answer...

    But I welcome further opinion on the matter....

    Pete B
     
  8. Apr 3, 2016 #7
    It shouldn't be close to that many. The first two moves each have 20 possibilities and doesn't increase that fast for the next two moves either. A good chess engine search a lot further than 10 moves currently. While that is with a lot of pruning I'm pretty sure the problem would be solvable in decent time with a computer. A recursive algorithm just counting the nodes is faster than actually evaluating the positions as well like you do in a minmax search.
     
  9. Apr 3, 2016 #8

    OmCheeto

    User Avatar
    Gold Member
    2016 Award

    From this, I'm guessing each player has moved his pieces 5 times.

    I made it to 2 moves(white then black), started on "move # 3" number of the possible positions, had to give up, and started googling.
    That didn't help much, as there seems to be a difference of agreement between numberphiles and chessaholics.

    Numberphile:
    How many chess games are possible? [youtube]
    posted by: Numberphile
    Published: Jul 24, 2015
    move positions
    1(w) 20
    2(b) 400
    3(w) 8,902
    4(b) 197,742
    5(w) 4,897,256
    6(b) 9,132,484​

    Chessaholics:
    Mathematics and chess [chessdotcom]
    Last updated on 9/27/13, 5:27 AM.
    The number of possible chess positions after White’s first ply move is 20 (16 pawn moves and 4 knight moves). There are 400 possible chess positions after two ply moves (first ply move for White followed by first ply move for Black).
    There are 5,362 possible positions (White’s second ply move) or 8,902 total positions after two ply moves each. There are 71,852 possible positions or 197,742 total positions after four moves. There are 809,896 possible positions or 4,897,256 total positions after 5 moves.There are 9,132,484 total positions after 6 moves.​

    There seems to be a missing "5,362" missing from Numberphile's list.

    But, I went with his numbers anyways, even though he claimed he was not a chessaholic.

    I graphed them logarithmically, took a linear interpolation, and came up with an answer of 1.77e12.

    And that's my final guess.

    ps. I'm guessing Numberphile and Chessaholic both looked at Wolfram, and picked from the lists of possible options:

    Chess [WolframMathWorld]
    ...To be precise, the number of distinct chess positions after n moves for n=1, 2, ... are 20, 400, 5362, 71852, 809896?, 9132484?, ... (Schwarzkopf 1994, OEIS A019319). The number of chess games that end in exactly n moves (including games that mate in fewer than n plies) for n=1, 2, 3, ... are 20, 400, 8902, 197742, 4897256, 120921506, 3284294545, ... (OEIS A006494).​
     
  10. Apr 3, 2016 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You could get a rough estimate by playing through a typical opening and counting the number of possible moves at each turn. It starts with 20 and increases a bit. For the first n moves (technically half moves) it must be about ##25^n##.

    This is an estimate of the number of games, not the number of possible positions after n moves.
     
  11. Apr 3, 2016 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That page is nonsense from start to finish.
     
    Last edited by a moderator: May 7, 2017
  12. Apr 3, 2016 #11
    If there are 9 million+ possible positions after 6 play moves, how many possible positions are there after 10 ply moves? I confess I had checked the Wolfram site, but on my PC I have a very hard time reading the formulas in the articles, they are displayed as some kind of exotic script, so I cannot even use the formulas else I would have done so.

    The original info I had that prompted this thread was that for a 10-move game (not sure whether that means each player has made 10 moves, or both players together have made 10 moves) there were 169,518,829,100,544 x 10^16 possible moves. Is that an accurate figure based on the sources you provide?

    Pete B
     
  13. Apr 3, 2016 #12

    OmCheeto

    User Avatar
    Gold Member
    2016 Award

    Wait! Regis Philbin just called me, and said I could change my mind.

    My final, honest to goodness, final answer is: 69,353,270,203,366

    based upon the list that Wolfram referenced to: http://oeis.org/A006494/list

    6.91E+13/1.77E+12 ≈ 40

    Ha! Only off by a magnitude and a half. Much better than my usual answer. :biggrin:
     
  14. Apr 3, 2016 #13

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That's for 10 full moves - 10 by each player - and is a bit more than ##25^{20}##.

    It's about ##29^{20}##, so there are about 29 possible moves on average in each position, near the beginning of the game.
     
    Last edited: Apr 3, 2016
  15. Apr 3, 2016 #14

    OmCheeto

    User Avatar
    Gold Member
    2016 Award

    You can graph and interpolate the given numbers for yourself.
    Logarithmically, they look pretty linear to me.

    chess.positions.after.n.absolute.moves.png
     
  16. Apr 9, 2016 #15

    fluidistic

    User Avatar
    Gold Member

  17. Apr 9, 2016 #16

    OmCheeto

    User Avatar
    Gold Member
    2016 Award

    I would ask why the numbers are 410,490,949 apart, but I'm sure I wouldn't understand the answer.
    I am dreadfully bad at maths. :redface:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How many possible plays in first 10 moves of a game of Chess
  1. How is this possible? (Replies: 3)

  2. In how many (Replies: 1)

Loading...