Natural TB

[mcostalba]

Contrary to what you think, this is not speculation.

You also wrote "The reason why it is there is to handle the case where DTZ is not available and the root position is in the TBs and winning."

Isn't this the same case...

[syzygy]

Contrary to what you think, this is not speculation.

You also wrote "The reason why it is there is to handle the case where DTZ is not available and the root position is in the TBs and winning."

Isn't this the same case...

There is the case where DTZ is available. SF then uses DTZ at the root only to filter out the non-winning moves (or the losing moves if the root is a draw). This code looks at the 50-move counter and tries to be a bit smart (e.g. it will go for losing moves will high DTZ if the root position is lost but the opponent has not too much 50-move margin). In this case, TB probing within the tree is disabled.

The other case is where DTZ is not available. If the root position is in the TBs, WDL is used to filter out the moves that are known to be suboptimal. But now it is impossible to properly take into account the 50-move rule. Since in this case the filtering step cannot guarantee a win within the 50-move rule, the search continues to do TB probes after captures and pawn moves. So now the search searches for either mate or a winning zeroing move. If the root posiion is a TB win and the search is able to bridge the distance from the root position to the next winning zeroing move, then the engine will convert the TB win (but engine play will be very ugly, as any winning pawn move will be preferred over a mate in two or a 2-ply combination that wins material). The engine may fail to convert the win if the distance to the next zeroing move is too large. This approach should normally work well in pawn endgames, where the winning path to mate can be very long and complicated, but the paths to each next winning pawn move will often be much shorter.

In this second case (root in TBs and winning, DTZ not available), one could do still a bit more by probing WDL at all OR nodes to quickly prune the non-winning moves, but this increases the number of probes a lot. The net effect of this change would probably be positive in endgames where the winning path is relatively narrow (like KRPvKP) and negative in endgames where basically all paths win (like KBNvK). When I wrote the root probing code I decided to keep the WDL root-probing fallback simple. So I only needed to add the rule50_count() == 0 condition. Play will be ugly, but it is only a fallback anyway.


While I am at it:
The root filtering approach has the problem that it might keep fewer moves than what multipv requires. It also has the problem that it might keep only those moves that the user has himself filtered out with the searchmoves option (in which case no moves are left to search at all).

To fix this, I implemented "root ranking" in Cfish. It turns out to be much simpler than the filtering code.

The ranking step assigns a "rank" to each root move based on its DTZ value and the value of the 50-move counter. Moves that are winning are assigned the top rank. Moves that do not win because of the 50-move rule are ranked lower. Moves that draw are ranked below that, moves that draw with high DTZ are ranked even lower. Moves that lose with low DTZ are ranked at the bottom. All root moves are then sorted by rank (top ranked first).

The idea of the ranks is that the main multipv loop is modified to search all equally ranked moves together. So if there are 3 moves that win and multipv = 5, then the multipv loop first searches the first 3 moves to find the best one, then the remaining two top-ranked moves to find the second best one, then the last top-ranked move to find the third best move. Then multipv searches moves ranked below the top-ranked moves to find the fourth and fifth best moves.

With this approach, multipv always produces the right number of lines and there is no problem if searchmoves happens to eliminate all top-ranked moves.

If DTZ is not available, then the ranks can be assigned on the basis of WDL values. This is of course less than ideal, because it cannot properly take into account the 50-move rule.

[jhellis3]

This is also very interesting. I see you don't use pos.rule50_count() == 0 condition to probe TB.

I still use the rule50 count, I just did not post the entirety of the code (only the relevant changes). Here is the complete code block:

