chess positions: how many legal ones are there ?

[diep]

Originally Posted by science_man_88

yeah it's hard because for example if you have a pawn in the edge of something like the 8 king move spaces ( so nine total squares use) along the edges you have 2 positions for each I think where the pawn doesn't affect king on king, the hard part is legality( without playing from the beginning). We've also got to consider what color the pawn is.

I did do a lookup using code. If you do your math correct
you will end up at something like for KPK:
81664 positions for one side to move
84012 positions for the other side to move

Thanks,
Vincent

[diep]

Originally Posted by Mr. P-1

You don't need to track king castlability, only the castlability of the rooks. Any move by the king removes castlability from both rooks.

question for sm88: defining a "configuration" as a particular arrangement of chess men on a board, without additional information, and a "position" as a configuration plus additional information sufficient to determine the entire space of possible games that might follow, what is the maximum number of positions that might be represented by a single configuration?

Your note is correct. That's also how my chessprogram tracks it internal.

As for the estimate: there is 2 requirements for 1 side to be able to castle.
A king must be on e1 (resp e8) AND the original rook must be on a1.

To use a rough estimate, this happens in less than 0.1% of the positions.
So we can safely ignore counting this, knowing that in my calculation i already do not reduce for attacks to the king, which is quite a big percentage. Yet all this is lineair overhead or lineair reduction. It's noise.

Same thing is the case for en passant by the way though this adds up a bigger percentage to the number of legal positions than castling as it involves 2 pawns and 2 empty squares.

[science_man_88]

Originally Posted by diep

A king must be on e1 (resp e8) AND the original rook must be on a1.

(respectively a8) or h1 (respectively h8).

[Mr. P-1]

Originally Posted by diep

Your note is correct. That's also how my chessprogram tracks it internal.

As for the estimate: there is 2 requirements for 1 side to be able to castle.
A king must be on e1 (resp e8) AND the original rook must be on a1.

To use a rough estimate, this happens in less than 0.1% of the positions.
So we can safely ignore counting this, knowing that in my calculation i already do not reduce for attacks to the king, which is quite a big percentage. Yet all this is lineair overhead or lineair reduction. It's noise.

Same thing is the case for en passant by the way though this adds up a bigger percentage to the number of legal positions than castling as it involves 2 pawns and 2 empty squares.

You don't appear to be answering the question I asked.

Minimally, I'm asking for a number. A complete solution would additional specify a particular configuration and would demonstrate that every position was legal in the "could be reached from the opening position in a legal game" sense of the word.

[Christenson]

Originally Posted by Mr. P-1

You don't appear to be answering the question I asked.

Minimally, I'm asking for a number. A complete solution would additional specify a particular configuration and would demonstrate that every position was legal in the "could be reached from the opening position in a legal game" sense of the word.

OK, the worst-case situation for P-1 type positions versus configurations that SM88 and I are counting (that is the configuration representing the most positions) has, on both sides, two rooks in castling position and a bunch of pawns in "en passant" position. That's 16 for the rooks, obviously all reachable, times a choice of none or one of 8 pawns ready to be taken "en passant", and one side or the other to move, so an upper bound for this is 16 * 9 * 2 =288. Not that I believe it is possible to have all 8 pawns in a position to be taken en passant, but I think 5 might be possible. Gallery?

[science_man_88]

Originally Posted by Christenson

OK, the worst-case situation for P-1 type positions versus configurations that SM88 and I are counting (that is the configuration representing the most positions) has, on both sides, two rooks in castling position and a bunch of pawns in "en passant" position. That's 16 for the rooks, obviously all reachable, times a choice of none or one of 8 pawns ready to be taken "en passant", and one side or the other to move, so an upper bound for this is 16 * 9 * 2 =288. Not that I believe it is possible to have all 8 pawns in a position to be taken en passant, but I think 5 might be possible. Gallery?

