Number of Possible Chess Games

[PatrickPowers]

How many possible chess games are there? There are a great many more if neither player is trying to win and instead are collaborating to play the longest possible legal games.

Officially, chess moves are defined as a piece moved by each player, that is, two half-moves. Instead of using this definition I'm going to call such a half-move a move. So there is a chess rule that the games ends in a draw after one hundred such moves with no captures or pawn moves.

Any game has at most 30 captures followed by the kings sashaying about for another one hundred moves so that's 31*100=3100. Now you want to maximize the number of possibilities per move. If all you have is a queen and a king then you usually have 7*8+8=64 possibilities per move. To maximize possibilities you value the most mobile pieces. So you want to promote your pawns into queens. One may sacrifice four pawns to get them out of the way. Move a pawn four squares, taken by enemy pawn. This allows three pawns to advance a full six squares. So this makes for (3*6+4-1)*4 = 84 pawn moves minus pawn captures. The length of the longest game is about (31+84)*100 = 11500 moves (which in official chess terminology is a 5750 move game). Games less than this length contribute little to the number of possible games.

So what about the average number of possibilities per move. The maximum is more than an eight queen board with its 64*8=512 possibilities. Let's reduce this to 200, each side has three queens and a couple of bishops or rooks. The number of games is then about 200^11500. Very roughly this is 10^26450. Optimists can round up to 10^30000, pessimists down to a measly 10^20000.

[Hugh]

Do you think chess will ever be solved? I think it will. AI will eventually be able to come up with a set of moves for white that will always assure victory.

https://en.wikipedia.org/wiki/Solving_chess

[PatrickPowers]

Halc said:
One queen can move to 21 to 27 squares depending on where it is, and assuming it is nowhere blocked. Not sure where the 56 comes from.

Whoops!

Halc: All 16 pawns can go the distance, at a cost of 8 captures (of non-pawns). So (25+96)*100 = 12100 moves. How else are we going to get 18 queens on the board?

Aha. White pawn captures and moves into a new column. The black pawn in that column captures in the original column of our white hero. Then both doubled up pawns can advance fully. So (16*6 + 30 - 8 + 2 + 1 ) * 100 = 12100. It appears you had 32 captures when only 30 are possible but the castling moves make up for it.

With minimal effort I came up with an 18 queen setup with 100 possible moves per side. I was able to jam some more pieces in there at no net cost. With eight queens it's about 90. It's easy to "protect" the king, just stick it in a corner with maybe a friendly blocking piece next to it. Moving the pieces around didn't change things much.

With two queens it's about 25+8= 33 possible moves per side. So a geometric average of 60 moves seems cautious but possible. I figure that for about a third of the game the geometric average is about 50, for 2/3 about 90. This makes for an overall GA of 74. That would be 10^23000 games.

[PatrickPowers]

Do you think chess will ever be solved? I think it will. AI will eventually be able to come up with a set of moves for white that will always assure victory.

https://en.wikipedia.org/wiki/Solving_chess

I dunno. Checkers was solved by enumerating every possible move. That can't be done in chess. AI uses evaluations which are estimates so you can't prove anything that way.

I'd also guess that perfect play leads to a draw.