Incorporating Endgame tablebases

[Sven]

So let's say: you do it your way and I do it my way, and everything's fine

Sure, I wasn't planning to change.

But it would be helpful to the OP to see the pseudo-code of how you do it, so that everyone can judge for himself if and how that simplifies things.

Of course.

Code: Select all

int fullSearch(...)
{
    CHECK_TIMEOUT(...)

    if (IS_DRAW() {
        // fifty moves rule, insufficient material, repetition draw
        return 0;
    }

    // At this point I would insert EGT probing - currently Jumbo does not use EGT yet.
    // If no EGT is available then I can only try to detect some drawn endgames like:
    // - KNN vs. K
    // - K + minor vs. K + minor
    // - KBP vs. K with wrong-colored bishop
    // - KQ vs. KP with pawn on a2/c2/f2/h2
    // This could either be done inside evaluate() or in a special function that is
    // implemented "close to the evaluation function" and is called at this point.
    // I did the latter in my older engine KnockOut. But that is quite dangerous since
    // you must be absolutely sure not to return a draw score for a position that can
    // be won. For this reason my current engine Jumbo detects these types of position
    // within the evaluation function and only scales down the score appropriately but
    // does not turn the current node into a terminal node.

    MATE_DISTANCE_PRUNING(...)

    TT_PROBE(...)

    staticEval = evaluate(...)
    RAZORING(...)
    FUTILITY_PRUNING(...)
    NULL_MOVE(...)

    IID(...)

    GENERATE_MOVES(...)
    MOVE_LOOP(...)
}

[universecoder]

Any guidance on so as how to I can generate an endgame tablebase myself?

[Dann Corbit]

Its pretty complicated as for details.

There are two open source implementations:
The syzygy bases on github
The Eugene Nalimov code

I think HGM's tablebase file generator might be found somewhere.

Here is an article that explains how they work:
https://en.wikipedia.org/wiki/Endgame_tablebase

I would recommend against doing it unless you have a driving desire for it.

We already have a dozen endgame tablebase file formats, and all of them chew up an enormous amount of space.

What is the value add of yet another EGTB format?

I do recognize that it might be fun to write one, though.

[hgm]

I think HGM's tablebase file generator might be found somewhere.

The source code is published here: http://home.hccnet.nl/h.g.muller/EGTB.html

Note that it only works for 8x8 boards, and full 8-fold symmetry. (So no Pawns!) A somewhat more elaborate source (which can also be used as a WB engine to play against the generated EGT) is included in the fairygen package ( http://hgm.nubati.net/fairygen.zip ).

I also have an even simpler generator, which I never released. This is not because I want to keep it secret, but just because I assumed no one would want it. It can only do 4 men (3-vs-1) EGT, with pieces that on their own have no mating potential, not even for help mates. (It assumes draw as soon as one of the white pieces is captured. I also have a 3-men version of it, obviously for pieces with mating potential.) It does not assume any symmetry, though, and can handle any rectangular board (limited by memory requirements only). So it can do asymmetric pieces, like Gold General, and end-games for Capablanca Chess (10x8 board). It doesn't handle promotions, however. (So still no Pawns.)

One of the reasons I always focused on pawnless end-games is that Pawns are usually treated entirely different from pieces: every Pawn constellation is basically a different EGT (a 'P-slice'), and Pawn advances conversions between them. So you would solve those end-games P-slice by P-slice, working your way back through the sequence of irreversible moves.

Of this latter generator I also have a Xiangqi version, which treats the Palace (King + Advisers) and Elephants each as a single piece, with 119 or 29 'locations', respectively. This one actually does handle conversions (loss of one of the attacking pieces). So it can do KHHKEEAA.

Marcel van Kervinck also published a 'Pretty Fast' generator for KBNK. I have been working on generalizing it to do P-slices, which does work. But the project got stalled before I actually got to make it solve P-slices in an organized fashion to do end-games with Pawns.