well you can only set up one at a time by the rules I know which is that if en passant is to be done it is to be done on the move directly after the 2 square move that allows it. by the way I gave you a number for bounds as I see them ( I could be wrong using one thing but I'm unsure about what it was I was originally thinking).

[diep]

Originally Posted by Mr. P-1

You don't appear to be answering the question I asked.

Minimally, I'm asking for a number. A complete solution would additional specify a particular configuration and would demonstrate that every position was legal in the "could be reached from the opening position in a legal game" sense of the word.

The current estimates on the number of positions are so bad estimated, i've seen many estimate it as 10^50, and the last research that was officially published estimated it at 10^43; that even if a sane person would calculate just for a few hours, you already have a much better estimate.

Right now the exponent is not even close to reality; i see a big difference between 10^43, the current estimate, and my guess being something in the 10^3x where x is probably something around 4-6, making it 10^34 to 10^36

As the number in front of that 'y' in y * 10^34 is not even going to get mentionned, is it relevant, knowing we speak about something that will influence the number y for less than a few percent; this where by measuring the average number of possibilities in a guided chess search, i know from statistics that the average number of semi-legal moves is 40 (nearly exactly 40, so not 35 as you will find in literature from before the times that we had computerchessprograms where we could measure it with).

Knowing there is 64 squares and many pieces of the own color at the board, that means that the number of illegal positions, caused by attacks of the opponent, is much more frequent, than the number of en passant positions + positions with castling.

Yet we reduce only a small factor for that, as the most important thing is to get a much better exponent; right now the exponent in all published work is so ugly bad estimated, that i'd argue it's better to first estimate that more correct.

Arguing here about something far behind the dot is not a hobby mine when the current estimate is approximately 1000000000% off, as they didn't know how to count the number of possibilities.

Regards,
Vincent

[diep]

Originally Posted by Christenson

OK, the worst-case situation for P-1 type positions versus configurations that SM88 and I are counting (that is the configuration representing the most positions) has, on both sides, two rooks in castling position and a bunch of pawns in "en passant" position. That's 16 for the rooks, obviously all reachable, times a choice of none or one of 8 pawns ready to be taken "en passant", and one side or the other to move, so an upper bound for this is 16 * 9 * 2 =288. Not that I believe it is possible to have all 8 pawns in a position to be taken en passant, but I think 5 might be possible. Gallery?

In chess you can only capture en passant according to the rules when the opponent has just played forwards a pawn 2 steps, still obeying all other rules of chess.

So at most at 1 square on the board, you can capture en passant.

The only thing that needs to get hashed then is that square you can capture en passant at that moment.

For example from openings position: 1.e4,f5 2.e5,d5

Now white is allowed to capture en passant at d6 and remove the pawn from d5 from the board; capturing en passant at f6 and removing the f5 pawn is not legal.

So at most from 2 sides you can capture a pawn en passant; for example:

1.e4,Nf6 2.e5,Ng8 3.c4,Nf6 4.c5,d5 now white is allowed to take en passant at d6 with either the c5 pawn or the e5 pawn.

Regards,
Vincent

[diep]

Originally Posted by science_man_88

I know there have been estimates in the past I want to work together to find an exact number. I know from math that there are 3612 positions with only each players king on the board. So far using 1 of every other piece possible positions jump to 800,000 + the last estimate I heard was 10^49 I think. I can upload a image of all the legal moves/ places each piece can use the hard part then is not coming up to a conclusion that Mr p-1 said in another thread after I stupidly talked about this.

The only correct mathematical method is to give 3 numbers

a) hard upperbound
b) hard lowerbound
c) estimate how many positions there probably are

Yet the methods used to calculate are so primitive that so far the estimate is 10^43 positions and nothing else exists. All the mathguys have only generated estimates which is fine with me, but they are off by factor 10^7 to 10^9 or so for the latest number estimated which was 10^43.

As i have shown the upperbound on 32 pieces is 10^32
The difficult to calculate and most likely biggest entity is 31 pieces.
Also interesting to calculate, in order to prove it has less positions than 31 pieces, that will be 30 pieces. Only when this number is bigger than 31 pieces, then calculating 29 pieces also becomes interesting, otherwise from my viewpoint it is not.

The grand total of that all will be the new estimate.

When that estimate gets calculated in an upperbound method, that's fine with me, yet it will get cited as the 'real number of chesspositions' elsewhere, so it better be well calculated instead of the rudimentary methods i've seen so far; All estimates so far you didn't need even a computer for to calculate; so to speak the old Egyptians could already calculate it, had they known the modern rules of chess :)

Regards,
Vincent

[Mr. P-1]

Originally Posted by Christenson

OK, the worst-case situation for P-1 type positions versus configurations that SM88 and I are counting (that is the configuration representing the most positions) has, on both sides, two rooks in castling position and a bunch of pawns in "en passant" position. That's 16 for the rooks, obviously all reachable, times a choice of none or one of 8 pawns ready to be taken "en passant", and one side or the other to move, so an upper bound for this is 16 * 9 * 2 =288. Not that I believe it is possible to have all 8 pawns in a position to be taken en passant, but I think 5 might be possible. Gallery?

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.

[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, there is a few good diagrams.
See: http://en.wikipedia.org/wiki/En_passant