potential deadlock in syzygy reference implementation

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Post Reply
User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

potential deadlock in syzygy reference implementation

Post by rvida » Sat Nov 23, 2013 2:43 pm

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
Posts: 4221
Joined: Tue Feb 28, 2012 10:56 pm

Re: potential deadlock in syzygy reference implementation

Post by syzygy » Sat Nov 23, 2013 3:14 pm

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.

User avatar
gcramer
Posts: 40
Joined: Mon Oct 28, 2013 10:21 pm
Location: Bad Homburg, Germany
Contact:

Re: potential deadlock in syzygy reference implementation

Post by gcramer » Sun Nov 24, 2013 6:34 am

I think there is another critical place in probe code:

Code: Select all

static int probe_ab&#40;Position& pos, int alpha, int beta, int *success&#41;
&#123;
  int v;
  ExtMove stack&#91;64&#93;;
  ExtMove *moves, *end;
  StateInfo st;

  // Generate &#40;at least&#41; all legal non-ep captures including &#40;under&#41;promotions.
  // It is OK to generate more, as long as they are filtered out below.
  if (!pos.checkers&#40;)) &#123;
    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&#91;&#40;TBPIECES - 2&#41;*27 + 16&#93;;
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&#91;TBPIECES*27&#93;;
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
Posts: 4221
Joined: Tue Feb 28, 2012 10:56 pm

Re: potential deadlock in syzygy reference implementation

Post by syzygy » Sun Nov 24, 2013 12:24 pm

gcramer wrote: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?

User avatar
gcramer
Posts: 40
Joined: Mon Oct 28, 2013 10:21 pm
Location: Bad Homburg, Germany
Contact:

Re: potential deadlock in syzygy reference implementation

Post by gcramer » Sun Nov 24, 2013 6:37 pm

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&#91;&#40;TBPIECES - 2&#41;*27 + 8&#93;;
for standard chess, and

Code: Select all

ExtMove stack&#91;&#40;TBPIECES - 1&#41;*27&#93;;
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
Posts: 4221
Joined: Tue Feb 28, 2012 10:56 pm

Re: potential deadlock in syzygy reference implementation

Post by syzygy » Sun Nov 24, 2013 8:53 pm

gcramer wrote: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.

User avatar
gcramer
Posts: 40
Joined: Mon Oct 28, 2013 10:21 pm
Location: Bad Homburg, Germany
Contact:

Re: potential deadlock in syzygy reference implementation

Post by gcramer » Sun Nov 24, 2013 9:13 pm

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.

User avatar
gcramer
Posts: 40
Joined: Mon Oct 28, 2013 10:21 pm
Location: Bad Homburg, Germany
Contact:

Re: potential deadlock in syzygy reference implementation

Post by gcramer » Fri Nov 29, 2013 12:24 pm

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
Posts: 4221
Joined: Tue Feb 28, 2012 10:56 pm

Re: potential deadlock in syzygy reference implementation

Post by syzygy » Fri Nov 29, 2013 8:09 pm

gcramer wrote: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
Posts: 10
Joined: Fri Nov 29, 2013 7:05 am

Re: potential deadlock in syzygy reference implementation

Post by seyyedparsakhatami » Wed Dec 04, 2013 2:10 pm

Hi Dear Richard
Thx

Post Reply