# Homework Help: Chess game combinations

1. Aug 12, 2013

### MathJakob

1. The problem statement, all variables and given/known data
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 occuring on the 40th move a completed game.

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

Last edited: Aug 12, 2013
2. Aug 12, 2013

### BruceW

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

3. Aug 12, 2013

### MathJakob

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

4. Aug 12, 2013

### 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?

5. Aug 12, 2013

### 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 peice is allowed to move it.

6. Aug 13, 2013

### 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?

7. Aug 13, 2013

### 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 peice 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.

8. Aug 13, 2013

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

9. Aug 13, 2013

### 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?

10. Aug 13, 2013

### PhotonCurve

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.

11. Aug 13, 2013

### MathJakob

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.