How many different chess positions are there?

I have seen criticism of your method and your article by other posters ( and all other credible looking estimates are much higher than yours ). I'm not in the position however to decide what the correct number is.

More important that I'm speaking about a full tablebase of chess which means that the database has to include the evaluation of all positions ( by evaluation I mean +/- mate in N moves or draw - a signed integer, zero meaning draw ). So if storing a position and its evaluation requires some low multiple of 10^2 bits ( many estimates speak of cca. 150 bits to store a position + you need to store the evaluation as well ) this increases the number of required bits by two orders of magnitude compared to the number of legal positions. My calculation is based on chess having cca. 10^44 legal positions.

[ EDIT : ]

If both sides have 9 queens ( which is legal in chess ) plus a king and coding a queen and a king both takes 6 bits, that means ( 18 + 2 ) * 6 = 120 bits, plus you will have 44 empty squares giving a total of 120 + 44 = 164 at least. So the maximum of 131 bits per position does not seem to be right in your article.

When I entered "how many chess positions" in Wolfram Alpha, it gave me the geographical distribution of rye brome in North American. 

Regardless if there are bugs in gonzepge's representation, I think this is a slight improvement:

- Store the king positions *separately*, outside of the Huffman compressed stream. A square requires 6 bits, and is no worse than having a 6-bit code for the king in the stream. Any legal position has kings anyway.

- This allows you to shorten the queen representation to 5 bits in your Huffman encoding, stripping a few bits off when there are queens on the board.

This is a good idea.

In addition I have a few observations:

Having 3 bit codes for pawns does not achieve much since at the cost of 4 pawns all other pawns can be promoted. It is legal to have 26 non pawn, non king pieces on the board. If the 26 pieces on average have 5 bit codes, this means 130 bits, plus you need 36 [ 64 - ( 26 pieces + 2 kings ) ] bits for empty squares, plus 12 bits for the two kings according to your representation which is 178 bits, this gives an upper bound of 10^53. Even if you could store every piece apart from pawns on four bits ( which is impossible ) the same calculation would yield 26 * 4 + 36 + 12 = 152 bits, which gives an upper bound of 10^45. This encoding can not put a lower upper bound on the number of legal positions than other estimates purely on the basis of the bits needed to store a position in the worst case, this is for sure.

This is how Shannon calculated:

This is the exact figure of Shannon's calculation:

This means that you can shuffle the pieces in the starting position in nearly 10^43 distinct ways ( of course some of the positions will be illegal ). No matter what encoding you use this is a sheer combinatorical fact.

My Darling Mathematicians,

Since we can quickly & exactly quantify say, the first 5+ move grand total possibles, can we chart that ?....then find a similar matching calculus function (half-parabola ?) that can roughly estimate (say within 5% or less ?) the possible combos after say, 50 moves ?........Lola

I think you are calculating the game complexity here ( the number of distinct games ). It is much higher than the number of possible positions.

Note: even if the number of legal positions turns out to be as ridiculously low as 10^30 ( which seems unlikely ) it would take 10000 cubic meters of memory to build a tablebase of all those positions ( assuming that the 'memory' consists of water molecules each storing 1 bit information ). Unless you can store 1 bit information in a space significantly smaller than a water molecule this would require a 1 meter high, 100 meters wide, 100 meters long 'memory'. This shows how incredibly difficult this problem is.

I have an idea: one could theoretically check the validity of Shannon's number on legal positions in the following way:

Shuffle the pieces in the starting position in random ways. Do this for a large enough number of positions ( let this number be 'N' ). Establish for each randomly generated position whether it is legal or not. Count the legal positions ( let this number be 'L' ). You can measure the validity of Shannon's number by L / N.

In order to reach a number in the order of 10^30, L / N has to be in the order of 10^-12. This means that only the one trillionth of the random positions reached by shuffling the starting position can be legal. This is a very low ratio. If you can generate a hundred thousand positions in a second, it would take time in the order of a year to find only one legal position among them! Can anyone claiming the number of legal positions to be in the order of 10^30 really believe this?