Code: Select all

    // Step 4a. Tablebase probe
    if (!rootNode && TB::Cardinality)
    {
        int piecesCount = popcount(pos.pieces());

        if (    piecesCount <= TB&#58;&#58;Cardinality
            && &#40;piecesCount <  TB&#58;&#58;Cardinality || depth >= TB&#58;&#58;ProbeDepth&#41;
            &&  pos.rule50_count&#40;) == 0
            && !pos.can_castle&#40;ANY_CASTLING&#41;)
        &#123;
            TB&#58;&#58;ProbeState err;
            TB&#58;&#58;WDLScore v = Tablebases&#58;&#58;probe_wdl&#40;pos, &err&#41;;

            if &#40;err != TB&#58;&#58;ProbeState&#58;&#58;FAIL&#41;
            &#123;
                thisThread->tbHits.fetch_add&#40;1, std&#58;&#58;memory_order_relaxed&#41;;

                int drawScore = TB&#58;&#58;UseRule50 ? 1 &#58; 0;

                if (    abs&#40;v&#41; <= drawScore
                    || !ttHit
                    || &#40;v < -drawScore && ttValue > -VALUE_KNOWN_WIN&#41;
                    || &#40;v >  drawScore && ttValue <  VALUE_KNOWN_WIN&#41;)
                &#123;
                    value =  v < -drawScore ? -VALUE_MATE_IN_MAX_PLY + ss->ply + &#40;pos.non_pawn_material&#40;pos.side_to_move&#40;)) - pos.non_pawn_material&#40;~pos.side_to_move&#40;))) / 256
                           &#58; v >  drawScore ?  VALUE_MATE_IN_MAX_PLY - ss->ply + &#40;pos.non_pawn_material&#40;pos.side_to_move&#40;)) - pos.non_pawn_material&#40;~pos.side_to_move&#40;))) / 256
                                            &#58;  VALUE_DRAW + v * drawScore;

                    tte->save&#40;posKey, value_to_tt&#40;value, ss->ply&#41;,
                              v > drawScore ? BOUND_LOWER &#58; v < -drawScore ? BOUND_UPPER &#58; BOUND_EXACT,
                              depth, MOVE_NONE, VALUE_NONE, TT.generation&#40;));

                    if &#40;abs&#40;v&#41; <= drawScore&#41;
                        return value;
                &#125;
            &#125;
        &#125;
    &#125;

[BBauer]

I tried Ellis' aproach and it works very well.
Kind regards
Bernhard

[Nordlandia]

Ronald:

How long will it take to generate 5-men syzygy in DTM format on high-end hardware (in my case i7-5960X 8-core) and estimated volume with good compression technique?

[mcostalba]

I still use the rule50 count, I just did not post the entirety of the code (only the relevant changes). Here is the complete code block:

Code: Select all

<cut>    
                    tte->save&#40;posKey, value_to_tt&#40;value, ss->ply&#41;,
                              v > drawScore ? BOUND_LOWER &#58; v < -drawScore ? BOUND_UPPER &#58; BOUND_EXACT,
                              depth, MOVE_NONE, VALUE_NONE, TT.generation&#40;));

                    if &#40;abs&#40;v&#41; <= drawScore&#41;
                        return value;
<cut>

Thanks for sharing. Another interesting thing that you do is to save with LOWER / BOUND_UPPER instead of always BOUND_EXACT as it is usually done. Can you pelase elaborate on that?

I also see you keep searching losing positions, maybe this could reduce efficency a bit compared to return immediately but of course it is impossible to tell if it has an ELO impact or not.

[MikeB]

Ronald:

How long will it take to generate 5-men syzygy in DTM format on high-end hardware (in my case i7-5960X 8-core) and estimated volume with good compression technique?

The generation time is ultimately based the size of the TB's. Using a 12 core Mac Pro with slightly older CPUs (x5690) was able to generate syzygy all 6 Man EGTB's in less than 72 hours - let's call it 60 hours . This is about 150 GB. The Syzygy 5 Man EGTB takes up about 1 GB. Should not take more than an hour or so to generate using all 8 cores on your machine - maybe even 45 minutes or faster It will take you more time to read the documentation and to make sure one is using the right commands Don't attempt to generate the 6 Man unless you have 32 GB of RAM. It can take advantage of multiple CPUs - just read the fine print.

[Michel]

Another interesting thing that you do is to save with LOWER / BOUND_UPPER instead of always BOUND_EXACT as it is usually done. Can you pelase elaborate on that?

The TB scores are saved as bounds because they are bounds.... as has been pointed out time and time again. This is not rocket science.

[jhellis3]

Thanks for sharing. Another interesting thing that you do is to save with LOWER / BOUND_UPPER instead of always BOUND_EXACT as it is usually done. Can you pelase elaborate on that?

Well, Bound Exact is only correct for draws, the result will never be greater than or less than a draw. But in the case of a TB win, that DTZ result implies mate eventually. To me, it certainly makes sense to treat a mate in X number of moves as greater value than mate eventually (and indeed this is the way they are actually scored in the engine), so use Bound Lower. Same principle applies to being mated.

[Nordlandia]

Michael: Nice to know.

I want depth to mate format for Chessbase's Let's Check Database.
Many endgame studies ignore 50-move rule. And exact distance to mate is very handy feature. I think it's easier if Ronald can share blueprint/recipe how it can be done.

I've already requested to implement of Gaviota on Asmfish/Sugar for this particular purpose.

Requesting DTM syzygy for miscellaneous usage. 5-men is good enough.