Question to syzygy author

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 4425
Joined: Tue Feb 28, 2012 10:56 pm

Re: Question to syzygy author

Post by syzygy » Wed May 18, 2016 7:26 pm

syzygy wrote:
mcostalba wrote:Looking at the initialization of WDLEntry, I see that in case of symmetric material distributions (same material key for both sides), the precomp struct is fully initialized only for one key and during probe stm is always WHITE.

Nevertheless, even in this case, both precomp are allocated and the second (useless?) one is init with some partial data (pieces, norms and factors).

There is a reason for this?
Maybe I am misunderstanding you, but I think the original code only allocates one in that case.
OK, my code does allocate only one precomp, but it also initialises some fields in TBEntry_piece/pawn for both sides. You have moved those fields to the precomp struct, so to initialise both you now need to allocate both precomps.

The question is whether you could skip this. The reason I initialise both is that it's simply easier the way I set things up.

In the symmetric case, my variable bside is always 0, so only pieces[0], norm[0], factor[0] and precomp[0] need to be initialised.

So if it is just as easy for you to skip allocating and initialising precomp[1] in the symmetric case, then you could do that. Otherwise, it doesn't really matter as there are only few symmetric tables anyway.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Question to syzygy author

Post by mcostalba » Wed May 18, 2016 8:24 pm

syzygy wrote: The question is whether you could skip this.
Yes I can (and I did).

Thanks for pointing me to the correct direction.

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Question to syzygy author

Post by wgarvin » Thu May 19, 2016 7:47 pm

Michel wrote:
Yours is linear in N and mine seems to be quadratic on average. Skipping the last loop is of course also possible in your approach.
It is possble to do the unmapping in O(k) since you know the inner while loop (in Rein's modified code) will exit when sq is of the order of fact(k)*root^k(index). So you can do a small loop around that value (I haven't bothered to look for exact bounds).

Of course for small k the overhead will probably be too large.
I think if you have a cheap integer sqrt function you could do this unmapping in O(1) time with no table (i.e. sqrt(n+n+1) would either give you the correct square, or a square off by 1).

But its probably easier to just have a lookup table using N high bits of the mapped value as an initial guess. These tables are small enough to use exhaustive testing and confirm the max number of iterations needed to adjust the initial guess until it is correct. If you can just use all of the bits, no iterations are even needed. So e.g. for 64*63/2 (which includes 62*61/2), a 2016-byte lookup table can give you the larger square number in O(1) time. You then do a lookup in the same 64-short table that was used to compute the mapped index in the first place, and subtract that from the mapped index, to get the smaller square number.

[Edit: for example, if you take N=8, you can make a 252-byte table that gets you within 3 squares of the correct value, and almost always within 1. ]

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Question to syzygy author

Post by mcostalba » Fri May 20, 2016 5:50 am

Moving on I reached the probing functions. Probe_dtz and its twin Probe_dtz_noep are really more complex than what you'd expect. I count at least 4 searches, I also don't understand the meaning of 'success' apart from the natural one of fail reporting. But I see you multiplexed in some other meaning.

Care to walk through the probe dtz functions? Thanks.

syzygy
Posts: 4425
Joined: Tue Feb 28, 2012 10:56 pm

Re: Question to syzygy author

Post by syzygy » Fri May 20, 2016 7:28 am

mcostalba wrote:Moving on I reached the probing functions. Probe_dtz and its twin Probe_dtz_noep are really more complex than what you'd expect. I count at least 4 searches, I also don't understand the meaning of 'success' apart from the natural one of fail reporting. But I see you multiplexed in some other meaning.

Care to walk through the probe dtz functions? Thanks.
success == 1 means succes,
success == 0 means failure,
success == -1 means "probe the other side of the table" (from probe_dtz_table to probe_dtz_noep).

The tables do not contain information on position with ep rights. So for those the probing code has to do some extra work: first probe the position assuming ep is not possible (probe_dtz_noep()), then figure out whether ep captures affect the outcome.

More later.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Question to syzygy author

Post by mcostalba » Fri May 20, 2016 5:05 pm

syzygy wrote: More later.
Thanks for you answer. Indeed 'success' seems a bit more complex to me, like here:

Code: Select all

 *success = 1 + (alpha > WDLDraw)
Anyhow I tried to integrate ENPASSANT case in the loop. I think I made it right, but this code is a bit difficult. Can you please give it a look?

https://github.com/official-stockfish/S ... .cpp#L1213

In particular now probe_wdl() becomes trivial

https://github.com/official-stockfish/S ... .cpp#L1641

syzygy
Posts: 4425
Joined: Tue Feb 28, 2012 10:56 pm

Re: Question to syzygy author

Post by syzygy » Fri May 20, 2016 11:13 pm

mcostalba wrote:
syzygy wrote: More later.
Thanks for you answer. Indeed 'success' seems a bit more complex to me, like here:

Code: Select all

 *success = 1 + (alpha > WDLDraw)
You're right, there is one more case.

If a position has a winning capture, or if the position has a cursed winning capture and the position is a cursed win, then we know that DTZ = 1. The DTZ compressor makes use of this fact by treating such positions as don't care.

