# Computer Chess Club Archives

## Messages

### Subject: Re: Counting & Encoding Any Chess Position in 157 bits

Author: Ratko V Tomic

Date: 12:34:36 11/15/99

Go up one level in this thread

```> I haven't read all of your other two posts (they will take a while to
> digest), but I am still confused on how you could encode/decode a 117
> bit (143 - 26 bit) single value. Seems beyond the capabilities of
> normal C unless I'm missing something (a special library for large
> binary values maybe).

Well, you would certainly need the large integer multiply & divide operations
for calculating the binomial coefficients. The multiply, add and subtract need
to work in the full precision (155 bits), while the large divide occurs only in
the binomial coefficients, whith small denominators (such as k!, with k<=10),
hence it would be a large integer divided by a 32 bit integer at most, which is
the easy and quick case of division to implement). The +,- and * are easy in any
precision. For the n-digit integers (and, say, a byte or an int32 being a single
"digit"), the multiply can be easily done so that the number of digit*digit
multiplications is proportional to the n^1.5 instead of the n^2, which the
regular paper and pencil method would use.

So, yes, we don't have these data types and operations on them ready made in
standard C, but we don't have Huffman coding ready made in standard C, either,
or much of the rest of the data structures or operations on them in the overall
algorithm (many of which  are probably trickier to implement than a few large
integer operations, which one can copy out of the Knuth Vol 2, or find some C
library on the web).

> digest), but I am still confused on how you could encode/decode a 117
> bit (143 - 26 bit) single value. Seems beyond the capabilities of

The 143 bit (or rather 142 bits) for the worst case position, referes to the
placement part of the code, so you wouldn't remove the 26 bits from it (for the
MC26 code). Rather the MC26 code is in addition to the 142 bits, which would
make the total code 142+26=168 bits, if one doesn't use the Huffman code to
reduce MC26 code for these types of positions, with large number of placements
for a given material. In this case the Huffman code for this MC26 state (this
material content) would have the length 155-142=13 bits.

In other words, the Huffman code for any of the 58 million Material Content
states (for which I used MC26 code only in the intermediate phase of coding, as
work variables) have the length exactly completing the placement code length for
the given material to the 155 bits. The worst case, the 142 bit placement code
(MP code), thus has a 13 bit Huffman code for its MC part. The "best" case, the
2 lone kings, needing only 12 whole bits for their placement code, would have
their Material Content Huffman code of 155-12=143 bits, i.e. to specify that the
material is 2 lone kings (or in our count records, to have all C1,..,C10 zeros)
one would use a 143 bit Huffman code. But to specify the 30 piece "worst" case
material counts, one would use only a 13 bit Material Count Huffman code (which
happens to be half the size of the MC26 uniform code).

The point of the Huffman code was to make the full (MC+MP part) position code
uniform in length, exactly 155 bits for any position. That minimizes the worst
case and also minimizes the average case for a random pick out of the 2.46*10^46
positions.

```