Question to syzygy author

[mcostalba]

Ronald de Man code for Syzygy has been added to SF already some years ago, but never touched nor integreted and always considered a kind of external library (as actually it is). Currently we are in the process of rewriting it to conform to SF standard. In this process I find some parts that are not clear to me (code is complex and sparsely commented). I will post here form time to time my questions, hoping for someone with internal kwnoledge of syzygy to help. I start with a function called probe_ab() that, given a position, does a kind of qsearch, looking for captures and eventually evasions until a quiet position is found.

Now I have 2 questions:

1) In probe_ab() position evaluation with probe_wdl_table() is done _after_ the depth search and not before as in usual qsearch. This is not obvious to me, becuase if TB lookup is succesful (as supposely it is, given that probe_ab() is only called when the position is in the TB) why don't just do it at the start and return immediately?

2) Why probe_ab() exsists in first instance? If I ask syzygy to look up a given position (with number of pieces less or equal the current installed TB), I'd expect the TB code to do just that: look up the position and return what it has found. Why TB code does a qsearch instead?

Thanks for answering.

[syzygy]

2) Why probe_ab() exsists in first instance? If I ask syzygy to look up a given position (with number of pieces less or equal the current installed TB), I'd expect the TB code to do just that: look up the position and return what it has found. Why TB code does a qsearch instead?

This is part of the compression scheme.

If in a TB position the side to move has a winning capture, then the position is won. For such positions it is not necessary to store a winning value. The compressor treats such positions as "don't cares" and tries to assign to it a value that improves the compression ratio.

Similarly, if the side to move has a drawing capture, then the position is at least drawn. If the position is won, then the TB needs to store a win value. But if the position is drawn, the TB may store a loss value if that is better for compression. (Cursed wins and losses make things still more complicated, but the principle remains the same.)

All of this means that during probing, the engine must look at captures and probe their results (using probe_ab()) and must probe the position itself (using probe_wdl_table()). The "best" result of these probes is the correct result for the position.

1) In probe_ab() position evaluation with probe_wdl_table() is done _after_ the depth search and not before as in usual qsearch. This is not obvious to me, becuase if TB lookup is succesful (as supposely it is, given that probe_ab() is only called when the position is in the TB) why don't just do it at the start and return immediately?

The probe_wdl_table() call can logically be done either before or after probe_ab() on captures, but it cannot replace the probe_ab() calls for the reasons given above (the WDL table might store a (partial) don't care value if good captures are available). The code postpones the call to probe_wdl_table() until after the probe_ab() calls, because probe_ab() accesses smaller tables (one piece less) which are more likely to be cached in RAM. So those probes should be cheaper (and if the result they return is "good enough", there is no need to look further, as in regular alpha-beta).

Thanks for answering.

You're welcome

[mcostalba]

This is part of the compression scheme.

Thanks for the answer!

One of the most obscure parts is the encoding, where you can find someghting like this:

Code: Select all

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

        if (OffdiagA1H8[pos[0]])
            idx = Triangle[pos[0]] * 63*62 + (pos[1] - i) * 62 + (pos[2] - j);
        else if (OffdiagA1H8[pos[1]])
            idx = 6*63*62 + Diag[pos[0]] * 28*62 + Lower[pos[1]] * 62 + pos[2] - j;
        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]];
        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);

There is some documentation available that explains what the encoding does? It would be much easier to follow the code if you have an idea of what you are looking at...

[syzygy]

One of the most obscure parts is the encoding, where you can find someghting like this:

Code: Select all

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

        if (OffdiagA1H8[pos[0]])
            idx = Triangle[pos[0]] * 63*62 + (pos[1] - i) * 62 + (pos[2] - j);
        else if (OffdiagA1H8[pos[1]])
            idx = 6*63*62 + Diag[pos[0]] * 28*62 + Lower[pos[1]] * 62 + pos[2] - j;
        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]];
        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);

There is some documentation available that explains what the encoding does? It would be much easier to follow the code if you have an idea of what you are looking at...

The encoding function maps a position to its index into the table.

Suppose we have KRvK. Let's 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: Select all

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

But this way the TB is going to be an array of 64*64*64 = 262144 positions, 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. See the KK_idx[10][64] array.

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: Select all

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

In words: if wR "comes later" than wR, we deduct 1, and the same if wR "comes later" than bK.

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 (I think).