This means that the DTZ probing code must detect this case and avoid a call to probe_dtz_table for such positions (since the value returned would be random).

For this reason, probe_ab() sets success to 2 if there was a winning capture or if there was a cursed winning capture and the position is a cursed win. Probe_dtz_no_ep() checks for this:

Code: Select all

  if (*success == 2)
    return wdl == 2 ? 1 : 101;
Either wdl == 2 (win) and dtz = 1, or wdl == 1 (cursed win) and we return 101 meaning 1 ply to a conversion into a cursed win.
Anyhow I tried to integrate ENPASSANT case in the loop. I think I made it right, but this code is a bit difficult. Can you please give it a look?
One problem is that there may be two en passant captures. So you would need to do:

Code: Select all

        if (type_of(move) == ENPASSANT) {
            if (vale > epValue) epValue = value;
            moveCount--;
        }
and

Code: Select all

    if (epValue != WDLScoreNone && (moveCount == 0))
        value = epValue;
Apart from this, the code seems to be correct, but I might be missing something.

However, I personally don't like this modification. Probe_ab() is invoked a lot and generating all moves there and checking them for legality instead of only generating captures is a lot of unnecessary work. From an optmisation point of view, anything EP related should be left out of probe_ab().

syzygy
Posts: 4425
Joined: Tue Feb 28, 2012 10:56 pm

Re: Question to syzygy author

Post by syzygy » Sat May 21, 2016 12:15 am

syzygy wrote:More later.
So probe_dtz_no_ep() returns the correct dtz value assuming en passant is not possible in the probed position.

First probe_ab() is invoked (which thus is expected to return the correct WDL result assuming ep is not possible).

If probe_ab() returns 0, the position is a draw and probe_dtz_ep() can (and must, because the DTZ table contains a random value) return 0 immediately.

If success == 2, we know there is a (cursed) winning capture and we can (and must) return immediately as well.

The next part checks for (cursed) winning pawn moves. If we have such a move, we also know that dtz = 1 (and the compressor made use of this fact, so the DTZ table also contains random values for such positions). Obviously winning pawn moves only need to be checked for if probe_ab() returned wdl > 0.

If the position is not a draw and there are no winning captures or pawn moves, we have run out of cheap tricks and we must probe the DTZ table. Since DTZ tables are one-sided, we may be unlucky and find out that the "wrong" side is to move. In that case probe_dtz_table() will have returned success == -1.

If success == 0 (failure) or success > 0 (success), we can return.

If success == -1, we need to do a 1-ply search.
Because of the structure of the dtz values, it is easier to distinguish between wdl > 0 and wdl < 0.

If wdl > 0, then we want to find the move with the smallest winning (i.e. positive) dtz value. We can skip the captures and pawn moves, because we already know that those are not winning. Since we only try non-zeroing moves, the dtz value for a winning move is -probe_dtz(position_after_the_move) + 1.

If wdl < 0, then we want to find the move with the highest losing (i.e. negative) dtz value. Of course, all moves will return a negative dtz value because the position is known to lose.

The dtz value for a losing non-zeroing move is -probe_dtz(position_after_the_move) - 1.

For losing zeroing moves we have to be a bit more careful. A zeroing move always has distance to zero equal to 1. So those moves count as either -1 (in case of a real loss) or as -101 (in case of a cursed loss).

If wdl == -2, the position is a real loss, so all moves are real losses, so also all zeroing moves. So no need to investigate further.

If wdl == -1, the position is a cursed loss, so each move is either a real loss or a cursed loss (and at least one move is a cursed loss). So we need to investigate a bit for zeroing moves:

Code: Select all

          v = probe_ab&#40;pos, 1, 2, success&#41;;
          v = &#40;v == 2&#41; ? 0 &#58; -101;
The first line looks up the wdl value for the position after the zeroing move. We already know that that position is either a cursed win (= 1) or a real win (= 2). So to a bit more efficient, we call probe_ab() with alpha = 1 and beta = 2. If it returns 2, then the position is a real win, so the zeroing move is a real loss. If it returns < 2, then the position is a cursed win, so the zeroing move is a cursed loss.

The real losing zeroing move should count as -1 and the cursed losing zeroing move as -101. I guess the reason for "0 : -101" is that in that situation, if the zeroing move we are looking leads to a real loss, we know that some other move will anyway be "better" (namely a cursed loss). So it does not matter whether we count it as 0 or -1. But less confusing would have been -1 in this place. So to recapitulate what I just wrote (with the suggested readability change):

Code: Select all

      pos.do_move&#40;move, st, pos.gives_check&#40;move, ci&#41;);
      if &#40;st.rule50 == 0&#41; &#123; // is this move a zeroing move? &#40;capture or pawn move&#41;
        if &#40;wdl == -2&#41; v = -1; // if the position is a real loss, the move has dtz = -1
        else &#123; // if the position is a cursed loss, we have to take a closer look
          v = probe_ab&#40;pos, 1, 2, success&#41;; // test for cursed win or win &#40;for the position after the zeroing move&#41;
          v = &#40;v == 2&#41; ? -1 &#58; -101; // if win, count move as -1; if cursed win, count as -101
        &#125;
      &#125; else &#123;
        v = -Tablebases&#58;&#58;probe_dtz&#40;pos, success&#41; - 1; // for non-zeroing move
      &#125;
      pos.undo_move&#40;move&#41;;

