What is the complexity of possible chess game combinations?

[MathJakob]

Homework Statement

Given a standard chess board consisting of 64 squares with each game taking a total of 40 moves. Calculate the total number of games which can be played. You are to assume a stalemate situation occurring on the 40th move a completed game.

The Attempt at a Solution

So there are 20 possible moves at the start of the game. 20 for white and 20 for black. There are a total of 400 possible games which consist of only 2 moves in total.

This is as far as I got, I literally have no idea how to calculate this.

 

[BruceW]

are you meant to calculate an upper bound on the number of possible games, or the exact number of possible games?

 

[MathJakob]

are you meant to calculate an upper bound on the number of possible games, or the exact number of possible games?

The upper bound. I don't think anyone knows the exact number of games.

 

[BruceW]

good. now it is really your choice on how to calculate an upper limit. first think about white's first move. 20 moves is the exact number. But you don't want to be exact. You want to give an answer which over-estimates, but is easy to calculate. So how would you do it?

 

[MathJakob]

I don't understand... I'd just say that 10 peices can be moved, each can move to 2 different places so 20 valid squares in which the first piece is allowed to move it.

 

[BruceW]

that's true. but that is specific to the first move. Think of a more general over-estimate, which will be easy to calculate for any of the moves, not just the first move. You are still thinking in terms of finding an exact answer, but you don't need to do that. Another way to say it, let's say I tell you there are a number of pieces on the chessboard, but I don't tell you where they are, then what would be your over-estimate for how many moves you can make this turn?

 

[MathJakob]

when you say over estimate I really hope you mean OVER estimate because on the larger scale the only thing I can think of is that there are $64!$ ways to arrange each piece on the chess board. This doesn't work though because that includes a lot of illegal moves.

I posted this in the homework section but it isn't actually school homework, it's just a fun question I found online so don't be too worried about giving me a bit more info.

 

[BruceW]

Well, you are starting to get the idea. Since we are just trying to find an upper bound, it doesn't matter if we include a lot of illegal moves. In fact, to get an over-estimate, we must include at least some illegal moves, otherwise we would have found the exact answer.

But there are not 64! ways to arrange the chess pieces, since there are not 64 pieces. There are only 16 pieces, so the number is not quite so huge. If you find the number of ways to arrange all 16 pieces on the chess board, then do this to the power of the number of moves, then this is an over-estimate of the number of possible games. So yes, this would be a reasonable answer.

But another way to get an over-estimate is to consider that you only move one white piece and one black piece per move. So you can get a better estimate by taking this into account.

 

[MathJakob]

How about if you were to go about finding the exact answer? Is there even a way to find the exact number of 40 move games?

 

[PhotonCurve]

Homework Statement

Given a standard chess board consisting of 64 squares with each game taking a total of 40 moves. Calculate the total number of games which can be played. You are to assume a stalemate situation occurring on the 40th move a completed game.

The Attempt at a Solution

So there are 20 possible moves at the start of the game. 20 for white and 20 for black. There are a total of 400 possible games which consist of only 2 moves in total.

This is as far as I got, I literally have no idea how to calculate this.

Ah chess... a strong subject of mine.

''Given a standard chess board consisting of 64 squares with each game taking a total of 40 moves. Calculate the total number of games which can be played. ''

What is that meant to mean? A game depends on how fast it can achieve checkmate? In 40 moves, you can only play one game! :)

Is it a riddle?

If not, and I take what you have said below

''So there are 20 possible moves at the start of the game. 20 for white and 20 for black. There are a total of 400 possible games which consist of only 2 moves in total.''

I can tell you this... the number of possible choices of moves in any game reduce drastically towards an end game. I believe however the problem you are speaking about is called the ''game tree complexity.'' http://en.wikipedia.org/wiki/Game_tree

I assume you get the 20 moves in a possible opening by taking all pawns that can move once, which is 8, then the pawns can move also two squares which amounts to 8, then the knights which make four (since a knight can move towards to the rim or towards the center). If that is the product of how many game's that can possibly start, then sure, you have 400 possible start-up conditions, this doesn't allude to how many games can be won in the complexity of the moves within the middle and end game.

 

[MathJakob]

Ah chess... a strong subject of mine.

''Given a standard chess board consisting of 64 squares with each game taking a total of 40 moves. Calculate the total number of games which can be played. ''

What is that meant to mean? A game depends on how fast it can achieve checkmate? In 40 moves, you can only play one game! :)

Is it a riddle?

If not, and I take what you have said below

''So there are 20 possible moves at the start of the game. 20 for white and 20 for black. There are a total of 400 possible games which consist of only 2 moves in total.''

I can tell you this... the number of possible choices of moves in any game reduce drastically towards an end game. I believe however the problem you are speaking about is called the ''game tree complexity.'' http://en.wikipedia.org/wiki/Game_tree

I assume you get the 20 moves in a possible opening by taking all pawns that can move once, which is 8, then the pawns can move also two squares which amounts to 8, then the knights which make four (since a knight can move towards to the rim or towards the center). If that is the product of how many game's that can possibly start, then sure, you have 400 possible start-up conditions, this doesn't allude to how many games can be won in the complexity of the moves within the middle and end game.

I know, but as the game progresses the amount of different moves grows at an incredible rate. If 2 people were to play a game of chess, and then play that exact same game move for move but instead of white moving pawn A2 - A3 he moved pawn A2 - A4 then that would be classed as a different game.

For example there are 318,979,564,000 possible ways to play the first four moves of chess. This is with just 4 moves... still another 36 moves left. Then there are 169,518,829,100,544,000,000,000,000,000 ways to play the first ten moves of chess.

Like I said the number grows incredibly as the game hits 10 moves. If a computer can calculate 10billion games per second, the computer would only be able to compute $4.32098\times10^{27}$ games in 13.7billion years. The estimated number of chess games is considered to be as high as $10^{100,000}$ but only $10^{120}$ of those being playable games which end within 40 moves with either a checkmate or a draw.