Exact number of possible chess games

[MathJakob]

I've googled this and it appears that there doesn't seem to be an exact number of games. Assume that no illegal moves are allowed, peices must start in their correct squares and each game lasts a total of 40 moves.

Is there a way to work out exactly how many 40 move games exist? There are a few different upper bounds but they include illegal moves, pawns on the first rank and kings on adjacent squares ect.

Any particular reason why there are only estimations on the number of games? I guess it's pretty difficult to work out exactly how many games exist...

 

[Pythagorean]

Technically, two people could get into a loop and repeat the same moves over, or go back and forth, or return to a previous board state some other way. So it's essentially recursive (potentially infinite).

 

[scurty]

Technically, two people could get into a loop and repeat the same moves over, or go back and forth, or return to a previous board state some other way. So it's essentially recursive (potentially infinite).

I agree for an unlimited number of moves, but with a 40 move limit it certainly appears finite.

 

[Nugatory]

Technically, two people could get into a loop and repeat the same moves over, or go back and forth, or return to a previous board state some other way. So it's essentially recursive (potentially infinite).

If the same position is reached three times (the definition of "same position" is not completely trivial, but it's there and unambiguous) the game is a draw, so there are a finite number of chess games.

 

[Integrand]

Your requirement that each game lasts a total of 40 moves is strange, I guess you meant no more than 40?

I agree with Pythagorean, although regarding loops note the rule making a draw claimable upon three-fold repetition of a position. I don't think you can avoid the requirement to analyse each new position you generate for legality, to see whether it has already occurred twice, or to see whether it's checkmate or stalemate and terminates the game prematurely. To do all this from the opening position is probably beyond us at present, considering our tablebases are only at seven right now: http://en.wikipedia.org/wiki/Tablebase

http://mathworld.wolfram.com/Chess.html has some links to relevant literature, though I guess you probably found this already.

 

[Nugatory]

Any particular reason why there are only estimations on the number of games? I guess it's pretty difficult to work out exactly how many games exist...

That's why there are only estimates: It's pretty difficult to work out an exact answer. Indeed, there is no known way of calculating it that is appreciably less work than systematically enumerating all possible games, and that's a rather computationally daunting problem.

 

[MathJakob]

Your requirement that each game lasts a total of 40 moves is strange, I guess you meant no more than 40?

Yes I did mean that no game can go on past the 40th move otherwise the game is a stalemate. Also I guess you could have 2 players loop the same two moves but it doesn't matter because upon the 40th move the game is a stalemate.

 

[jbriggs444]

Yes I did mean that no game can go on past the 40th move otherwise the game is a stalemate. Also I guess you could have 2 players loop the same two moves but it doesn't matter because upon the 40th move the game is a stalemate.

The actual rule appears to be that a draw may be claimed after 50 moves without a capture or the movement of a pawn.

There being 16 pawns able to move 6 spaces each and 30 pieces that can be captured, it is possible for legal games to continue to thousands of moves, even if the players declare a draw at the first opportunity.

 

[PeroK]

The answer to the original question is that the number of legal moves in any position varies depending on the position. So, you can only estimate this for more than a few moves ahead.

There are just too many factors governing the number of legal moves in any position: how many pawns are blocked, how many pieces have been taken, whether there's a check.

All you can do is estimate the average or maximum number of moves and raise that to the power of 80 or whatever.

To get an exact figure you would have to go through every possible game.

 

[PeroK]

The actual rule appears to be that a draw may be claimed after 50 moves without a capture or the movement of a pawn.

There being 16 pawns able to move 6 spaces each and 30 pieces that can be captured, it is possible for legal games to continue to thousands of moves, even if the players declare a draw at the first opportunity.

It's not hard to calculate the longest legal game. Each player would play 50 moves before a pawn is moved or a piece taken: athough, in order to get the pawns past each other, they have to capture. Half the pawns have to do this, so that's 8 pieces that need to be captured.

Each pawn could then move 6 times: 96 moves. That leaves 22 more pieces to be captured. So, the longest game is about 50*118 moves each.

I make it 0.5 + 49.5*118 to be exact. The game would end at that point, as you don't have to play out 50 moves with two Kings.

So, the game would end on white's 5,842nd move!

But, of course, the 50-move rule only allows either player to claim a draw. In practice, two players could go on playing beyond this.

 

[The_Duck]

Is there a way to work out exactly how many 40 move games exist? There are a few different upper bounds but they include illegal moves, pawns on the first rank and kings on adjacent squares ect.

Any particular reason why there are only estimations on the number of games? I guess it's pretty difficult to work out exactly how many games exist...

No, there's no good way of doing this besides having a computer enumerate all the possibilities. This is actually a common test that chess engine programmers use to verify correctness of their move-generation routines. From the initial position people have used computers to answer your question for games of up to 13 half-moves: see http://chessprogramming.wikispaces.com/Perft+Results. Apparently the number of possible games of 13 half-moves is 1,981,066,775,000,396,239.

 

[ChessWiz]

Actual maximum number of possible moves in a chess game

It's not hard to calculate the longest legal game. Each player would play 50 moves before a pawn is moved or a piece taken: athough, in order to get the pawns past each other, they have to capture. Half the pawns have to do this, so that's 8 pieces that need to be captured.

Each pawn could then move 6 times: 96 moves. That leaves 22 more pieces to be captured. So, the longest game is about 50*118 moves each.

I make it 0.5 + 49.5*118 to be exact. The game would end at that point, as you don't have to play out 50 moves with two Kings.

So, the game would end on white's 5,842nd move!

But, of course, the 50-move rule only allows either player to claim a draw. In practice, two players could go on playing beyond this.

Assuming the 50-move rule is enforced, every 50th move would have to be either a pawn move or capture. This would make move #5900 the final move.
But there is an exception to the 50-move rule in certain endgame positions. For example, a King, Rook & Bishop can force checkmate against a King & Rook. However, computers have calculated that even with perfect play against perfect defense, it cannot be accomplished in fewer than 54 moves. In these special situations, players are allowed 100 moves. So for the absolutely greatest number of moves in a chess game, it would be Black either checkmating, stalemating or drawing by the 50-move rule on his 5,950th move.

 

[PeroK]

Assuming the 50-move rule is enforced, every 50th move would have to be either a pawn move or capture. This would make move #5900 the final move.
But there is an exception to the 50-move rule in certain endgame positions. For example, a King, Rook & Bishop can force checkmate against a King & Rook. However, computers have calculated that even with perfect play against perfect defense, it cannot be accomplished in fewer than 54 moves. In these special situations, players are allowed 100 moves. So for the absolutely greatest number of moves in a chess game, it would be Black either checkmating, stalemating or drawing by the 50-move rule on his 5,950th move.

It's 49.5 moves not 50, because white and black have to alternate the pawn and capture moves. Also, FIDE has removed to 50+ rule as computers were finding more and more such positions.

 

[ChessWiz]

Don't BOTH players have to complete 50 full moves before a draw can be called? In other words, would it NOT be a draw, if for example:
1. ... ...
50. ... a6
100. a3 ...
150. ... b6
200. b3 ...
etc. ?

Also, what is the exact FIDE rule concerning this?

 

[craigi]

Technically, two people could get into a loop and repeat the same moves over, or go back and forth, or return to a previous board state some other way. So it's essentially recursive (potentially infinite).

Don't BOTH players have to complete 50 full moves before a draw can be called? In other words, would it NOT be a draw, if for example:
1. ... ...
50. ... a6
100. a3 ...
150. ... b6
200. b3 ...
etc. ?

Also, what is the exact FIDE rule concerning this?

Try this:
http://en.wikipedia.org/wiki/Threefold_repetition

I've googled this and it appears that there doesn't seem to be an exact number of games. Assume that no illegal moves are allowed, peices must start in their correct squares and each game lasts a total of 40 moves.

Is there a way to work out exactly how many 40 move games exist? There are a few different upper bounds but they include illegal moves, pawns on the first rank and kings on adjacent squares ect.

Any particular reason why there are only estimations on the number of games? I guess it's pretty difficult to work out exactly how many games exist...

You're not going to be able to solve it using pen and paper. The problem is a computational one and you're going to be looking to use the current state of the board as a way to merge branches to reduce complexity by taming the exponential growth.

If you're familiar with a programming language, you could try to solve it. It's an interesting challenge. I'd start by working out a way to create an efficient hash of the current disinguishable state of the board. This part is an interesting challenge in itself. Then branch on each move checking to see if you've seen that state before, either in this match, in which case you will use it to test for a termination condition, or in another match in which case you can prune the current branch. You'll need to store sufficient data for each board state to facilititate the pruning.

I suspect that the problem has now been solved using super-computers, but the amount of computational power required is beyond the device that you're currently using, within any reasonable timescale.

If you manage to do it, then you've pretty much 'solved' the game of chess. All that remains is to stay on a branch that gives at least one successful or neutral outcome and you're unbeatable.

 

[PeroK]

Don't BOTH players have to complete 50 full moves before a draw can be called? In other words, would it NOT be a draw, if for example:
1. ... ...
50. ... a6
100. a3 ...
150. ... b6
200. b3 ...
etc. ?

Also, what is the exact FIDE rule concerning this?

Either player could claim a draw after White's 150th move above. As both players have then played 50 moves each without a pawn move or capture.

 

[PeroK]

... however, I realize that there's no need to lose half a move every time. Instead, black could play as many moves as possible first: on moves 50, 100, 150 etc. Eventually, White would have to make a pawn move, but then White would keep playing the key moves for as long as possible, before Black would take over again.

It's tricky to work out exactly how often they need to change over (losing half a move in the process), so the answer is close to 5,900, but a few moves short.

 

[craigi]

I suspect that the problem has now been solved using super-computers, but the amount of computational power required is beyond the device that you're currently using, within any reasonable timescale.

In response to my own post, it doesn't look like its a solveable problem any time soon.The number of different possible game states is going to be:

64!/32!/8!/8!/2/2/2/2/2/2 * (32*32+32)/2 = 2.4471357e+45

This includes a black/white symmetry and bishops on same colour squares, which is possible. There is no left/right symmetry due to castling. It also includes a number of invalid pawn positions. If we removed those we could reduce it a little. Then some of those remaining states are going to be unreachable within 50 moves, so sparse storage would help, but it isn't going to make the problem solveable, with current technology.

We could partition based upon irreverisble pawn structure, but even the case with no pawns would involve game states equal to:

64!/48!/2/2/2/2/2/2 * (16*16+16)/2 = 2.1720361e+28

So it's doubtful that it would even be suitable for a distributed computation problem.

 

[Deedlit]

... however, I realize that there's no need to lose half a move every time. Instead, black could play as many moves as possible first: on moves 50, 100, 150 etc. Eventually, White would have to make a pawn move, but then White would keep playing the key moves for as long as possible, before Black would take over again.

It's tricky to work out exactly how often they need to change over (losing half a move in the process), so the answer is close to 5,900, but a few moves short.

After some analysis, it looks like the minimum number of changes is three, so the longest game (assuming 50-move rule is always applied) ends on white's 5899th move.

 

[Abhijit4law]

Technically, two people could get into a loop and repeat the same moves over, or go back and forth, or return to a previous board state some other way. So it's essentially recursive (potentially infinite).

As per FIDE Rules, three repetition of moves will make a drawn game or even if repetition is tried to be made in a long tree, it is 50 moves limit after which a game is drawn if no piece is captured or no pawn is advanced therein.

Hence, that's not potentially infinite.

 

[Pythagorean]

As per FIDE Rules, three repetition of moves will make a drawn game or even if repetition is tried to be made in a long tree, it is 50 moves limit after which a game is drawn if no piece is captured or no pawn is advanced therein.

Hence, that's not potentially infinite.

That's what Nugatory said above. When I play with friends, I've never used these rules though, we go to mate (stale or check). We did often have a rule of three checks on a lone king means a stale mate (Iirc, been a while now). Often people will tip their king and start a new game rather than try to drag a check mate into a stale mate, though, and it was socially encouraged.

I've never played official tournaments, personally.