Possible Positions in Chess After n Moves

[leehufford]

Hello,

I am wondering if there is a forumula for the number of possible positions in chess after n moves. I searched google and found some estimates (including Shannon's number) for the number of possible positions after n=1,2,3,4 but seems to get a little hazy after that.

I was also wondering if it would be an infinite series that converges to a number.

If this isn't possible to do for some reason I would be interested in knowing exactly why it isn't doable. Thanks in advance,

Lee

 

[mfb]

Chess is just too complicated to find a general formula. And it is way too complex to simulate every option. It is not even known how many legal positions there are in the game (although there are good approximations).

 

[leehufford]

Chess is just too complicated to find a general formula. And it is way too complex to simulate every option. It is not even known how many legal positions there are in the game (although there are good approximations).

Thanks for the reply. I think one of the hardest parts to account for would be "mobility" of pieces, i.e one move can leave your knight with 3 possible squares to move to while another move might leave the same knight with 4 possible moves (due to the board edges or your own pieces already occupying that square).

But what if we used averages in the formula? Could we come up with a reliable formula that estimates the number of possible positions after n moves? And maybe even report the level of certainty? Thanks again,

Lee

 

[jedishrfu]

Chess has other things like piece capture, en-passant, castling and piece promotion when a pawn gets to the other side.

Consider the simple example of moving a knight as the first move, it will block a pawn from making a move in the second round. This frustrates any attempt to count the number of move choices and makes chess so fascinating to players.

You could develop a program to estimate choices after n moves but only because it can evaluate the board configuration after each move.

There would be no way to tell if your average estimate was even remotely correct as n increases unless you used a program to verify it.

 

[leehufford]

Chess has other things like piece capture, en-passant, castling and piece promotion when a pawn gets to the other side.

Consider the simple example of moving a knight as the first move, it will block a pawn from making a move in the second round. This frustrates any attempt to count the number of move choices and makes chess so fascinating to players.

You could develop a program to estimate choices after n moves but only because it can evaluate the board configuration after each move.

There would be no way to tell if your average estimate was even remotely correct as n increases unless you used a program to verify it.

Thanks for the reply. I actually play chess quite a bit (at the skill of a good intermediate). Your response raises a few more questions.

1. How would a computer be able to analyse a current position and estimate the number of possible positions thereafter if things like en passant/castling/piece capture/mobility change the number of possibilities constantly?

2. Would it be possible to determine the total number of possible paths to a certain current position?

3. How did Shannon / others estimate the possible positions available after n=1,2,3 and 4? What branch of mathematics is that?
Thanks again,

Lee

 

[jedishrfu]

The branch is Combinatorics:

http://en.wikipedia.org/wiki/Combinatorics

There was a computer science algorithm called min/max that was used to create initial chess programs

http://en.wikipedia.org/wiki/Minmax

http://chessprogramming.wikispaces.com/Minimax

 

[mfb]

For 4 moves, it is possible to count all options. The first two moves on both sides have a very limited number of options (mainly "move a pawn" with a few other options), and I would expect that move 3 and 4 do not have more than 100 options each. This leads to something like a million different moves for each side, with little interference. Computers can handle that.

For the full game tree complexity, see the quote at Wikipedia. It is a very rough estimate.

 

[AlephZero]

You might find some interesting information (but not the full answer to your question) by doing some research into "tablebases" of chess endings. These are databases of all possible positions with a limited number of pieces (about 7 or fewer) on the board.

The basic difficulty with the counting is that chess has a large number of arbitrary rules, compared with most mathematical systems. As an extreme example, after a certain (unknown!) number of moves, both sides might have 9 queens on the board - and counting the number of those positions would be complicated if you want to exclude all the illegal positions where both kings are in check at the same time.