chess positions: how many legal ones are there ?

[diep]

Originally Posted by Mr. P-1

The most pawns possibly capturable e.p is five, and this is achievable for both colours in the same configuration, giving 16 * 6 * 2 = 192 positions. The attached position is demonstrably reachable in every case as follows:

1 e3 e5
2 Qh5 h6
3 Qg5 hg
4 h4 b5
5 h5 Qf6
6 Nf3 Qf4
7 ef e4
8 Nh4 gh
9 Nc3 Ba3
10 ba b4
11 a4 Ba6
12 Nd1 Bb5
13 ab Nc6
14 Be2 Ne5
15 fe Ne7

Call the configuration after black's 15th move "configuration a". After

16 Bg4 Ng8
17 Bf3 Ne7
18 Be2

We are back to configuration a, but with black to move. Hence configuration a is achievable with all Rooks castleable with either side to move.

We can achieve configuration a with any possible castleability situation in two further moves by moving away then back to where it was, each side's King, Rook, or minor piece, depending upon whether we want to remove castleability from both, just one, or none of that side's Rooks.

Finally we reach the attached configuration by advancing each of the unmoved pawns two spaces, and we may do this in any order. In particular each of the five pawns of either colour may be the last to move, and therefore be eligible to be captured e.p. Or the last pawn to move could have reached its position in two moves, leaving no pawns eligible for capture e.p.

A corollary to this is that if N is an upper bound to the number of possible legal configurations, then 192*N is an upper bound to the number of possible positions. I suspect the actual ratio of positions to configurations is closer to 2.

In this position you're not allowed to capture a single pawn en passant.

For an explanation on what en passant is see the great explanation at: http://en.wikipedia.org/wiki/En_passant

[diep]

On en passant:

For 32 pieces we can calculate the overhead. I calculate it now as an upperbound:

So from a theoretic viewpoint, if you have the conditions to capture en passant, you just double count the position, for each square where you could potentially take en passant, that is all.

We can look at it from a much lower level viewpoint though.

There is 3 requirements:
a) a pawn on 4th row
b) 2 empty squares
c) opponent pawn next to it that can take en passant

What's the odds of all those 3 conditions to hold true?

So in the 32 piece example the addition is biggest for en passant;
You can argue that for every given combination of 15 possibilities for 2 pawns,

the a-pawn which has 3 possibilities. So that's 1/5
Then secondly we need all configurations for an opponent pawn to be next to it.
That occurs in only 2 positions. So that's 2 out of 15 there.

So odds is then for a-pawn to be able to be taken en passant = 3 / 15 * 2 / 15 = 6 / 225 = 2.3% of the cases
Same holds true for h-pawn. So in 1/4 of the cases the odds are 6/225

Now for the b-file up to g-file odds are bigger.

There we have the same 3/15 for the first pawn, then 2 times the number 2/15 and one position overlaps
where both pawns can capture en passant, as we don't want to double count that position.

So that's 12/225 - 1/225 = 11/225, which still is in 3/4 of the cases so:

3/4 * 11/225 + 1/4 * 6/225 = 34 / 900 = 3.77%

So it adds far less than 3.77%, as there also could be pieces located at one of the 2 squares
that must be empty in which case en passant is legally not possible to exist there.

So it's peanuts; we already reduced "only" factor 2 for K-K reduction and legality,
so this few % added is really not interesting at all and castling is even much much less than this.

[science_man_88]

Originally Posted by diep

We can look at it from a much lower level viewpoint though.

There is 3 requirements:
a) a pawn on 4th row
b) 2 empty squares
c) opponent pawn next to it that can take en passant

unless you mean the 2 empty squares compared to the initial position I don't see the # 2 "requirement" wikipedia list:

the pawn making the en passant capture must be on its fifth rank
an opposing pawn on an adjacent file must move two squares from its initial position in a single move
the pawn can be captured as if it moved only one square
the capture can only be made at its first opportunity.

[CRGreathouse]

Originally Posted by science_man_88

unless you mean the 2 empty squares compared to the initial position I don't see the # 2 "requirement"

The two squares in front of the pawn must be empty, else the pawn cannot move two squares at all.

[Christenson]

Originally Posted by Mr. P-1

The most pawns possibly capturable e.p is five, and this is achievable for both colours in the same configuration, giving 16 * 6 * 2 = 192 positions. The attached position is demonstrably reachable in every case as follows:

A corollary to this is that if N is an upper bound to the number of possible legal configurations, then 192*N is an upper bound to the number of possible positions. I suspect the actual ratio of positions to configurations is closer to 2.

Sold! (and of interest to me, the upper-bound man, but not the LEAST upper-bound man).

Diep:
I disbelieve that the maximum number of Mr P-1's legal configurations occurs with 32 pieces on the board. As counted somewhat precisely earlier in this thread, there are some significant restrictions on the locations of the pawns, and the number of sets of different pieces on the board is precisely 1. Remove a piece, without promoting a pawn, and there are suddenly 18 different sets of pieces. There are more since if a pawn takes another pawn, it is possible (though unlikely in a game played to win with any skill) to promote three pawns to queen, and if it doesn't take a pawn, there are possibly two pawns that can become queens, branching out into still more sets of pieces.
Why don't you calculate the number of different sets of possible chess pieces with 31 pieces remaining on the board for us?