syzygy
Posts: 4425
Joined: Tue Feb 28, 2012 10:56 pm

Re: Question to syzygy author

Post by syzygy » Sat May 21, 2016 12:50 am

Then we have probe_dtz(). It first assumes that ep is not possible and calls probe_dtz_no_ep(). If en passant is indeed not possible, it is finished.

If en passant is possible, it needs to look at the one or two en passant moves. Since they are captures and therefore zeroing moves (and en passant is not possible after a zeroing move), a call to probe_ab() gives sufficient information:

Code: Select all

    int v1 = -3;
    ....
    for &#40;moves = stack; moves < end; moves++) &#123;
    Move capture = moves->move;
    if &#40;type_of&#40;capture&#41; != ENPASSANT
                || !pos.legal&#40;capture, ci.pinned&#41;)
      continue;
    pos.do_move&#40;capture, st, pos.gives_check&#40;capture, ci&#41;);
    int v0 = -probe_ab&#40;pos, -2, 2, success&#41;;
    pos.undo_move&#40;capture&#41;;
    if (*success == 0&#41; return 0;
    if &#40;v0 > v1&#41; v1 = v0;
  &#125;
(We could try to be really smart and call probe_ab() with sharper bounds. But en passant is rare and calls to probe_dtz() are also rare.)

What follows is a bit tricky (and for a long time contained a bug). The reason for the trickiness is the structure of the dtz values. You can't easily compare two dtz values with < or > without knowing in what range you are.

If there are legal ep captures (v1 > -3), then normally we only need to check if they are better than the best other move, whose dtz value was returned by probe_dtz_no_ep() and is stored in v.

First we convert v1 = -2, -1, 0, 1, 2 to -101, -1, 0, 1, 101:

Code: Select all

 v1 = wdl_to_dtz&#91;v1 + 2&#93;;
Now we just walk through the possible cases:

Code: Select all

    if &#40;v < -100&#41; &#123; // probe_dtz_no_ep&#40;) returned a cursed loss
      if &#40;v1 >= 0&#41; // 0, 1, 101 are better than cursed loss. -1 is worse. -101 is the worst dtz value for a cursed loss
        v = v1;
    &#125; else if &#40;v < 0&#41; &#123; // probe_dtz_no_ep&#40;) returned a real loss
      if &#40;v1 >= 0 || v1 < -100&#41; // -101, 0, 1, 101 are better than a loss &#40;I guess v1 != -1 would do as well&#41;
        v = v1;
    &#125; else if &#40;v > 100&#41; &#123; // probe_dtz_no_ep&#40;) returned a cursed win, i.e >= 101
      if &#40;v1 > 0&#41; // both 1 and 101 are guaranteed to be at least as good
        v = v1;
    &#125; else if &#40;v > 0&#41; &#123;
      if &#40;v1 == 1&#41;
        v = v1;
    &#125;
Now the only remaining case is where probe_dtz_no_ep() returned a draw. If the no_ep position is a stalemate, then we must take v1 as the position's value. But we also must take v1 as the position's value if it is equal or better than a draw. So we first check for the latter, and only check for stalemate if the en passant moves are losing:

Code: Select all

    &#125; else if &#40;v1 >= 0&#41; &#123; // probe_dtz_no_ep&#40;) returned a draw and the en passant moves are at least draw
      v = v1;
    &#125; else &#123; // en passant moves are worse than draw, but they are still "best" if there are no other legal moves
      for &#40;moves = stack; moves < end; moves++) &#123;
        Move move = moves->move;
        if &#40;type_of&#40;move&#41; == ENPASSANT&#41; continue;
        if &#40;pos.legal&#40;move, ci.pinned&#41;) break;
      &#125;
      if &#40;moves == end && !pos.checkers&#40;)) &#123;
        end = generate<QUIETS>&#40;pos, end&#41;;
        for (; moves < end; moves++) &#123;
          Move move = moves->move;
          if &#40;pos.legal&#40;move, ci.pinned&#41;)
            break;
        &#125;
      &#125;
      if &#40;moves == end&#41;
        v = v1;
    &#125;

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Question to syzygy author

Post by mcostalba » Sat May 21, 2016 5:39 am

syzygy wrote: One problem is that there may be two en passant captures. However, I personally don't like this modification.
Yes you are right! I have fixed the code to handle up to 2 ep moves (although it is very difficult to figure out such positions with 5-men, perhaps with 6-men).

Regrading optimization, unfortunatly this topic is 10% intuition and 90% measurement. I plan to correctly profile the code after I have simplified it and eventually I will (re)add an optimization if profile shows me it is useul. For the moment I prefer to proceed with the simplest code base (that usually it is also the fastest and best).

P.S: Regrading figuring out positions to excercize this code path, well it seems we are talking of potential stalemates when the ep move is the only possible and the code path has an effect only if the ep is losing....very difficult to figure out such positions with 5-men.

Post Reply