Author: Uri Blass
Date: 10:14:41 01/02/06
Go up one level in this thread
On January 02, 2006 at 12:44:36, Guido wrote: >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 There is a better upper bound see http://chessprogramming.org/cccsearch/ccc.php?art_id=77068 Uri
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.