[QUOTE=science_man_88;257497]I'm not talking practical I'm talking legal (just because it doesn't usually happen does not mean it can't happen).[/QUOTE]

there is a lot of things that *legally* cannot happen.

a pawn cannot pass its opposing pawn without capturing.
when capturing a piece gets removed from the board, reducing the number
of possibilities really a lot.*

when you look theoretic to chess, you go for chaos positions. chaos positions have lots of possibilities usually; that means king in check reduction is huge there as you can theoretic prove that 2 kings never can be at the same time in check, nor is it possible that a king is on a field that's attacked 3 times by the opponent.

it's not possible to promote to 9 queens without a bunch of captures.

I didn't calculate the minimum of captures there, but it's *huge*.
Same thing for 4 queens, also requires quite some captures.

So that really reduces your theoretic gamespace bigtime.

The real big reduction is the pawn reduction based upon space they can't occupy.

For a number of pawns you can prove that it is not possible to put them sooner on the board than other pawns, without captures being done.

Now of course an easy way to calculate this is by redefining the way how we count squares on the board.

Equally you have another complex reduction, theoretically, when just 1 capture occured, giving us 31 pieces.

It is possible then for 1 pawn to have shifted direction from the normal order, yet it also means again that in case of promotion it is one of these 2 pawns involved (either the capturing pawn or the pawn that opposed it) that limits the possibilities.

This is reductions no one ever has done when estimating the number of theoretic possibilities, AFAIK.

You need huge lookup tables to calculate all all this. Calculating the number of legal positions in this manner really will eat massive system time.

* = what i mean is this type of calculation:

{
Let's use as an example an empty board with just 2 pawns of black and 2 from white.

white has a2,b2, black has a7, b7

Now normally spoken we have 12 squares where the pawns can be.

Yet if for example the white pawn is on a5 we can prove that with 4 pawns on the board, there is a black pawn on a6 or a7, so it cannot be located at a2..a4 as the a5 pawn blocked it. So we have then in this example 2 possibilities for a black pawn instead of 9. That really reduces the number of theoretic possibilities isn't it?

This really reduces the number of theoretic possibilities bigtime.
Also not that it reduces the number of doubled pawns.

To give an example of that:
If we have a pawn on a6 and there is a pawn on b7 or when there is no capture done,
then we can prove that it is not possible for a black pawn to be on a7.

}

[QUOTE=CRGreathouse;257488]Didn't he answer that in his original post?[/QUOTE]
@diep: As long as we understand that we are counting the number of legal chess positions, and not the ones that actually occur with reasonable opponents, the math is fine.

Science Man has indeed been throwing out this number, and it is indeed correct. However, I mis-recognized it, as it came without a good label.

What we can do with it is to recognize that there are only 3612 possible ways to place the two kings in *any* legal chess position, regardless of how we may place the other pieces.

so for the estimate with all the pieces on the board, we have 3612 * 62!/32! instead.

Now, for the three pieces on the board problem: We have to choose the other piece, rook, knight, bishop, black queen, or pawn (5 choices), and there are at most 62 places those pieces could be.

[QUOTE=diep;257498]It is possible then for 1 pawn to have shifted direction from the normal order, yet it also means again that in case of promotion it is one of these 2 pawns involved (either the capturing pawn or the pawn that opposed it) that limits the possibilities.

This is reductions no one ever has done when estimating the number of theoretic possibilities, AFAIK.[/QUOTE]

Hah! unlikely.

So to approximate things in a silly manner in case of 32 pieces, we can prove we didn't have any promotion yet nor capture.

That means that by rough estimate, and i definitely do not take into account the king in check legalty, we have this amount of possibilities:

pawns: 3^16
Now 48 possibilities left count down to 33
Division by mirrorring left-right is factor 2
the same pieces reductions which simply we'll use 2^6
for rough estimation i count factor 2 for king-king reduction and legality.
In reality it is a lot more of course.

So that's (3^16 * 48!) / (32! * 2^8) = 7.9 * 10^30 for the openingsposition

That sounds *very* realistic approximation to me.

Vincent

[QUOTE=Christenson;257499]so for the estimate with all the pieces on the board, we have 3612 * 62!/32! instead.[/QUOTE]

I'm not particularly happy with that bound, since it essentially just labels each of the pieces and tracks where they go. Obviously replacing unlabeled pieces by labeled ones is valid for finding an upper bound, but this does not take into account other states that pieces may be in. For example, suppose all the pieces but a single pawn are placed; in your upper-bound, there are at most 3612 * 62!/33! ways to place them and at most 33 ways to place the pawn on the remaining squares. But the pawn has many more than 33 possibilities: in each of the legal positions it can be normal, promoted to queen, vulnerable to [i]en passant[/i], etc.

Now the upper bound is high enough that it's still a true upper bound, but not 'for the right reasons' as far as I'm concerned.

