4

Reading about the Shannon number, I see that there are about 1043 positions in chess, but how many of them are even? That is, materially (as an approximation). A position with one king vs 8 pawns and a king is not really interesting.

  • It's still staggeringly large. Say that only one out of every thousand positions has approximately even material; that would still leave us with 10^40 such positions. – dfan Feb 10 '14 at 18:38
  • How would you calculate it? Cheers. – Rauan Sagit Feb 11 '14 at 14:40
  • 1
    I don't think using materially even as an approximation of the game being even would be accurate, especially if we're considering all possibilities (and not just ones likely to occur naturally in a game). The number of positions where material is even but the game is clearly one-sided would be huge. – OnABauer Feb 18 '14 at 12:11
3

What follows is basically a partial answer that is heavy on explanation, plus a pointer for using it to obtain a fuller answer if so desired.


Suppose we start with a blank 64-square chessboard and ask how many different positions we can make by placing down just 2 white knights. A quick answer is that it is 64*63 = 4032 positions, because we can place the first knight on any of 64 squares, and for each of those choices there are 63 remaining choices for the other knight. But this overcounts a bit. Specifically, that number double-counts every possibility, the reason being that our white knights are indistinguishable in terms of a chess position. What I mean is this: the counting scheme above treats (A) placing Knight1 at a1 and then Knight2 at a2, and (B) placing Knight1 at a2 and then Knight2 at a1, as two different chess positions. But they aren't: each has a white knight at a1 and at a2; they are the same chess position, as white knights don't come with individual labels. So the real answer should be (64*63)/2 = 2016 positions.

If we were instead placing 8 white pawns on an empty 64-square board, the number of possibilities is

(64*63*62*61*60*59*58*57) / 8! = 4,426,165,368

This is just like the previous example, where the numerator naively counts the ways to place the 8 pawns, and the 8! of the denominator accounts for the fact that our white pawns are indistinguishable from one another in a position (and there are 8! ways to order the 8 pawns). Note too that the numerator can be written more succinctly as 64! / 56!, so a snappier way to give the number is as

64! / (56! * 8!)

OK, so what about Shannon's paper itself? The estimate of the number of chess positions given there is that it is "of the general order of"

64! / (32! * (8!)^2 * (2!)^6) = 4.63E+42

From the examples above, we know what this is counting. The 64! / 32! naively counts the number of ways to drop 32 pieces onto the 64 squares of the chessboard. Then we divide by 8! twice to ignore the order of the white pawns and the black pawns. Finally, we divide by 2! = 2 a total of 6 times, to account for the white/black knights, bishops and rooks. So this 4.63E+42 is a rough estimate of the number of 32-piece positions, all of which have even material of course. (Note that we are totally ignoring legality, e.g. we can have pawns on the first rank, both kings in check, and so on; for an interesting thread on the proportion of positions that are actually legal, see this MathOverflow post. We are also ignoring promotions by saying that the original 32-piece set is all we get.)

A similar "Shannon estimate" for the number of 31-piece positions is given by

  1.40E+41 = 64! / (33! * (8!)^2 * (2^6))      remove white Q
  2.81E+41 = 64! / (33! * (8!)^2 * (2^5))      remove a white R
  2.81E+41 = 64! / (33! * (8!)^2 * (2^5))      remove a white B
  2.81E+41 = 64! / (33! * (8!)^2 * (2^5))      remove a white N
+ 1.12E+42 = 64! / (33! * 8! * 7! * (2^6))     remove a white P
----------
  2.11E+42
* 2           to count those positions removing a single black piece
----------
  4.21E+42

Note the huge drop in the number of positions: there are 4.21E+41 more 32-piece positions than there are 31-piece positions. The numbers will continue to drop dramatically, and in fact the proportion of 32-piece positions among all possible positions will be fairly sizable (hence so too will the number of even-material positions).

It wouldn't be too difficult for someone to write a program that produces these Shannon estimates for all numbers of pieces (one would just need to make sure to account for all combinations of a given number of pieces), and we could keep track of all those combinations that have equal material as we go. At the end we would have the Shannon estimate for all possible positions (though the 32-piece number already gives a rough sense of the total, as Shannon notes, because of the quick drop in positions as we drop pieces), as well as a count/proportion of how many of those (pseudo-legal) positions have equal material.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.