Author: Guido
Date: 07:04:47 04/15/02
I noticed that more than once on CCC there are requests about the total number
of tablebases for 3, 4 and 5 men or more.
To compute these numbers a very easy scheme exists. If such a scheme has been
reported before, than forgive me, on the contrary I'll be waiting for thanks
from people who generally answer to such requests :-).
We can start building the following table, sufficient for all the endings till
12 men, the last column being correspondent to 10 = 12 - 2 (number of Kings).
0 1 2 3 4 5 6 7 8 9 10
A 1 1 1 1 1 1 1 1 1 1 1
B 0 1 2 3 4 5 6 7 8 9 10
C 0 1 3 6 10 15 21 28 36 45 55
D 0 1 4 10 20 35 56 84 120 165 220
E 0 1 5 15 35 70 126 210 330 495 715
S 1 5 15 35 70 126 210 330 495 715 1001
The first line and the first column are used only to indicate the elements of
the 5x11 matrix; the last row (S) contains the sum of each column.
A part from the 0 column, the rest of the matrix is built by this easy rule:
each element is the sum of the elements of the preceding column from the A row
till the same row of the element itself. Extensions of the matrix for more than
12 men is then obvious.
Examples:
C6 = A5 + B5 + C5
E8 = A7 + B7 + C7 + D7 + E7
This explains the fact that the S row is equal to the E row shifted to left of
one column.
Now to obtain the total number of tablebases versus the number N of men, it is
sufficient to sum the products, two by two, of the elements of the S row from
column 0 to column N-2, starting from the boundaries towards the center. There
are two cases, depending on the parity of N:
1. Number of tablebases for N men (N odd):
S0 * S[N-2] + S1 * S[N-3] + ...+ S[(N-1)/2 -1] * S[(N-1)/2]
(Quantities in square brackets are the indexes of the sums)
2. Number of tablebases for N men (N even):
S0 * S[N-2] + S1 * S[N-3] + ...+ S[N/2-1] * (S[N/2-1] + 1) / 2
Therefore we have the following results:
N Formula Values
2 S0*(S0+1)/2 = 1*2/2 1
3 S0*S1 = 1*5 5
4 S0*S2 + S1*(S1+1)/2 = 1*15 + 5*6/2 30
5 S0*S3 + S1*S2 = 1*35 + 5*15 110
6 S0*S4 + S1*S3 + S2*(S2+1)/2 = 1*70 + 5*35 + 15*16/2 365
7 S0*S5 + S1*S4 + S2*S3 = 1*126 + 5*70 + 15*35 1001
8 S0*S6 + S1*S5 + S2*S4 + S3*(S3+1)/2 = ... 2520
9 S0*S7 + S1*S6 + S2*S5 + S3*S4 = ... 5720
10 S0*S8 + S1*S7 + S2*S6 + S3*S5 + S4*(S4+1)/2 = ... 12190
11 S0*S9 + S1*S8 + S2*S7 + S3*S6 + S4*S5 = ... 24310
12 S0*S10 + S1*S9 + S2*S8 + S3*S7 + S4*S6 + S5*(S5+1)/2 = ... 46252
The values found in the last two lines don't keep into account the rules of
chess game, that forbid some endings, because a player cannot have more than 8
pawns or 9 queens.
The total number of files for 3, 4 and 5 men is then 5+30+110 = 145 multiplied
by 2 for a total of 290 files (ending KK excluded). Adding 6 men EGTBs the
total number of files is: 290 + 2*365 = 1020.
The structure of the formula is easily understandable: each product gives the
number of a particular group of EGTBs. For example, in the case of 5 men, the
two products have these meanings:
S0*S3 = number of endings of the type KXXX-K where KXXX ==> S3 and K ==> S0
S1*S2 = number of endings of the type KXX-KX where KXX ==> S2 and KX ==> S1
As in statistics, the product is justified by the mutual independence of the
white and black men compositions, while the sum S0*S3 + S1*S2 is justified by
the incompatibility between KXXX-K and KXX-KX.
For even number of men a correction to the mutal independence of compositions
must be made for symmetrical cases.
I find very strange the fact that 1001 is the sum of the 10th column and also
the number of tablebases for 7 men (also 5 has an analogous property). Can a
mathematician explain this fact or is it only casual as IMHO?
The described scheme is useful for calculating also the number of endings
without pawns. It is sufficient to create a similar matrix with 4 rows instead
of 5, eliminating the E column, and use the same above mentioned formulas.
Hoping not to have made errors or repeated obvious things...
Ciao
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.