This is an old revision of the document!

Chess - Programming - Endgame Table-Bases - Encoding

Suppose we have KRvK.

Let us say the pieces are on square numbers wK, wR and bK (each 0…63).

The simplest way to map this position to an index is like this:

index = wK * 64*64 + wR * 64 + bK;

NOTE: This is going to be an array of 64*64*64 = 262144 positions.

But with lots of positions being equivalent (because they are mirrors of each other) and lots of positions being invalid (two pieces on one square, adjacent kings, etc.).

Usually the first step is to take the wK and bK together.

There are just 462 ways to place the wK and bK on the board if we discard mirror positions and illegal positions (adjacent kings).
These are positions with wK in the a1-d1-d4 triangle and bK on a non-adjacent square.
If wK is on the a1-d4 half-diagonal, then bK can be forced to be on or below the a1-h8 diagonal.

Once we have placed the wK and bK, there are 62 squares left for the wR.

That gives 462 * 62 = 28644 in total.
Mapping the value of wR from 0…63 to 0…61 can be done like this:

wR -= (wR > wK) + (wR > bK);

If wR “comes later” than wR, we deduct 1.
If wR “comes later” than bK, we deduct 1 (the same).

Example:

wK = 11 (d2)
bK = 32 (a4)

then wR = 63 is mapped to 61 (we skip 11 and 32)
wR = 30 is mapped to 29 (we skip 11), 
and wR = 8 is mapped to 8 (nothing to skip).

We can still improve on 28644.

If wK and bK are on the a1h8-diagonal, we can force the wR to be on or below the a1h8-diagonal to get a total of 28056 positions.

NOTE: This is for 3 pieces.

The extension to 4, 5 and 6 pieces is not all too difficult, but we get new complications once we have like pieces of the same color.
For example KRRvK.
- We do not want to have one index value for R1 on a1, R2 on b1 and another index value for R1 on b1, R2 on a1.
- What we do is place the two Rs together.
- If we have 62 squares left, we can place two Rs “together” in 62*63/2 ways.
- If we have 3 Rs, it is 62*63*64/6 ways.
- If we have 4 Rs, it is 62*63*64*65/24 ways.

Encode Piece

Encode Piece works like this:

First, the leading piece is mirrored to the a1-d1-d4 triangle (and if the first k pieces are on the a1h8-diagonal, piece k+1 is mapped to below that diagonal).
Second, the positions of the 2 or 3 leading pieces are converted into a single number.
There are three cases.
- In the “K2” case, an index for the two kings is calculated.
  - Index calculation then continues from the 3rd piece (“i = 2”).
- In the “K3” case, an index for the two kings and one further piece (e.g. R) is calculated.
  - If the two kings are on the diagonal (KK_idx >= 441), we take special care of the R (as discussed above).
  - Index calculation continues from the 4th piece (“i = 3”).
- In the “111” case, an index is calculated for three “different” pieces that only occur once (i.e. different type and/or color) which may include kings.