Not logged inRybka Chess Community Forum
Up Topic Rybka Support & Discussion / Rybka Discussion / What you People Think ?
1 2 Previous Next  
Poll Chess is a ........ (Closed)
Draw 34 68%
Win for White 7 14%
Win for Black 2 4%
No idea 7 14%
Parent - - By George Tsavdaris (****) Date 2007-06-26 17:04

>So a corollary of your idea would be that the largest number of possible positions would be with one piece or zero pieces.

As Uri already said: He didn't say that!
He just said that the positions with 31 pieces are more than the positions of 32 pieces.
He didn't generalize that.

>Let's count from the very beginning now:...............bla bla............indistinguishable, and this now gives 2.966225 x 10^44.  ..................bla bla.............................Doing this yields 4.6347 x 10^44 as the number of ways of putting 32 chess pieces on 64 squares.

These two 10^44 must be 10^42.

>Now for the number of ways of putting 31 chess pieces on 64 squares.  We start off with 64 permute 31 = 64!/(64 - 31)! = 64!/33! = 1.46 x >10^52.  ............................Thus, we take my previous answer and divide first by 8! (since one side still has all eight pawns) and now by 7!, and >then again six times by 2!, yielding 1.12357 x 10^44 as the number of ways of putting 31 chess pieces on 64 squares.

Again this is 10^42

>Note that it doesn't matter which color is the pawn--that's already taken into account by the fact that I already double-counted by saying "32 >chess pieces" at the beginning instead of "16 chess pieces of each color".  You might come back and say, "well we need to add in what >happens if we remove a knight, a bishop, or a rook, etc.".  For each of those, the answer is smaller by AT LEAST a factor of four, and with >removing the queen, the answer is smaller by a factor of 8.  Thus, adding these in gives an answer that is still smaller than what we had with >32 pieces.  In addition, I'm quite certain that we're at least double-counting in here somewhere--at least, that's what my combinatoric gut tells >me.

Let's do your calculations again of 31 Chess pieces with:

Missing a Pawn:
64! / (33! · (2!)^6 ·8! ·7!) ~= 1.12·10^42

Missing a Rook OR Knight OR Bishop:
64! / (33! · (2!)^5 · (8!)^2) ~= 2.8·10^41

So positions with missing a Rook + positions with missing a Knight + positions with missing a Bishop are:
3·2.8·10^41 = 8.4·10^41

Missing a Queen:
64! / (33! · (2!)^6 · (8!)^2) ~= 1.4·10^41

So all positions until now are: 1.12·10^42 + (1.4+8.4)·10^41 = 1.12·10^42 + (0.98)·10^42 = 2.1·10^42

Still smaller than the 4.6347 · 10^42 for all 32 pieces permutations.

BUT we haven't included promotions into the game yet. And this is where Uri will be right:

Positions with a missing Pawn and with one promotion of a Pawn(obviously) to a queen:

64! / (33! · (2!)^6 ·2! · 8! ·6!) ~= 3.93·10^42

So until now we have for 31 pieces:
2.1·10^42 + 3.93·10^42 = 6.03·10^42  Bigger than that with 32 piece permutations.

Not to mention where the positions will reach for 31 pieces if we start promoting to Knight, Bishop etc.... MUCH bigger than the positions with 32 pieces.
Parent - By turbojuice1122 (Gold) Date 2007-06-26 18:21
I don't see anything generally wrong with your results here at first glance; if I think of anything major, I'll be sure to let you know :-). 

On your last statement, the result wouldn't be "much" larger because underpromotions would yield fewer possible positions than promotion to queen because the division due to identical pieces would be greater; assuming everything else is correct, though, adding these in would still yield a result greater than with 32 pieces.

In this case, I wonder which number of pieces would yield the largest number of positions--I would guess probably 29 or 30, after which we wouldn't really be able to increase our variety more than the cost we get from decreasing the total number of pieces on the board.
Parent - - By George Tsavdaris (****) Date 2007-06-26 17:34

>with 32 pieces you know that there are no captures so in every file there are 2 pawns and the number of options for pawns is only 15^8
>You also know that there are no promoted pawns and you have not these restiction with 31 pieces.

>number of legal positions with 32 pieces is smaller than 15^8*48*47*46*45*(44*43/2)*(42*41/2)*(40*39/2)*(38*37/2)*(36*35/2)*(34*33/2)

Yes this is from a point of view where we don't include en-passant in the calculations.

But en-passant is a rule of Chess and makes things different, so your above upper limit for 32 pieces is not correct(it is lower than the limit with en-passant).

I mean:

Your above number obviously has been derived with the following way:
-In every file there will always be 2 Pawns(one black and one white) from ranks 2 to 7 that means 6 available positions.
-That means 6·5/2 ways for each file, the 2 Pawns can be arranged.
-That means 15 ways for each file for the Pawns.

Since we have 8 files we will have 15^8 possible arrangements for the Pawns.

There remain 48 squares for the white Queen. So we have 15^8·48.
There remain 47 squares for the white King. So we have 15^8·48·47.
There remain 46 squares for the black Queen. So we have 15^8·48·47·46
There remain 45 squares for the black King. So we have 15^8·48·47·46·45
There remain 44 squares for the 2 white Rooks. So 44·43/2 ways to place these 2 Rooks. So we have 15^8·48·47·46·45·(44·43/2)

