Differences

This shows you the differences between two versions of the page.

--- chess:programming:endgame_table-bases:encoding [2022/01/11 16:02] – created peter
+++ chess:programming:endgame_table-bases:encoding [2022/01/11 16:18] (current) – peter
@@ Line 59: / Line 59: @@
   * 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**.
+    * We can place two Rs "together" in 62*61/2 ways.
-    * 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*61*60/6 ways.
-    * If we have 3 Rs, it is 62*63*64/6 ways.
+    * If we have 4 Rs, it is 62*61*60*59/24 ways."
-    * If we have 4 Rs, it is 62*63*64*65/24 ways.
 </WRAP>
@@ Line 84: / Line 83: @@
 ----
+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