Author: Ratko V Tomic
Date: 00:37:05 11/15/99
Go up one level in this thread
-------------------------------------------
CODING ANY LEGAL CHESS POSITION IN 155 BITS
-------------------------------------------
> 2) How do you decode such a monster?
Although I didn't originally plan to work out a practical and
detailed encoding/decoding algorithms (I only knew, from the
general programming experience, that the framework described
could be implemented efficiently in time & space), now that you
wish to be convinced beyond any doubt, I'll describe the
algorithm in enough detail for anyone to try it out (I have no
idea why would anyone wish to do so, but here it is anyway).
The full position code FPC was a fixed length (155 bit without
castle or EP; around 157 with these included) code, consisting
of 2 variable length components, the Material Content (MC, i.e.
material counts) part and the Material Placement part (MP), or
symbolically: FPC=(MC,MP(MC)), where we use MP(MC) to denote
that the placement encoding is dependent on the given MC state.
The MC part was a Huffman coded index into an array of all MC
states (there are 58,084,310 distinct MC states). The MP part,
for a given MC, was an index into an array of all distinct
permutations (placements) of the given (by this MC) material.
These (conceptual only, of course) arrays, one for each of the
58 million MC states, would have as many as 3*10^42 entries, or
in total 2.46*10^46 entries for all such arrays. This
conceptual "algorithm" is obviously impractical due to the huge
memory demands.
For clarity, the description of the practical algorithm is
divided into 3 parts (phases) and the encoding + decoding are
covered in parallel in each phase. Part 1 covers
encoding/decoding of the MC part to and from a fixed length
(26 bit) binary coded MC index (MC26 index). Part 2 decribes
how, for a given MC and any one of its placements, to produce
an MP index and how, given an MC and any of its index values to
reconstruct the placement. Part 3 describes Huffman (de)coding
of the MC26 index, in conjuction with the MP part of the code,
resulting in the fixed length FPC-155 code.
The algorithm is "practical" in the sense that it will complete
on any PC and encode/decode hundreds of positions in a "blink
of an eye," although it certainly could be optimized further
(if one were to convert it into a C code).
Notation:
BINOMIAL COEFFICIENTS:
{n;k} = n*(n-1)*...*(n-k+1)/k! = n!/(k!*(n-k)!) = {n,n-k}
{n;n} = {n;0} = 1
if n<k --> {n;k} = 0
MULTINOMIAL COEFFICIENTS:
{n;k1,k2,...,km} = n!/(k1!*k2!...*km!*(n-k)!) =
= n*(n-1)*...*(n-k+1)/(k1!*k2!*...*km!)
where k=k1+k2+...+km
a % b is a modulo b
a \ b is integer division (or a\b = floor(a/b) = (a-a%b)/b)
1. INDEXING MATERIAL CONTENT
----------------------------
The MC state is specified via a record of 10 counts for the 10
pieces MC2 = (QRBNP,qrbnp) which have changeable counts. The
construction in the original post would first build an array of
MC states for one side only, MC1 = (QRBNP), under the
constraint that the total excess in the counts of Q,R,B,N plus
the number of pawns cannot exceed 8 (since each excess piece
could only come from the promotion). The resulting array MA1[]
had 8694 distinct states (13.1 bits index). The two side MC
state array MA2[] was constructed by pairing elements of MA1[]
among themselves as MC2 = (MA1[w], MA1[b]), where w index would
run 0..8693 and b index from 0..w (the case b>w is identical
regarding legality & # of placements, so it wasn't explicitly
recomputed, just the results of the sums were doubled for all
w>b cases), and for each pair the promotions/capture costraint
was checked:
wx <= 2*bpd + bnd + wd (1w)
bx <= 2*wpd + wnd + bd (1b)
where wx (or bx) is excess in white (black) pieces, wc (bc) is
the total white (black) count defect, bpd (wnd) is black
(white) pawn defect, and bnd (wnd) is black (white) nonpawn
defect. The terms excess and defect were covered in detail in
another post in this thread (which also deduced eqs. 1w,b),
briefly the definitions are:
D-1. The EXCESS of a piece is the piece count excess above its
initial state (e.g. 5 W.Queens have WQ excess 4), and it is
0 if piece count is not above the initial count. Only nonpawns
can have excess. The sum of excesses for all white (black)
pieces is wx (bx).
D-2. The DEFECT for a nonpawn is the defect in the piece count
below its initial count (e.g. 0 W.Rooks have W.Rook defect 2;
1 W.Rook has defect 1; 3 W.Rooks have defect 0). The sum of
white (black) nonpawn defects is wnd (bnd).
D-3. The DEFECT for white (black) pawns is the number of
missing pawns below the number 8-wx (or 8-bx) implied by
the excess for white (black), e.g. wpd = 8-wx-wnp (where wnp
is number of white pawns).
D-4. The total white (black) DEFECT is wd=wnd+wpd (or bd=bnd+bpd).
Important point is that all these excesses and defects are
computed directly from the counts in a given MC state, without
speculating on number of actual captures and promotions (which
are not uniquely determined from the MC counts).
The number of all (w,b) pairs is 8694^2 = 75,585,636 but the
constraint 1 was satisfied by only NMC = 58,084,310 pairs i.e.
26 whole bits (25.7916 bits) is needed for indexing. If we were
to fill out entire MCA2[NMC] array, we could easily decode any
MC26 Index i (i=0..NMC-1) by simple lookup in MCA2[i] to
retrieve the MC2 state for this i. The encoding (i.e. producing
an index i from a given MC) would involve searching for a given
MC in MCA2[NMC] (using log2(NMC) comparisons) and the index
where the matching MC was found is our MC26 index i.
Had we not eliminated the elements from the (w,b) pairs, which
left scattered holes in the square array (w,b), we could have
used for both encoding and decoding only the MCA1[8694] array,
constructing the needed (w,b) pairs on the fly. Namely, to
encode (MCW,MCB) state, we would do 2 binary searches in the
MCA1[], obtaining w and b one side indices, then compute:
i(w,b)=8694*w+b (2)
The decoding of i would be done as:
b=i%8694, w=i\8694 (3)
We can still do this, but this index would require 26.1716 bits
or 27 whole bits (instead of 26 whole bits) and would require
checking of the pair for legality (under the pair constraint
(1w,b)) before computing the placement index.
If the holes left by the constraint (1) in the square (w,b)
array were more regular e.g. if for each w index in the pairing
loop, the accepted pairs had a contiguous range of the b index,
say 0..bmax, then we could still apply the method (2) for
encoding by replacing in (2) the term 8694*w with an array
lookup OFFS[w], where the OFFS[0..8693] would contain code
offsets for each w index.
In fact, we can sort our original MCA1[] array so that exactly
this type regularity does hold. Namely, if we rewrite constraint
(1w,b) as:
wx - wd <= 2*bpd + bnd (4w)
bx - bd <= 2*wpd + wnd (4b)
we have the white and the black parameters on different sides of the
inequality. If we now sort the array MA1[] in the decreasing order of
the value 2*bpd+bnd (which is the right hand side of (4w)), and for a
given w, run the b index from 0 and up, as soon as the first failure of
(4w) occurs, say at some index B1, all the remaining values of index b
(from B1 to 8693) will violate (4w) automatically. Namely, the right
hand side of (4w) can only stay the same or get lower as b index
increases (due to the sorting in decreasing order), hence if for b=B1
(4w) is violated it will stay violated for b>B1. If no violation
occured for any b, we will set B1=8694, so that each w will have its
own B1.
The total number of pairs produced this way, i.e. under the (4w)
constraint but without the (4b) constraint, is 62,096,507 = 25.888009
bits, which is 0.096 bits more than 25.791645 bits for the 58,084,310
pairs optimal array (obtained when both (4a) and (4b) are applied). But
in both cases the count fits in a 26 whole bits binary index. Note also
that we still maintain the full constraint (4w) and (4b) at our encoder
main entry, i.e. we return an error when we get an MC state which
violates either inequality. We also maintain the full constraint when
enumerating all possible placements, hence all the figures for
placement counts for all fully valid MCs, and the resulting Huffman
code weights (hence the MC Huffman code lengths) remain the same for
all fully valid MC states. Since the MC26 code is only an intermediate
code (being turned into a Huffman code, which remained same as for the
full constraint), the only effect of this relaxation is that some
numbers (MC26 binary index values) in the intermediate calculations
gain 0.096 bits, which given the use of whole bits (which remain under
the 26 whole bits) here doesn't produce any practical difference (other
than slightly enlarging the Huffman code tables, as we will see in part
3).
We now continue with the encoder/decoder construction. The value of B1
varies as w index varies (the outer loop index). As we check all pairs
this way, we compute and store B1 values (one obtained for each w
index) in an array B1[0..8693]. Then we compute cummulative values of
B1's into an array CB1[0..8693], where CB1[0]=0, ..., CB1[w+1] =
CB1[w]+B1[w], i.e. the CB1[] array will have 0, B1, B1+B2, B1+B2+B3,
..., B1+B2+...+B8692 as its elements. The encoding of MC into MC26 code
then works as follows:
E1) We obtain input MC state as (MCw,MCb), we check it
against the (4w,b) constraints and return an error if it
violates either.
E2) Then we search in the one side MC array (the MA1[0..8693] array
containing all valid one side MC records, which are the piece
counts) the MCw and Mcb states, and say we find them at positions
w and b. (If either is not found, the one side state is illegal
and we return an error).
E3) We compute the MC26 code as MC26 = CB1[w]+b.
(The followup Huffman encoding of MC26 is in part 3)
The decoding of MC26 works as follows:
D1) We obtain MC26 (from Huffman decoder, given in part3)
and do a binary search in the CB1[0..8693] array to find
the nearest lower (or equal) value to MC26 (this will take
up to 14 comparisons). The index at which this was found is,
say, w (it will always be found since it doesn't have to
match excatly MC26).
D2) The b index is then: b = MC26-CB1[w]. Since CB1[w] is the
nearest lower/equal CB1[] element to MC26, and since the
difference between adjacent CB1[] elements is at most 8694,
the value of b will always be in range 0..8693.
D3) Using these w and b we retrieve MCw=MA1[w] and MCb=MA1[b] to
obtain the full MC state (MCw,MCb).
So we have a quick way to get from the MC state to the MC26 index and
back, using the 2 arrays of 8694 elements each, MA1[] (using at most 17
bits per entry) and CB1[] (using at most 26 bits per entry). These
arrays are precomputed and are part of the program's constants (either
loaded as data files or included into the code as preinitialized arrays
of constants), hence their construction time isn't a part of the
encoder/decoder execution time.
2. INDEXING MATERIAL PLACEMENTS
--------------------------------
For a given MC state there will be NP different piece placements. The
task here is to compute index IP (IP range: 0..NP-1) for a given
specific placement MP. Alternatively, given IP, decoder must
reconstruct (uniquely, of course) the specific placement MP. There is a
more generic subtask here, which is: given some piece type with count M
and with NS available squares for placing the M copies of the piece,
find the indexing for all the unique placements of the M copies. Once
we have solved this problem, we can use variable radix coding to encode
the combined index for all piece types present, hence produce the the
MP(MC) part of the full code. The variable radix scheme will use the
maximum arrangements for each piece type (in given order of types) as
the radix for a given position, while the index value for a specific
placement of that piece type will be a digit in that place. We'll
tackle the generic sub-problem first.
2.1 INDEXING ARRANGEMENTS OF A SINGLE PIECE TYPE
-------------------------------------------------
We have M copies of a single piece type and NS squares (NS>=M) to place
this piece. The number of distinct placements is:
NP = NS*(NS-1)*..*(NS-M+1)/M! = {NS;M} (5)
We will order our M pieces by placing piece P1 on square S1, P2 on
S2,... PM on SM, where no 2 pieces can go on one square. We will use
labeling convention where the following is satisfied:
1 <= SM < ... < S2 < S1 <= NS
i.e. if we imagine NS squares in an array 1,2,...NS then P1 is placed
rightmost (the front piece), P2 to the left of it, and the PM last to
the left of the rest (the tail piece). The encoder's objective is,
given a position list for the M pieces, SP=(SM,..,S2,S1), to obtain a
number I = f(SP) such that 0<=I<NP and that any two different SP1 and
SP2 always give a different I1 and I2. Decoder has to reconstruct for a
given I the unique SP(I) list.
This problem has an obvious recursive nature. Namely, if we look at the
fixed position of the front piece P1, the remaining pieces replicate
the same problem, but on smaller scale, with M1=M-1 pieces and on
NS1=S1-1 squares. Conceptually, the solution to the indexing problem
could work as follows: if we have some array of index base values IB[]
for each valid position of the P1 (which is M,M+1,...,NS), then the
Index for SP(NS,M) would be IB[S1] + Index(SP(S1-1,M-1)). The base
values IB[S1] would be constructed by adding up numbers of used up
index values for P1 positions lower than S1. Before giving the general
formula for the index, let me illustrate the method on 3 rooks
placements on an empty board (NS=64, M=3). The placement I=0 is 123,
i.e. the squares for the rooks are: S1=3, S2=2, S3=1. Here are several
more in a table, arranged by the front rook:
S1 IB NA Arrangements
-------------------------------------
3 0 1 123
-------------------------------------
4 1 3 124 134
234
-------------------------------------
5 4 6 125 135 145
235 245
345
-------------------------------------
6 10 10 126 136 146 156
236 246 256
346 356
456
-------------------------------------
7 20 15 127 137 147 157 167
237 247 257 267
347 357 367
457 467
567
-------------------------------------
8 35 21 128 ..... 178
.............
678
-------------------------------------
k {k-1;3} {k-1;2} 12k ... 1(k-1)k
...............
(k-2)(k-1)k
-------------------------------------
64 {63;3} {63;2}
The NA coulumn gives number of arrangements for the given front rook
position S1. The IB column is the cummulative value for NA up to (but
not including) a given S1. Our index for, say the entry 257 (S1=7) is
20+1+2+3+1=27, i.e. we take IB which is 20, then going column by column
(using thus rook 2 as the front rook) within the S1=7 group we count
how many arrangements came before the 257. To decode 27 into 257
arrangement, we first search in the IB array for the nearest IB[x]<=27
and IB[x+1]>27. This returns IB[7]=20, thus our front rook is at S1=7.
The sub-table for S1=7 is the same kind of arrangement table, except
that it is for 2 rooks on 6 squares, and flipped horizontally. The NA,
IB and S2 values here are:
S2 2 3 4 5 6
NA 1 2 3 4 5
IB 0 1 3 6 10
for the S2 values 2 3 4 5 6. The 2-rook index, which was offset by 20
for the 3 rook index, is 27-20=7. So we look in the 2 rook table for
the nearest IB<7, which is 6, for S2=5. The remaining 1-rook code is
7-6=1, and we have for the 1 rook table:
S3 1 2 3 4
NA 1 1 1 1
IB 0 1 2 3
We look for the nearest IB<=1, and find it for S3=2, giving the full
placement S3,S2,S1 as 257. Now we'll look how to create these types of
tables in the general case, (NS,M).
For M pieces on NS squares, the NA coulumn gives for each S1 (the front
piece position, which goes from M to NS) the number of arrangements of
the remaining M-1 pieces on S1-1 squares, hence using eq.(5):
NA(S1) = {S1-1;M-1} (6)
The IB column for S1 is a cummulative NA() value up to the preceding S1
value, i.e. IB(S1) = IB(S1-1)+NA(S1-1), for S1=M+1...NS and IB(M)=0,
for 0 based index. Expanding the recursion into a sum:
IB(S1) = Sum(j=M..S1-1; NA(j)) (7)
for S1>M and IB(M)=0 (by definition).
Using the binomial coefficient formula for summation on the upper
binomial coefficient index:
{n;n}+{n+1;n}+{n+2;n}+...+(m;n} = {m+1;n+1} (where m>=n)
we get, IB(S1) = Sum(j=M..S1-1; {j-1;M-1}) = {M-1;M-1} + {M;M-1} + ..
.. + {S1-2;M-1} = {S1-1;M}, i.e.
IB(S1) = {S1-1;M} (7)
Our cummulative index base is simply a binomial coefficient. The full
index is obtained recursing down to M=1 and adding all (lower M) IB(Sk)
contributions, yielding:
I(S1,S2,..SM) = Sum(j=1..M; {Sj-1;M-j+1}) (8)
= {S1-1;M} + {S2-1;M-1} + ... + {SM-1;1}
(Note that (8) assumes that by definition the terms of type {n;k} with
n<k are 0, e.g. if S3=1 or S2=2 or S1=3 in our M=3 rook example, then
the three terms are {2;3}=0 {1;2}=0 and {0;1}=0, giving I(3,2,1)=0.)
Decoding of I(S1,..,SM) works by finding x for the largest {x;M} < I,
the obtained {x;M} gives us the leading term in (8), with x=S1-1 i.e.
S1=x+1. Then we reduce I by this {x;M} i.e. assign I1=I-{S1-1;M} and
repeat this for the next term in (8), obtain S2, etc. The uniqueness of
decoding follows from observing how we obtained (7) & (8), i.e. by
noting that any term in (8) is greater than the sum of all the terms to
the right of it (the closests the two ever come together is if the
S1-S2=1, S2-S3=1, S3-S4=1,.. in which case {S1-1;M} is greater from the
sum to the right of it in (8) by exactly 1}, which makes this a sort of
number base with S1, S2,.. being its digits (S1 the most significant,
SM the least). The sum (8) achieves maximum when all S values are at
maximum, i.e. S1=NS, S2=NS-1, ... Sk=NS-k+1. In that case the sum (8)
is exactly equal {NS;M}-1, meaning that index values cover the required
range 0..NP-1, where NP was given by (5).
Searching for {x;M}<I we use in decoding involves a short binary search
in the table of {x;M} with x<=64 (which should complete in at most 6
comparisons). A precomputed 64x64 table could serve encoding & decoding
needs (since M is always given, we could make array of 64 pointers
indexed by M, each entry giving us a pointer into an array of 64 {x;M}
values). If one were doing other than chess enumerations with this
combination indexing method, with large x values, and a machine has a
fast floating point, one can use estimate x ~~ M/2+(I*M!)^1/M (the m-th
root finds roughly the middle of the range of M multipliers in the
numerator of the {x;M}) to get us very near the correct x.
We can illustrate (8) by encoding our earlier example 257 (S3=2, S2=5;
S1=7, M=3):
I(7,5,2)={7-1;3} + {5-1;2} + {2-1;1} = 20+6+1 = 27
Decoding od 27 starts with looking for {x;3} nearest to 27, not
exceeding 27. Value {6;3}=20 and {7;3}=35, hence x=6 or S1=x+1=7. Then
I1=27-20=7. We look for {x;2}<=7 which from {4;2}=6 {5;2}=10 gives x=4,
hence S2=x+1=5. Then I2=6-5=1 and we look for {x;1}=x<=1, hence x=1 and
S3=x+1=2, i.e. the placement for the index 27 is 257.
2.2 INDEXING MULTIPLE PIECE TYPES
---------------------------------
Now we have k piece types, P1, P2 to Pk, and for each we have a count
M1, M2,.., Mk and the squares available, NS1 squares for the P1,
NS2=NS1-M1 for P2, NS3=NS2-M2 for P3, etc. For this particular
convention of placing the pieces, the number of arrangements for P1 is
NP1={NS1;M1}, for P2 NP2={NS2;M2},... NPk={NSk;Mk}. The total number of
arrangements for the k types is NP=NP1*NP2*...*NPk.
Some particular arrangement of these k piece types will produce k
independent index values I1, I2, ... Ik (using the indexing method from
part (2.1)), and these index values have property: 0 <= Ij < NPj for
all j=1,2..,k. To represent the full index I for all k piece type, we
will use I1,..Ik as k digits in a mixed radix representation, where the
1st digit is in radix B1=NP1, second digit in radix B2=NP2,.. , k-th
digit in radix Bk=NPk. Hence we form the full index for all k piece
types as:
I = I1+B1*(I2+B2*(I3+...+B[k-2]*(I[k-1]+B[k-1]*Ik)..) (9)
Where the range of the MP index I is 0..NP-1.
This is the same type of representation as for, say, a 4 digit decimal
number d with digits (d4 d3 d2 d1) as:
d = d1+10*(d2+10*(d3+10*d4)) = d1 + d2*10 + d3*10^2 + d4*10^3
Decoding of index I works in exact analogy with conversion of binary to
decimal radix, i.e. from given I we obtain "digits" I1, I2, ... using
the steps:
I1=I%NP1, I=I\NP1, (10)
I2=I%NP2, I=I\NP2,
....
I[k-1]=I%NP[k-1], I=I\NP[k-1],
Ik=I
The obtained values I1, I2,..Ik would be decoded as the placement index
I in section (2.1). Note also that each subsequent piece uses the
left-over square array from the previous piece, hence the S1,S2,..,SM
in the section (2.1) refer to the empty square holes, 1 denoting the
1st hole, 2 the second hole, etc.
In using the mixed radix method for a given MC state, the pawns, which
can occupy only the 48 squares instead of 64 should be encoded in the
1st 2 "digits" if both color pawns are present, or as 1st digit if only
one color pawns are present. If we have wp and bp white and black
pawns, and n3,n4,n5,..,nk of other pieces, and we denote p=wp+bp, then
in the scheme above we will have:
NS1=48, M1=wp,
NS2=48-M1 M2=bp,
NS3=64-p M3=n3,
NS4=NS3-n3 M4=n4,
...
NSk=NS[k-1]-n[k-1] Mk=nk.
To minimize the size of the NP numbers (the radix values), it is best
for a given MC, after dealing with pawns (which always come 1st if
present) to sort the counts n3,n4,.. in increasing order, so that the
largest n's come with the least NS number. Thus n3=1 and n4=1 would be
set for kings, then the rest of pieces. The worst case (for a size of
an individual NP) occurs when we have only the 2 kings and 10 copies of
a single piece (R,B or N). In that case the NP for this piece type is
{62;10}=1.1*10^11 = 36.6 bits, i.e. we cannot generally use 32-bit
integer for the NPs, but the 64-bit integers will work safely. The full
index value in (9) is much larger, the worst case being a 30 piece
MC={QRBNP=3,3,2,4; qrbnp=3,3,2,4} with number of placements and index
0<= I< NP=3.0678*10^42 = 141.14 bits i.e. at least 18 byte integers are
needed for to handle the mixed radix arithmetic in (9) and its decoder
in (10).
-- continued in 2/2
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.