Question to syzygy author
Moderators: hgm, Rebel, chrisw

 Posts: 2684
 Joined: Sat Jun 14, 2008 9:17 pm
Question to syzygy author
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.
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.

 Posts: 5646
 Joined: Tue Feb 28, 2012 11:56 pm
Re: Question to syzygy author
This is part of the compression scheme.mcostalba wrote: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?
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.
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 alphabeta).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?
You're welcomeThanks for answering.

 Posts: 2684
 Joined: Sat Jun 14, 2008 9:17 pm
Re: Question to syzygy author
Thanks for the answer!syzygy wrote: This is part of the compression scheme.
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);

 Posts: 5646
 Joined: Tue Feb 28, 2012 11:56 pm
Re: Question to syzygy author
The encoding function maps a position to its index into the table.mcostalba wrote:One of the most obscure parts is the encoding, where you can find someghting like this:
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...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);
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;
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 a1d1d4 triangle and bK on a nonadjacent square. If wK is on the a1d4 halfdiagonal, then bK can be forced to be on or below the a1h8 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);
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 a1h8diagonal, we can force the wR to be on or below the a1h8diagonal 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 a1d1d4 triangle (and if the first k pieces are on the a1h8diagonal, 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 (i = 0, j = 0; i < 16; i++)
if (pcs[i] == 1) j++;
if (j >= 3) ptr>enc_type = 0;
else if (j == 2) ptr>enc_type = 2;
else { /* only for suicide */
j = 16;
for (i = 0; i < 16; i++) {
if (pcs[i] < j && pcs[i] > 1) j = pcs[i];
ptr>enc_type = ubyte(1 + j);
}
}
 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.)

 Posts: 5646
 Joined: Tue Feb 28, 2012 11:56 pm
Re: Question to syzygy author
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 a1d1d4 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.
Precalculate the values we will have to deduct from pos[1] and pos[2].
wK is below the diagonal. Triangle[pos[0]] maps the b1d1d3 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*621).
wK is on the halfdiagonal a1d4, wR is below the diagonal.
Diag[pos[0]] maps a1d4 to 0...3. Lower[pos[1]] maps the b1h1h7 triangle to 0..27. 62 squares remain for bK.
Here, idx will be in (6*63*62)...(6*63*62 + 4*28*621).
Now wK is on the halfdiagonal a1d4, wR is on the diagonal a1h8, bK is below the diagonal.
And the final case: all on the diagonal a1h8.
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 a1d1d4 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]);
Code: Select all
if (OffdiagA1H8[pos[0]])
idx = Triangle[pos[0]] * 63*62 + (pos[1]  i) * 62 + (pos[2]  j);
Code: Select all
else if (OffdiagA1H8[pos[1]])
idx = 6*63*62 + Diag[pos[0]] * 28*62 + Lower[pos[1]] * 62 + pos[2]  j;
Diag[pos[0]] maps a1d4 to 0...3. Lower[pos[1]] maps the b1h1h7 triangle to 0..27. 62 squares remain for bK.
Here, idx will be in (6*63*62)...(6*63*62 + 4*28*621).
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]];
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);

 Posts: 2684
 Joined: Sat Jun 14, 2008 9:17 pm
Re: Question to syzygy author
Thanks for this! Now it's much more clear.

 Posts: 4052
 Joined: Thu May 15, 2008 9:57 pm
 Location: Berlin, Germany
 Full name: Sven Schüle
Re: Question to syzygy author
Shouldn't this read like:syzygy wrote: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.
"[...] 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."

 Posts: 5646
 Joined: Tue Feb 28, 2012 11:56 pm
Re: Question to syzygy author
Yes it should. I wasn't thinking.Sven Schüle wrote:Shouldn't this read like:syzygy wrote: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.
"[...] 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."

 Posts: 2684
 Joined: Sat Jun 14, 2008 9:17 pm
Re: Question to syzygy author
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?
Thanks!
Code: Select all
uint8_t norm[TBPIECES];
int factor[TBPIECES];
uint8_t* sympat;
uint8_t* symlen;

 Posts: 5646
 Joined: Tue Feb 28, 2012 11:56 pm
Re: Question to syzygy author
Code: Select all
uint8_t norm[TBPIECES];
int factor[TBPIECES];
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;
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 32byte 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 Huffmandecompresses 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.)