[QUOTE=diep;257501]So to approximate things in a silly manner in case of 32 pieces, we can prove we didn't have any promotion yet nor capture.

That means that by rough estimate, and i definitely do not take into account the king in check legalty, we have this amount of possibilities:

pawns: 3^16
Now 48 possibilities left count down to 33
Division by mirrorring left-right is factor 2
the same pieces reductions which simply we'll use 2^6
for rough estimation i count factor 2 for king-king reduction and legality.
In reality it is a lot more of course.

So that's (3^16 * 48!) / (32! * 2^8) = 7.9 * 10^30 for the openingsposition

That sounds *very* realistic approximation to me.

Vincent[/QUOTE]

this 32 piece case we can further calculate by accurate calculation of the pawns, where the first approximation was a bit weird of course.

the tough thing to count is the pawns.

If a2 pawn is on a2, then black's a-pawn has 5 possibilities.
a2 => 5
a3 => 4
a4 => 3
a5 => 2
a6 => 1
---------+
15 possibilities.
My rough estimate was 3^2 = 9, A BIT PRIMITIVE EVEN IF I SAY SO MYSELF AS A TITLED CHESSPLAYER.
That'll increase our total a tad :)

So we get then to :

(15 ^ 8 * 48!) / (32! * 2^8) = 4.7 * 10^32

Ah off by less than factor 100 in the first estimate, not bad :)

I guess if you are going to count like this in a systematic manner,
you'll end up with far under 10^40 legal chesspositions.

We didn't even correctly estimate king-king + legality reduction yet then.

[QUOTE=CRGreathouse;257502]I'm not particularly happy with that bound, since it essentially just labels each of the pieces and tracks where they go. Obviously replacing unlabeled pieces by labeled ones is valid for finding an upper bound, but this does not take into account other states that pieces may be in. For example, suppose all the pieces but a single pawn are placed; in your upper-bound, there are at most 3612 * 62!/33! ways to place them and at most 33 ways to place the pawn on the remaining squares. But the pawn has many more than 33 possibilities: in each of the legal positions it can be normal, promoted to queen, vulnerable to [i]en passant[/i], etc.

Now the upper bound is high enough that it's still a true upper bound, but not 'for the right reasons' as far as I'm concerned.[/QUOTE]

It's a very bad first upperbound estimate if i may say so, as the pawns have only 48 legal squares.

This upperbound is 10^53. The next simplistic upperbound is of course:

pawns: 48! / 32!
pieces: 48! / 32!
which gives 10^51

However as i showed already for the 32 piece example it's going to be tough to get to 10^40 in fact.

[QUOTE=diep;257505]It's a very bad first upperbound estimate if i may say so[/QUOTE]

It's not mine, and the purpose is not to be small but to be correct. I was debating that point.

[QUOTE=diep;257505]However as i showed already for the 32 piece example it's going to be tough to get to 10^40 in fact.[/QUOTE]

I think there are more than 10^40 positions in total, so I don't think any method can get that small.

[QUOTE=CRGreathouse;257508]I think there are more than 10^40 positions in total, so I don't think any method can get that small.[/QUOTE]

Well i prove to you that for 32 pieces it's 10^32 positions.

That's far away from that 10^50 upperbound.

With just 10^32 positions for 32 pieces,
how on planet earth would you want to get to above 10^40 then for all the combinations of 31 pieces and 30 pieces; obviously when we get down to less pieces than 32, removing a piece from the board has a rather dramatic impact on the number of possibilities. It gets down dramatically, especially if we remove a piece rather than a pawn; removing a piece already removes a factor of 33.

That's *huge* reduction.

I'd give you as a hint to remove a pawn from the board, getting to 31 pieces.

Your pawn now can promote to {queen,rook,bishop,knight}. Note it can't stay a pawn at promotion :)

Ok on second thoughts i'm guessing now it's going to be hard to get to 10^38

Probably i can shift the upperbound down as well when i fiddled with 31 pieces one day :)

Yeah i claim it's less than 10^38 now.

Vincent

[QUOTE=CRGreathouse;257507]It's not mine, and the purpose is not to be small but to be correct. I was debating that point.[/QUOTE]

Indeed, we were interested in *correct* upper bounds on the number of positions, with a little teaching on how to construct these to one of our members, who is a bit challenged on the subject, or at least when it comes to communicating his estimates.

With all 32 pieces on the board, I am indeed expecting the number to be a little small, as we have lots of constraints, especially the one on the pawn position, and no pawns can be promoted. But as we lose pieces, we have to keep track of how many pawns got promoted to what, and we lose convenient constraints, and the number explodes.

We haven't even gotten to the question of whether tactically identical positions are counted separately; for example, if one side is in the starting position except for the pawn in the a file, (queen's rook, I think), which is in the 4th row, and the other side is in the starting position (either side can be ready to move), does this count as one or two distinct positions?

ScienceMan, back to the question about the number of distinct legal positions with three pieces on the board. There's a problem or two with my math in the previous post; what is it?