potential deadlock in syzygy reference implementation

[rvida]

https://github.com/syzygy1/Stockfish/bl ... e.cpp#L136

in function probe_wdl_table(), there is a return statement at line 136 which exits the function without releasing the mutex first:

Code: Select all

 if (!ptr->ready) {
    LOCK(TB_mutex);
    if (!ptr->ready) {
      char str[16];
      prt_str(pos, str, ptr->key != key);
      if (!init_table_wdl(ptr, str)) {
        ptr->data = NULL;
        ptr2[i].key = 0ULL;
        *success = 0;
        return 0;         // <- deadlock here
      &#125;
      ptr->ready = 1;
    &#125;
    UNLOCK&#40;TB_mutex&#41;;
  &#125;

[syzygy]

Oops, you're right.

I think it can only be triggered if a table is present that does not have the expected "magic" first 4 bytes (or if the file was removed between engine intialisation and first use of the table), but obviously this should be fixed.

Btw, I think there is also a resource leak on Windows if the path variable is changed. The function map_file() creates a FileMapping which is not released. I should rename "size" and "mapped_size" into something more generic, use those to keep track of the handle, and let unmap_file() release it.

[gcramer]

I think there is another critical place in probe code:

Code: Select all

static int probe_ab(Position& pos, int alpha, int beta, int *success)
{
  int v;
  ExtMove stack[64];
  ExtMove *moves, *end;
  StateInfo st;

  // Generate (at least) all legal non-ep captures including (under)promotions.
  // It is OK to generate more, as long as they are filtered out below.
  if (!pos.checkers()) {
    end = generate<CAPTURES>&#40;pos, stack&#41;;

The stack size is problematic. In stockfish this may be sufficient. But in a different environment it's a memory problem, because due to your comment generate<CAPTURES>() is allowed to generate all pseudo-legal moves. Look at the FEN

Code: Select all

8/4K3/2Q5/5Q2/3Q4/1Q6/4k3/8 w - - 0 1

The number of all pseudo-legal moves is exceeding the stack size (116 legal moves - if I counted right). Furthermore the current stack size does not depend on TBPIECES.

I suggest to use a safe size, for example

Code: Select all

  ExtMove stack[(TBPIECES - 2)*27 + 16];

Maximal 27 for each queen, and maximal 8 for each king (in case of TBPIECES=6 the stack size is now 124). This is sufficient for standard chess. But if your probe code will be used in Antichess, even this stack size is problematic, theoretically there can be 6 queens on the board (I don't know if this happens in practice). So probably the stack size should be further increased:

Code: Select all

  ExtMove stack[TBPIECES*27];

PS: I'm using your original probe code in Scidb (http://scidb.sourceforge.net). I've written a wrapper class which maps to my own bitboard.

[syzygy]

The stack size is problematic. In stockfish this may be sufficient. But in a different environment it's a memory problem, because due to your comment generate<CAPTURES>() is allowed to generate all pseudo-legal moves.

I see your point. I think our views are a bit different.

My comments assume that a programmer will replace all SF-specific declarations and function calls by his own declarations and function calls (using the move generator of his engine (or GUI)). It would then be natural that the programmer also makes sure that all local arrays he allocates are sufficiently large. The SF-specific code is mainly there to clarify the comments. (I think it mostly speaks for itself, but in case of doubt anyone can check the SF sources to see what a particular function does.)

If you instead write a wrapper and try not to touch tbprobe.cpp, then indeed the stack size becomes a problem. For a GUI a wrapper is of course fine (but I don't know if that would be less work than adapting tbprobe.cpp to directly interface with your generator code). For an engine I would recommend against using a wrapper (especially if that entails converting board representations on every probe).

PS: I'm using your original probe code in Scidb (http://scidb.sourceforge.net). I've written a wrapper class which maps to my own bitboard.

Nice!
Would it not have been easier to adapt probe_ab() etc to directly use your bitboard routines?

[gcramer]

At first a small correction, although you do not change this part. Funnily enough I've counted the moves of both sides. So the given FEN has only 108 valid moves (black king subtracted), and the stack size can be a bit smaller:

Code: Select all

ExtMove stack[(TBPIECES - 2)*27 + 8];

for standard chess, and

Code: Select all

ExtMove stack[(TBPIECES - 1)*27];

for Antichess.

Would it not have been easier to adapt probe_ab() etc to directly use your bitboard routines?

I don't think so:

1. In this way I can use probe_wdl directly.

2. In this way it's easy to be synchronized with the latest repository version, a simple merge.

3. My bitboard does not have the required material count, I don't need this count in my application - not with this counting method -, but the wrapper class is computing this count.

4. The wrapper is quite thin and performant.

[syzygy]

At first a small correction, although you do not change this part.

I might add some extra comments to this part and various other parts.

3. My bitboard does not have the required material count, I don't need this count in my application - not with this counting method -, but the wrapper class is computing this count.

Do you mean the material signature key? There are many ways to do this and the one chosen for Stockfish is imho not the easiest or most efficient one. It is simpler to have a random value per piece/color and add those together. Or choose them well (as I do here, lines 50-100) and be sure they are all unique.

Note that the code expects the high 10 (= TBHASHBITS) bits to be relatively random. This also still has to be documented.

[gcramer]

Yes, I've meant the material signature key. I've implemented the Stockfish computation, but I think I will change this to your recommended method. Thanks for the hint.

[gcramer]

I have a question to calc_key() and calc_key_from_pcs(). In tbcore.cpp variants like Antichess are taken into account (if CONNECTED_KINGS is defined), but the key computation in these functions do not consider the King. I think that in general

Code: Select all

 
  for &#40;pt = PAWN; pt <= KING; ++pt&#41;

has to be used instead of

Code: Select all

 
  for &#40;pt = PAWN; pt <= QUEEN; ++pt&#41;

So far as I can see stockfish is generating the Zobrist keys for the King.

[syzygy]

So far as I can see stockfish is generating the Zobrist keys for the King.

No, Stockfish does not include the King in the material signature key, see Position::compute_material_key().

The functions calc_key() and calc_key_from_pcs() must calculate the key in the same way as the engine does (or one cannot use the engine's material key to quickly look up the right table).

For variants with king captures and king promotions the material key obviously has to include the number of kings. But for these variants many more changes are required as well.

[seyyedparsakhatami]

Hi Dear Richard
Thx