So 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 colour. For example KRRvK. We don't 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.

So 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 calcuted. 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.

In init_tb() the relevant case is determined for each TB (this mirrors how the generator picked the encoding type):

Code: Select all

    for &#40;i = 0, j = 0; i < 16; i++)
      if &#40;pcs&#91;i&#93; == 1&#41; j++;
    if &#40;j >= 3&#41; ptr->enc_type = 0;
    else if &#40;j == 2&#41; ptr->enc_type = 2;
    else &#123; /* only for suicide */
      j = 16;
      for &#40;i = 0; i < 16; i++) &#123;
        if &#40;pcs&#91;i&#93; < j && pcs&#91;i&#93; > 1&#41; j = pcs&#91;i&#93;;
        ptr->enc_type = ubyte&#40;1 + j&#41;;
      &#125;
    &#125;

- 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. A bit surprising that it is still there.

(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 adjecent kings, and such positions anyway compress very well (as don't cares).)

I guess I 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() .

You should see the special case routine for indexing KKKvNN for suicide chess for the previous iteration of my suicide TB generator! The two current generic encoding functions save thousands of lines over what I previously had. (Plus they lead to better compression, because of the flexibility in ordering pieces.)

[syzygy]

Line by line explanation of the "111" case.

We are calculating an index for wK, wR, bK (pos[0], pos[1], pos[2]). We don't 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: Select all

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

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

Code: Select all

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

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: Select all

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

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: Select all

        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]];

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

Code: Select all

        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);

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

[mcostalba]

Thanks for this! Now it's much more clear.

[Sven]

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.

Shouldn't this read like:

"[...] 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."

[syzygy]

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.

Shouldn't this read like:

"[...] 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."

Yes it should. I wasn't thinking.

[mcostalba]

Browsing through code, I found some data I am not able to figure out what it means. I have seen their definitions, but are all quite complicated. Could you please explain what the following vectors mean and how are defined?

Code: Select all

uint8_t norm[TBPIECES];
int factor[TBPIECES];
uint8_t* sympat;
uint8_t* symlen;

Thanks!

[syzygy]

Code: Select all

uint8_t norm[TBPIECES];
int factor[TBPIECES];

These have to do with how pieces are "ordered" in a particular table. They are calculated once for each table.

For example KRRvK. As explained above, index calculation for this table takes the two Ks together and then adds the two Rs together.

The index calculation of the two Ks is in the first part of encode_piece(). The code after the switch() statement then places the two Rs. For this, it needs to know that there are two "like pieces" to be placed, i.e. two pieces of the same color and type. This is encoded in norm[]: norm[2] = 2.

For KQRvK we will have norm[2] = norm[3] = 1.

For KRRRvKB, the KKB will be placed first (case "111") and norm[3] = 3.

The term "norm" originally can from "normalise" or "normalisation". But it's just a helper array.

The factor[] array determines, in case of KRRvK, how to map the two separate values calculated for KK and RR to one index value. Either idx_KK * 1891 + idx_RR * 1 or idx_KK * 1 + idx_RR * 462. (This is because idx_KK is in 0..461 and idx_RR is in 0..1890, because 62*61/2=1891.)

There is really not too much to understand here. The generator has indexed all positions in a particular way (after trying out many possibilities and selecting what looks to be the best one) and the probing code will just have to use the same indexing method.

Code: Select all

uint8_t* sympat;
uint8_t* symlen;

This is part of the decompression code. sympat stands for symbol pattern, symlen for symbol length.

In case of a WDL table, we start with a series of values -2,-1,0,1,2 (loss, cursed loss, draw, cursed win, win). The compressor finds most frequent pairs of values (or rather, symbols) and replaces these with new symbols. This is repeated until there are at most 4095 symbols. These symbols are then compressed using Huffmann compression.

The probing code first calculates the index for the position. This index is used to find the right 64- or 32-byte block of compressed data and the position within this block that contains the value we need (for DTZ blocks are up to 1024 bytes; any block stores at most 65536 compressed values). The probing code then Huffman-decompresses symbols (each symbol s corresponding to symlen[s]+1 decompressed original values) until we are at the symbol that contains the value we need. That symbol is then "unpaired" until we have the right value. (There is also some mapping of values going on that reverses some mapping done in the compressor to further improve the compression ratio.)