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

1. Apr 2, 2016

peteb

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. Apr 2, 2016

mathman

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 $218^n$.

Last edited by a moderator: May 7, 2017
3. Apr 2, 2016

FactChecker

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
4. Apr 2, 2016

billy_joule

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

5. Apr 2, 2016

micromass

Staff Emeritus
Yes, all legal moves.

6. Apr 3, 2016

peteb

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

7. Apr 3, 2016

Incand

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.

8. Apr 3, 2016

OmCheeto

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).​

9. Apr 3, 2016

PeroK

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.

10. Apr 3, 2016

PeroK

That page is nonsense from start to finish.

Last edited by a moderator: May 7, 2017
11. Apr 3, 2016

peteb

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

12. Apr 3, 2016

OmCheeto

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.

13. Apr 3, 2016

PeroK

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
14. Apr 3, 2016

OmCheeto

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

15. Apr 9, 2016

fluidistic

16. Apr 9, 2016

OmCheeto

I would ask why the numbers are 410,490,949 apart, but I'm sure I wouldn't understand the answer.