Author: Guido
Date: 09:44:36 01/02/06
I remember that this topic had already been considered in the past. Nevertheless, having some time, I tried to write a simple program for a more precise computation of the number of possible positions in chess. I try to explain what I did, asking hints and helps for some unresolved questions: 1. I computed the number for all the possible combination of 2, 3, 4, ... 32 men, i.e. of all the possible future tablebases, considering two cases for asymmetrical endings (e.g. both KQRKP and KPKQR) and one case for symmetrical endings (e.g. KRNKRN). This corresponds exactly to the number of files in Nalimov's EGTBs. Supposing for now that all the pawns can be promoted I found that such number is 168740100 (KK case included). 2. For each of these endings I computed the number of possible positions with this rule: 2a. If the ending doesn't contain pawns, the possible dispositions of the King are 462, while the remaining pieces contribute with factors of 62, 61, 60 etc.. If n pieces are equal I divide for n! as usual. 2b. If the ending contains pawns I follow a more complex calculation, normally not used in the computation of EGTBs. The total possible positions of the King are 1806, but to be more precise, I found that there are: a) 106 positions where both the Kings are out of the rectangle of the pawns (defined by the diagonal a2...h7) b) 724 positions where one King is inside the rectangle and the other is out c) 976 positions where both the Kings are inside the rectangle. Has someone found the same values? So adding the pawn I must use factors which start from 48 for a), 47 for b) and 46 for c). Finally I add the remaining pieces keeping into account the already considered Kings and pawns. I did the computation under Linux using the gmp library, a multiple precision mathematical library that permits to have integers of any dimension. The final result of the computation (if right!) gives: 26711818089562360926340822369913946949637279271906 =~ 2.67 10^(49) in the hypothesis that all the 16 promotions of pawns would be possible also with 32 men. I know that this result is clearly wrong but it is useful for a first rough superior limit. Disregarding any promotion I found another rough inferior limit: 32570737649099181299991054392639521259442 =~ 3.26 10^(40) Now it could be interesting to see how is possible to better the calculation in order to reduce the range considering the following points: - What is the maximum number of promotions theoretically possible? - What is the relation between the number of promotions and the total number of men? It is clear that if I have a promotion, the total number of men cannot be 32, because at least one capture is necessary for a promotion, but one capture can permit the promotion of more than one pawn (until 3 promotions IMHO in the case that a pawn is captured). In other words the problem is that of determining how many of the 168740100 EGTBs aren't possible and to find a rule for eliminating them. - How many positions must be added by considering ep and castling? This is a point that should not be too much difficult to compute. - How many positions should be cancelled by further symmetries? This refers to endings with only pieces when both the Kings are on the main diagonal. - What could be the percentage of illegal, because unreachable, positions? Surely the problem of determining the exact number of legal positions, in particular with reference to the last question, is probably unsolvable because the only correct criterion would be that of starting from the initial position of the game, executing all the possible moves and counting all the different legal positions. I would be interested to know if someone has already done analogous calculations and the results he obtained. Thanks, Guido
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.