Questions on Syzygy / Fathom, implementation and testing

[AndrewGrant]

I have forked Arasan's development repo for Fathom, as the main repo seems to be stale and or broken, and Jon Dart seems to have taken it into his own hands to fix it (https://github.com/jdart1/Fathom)

A couple of things about how Stockfish implements Syzygy:
When SF probes and causes a cutoff, it is stored with depth = MIN(MAY_PLY-1, depth + 6).
I get that the idea is to store with a higher depth to avoid overwritting, and to allow more cutoffs,
since we should have a perfect eval of the position. But why not just save with MAX_PLY - 1?

Also, when in a PvNode, SF does the following:

Code: Select all

if (PvNode){
    if (bound == ALLNODE)
        best = value, alpha = MAX(alpha, best);
    else
        maxValue = value;
}

And right at the end of the search, before storing in the table, SF has

Code: Select all

if (PvNode) best = MIN(best, maxValue);

Also, do I really need the root_probe_dtz()? Won't the probes inside the search find A winning line on their own?

Finally, how to go about showing that TB is worth elo? I normally just test with a 32-concurrency on my machine, but that sounds like a bad idea since that ( maybe ? ) causes 32 copies of the 5man TB to be thrown around.

Also, I imagine time control is an important factor. Usually I test with some ultra-bullet TC like fishtest does...

Thanks,
Andrew Grant

[jdart]

When SF probes and causes a cutoff, it is stored with depth = MIN(MAY_PLY-1, depth + 6).
I get that the idea is to store with a higher depth to avoid overwritting, and to allow more cutoffs,
since we should have a perfect eval of the position. But why not just save with MAX_PLY - 1?

I actually do store TB entries with max depth.

Re ELO improvement: I think prior tests have shown that it is quite small, especially since Stockfish-level engines are reaching such gigantic search depths. But once in a while you will find something with the TBs that the engine would miss without them.

--Jon

[syzygy]

I have forked Arasan's development repo for Fathom, as the main repo seems to be stale and or broken, and Jon Dart seems to have taken it into his own hands to fix it (https://github.com/jdart1/Fathom)

A couple of things about how Stockfish implements Syzygy:
When SF probes and causes a cutoff, it is stored with depth = MIN(MAY_PLY-1, depth + 6).
I get that the idea is to store with a higher depth to avoid overwritting, and to allow more cutoffs,
since we should have a perfect eval of the position. But why not just save with MAX_PLY - 1?

If I remember well, the "depth + 6" was just a relatively arbitrary choice by me. A compromise between avoiding repeated TB probes of the same position and avoiding filling the TT with positions that may stop being relevant as the tree develops but won't let themselves be overwritten. I think the correction for MAX_PLY-1 was added by someone else (perhaps Gary, but I'm not sure).

My concern about MAX_PLY-1 is probably not valid given the current TT replacement policy of SF. But I'd have to check again to be sure.

A while ago I ran some local tests with both "MAX_PLY-1" and "depth", but neither seemed to be an improvement.

Also, when in a PvNode, SF does the following:

Code: Select all

if (PvNode){
    if (bound == ALLNODE)
        best = value, alpha = MAX(alpha, best);
    else
        maxValue = value;
}

And right at the end of the search, before storing in the table, SF has

Code: Select all

if (PvNode) best = MIN(best, maxValue);

This is part of the "early mate" patch.

Originally, SF simply probed and returned. That works "perfectly" but has the disadvantage of never finding a mate line that at some point enters the TBs. This is now solved by returning only if the TT value is outside the alpha/beta bounds. If it is not, the search is continued. To make sure the TT value is not forgotten if nothing better is found, bestValue or maxValue is adjusted in PV nodes.

If you want to start simple, just return immediately.

Also, do I really need the root_probe_dtz()? Won't the probes inside the search find A winning line on their own?

Not without special precautions. Assume the root node is in the TBs.

If you probe whenever the position is in the TBs, your search will return immediately from the root node and therefore not even look at any of the root moves. So it certainly won't find a winning line.

If you make sure the root node does not probe, your search will return immediately from nodes 1 ply away from the root. So the search will be able to distinguish winning moves from drawing and losing moves, but that is not sufficient even to win KBNK.

The simplest solution is to play a winning move that mates, captures or moves a pawn, if available, and otherwise a winning move that minimises DTZ. That will not be very pretty in certain positions, but it works.

Finally, how to go about showing that TB is worth elo? I normally just test with a 32-concurrency on my machine, but that sounds like a bad idea since that ( maybe ? ) causes 32 copies of the 5man TB to be thrown around.

The memory the TBs are mmap()ed to is shared between all threads and processes mmap()ing those files.

Also, I imagine time control is an important factor. Usually I test with some ultra-bullet TC like fishtest does...

Probing the DTZ tables can take a bit longer, especially if the relevant parts have to be loaded from disk. For normal TCs this should not be a problem as the DTZ tables are probed only at the root (once the root is in the TBs). At ultra-bullet TCs this could be more critical.

[syzygy]