The problem is that it is very difficult to algorithmically check the legality of a position.

Enough where its not worth wasting my time thinking about a useless question.

This position is certainly illegal, it is evident for a human at first sight, but what general algorythm would tell that it is such?

Houdini does it - so testing if a move is legal or not's been done....no ? IOW, the position cannot arrive....because Houdini knows this !....lol....that dam Houdini's smart, isn't it ?

What's fascinating to me is how, as pieces get captured (until pawn coronation........), the number of possible moves appear to decline. So, possible moves can, I dare say, begins its happy little journey towards asymtoticism.

and watcha ?....would you stop making me think about this stuff ?....it's all your fault !....(evidently I'm getting too much sun........)

      The algorythm of the starting position.

I was thinking about my own argument and it may have a flaw: indeed shuffling around the starting position is not a good example of generating legal positions since there are two many pawns which make many pawn formations illegal ( with all pieces on board you have no captures to place pawns randomly ). You have to remove or promote some pawns to get more legal positions.

Shannon calculated all possible shufflings of the starting position. This is clear from the formula he used. If you remove just one pawn you can start over again and you will get a number close to Shannon's number in magnitude:

this formula yields 1.12 * 10^42.

You have to add this number to the first one ( in fact twice that since you can remove either a white pawn or a black pawn ) and do so for all countless possibilities of having less than 32 pieces or promoting some pawns into pieces. If you add up all these shufflings you will get a final raw upper bound of the number of legal positions ( let's call this 'C' from now on ). This is a hard combinatorical fact ( see also (**) ).

Now if you have the number of the combinatorically possible random positions ( C ) you can start generating random positions (*) with any legal number and distribution of pieces ( two bare kings, 9 queens for each side, the original 32 pieces, anything ). You can measure the legality ratio of the positions by L / N ( legal positions / all generated positions ). If you generate enough positions you can establish L / N with high enough confidence. If you have L / N with enough confidence you can correct C by the formula E = L / N * C ( where E is the expected value of the number of legal positions in chess ). If you believe for example that C is 10^45 and the number of legal positions is 10^30 you also have to believe that if you generate random positions only one in 10^15 positions will be legal. I think this method is sound enough, the only problem that it is very difficult to test the legality of a high number of random positions. If I had a function that can tell the legality of a position I could run the test myself since generating random positions is easy.

 (*) You have to be very cautious when generating random positions. It is not right to first decide upon the number of pieces randomly and then decide the distribution of pieces randomly and then scatter the pieces around randomly for each position. This would lead to a biased sample since different number of pieces and distributions yield different number of total possibilites. If you have 2 pieces on board with the same chance as 32 pieces, this is not right since there are very few positions with two bare kings compared to the astronomical number of positions with 32 pieces, therefore two bare king positions will be over represented in the sample.

There is always a theoretically sound way to produce an unbiased sample: you can always enumarate all combinatorically possible positions. If you number the enumerated positions from 1 to C you can simply generate a random number in the range [ 1 .. C ] and choose the resulting random position.

Of course enumerating all the positions is not necessary ( also impractical ). If you know the number of positons that can be generated by a certain number of pieces and distribution ( let's call this N(d), 'd' stands for distribution (**) ) you simply have to make sure that a random position from this distribution is included with N(d) / C chance in the sample.

(**) There are D number of possible distinct distributions of chess pieces ( two bare kings and the 32 pieces in the starting position are instances of such distributions ). If you enumerate these distributions from 1 to D as d(1), d(2), ... , d(D), the following relationship should hold:

Shannon calculated only one ( yet very large ) term of this summation, namely:

N ( d = pieces in the starting position ).

With two bare kings legality is easy: a position is legal if the two kings are not on neighbouring squares. In this case it is possible to both enumerate all possibilities ( there are 64 * 63 = 4032 ) and to estabish the legality of each of those positions with a simple function ( 3612 are legal of those positions giving a theoretical legality ratio of 89.5% ).

Now it is possible to run a probabilistic legality test using randomly generated positions.

This program does this: 

Here is a screenshot of the result:

It can be seen that even if you test just 100 of the 4032 possible positions, you will get a legality L / N result that resembles the theoretical figure ( you can see the result of 10 different random runs in the diagram ).

Watcha doing my Dearest watcha ?

If we started with a board of, say, 4x4 squares, would that help ? Or if we started with excluding pawn coronation possibilities ?

Here's the most interesting part of the puzzle. We KNOW there is an EXACT number for possible chess positions (and thank you for getting me back on track regarding possible chess positions and possible outcomes). Our math backgrounds tell us this (it's not like calculating water molecules (evaporation ?) or stars (exploding ?)). It's fixed not variable....and I believe it's findable. Has anyone since Shannon taken on the task ?....some PhD dissertation maybe ?....Lola........

....and BTW, it must be findable now more than ever with the advent of computer strength and programming skills....and the problem's thrust seems to be determining if the position was legally arrived.... 

Wow. I have a constructive proof of something.

Listen.

Let's just stick with Shannon once again. Let us be stubborn and just try to shuffle the starting position. But now do it in a clever way. The key is that you need a legal pawn formation. Since if you have all 32 pieces on board there can be no captures and pawns can't go through each other, you get pawn phalanxes opposed to each other. It is possible to calculate all legal pawn phalanxes: white can choose to push any of their pawns by 0 to 4 squares. If a white pawn is pushed 0 squares ( remains in its original place ) black can push the opposing pawn by 0 to 4 squares ( 5 possibilities ). If white pushes this pawn 1 square black can choose to push the opposing pawn 0 to 3 squares ( 4 possibilities ) etc. You get 5 + 4 + 3 + 2 + 1 = 15 possibilities for each opposing pawn pair. You have 8 opposing pawn pairs wich yields 15^8 possible pawn phalanxes.

Now almost all of the placement of the remaining pieces behind the phalanxes and between the phalanxes ( yes, by pushing a few pawns pieces can be brought out to in between the phalanxes ) will be legal! There remains 48 squares to place those remaining 16 pieces.

Recalculating Shannon's formula with legal pawn phalanxes:

we get 1.88 * 10^33 positions.

So we have legal positions in the order of 10^33 without a single capture or promotion! Now you can remove two pawns and get a number of the same magnitude again. You can remove two pawns in 16 * 15 / 2!  = 120 different ways and you already added two orders of magnitude, now we are at 10^35 legal positions already. And there are countless other possibilities, I won't ( and I could not ) calculate all of them here.

This argument is good enough for me to believe that the 10^30 figure simply can not be correct ( it is way too low ).

[ EDIT : ]

Of course if you remove some pawns you lose some pawn phalanx complexity. But all of a sudden promoting new pieces becomes possible which adds even more complexity.

Just quickly read this. Will need time to think about it. Pretty bizzy rite now. Will get back....ttfn........  

A couple of thoughts....

* I think the 'nearly impossible' aspect is testing if each position was legally arrivable (like you said early on). How do you do that ?

* Some positions will be disqualified because it has held the opposing King in checkmate say, 1+ moves prior (e.g., 3 opposing pieces checkmating the king)

Trying to simplify....could someone begin by calc'ing the # using no pawns on the board ? In this case, bishops can only cover 32 squares per color - since one cannot promote to B due to no pawns being on board.

Or, what if you began by breaking it down using the 36 3x3 squares on a board ? Exclude pawns at this point. 3x3 because knights can still move within it and two kings can occupy this space without violating one another. Then attempt to commingle them....knowing that some pieces cannot move from one "far away" 3x3 to another w/out violating principle (foolishly brainstorming....but we need a breakthru my beautifully bright watcha....)

I can see this number screaming, "Someone come and find me and give me the glory I've been waiting for the last 500+ years !" It's out there....and it's exact....and that's pretty intriguing.....and if you find it ? Both you and the number are going down in history - forever....Lola........