Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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:

<code>
index = wK * 64*64 + wR * 64 + bK;
</code>

<WRAP info>
**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.).

</WRAP>

----

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:

<code>
wR -= (wR > wK) + (wR > bK);
</code>

  * If wR "comes later" than wR, we deduct 1.
  * If wR "comes later" than bK, we deduct 1 (the same).

Example: 

<code>
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).
</code>

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.

<WRAP info>
**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.
    * We can place two Rs "together" in 62*61/2 ways.
    * If we have 3 Rs, it is 62*61*60/6 ways.
    * If we have 4 Rs, it is 62*61*60*59/24 ways."

</WRAP>

----

===== 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.

----

The usual case is "111" (enc_type == 0).

  * If we have three different piece types (j >= 3), each occuring only once, we are in this case.
  * We always have at least two of these: the white king and the black king.
  * So we are in this case unless we have something like KRRvK, KRRvKBB, KRRRvK, KRRBBvK, KNNNNvK.
    * Otherwise we are in case "K2" (enc_type == 2).

The "only for suicide" case cannot happen: white king and black king ensure j >= 2.

  * So the code can be cleaned up a bit.

This also means that the "K3" case seems never to occur and could probably be removed. 

In principle, "111" does not reduce the index space as much as "K3".

  * However, "111" gives the generator more freedom to reorder pieces and that freedom pays off.
  * The order in which pieces are indexed has a big impact on compression efficiency, so the more possibilities for reordering, the better the compression.
  * Also, what the increase in index space that "111" gives compared to "K3" consists of broken positions with adjacent kings, and such positions anyway compress very well (as do not cares).

It was initially thought the "K3" case was useful to have, but then found out that compression is always better if we use "111".

After the switch(), we place groups of like pieces (RR, RRR, RRRR) together.

  * The norm[] array tells us how many like pieces we have.
  * Their positions are sorted and then mapped to an index using a formula involving binomials. The "j += (p > pos[l]);" is there to skip positions that are occupied by pieces we have treated earlier.

The factor[] values have to do with the "best" ordering found by the generator.

Similar story for encode_pawn().

There are special case routines for indexing KKKvNN for suicide chess.

----

===== Line by line explanation of the "111" case =====

We are calculating an index for wK, wR, bK (pos[0], pos[1], pos[2]).

  * We do not make use of the fact that the two Ks cannot be on adjacent squares.
    * (So this also works for indexing wQ, wR, wB, for example.)

The wK has been mapped to the a1-d1-d4 triangle.

  * If wK is on the diagonal, then wR is on or below the diagonal.
  * If wK and wR are on the diagonal, then bK is on or below the diagonal.

<code>
i = pos[1] > pos[0];
int j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
</code>

Precalculate the values we will have to deduct from pos[1] and pos[2].

<code>
if (OffdiagA1H8[pos[0]])
  idx = Triangle[pos[0]] * 63*62 + (pos[1] - i) * 62 + (pos[2] - j);
</code>

wK is below the diagonal.

  * Triangle[pos[0]] maps the b1-d1-d3 triangle to 0...5.
  * There are 63 squares for wR (pos[1] - i is in 0...62) and 62 squares for bK (pos[2] - j is in 0...61).
  * Here, idx wil be in 0...(6*63*62-1).

<code>
else 
if (OffdiagA1H8[pos[1]])
  idx = 6*63*62 + Diag[pos[0]] * 28*62 + Lower[pos[1]] * 62 + pos[2] - j;
</code>

wK is on the half-diagonal a1-d4, wR is below the diagonal.

  * Diag[pos[0]] maps a1-d4 to 0...3.
  * Lower[pos[1]] maps the b1-h1-h7 triangle to 0..27. 62 squares remain for bK.
  * Here, idx will be in (6*63*62)...(6*63*62 + 4*28*62-1).


<code>
else
if (OffdiagA1H8[pos[2]])
  idx = 6*63*62 + 4*28*62 + (Diag[pos[0]]) * 7*28 + (Diag[pos[1]] - i) * 28 + Lower[pos[2]];
</code>

Now wK is on the half-diagonal a1-d4, wR is on the diagonal a1-h8, bK is below the diagonal.

<code>
else
  idx = 6*63*62 + 4*28*62 + 4*7*28 + (Diag[pos[0]] * 7*6) + (Diag[pos[1]] - i) * 6 + (Diag[pos[2]] - j);
</code>

And the final case: all on the diagonal a1-h8.

----

==== References ====

http://www.talkchess.com/forum3/viewtopic.php?t=59947

http://www.talkchess.com/forum3/viewtopic.php?t=59904