If the DTZ tables are not available, SF detects this when probing at the root and falls back to using WDL tables to try to find a winning line. It does this by probing only positions following a capture or pawn move. This means that SF will search for a win by searching for a winning capture or winning pawn move (or mate). Still, this is not sufficient to resolve all difficult 5-men endings (but without DTZ you can't expect perfection).

[AndrewGrant]

Thank you for the insights.

Do either of you have any qualms with Fathom currently?

If I don't care about natural play when TB are used, if the root node is in the TB, can I simply return a best move immediately? Fathom's tb_probe_root appears to return some encoded results, as well as AN optimal move.

[AndrewGrant]

If you don't mind taking a second to look at my implementation, I would greatly appreciate it. I see that you have wrapped the return results of Fathom to match syzygy, exampling being the LOSS = -2, Bless Loss = -1, ...

Code: Select all

    if (!RootNode && TB_LARGEST){
        
        int piececount = popcount(board->colours[WHITE] | board->colours[BLACK]);
        
        if (    board->fiftyMoveRule == 0
            &&  board->castleRights == 0
            &&  piececount <= &#40;int&#41;TB_LARGEST
            && &#40;piececount <  &#40;int&#41;TB_LARGEST || depth >= &#40;int&#41;TB_PROBE_DEPTH&#41;)&#123;
                
            unsigned result = tablebasesProbeWDL&#40;board&#41;;
                
            if &#40;result != TB_RESULT_FAILED&#41;&#123;
                
                value = result == TB_LOSS ? -MATE + MAX_PLY + height + 1
                      &#58; result == TB_WIN  ?  MATE - MAX_PLY - height - 1 &#58; 0;
                      
                bound = result == TB_LOSS ? ALLNODE
                      &#58; result == TB_WIN  ? CUTNODE &#58; PVNODE;
                      
                if (    bound == PVNODE
                    || &#40;bound == CUTNODE && value >= beta&#41;
                    || &#40;bound == ALLNODE && value <= alpha&#41;)&#123;
                                            
                    storeTranspositionEntry&#40;&Table, MAX_PLY - 1, bound, 
                                            valueToTT&#40;best, height&#41;, NONE_MOVE, board->hash&#41;;
                            
                    return value;
                &#125;
                
                if &#40;PvNode&#41;&#123;
                    if &#40;bound == ALLNODE&#41;
                        best = value, alpha = MAX&#40;alpha, best&#41;;
                    else
                        maxValue = value;
                &#125;
            &#125;
        &#125;
    &#125;

And I wrapped up tb_probe_wdl to avoid the massive argument list ...

Code: Select all

unsigned tablebasesProbeWDL(Board* board){
    
    return tb_probe_wdl(
        board->colours[WHITE],
        board->colours[BLACK],
        board->pieces[KING  ],
        board->pieces[QUEEN ],
        board->pieces[ROOK  ],
        board->pieces[BISHOP],
        board->pieces[KNIGHT],
        board->pieces[PAWN  ],
        board->fiftyMoveRule,
        board->castleRights,
        board->epSquare == -1 ? 0 : board->epSquare,
        board->turn == WHITE ? 1 : 0
    );
}

[jdart]

Do either of you have any qualms with Fathom currently?

With the fixes I have put in, I don't have any issues with it presently. I have run many thousands of games with TBs enabled.

gcc generates a warning when compiling the code:

syzygy/src/tbprobe.c: In function ‘int probe_ab(const pos*, int, int, int*)’:
syzygy/src/tbprobe.c:775:22: warning: array subscript is above array bounds [-Warray-bounds]
p[i++] = lsb(bb) ^ mirror;
^
syzygy/src/tbprobe.c: In function ‘int probe_dtz(const pos*, int*)’:
syzygy/src/tbprobe.c:919:22: warning: array subscript is above array bounds [-Warray-bounds]
p[i++] = lsb(bb) ^ mirror;
^
But I think this is spurious (this is in the original code I forked from too).

If I don't care about natural play when TB are used, if the root node is in the TB, can I simply return a best move immediately? Fathom's tb_probe_root appears to return some encoded results, as well as AN optimal move.

I don't know the answer to this.

--Jon

[jdart]

Code: Select all

value = result == TB_LOSS ? -MATE + MAX_PLY + height + 1 
                      : result == TB_WIN  ?  MATE - MAX_PLY - height - 1 : 0; 

I think this is incorrect. You are converting a tablebase score into a distance to mate score. But the tablebases don't give you distance to mate.

For me TB_LOSS is a negative constant that is large but above a mate score, and TB_WIN is positive constant that is large but below a mate score. If I put a tb hit into the hashtable, I just store TB_LOSS or TB_WIN. I don't adjust it for depth (but maybe I should?). In any case I think you have to distinguish Syzygy tb scores from mate scores.

--Jon

[syzygy]

Code: Select all

value = result == TB_LOSS ? -MATE + MAX_PLY + height + 1 
                      : result == TB_WIN  ?  MATE - MAX_PLY - height - 1 : 0; 

I think this is incorrect. You are converting a tablebase score into a distance to mate score. But the tablebases don't give you distance to mate.

But that's why MAX_PLY is added to "height", which presumably is the distance from root to TB win.