Theorem:
The number of legal configurations in a chess game is the sum of the number of legal positions with n pieces left on the board, with n ranging from 32 to 2.

[diep]

Originally Posted by Christenson

Sold! (and of interest to me, the upper-bound man, but not the LEAST upper-bound man).

Diep:
I disbelieve that the maximum number of Mr P-1's legal configurations occurs with 32 pieces on the board. As counted somewhat precisely earlier in this thread, there are some significant restrictions on the locations of the pawns, and the number of sets of different pieces on the board is precisely 1. Remove a piece, without promoting a pawn, and there are suddenly 18 different sets of pieces. There are more since if a pawn takes another pawn, it is possible (though unlikely in a game played to win with any skill) to promote three pawns to queen, and if it doesn't take a pawn, there are possibly two pawns that can become queens, branching out into still more sets of pieces.
Why don't you calculate the number of different sets of possible chess pieces with 31 pieces remaining on the board for us?

Theorem:
The number of legal configurations in a chess game is the sum of the number of legal positions with n pieces left on the board, with n ranging from 32 to 2.

You remove a full piece or pawn. You correctly note that it gives a number of possibilities, yet if you remove 1 pawn still 6 sets of pawns are constrained, in fact it is possible if you captured with the pawn that there is more constraints.

You can do based upon 1 capture about 2 promotions.

So 31 pieces obviously has good odds for the max possibilities, as with 30 you have removed too much from the board already meanwhile the number of extra pieceset possibilities didn't explode more than what you removed.

So with 31 pieces the calculation is a bit tougher, yet even if you explode to 18 different piecesets, that'll add never more than a factor 100, whereas you did remove a pawn from the board.

Knowing 32 pieces is 10^32 possibilities, it's going to be tough to get over 10^34 with 31 pieces.

Therefore my estimate lies between 10^34 and 10^36 on the number of possible positions in chess, which is at factor 10^7 less than any publication on it had calculated so far.

I already had forwarded my method of calculating to the appropriate person.

[diep]

On second thoughts: calculating 27-29 pieces is also very important for a good estimate;

for every capture you can promote 3 pawns. That's 1 more than i had initially estimated and changes the context bigtime.

let's say we do that with 29 pieces. This seems, because of the 3 promote for 1 pawncapture rule, the optimum amount of pieces to calculate the maximum number of positions.

Now i'm interested in a very primitive upperbound,
so it's not even close to reality of estimation.

Say we have 2 pawns left for each side, and they are opposing.

That gives 2 files where they can sit. Say that's roughly 28 possibilities and then 15^2 for the pawn combinations as it is opposing pawns.

29-4 = 25 pieces left.

let's pick one of the piece combinations with
QQQQRRRBBBNNNqqqrrrbbbnnn

As i'm in big hurry to calculate it, just correct what i do if it's wrong
for this piececombination:

the 4 queens have a reduction of 4! and the rest is 3!^7
then a quick estimate of the factor 4 for KK reduction and legality and
mirrorring, though it would be more in this position.

15^2 * 28 * 60! / (35! 4! * 2^2 * (3!)^7) = 10^38

This is obviously factors too much, yet it already gives a clue that it is important to keep an eye on all those promotions, which practical in a game tree search won't ever happen (my chessprogram when searching never saw a 3d queen occur on the board, as it already gets chopped off in a guided search directly by the opponent, or you can already mate the opponent or reduce the search bigtime after being that much ahead).

Even the quickest method of calculation however never gets even close near 10^43 and i'd guess the above is pretty close to worst case.

Regards,
Vincent

[Christenson]

Vincent:
Forwarding your calculation at this point probably only raised your crank score. Let's start with a precise count of the number of piece sets with 31 pieces on the board. Don't forget that the pawn being promoted has a choice of what to be promoted to.

[diep]

Originally Posted by Christenson

Vincent:
Forwarding your calculation at this point probably only raised your crank score. Let's start with a precise count of the number of piece sets with 31 pieces on the board. Don't forget that the pawn being promoted has a choice of what to be promoted to.

I wrote code showing all different piecesets say a year or 12 ago already or so :)

For your information, my chessprogram has its own EGTBs.

Not very challenging therefore to continue; there is enough evidence now
that 10^43 really is far beyond the truth by some order of magnitudes, not to mention the 10^5x estimates i saw posted here :)

Regards,
Vincent

[Christenson]

Originally Posted by diep

I wrote code showing all different piecesets say a year or 12 ago already or so :)

For your information, my chessprogram has its own EGTBs.

Not very challenging therefore to continue; there is enough evidence now
that 10^43 really is far beyond the truth by some order of magnitudes, not to mention the 10^5x estimates i saw posted here :)

Regards,
Vincent

Your chess program may indeed be able to enumerate all possible sets of chess pieces with a given number of pieces remaining on the board. Would you care to share those numbers with us?

[Christenson]

Hi SM88

I decided to do a poor man's enumeration of all the possible positions (really, configurations) of a pawn and 2 kings. I ended up listing out 43 special cases; thus Batalov's howl is quite appropriate. I have attached a PDF; I'll do the arithmetic after someone has checked it.
The decoder key is that only numbers that have a letter directly in front of them count; a is for the top level positions of the pawn; b is for the positions of the opposing king; c is for the positions of the friendly king, the one of the same color as the pawn.

Christenson (and thanks for running prime95!)