BUT a position with a white Pawn for example on c4 and a black on c4 can mean 2 things: The en-passant move for c4-Pawn to be valid or not to be valid.
That means the following 2 positions are different for Chess:
r2qkb1r/ppp1pp2/n3bn2/4N1pp/2Pp1PP1/N7/PP1PP2P/R1BQKB1R b KQkq - 0 1

r2qkb1r/ppp1pp2/n3bn2/4N1pp/2Pp1PP1/N7/PP1PP2P/R1BQKB1R b KQkq C4 0 1

Your upper limit is correct if we forget en-passant but we can't forget en-passant since we are talking about Chess positions.
So we should count twice positions where a white Pawn is on 4th rank and a black Pawn near it on an adjacent file in the same rank.
So your upper limit increases a lot.

So in order to count correctly all possible Chess positions we should differentiate between those Chess positions that have the pieces on the exact same places, but the castle/en-passant rights, are different.
Parent - - By turbojuice1122 (Gold) Date 2007-06-26 18:22
If you have en passant, you no longer have 32 pieces on the board, as per at the beginning of your statement that his result with 32 pieces was wrong.
Parent - - By Uri Blass (*****) Date 2007-06-26 18:40
We are talking about enpassent possibility.

You can have 32 pieces on the board and enpassent possibility for next move and it is possible that we have not enpassent possibility for next move.

These 2 options are different chess positions.

Parent - - By turbojuice1122 (Gold) Date 2007-06-26 19:07
That's a minor technicality--since we're already talking about the # of legal chess positions, which for each number of pieces is clearly smaller than my overestimates, the percentage of legal en passent positions compared with those that don't exist with the same number of pawns is quite negligible; there is a reason why this "obviously necessary" rule didn't make its way into chess for so many centuries.
Parent - - By George Tsavdaris (****) Date 2007-06-26 19:52
Not exactly.

The en-passant rule adds some more positions to the upper limit of possible Chess positions Uri gave.
Even if the number of the added(by taking into account en-passant) positions is very very small for example even 2, then the upper limit would  be wrong.

Imagine for example the upper limit without en-passant to be 10^33.
The en-passant positions to be 10^25. Very small compared to 10^33.
And the non-legal positions of these 10^33 to be 10^21.

Then we would have as an upper limit the number 10^33, but the real Chess positions would be 10^33 + 10^25 - 10^21 which is bigger than our upper limit!
So the upper limit would be incorrect.

We don't know of course that the en-passant positions are more than the non-legal positions, but this is the reason also not to use an incorrect upper limit.
Parent - By turbojuice1122 (Gold) Date 2007-06-26 21:12
I think it's still quite fine to use the previous numbers--if we keep our numbers to 2 or 3 significant figures, which is certainly more than we're justified in using, taking en passent positions into account would not change these numbers.  Recall that the fundamental point is that the upper limit in the number of chess positions is 10^(40+n), of which I think we're all now in agreement, and also that n < 4.
Parent - By George Tsavdaris (****) Date 2007-06-26 19:38

>If you have en passant, you no longer have 32 pieces on the board, as per at the beginning of your statement that his result with 32 pieces was >wrong.

Wrong. In the following game we have en-passant and we have also 32 pieces on the board:
1. a4 e5 2. Nf3 e4 3. d4
Parent - By Uri Blass (*****) Date 2007-06-26 18:38
You are correct but most of the possibility of pawn squares are counted only one time.

we have 7 options to choose the 2 files when enpassent capture is possible
After that we have 2 options to choose the capturing file.
After that we have white a5 black b5 so white needs pawn at b2-b4 and black needs pawn at a6-a7 so we have 6 options.
After that we have 15^6 options to choose pawns.

total result
less than 7*2*6*15^6 positions that were counted more than once.

I say less than because cases like white pawns a5 c5 black pawns b5 were counted more than once.

practically there are piece placement when you need to count more than twice(white a5 e5 black b5 d5) that can be 3 different pawn structures based on ep possibility but this possibility was counted twice so practically the number of additional pawn structures is slightly smaller than

Parent - - By grolich (***) Date 2007-06-26 07:58
No they aren't.
That's a lower bound on the game tree complexity, which is much higher than the number of positions.

That number is between 10^42 and 10^50.
Parent - By BigBen (****) Date 2007-06-26 10:11
    I tend to agree that chess is a draw but have always thought it is a flawed game anyway lol ... When someone can be a Bishop and a Pawn up (just one example) and can only draw!!! because the queening square is the wrong colour .... I reckon junk the stalemate rule and see where this takes us ....

Parent - By Uri Blass (*****) Date 2007-06-26 11:20
I am not sure that the number is higher than 10^42

Can you prove it?
Parent - By Hetman (*****) Date 2007-06-26 19:56
Draw, to win you have to have rook more at the end :-).
Up Topic Rybka Support & Discussion / Rybka Discussion / What you People Think ?
1 2 Previous Next  

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill