all the unique legal placements of the simiar pieces. This way we can get
a saving of k!. For two similar pieces the required table size is reasonably small
however for 3 pieces or more it takes more than 1mb. I guess most just incorporte
this tables directly for simplicity.
This enumerations can be avoided by use of polynomial functions.
I found an explanation,with which I have difficulty to understand, given in a paper.
I am wondering if some one can help me with the math used to generate the polynomial
with 3 or more like pieces. Here is the explanation
- Code: Select all
4.10.2 Enumeration of k like pieces
This is somewhat simpler as there is no symmetry involved. As I have restricted
my focus on endgames with at most 5 pieces of which 2 are kings, we will only
need enumerations of 2 and 3 pieces. The definitions below are only valid when
the input are sorted in ascending order. I.e. i<j => si < sj is assumed in the
definition of Xn.
Intuitively, a sequence of the positions of k like pieces (s1, . . . , sk) is mapped to
the index in the lexicographic sorting of {(s1, . . . , sk) | i < j ⇒ 0 ≤ si < sj < 64}
X2(s1, s2) = {
X2(s1, s2 − 1) + 1 if s1 + 1 < s2
X2(s1 − 1, 63) + 1 if s1 > 0 ∧ s1 + 1 = s2
0 if s1 = 0∧ s2 = 1
}
X3(s1, s2, s3) = {
X3(s1, s2, s3 − 1) + 1 if s2 +1 < s3
X3(s1, s2 − 1, 63) + 1 if s1 +1 < s2 ∧ s2 + 1 = s3
X3(s1 − 1, 62, 63) + 1 if s1 > 0 ∧ s1 + 2 = s3
0 if s1 = 0∧ s2 = 1∧ s3 = 2
}
It is possible to express the above enumerations as polynomials by counting the
number of ways to place the pieces in a lexicographically smaller way. I will
show how to do this for X2(s1, s2), and simply state the result for the other
enumerations.
X2(s1, s2) = [SUM s1−1 i=0 SUM 63 j=i+1 1] + [SUM s2−1 i=s1+1 1]
= [SUM s1−1 i=0 ((63 + 1) − (i + 1))] + [((s2 − 1) + 1) − (s1 + 1)]
= [SUM s1−1 i=0 (63 − i)] + [s2 − s1 − 1]
= [(((s1 − 1) + 1) − 0) ∗ 63 –SUM s1−1 i=0 i] + [s2 − s1 − 1]
= [63 ∗ s1 – 1 / 2 ((s1 − 1) ∗ ((s1 − 1) + 1))] + [s2 − s1 − 1]
= [ 1 / 2 (127 ∗ s1 – s1^2)] + [s2 − s1 − 1]
= 1/2(125 ∗ s1 − s1^2) + s2 – 1
X3(s1, s2, s3) = −64 + 1/6(11531 ∗ s1 − 186 ∗ s1^2 + s1^3) + 1/2(125 ∗ s2 − s2^2) + s3
In my implementation the piece enumerations for 2 like pieces are simply
tabulated. For 3 like pieces such a tabulation would use 1 MB of memory and
I decided to use the polynomial expression instead. The polynomial expression
can be written f1(s1)+f2(s2)+f3(s3) and can hence be optimised by tabulating
f1, f2 and f3.
SUM X Y == summation (from Y, to X)
I want to know how the polynomial for 3 like pieces is arrived. The given polynomial is
for (64 * 63 * 62) / 2 placements. I want to derive other similar polynomials for (62 * 60 * 61) / 2 placements etc.
These polynomials are used to map the set of squares (s1,s2,s3) in to a table index.
Another problem, how to do the inverse process? Ordinarily I use a table here as well, but the table is big in this case.
thanks,
Daniel
