How many different chess positions are there?

pvmike wrote:

third times a charm I got 168024 for the number of possible positions in a K and P vs K ending

If this number is anywhere near the right ballpark I'd say one would be a lot better off studying endgame technique than trying to memorize the best move in every position.  But don't ask me.  I'm a terrible judge of bad whiskey, especially on Friday nights.

good point

But you have do basically double that to account for who's move it is, all the while, of course, eliminating any positions where one side is in check and it is the other side's move.

Here's another wrinkle to add to the complexity of the overall calculation.

Although legal, this position is also impossible to reach:

As is this one:

the number that I remember seeing quoted was 10^80 on Chessbase.com, which was listed as more than the number of atoms in the known universe...

Also, I don't think that anyone has yet mentioned things such as castling and en passant rights, which make things even more complex with more possibilities. Also, whose move it is is completely relevant and distinct, and to an extent even number of moves since a pawn move/capture or number of times that the exact position has been reached (cf. threefold repetition) is relevant here.

With all the discussion on just 1 or two pawns, this makes the feats achieved by endgame tablebases even more astounding...

Taking all of this into account, my rough estimate of the number of legal positions would be very near that 10^80 number

Yet another wrinkle:  every position also has to carry a count of how many moves it's been since the last pawn move or peice capture, so you can pretty much multiply your final position count by 50.

I could be wrong, but I believe the 10^80 estimate refers simply to legally reachable arrangements of the peices on the board without regard for whose move it is, castling rights, en passant, etc.  Just the raw position.  Could somebody ratify this for me?

bowanza wrote:

I could be wrong, but I believe the 10^80 estimate refers simply to legally reachable arrangements of the peices on the board without regard for whose move it is, castling rights, en passant, etc.  Just the raw position.  Could somebody ratify this for me?

I don't believe that is correct, as by the simple math that has been posted throughout this thread, 13 possibilities on a square, 64 squares, means 13^64 = 1.96 x10^71, which is significantly less than 10^80, not even taking out the many many illegal positions with pawns on the 1st or 8th, double checks, extra kings, no kings for a side, 9+ pawns, 10+ queens, 11+ of any other piece, etc.

En passant consideration does not significantly increase the number of positions, because it would only generate an additional position whenever the situation arose, which is very seldom.

The same could be said for castling.  Castling oppurtunity is rare, but when it does occur, it simply generates an additional possible position.

Who has the move generates an additional position for every single position, doubling the figure.  (Actually thats not true, that is an over-estimate.  But consider the following opening:  1  P-d3    P-d5    3   P-d4  ....)

And as somebody pointed out, the 50-move rule would multiply all positions by 50, because every raw position could have 1 through 50 moves have gone by without the movement of a pawn or the capture of a peice.  (actually that is an overestimate too, but imagine a game like this 1  N-c3   N-c6    2 N-b1   N-b8 3  N-c3 etc.)

Now lets assume you needed to know all the above information at all times, regardless if they applied (a gross overestimate).  That means take the total amount of raw positions, and multiply by 2 (for the move), 2(for whether castling is still legal), 2 (for whether en passant is legal), and 50 (for the number of moves gone by), and you would be multipying by 2*2*2*50 which is 4*100 = 400.  Now the log base 10 of 400 is 2.6.  In other words, 10 ^ 2.6 = 400.  That means the exponent on the 10 ^ 80 positions would be only 2.6 smaller than it should be, so the total number of positions would be bounded by 10 ^ 82.6.  Even if it were the other way around, if you needed to subtract the 2.6, you would get 10 ^ 77.4, which is much greater than 10 ^ 71. 

But 10 ^ 71 is much greater than the total number of positions, because almost every position generated by 13 ^ 64 would be impossible because a randomly generated position would be very unlikley to have one king of each color, let alone a possible number of pieces for each type of piece for both sides.

Oh, and some consideration for three fold repition needs to be made as well....

I'll tell you, I don't know who did the math on the 10 ^ 43 estimate, but I'm just glad I don't have to try to count that high.

excellent analysis bowanza. Although, there are lots of positions where castling in two directions would be possible, still the en passant and castling probably add "only" something like 10^20 to the count or something. I've got a feeling now that a much better estimate would be 10^50 or somewhere thereabouts. The exact number courld be determined, but what's the point really?

There are, of course, many more legal games than positions, as resigantion or draw agreement can happen at any time, and transpositions are way common. Actually it's infinite without the 50 move or threefold repitition rules being claimed as soon as they can, which of course they don't need to be.

Actually, re-looking at the chessbase article, it said that there are " at least 10^40" legal positions in chess

artfizz wrote:

of the general order of 64! / 32!(8!)2(2!)6   [Shannon]

hey, don't shout your numbers.

WanderingWinder wrote:

Actually, re-looking at the chessbase article, it said that there are " at least 10^40" legal positions in chess

Is that raw positions?  Or is that including the other details needed to formally play the game (en passant,  etc.)

WanderingWinder wrote:

 I've got a feeling now that a much better estimate would be 10^50 or somewhere thereabouts. The exact number courld be determined, but what's the point really?

I would beg to differ.  I don't think the exact number could ever be calculated.  When I say this I mean legal positions reachable only by legal play and not necessiarly including the extra information like who has the move.

dylan wrote:

artfizz wrote:

of the general order of 64! / 32!(8!)2(2!)6   [Shannon]

hey, don't shout your numbers.

If you're kidding, that's really funny. If you're not, that's really dumb.

I've been trying to think of a way to estimate how many positions there are and this comes to mind:

First figure out how many possible pawn positions there are.  Then based on the types of pawn positions, figure out how many pawn captures or promotions could have occurred and based on that first figure out, on average, how many different ways the kings could be placed and then figure out, again on average, how many possible different ways all the different possible amounts of peices for both sides could be placed legally on the board and placed there through legal play from the starting position (a hard sub-task).  Multiply all these together.

Does that make sense?

No, it doesn't.  You have to add up all probabilities of each type of pawn structure occurring times the average number of possible legal reachable arrangments of the remaining pieces for each type of pawn structure. 

Better?

EDIT:  For all legal pawn structures find all reachable legal positions with the remaining pieces.  The sum would be the total number of positions.

Billium248 wrote:

Fourpointo wrote:

Both numbers are very very high, but have limits. After 50 moves without a pawn movement or piece taken, the game can end in a tie.

 It CAN, but it doesn't have to.  Go to the list of current games on this site and sort by number of moves.  The #1 game at the time of this post was on move #347!!  The 50-move-rule is NOT automatic!!  It is designed to allow one player to declare a draw even when the other player refuses.  If neither side claims the draw, and both sides agree to play on, then there is no limit to the number of moves that can be made.

Yes, the game could continue; however, according to the current USCF rules, there are 4 ways to  deal  with  a  king  in check: move the king, capture the piece giving check, make an interposition, or declare a legal draw.  So, if in any game the position does repeat 3 times, say, and neither player declares a draw right away, then when one player's king get's checkmated, it is in fact not checkmate, as the player has a way out of check (to declare a draw), in fact, the player is zugzwang and must declare a draw at that point..............

ask chuck