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

[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

 

[mathman]

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

Above claims to be an answer - I think it is wrong. But using his idea, an upper limit would be $218^n$.

 

[FactChecker]

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

Above claims to be an answer - I think it is wrong. But using his idea, an upper limit would be $218^n$.

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.

 

[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

 

[micromass]

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

Yes, all legal moves.

 

[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

 

[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.

 

[OmCheeto]

How many different sequences of plays (moves of pieces) are possible in the first ten moves of a chess game?

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

...I don't think it would be possible to figure out the real answer without going crazy.

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

 

[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.

 

[PeroK]

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

That page is nonsense from start to finish.

 

[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

 

[OmCheeto]

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

And that's my final guess.
...

Chess [WolframMathWorld]

...(OEIS A006494).​

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.

 

[PeroK]

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

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.

 

[OmCheeto]

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

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

 

[fluidistic]

The answer is well known and is 69,352,859,712,417 according to https://chessprogramming.wikispaces.com/Perft+Results.
Edit: I see it's almost the same result that OmCheeto provided.

 

[OmCheeto]

The answer is well known and is 69,352,859,712,417 according to https://chessprogramming.wikispaces.com/Perft+Results.
Edit: I see it's almost the same result that OmCheeto provided.

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.

 

[jbenavidesv]

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

This is a late reply, but I have created a recursive function in Python that explores all the legal moves in $n$ turns based on the library python-chess. That gives me:

{
  "turn 0": {
    "plays": 20,
    "attacks": 0,
    "checks": 0,
    "mates": 0
  },
  "turn 1": {
    "plays": 400,
    "attacks": 0,
    "checks": 0,
    "mates": 0
  },
  "turn 2": {
    "plays": 8902,
    "attacks": 34,
    "checks": 12,
    "mates": 0
  },
  "turn 3": {
    "plays": 197281,
    "attacks": 1576,
    "checks": 469,
    "mates": 8
  },
  "turn 4": {
    "plays": 4865609,
    "attacks": 82719,
    "checks": 27351,
    "mates": 347
  }
}

 

[OmCheeto]

This is a late reply, but I have created a recursive function in Python that explores all the legal moves in $n$ turns based on the library python-chess. That gives me:
{
"turn 0": {
"plays": 20,
"attacks": 0,
"checks": 0,
"mates": 0
},
"turn 1": {
"plays": 400,
"attacks": 0,
"checks": 0,
"mates": 0
},
"turn 2": {
"plays": 8902,
"attacks": 34,
"checks": 12,
"mates": 0
},
"turn 3": {
"plays": 197281,
"attacks": 1576,
"checks": 469,
"mates": 8
},
"turn 4": {
"plays": 4865609,
"attacks": 82719,
"checks": 27351,
"mates": 347
}
}

How long would it take your machine to get to turn 14?
It looks as though it took Francois about 5 1/2 years to get to 13:

a(12) from François Labelle, Mar 04 2012​

a(13) from François Labelle, Aug 15 2017​

ref: https://oeis.org/A006494

Also, looking more closely at the numbers this time, I've discovered an odd jiggleyness to the change in numbers.

n​	change in moves​	moves​
1		20
2	20.00 = 400/20	400
3	22.26 = 8902/400	8,902
4	22.16	197,281
5	24.66	4,865,617
6	24.47	119,060,679
7	26.84	3,195,913,043
8	26.60	84,999,425,906
9	28.70	2,439,540,533,153
10	28.43	69,353,270,203,366
11	30.25	2,097,660,204,806,910
12	29.96	62,855,340,727,822,800
13	31.52	1,981,075,507,583,380,000

More apparent visually:

I don't understand.

 

[jbenavidesv]

How long would it take your machine to get to turn 14?
It looks as though it took Francois about 5 1/2 years to get to 13:

a(12) from François Labelle, Mar 04 2012​

a(13) from François Labelle, Aug 15 2017​

ref: https://oeis.org/A006494

Also, looking more closely at the numbers this time, I've discovered an odd jiggleyness to the change in numbers.

n​	change in moves​	moves​
1		20
2	20.00 = 400/20	400
3	22.26 = 8902/400	8,902
4	22.16	197,281
5	24.66	4,865,617
6	24.47	119,060,679
7	26.84	3,195,913,043
8	26.60	84,999,425,906
9	28.70	2,439,540,533,153
10	28.43	69,353,270,203,366
11	30.25	2,097,660,204,806,910
12	29.96	62,855,340,727,822,800
13	31.52	1,981,075,507,583,380,000

More apparent visually:

View attachment 333432
I don't understand.

51 minutes for 6 turns in Google Colab. However, I have not paralelized the algoritm yet. Also, I want to add a "save" feature, where you can save all the boards states for each turn. This will be useful to calculate further turns from those saved states. You can see the code here: https://colab.research.google.com/drive/1SV88fmepPxzpVsJBiXDto3snJufZ5JeC

It is a homework for a class and it is in Spanish. Anyway, at t the end you can find the recursive function.

Also, I have noticed something in my early versions of the algorithm. Some notes about those versions:
- One version counted previuos possible plays into further turns, resulting second turn in 420 plays, for instance.
- Other version counted shifted plays, resulting in turn 2 getting 20 plays
Besides, I am using the Standard set of rules from python-chess (https://python-chess.readthedocs.io/en/latest/variant.html). I am a noob chess player, haha, so I mentioned this as an hypothesis: Maybe some iterations where incorrect, some rules have changed over time, or some rules have been missinterpreted by other authors and after noticing it, they recalculated their total plays.

 

[apostolosdt]

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.

I can't follow your reasoning. 29 possible moves (average) for EACH position. So, French Defence and Four Knights result in similar positions and so do King's Gambit, etc., let alone the Queen's openings! Interesting. Poor Reuben Fine and your classic chess books!

 

[PeroK]

I can't follow your reasoning. 29 possible moves (average) for EACH position. So, French Defence and Four Knights result in similar positions and so do King's Gambit, etc., let alone the Queen's openings! Interesting. Poor Reuben Fine and your classic chess books!

We're talking about all possible games. Not just all possible games with sensible moves.

 

[apostolosdt]

We're talking about all possible games. Not just all possible games with sensible moves.

Of course I get it! But what's the point? If it is some sort of combinatorics exercise, you have earned my full attention, for I'm not a mathematician and I'd like to see how one deploys his (her) arguments over such a complicated game. A really interesting task! But it sounds enormous. Any genuine attempt so far?

[Added later.] The posts after #16 are all very nice approaches, indeed.

 

[jbenavidesv]

51 minutes for 6 turns in Google Colab. However, I have not paralelized the algoritm yet. Also, I want to add a "save" feature, where you can save all the boards states for each turn. This will be useful to calculate further turns from those saved states. You can see the code here: https://colab.research.google.com/drive/1SV88fmepPxzpVsJBiXDto3snJufZ5JeC

It is a homework for a class and it is in Spanish. Anyway, at t the end you can find the recursive function.

Also, I have noticed something in my early versions of the algorithm. Some notes about those versions:
- One version counted previuos possible plays into further turns, resulting second turn in 420 plays, for instance.
- Other version counted shifted plays, resulting in turn 2 getting 20 plays
Besides, I am using the Standard set of rules from python-chess (https://python-chess.readthedocs.io/en/latest/variant.html). I am a noob chess player, haha, so I mentioned this as an hypothesis: Maybe some iterations where incorrect, some rules have changed over time, or some rules have been missinterpreted by other authors and after noticing it, they recalculated their total plays.

I have updated the code and now it does what I mentioned before. One can start from any board state to compute the next possible legal moves (while paralelizing too!). And that is then saved into a dictionary that is able to be saved into a database. Soooooo, I will be running this from time to time and let you know where it leads. Interesting problem, by the way.

Important remark: Some moves generate "repeated" states. For instance, while they are 8902 possible legal moves for the third turn, only 6481 are unique!