A lot of unsolved positions

[viktpal]

I ran the test (test-vector.txt) but CHA failed to solve 118 out of 3652 positions. In the sample output (test.output) there were only 24 unsolved positions.

[miguel-ambrona]

Can you give more details?

Note that the tests are passing on GitHub, so the CI agrees with test.output.

[miguel-ambrona]

Note that the tests are run with a nodes limit of -limit 10000000, maybe that's the inconsistency if you didn't run the tests with make run-test.

[viktpal]

I created a project in Visual Studio and compiled the test program. I ran the program with input file test-vector.txt on Windows 10. In the test program (test.cpp) a nodes limit is a constant:

uint64_t globalLimit = 10000000;
search.set_limit(globalLimit);

[miguel-ambrona]

What's output that you get?

[viktpal]

The output file: output.txt

[viktpal]

Looks like I found the reason. I was using the latest version of Stockfish before. Now I changed the Stockfish version to the one specified in the Makefile and got correct results.

Interestingly, I got worse results with the newer version of Stockfish.

[miguel-ambrona]

Oh, thanks for the information!

I also observed that new versions were giving unexpected results and that's why I fixed a specific commit of Stockfish.

[viktpal]

Thank you for sharing your project!

[miguel-ambrona]

Thank you for using it! Feel free to close this issue if you think it's not a problem anymore.

[viktpal]

Everything works fine, but I noticed that CHA couldn't solve some positions like the following even with a node limit of 100.000.000: 7b/6Q1/4Bk2/p1p1p1p1/P1P1P1P1/8/8/4K3 b - - black

If all three positions after three possible moves by black (Kxf6, Kxg7, Bxg7) are solved separately, the program solves them quickly.

[miguel-ambrona]

The heuristic enters one of the branches and never goes back. This is very hard to improve without spoiling the average solving time in other positions. I will give it a try at some point.

Basically the tool is very bad at finding mates for a player with just a bishop when the opponent has a lot of material. On the other hand, finding an actual helpmate sequence when it exists is not so critical. What is important is that the tool can identify all unwinnable positions. What do you think?

[viktpal]

Yes, the most important thing is that the tool can identify all unwinnable positions. But I think it is possible to improve the algorithm so that it would analyze separately all the branches after the first move without losing efficiency. I rewrote the "full_analysis" function and now it solves more positions. Also, the new function found two misclassified positions in your test set (test-vector.txt) with the checkmate in the initial position.

#include <deque>

DYNAMIC::SearchResult DYNAMIC::full_analysis(Position& pos,
    DYNAMIC::Search& search) {

    search.init();
    search.set(0, 0, 0);

    std::deque<StateInfo> states;

    // Trivial progress
    for (int i = 0; i < 100; i++)
    {
        MoveList<LEGAL> moveList(pos);

        if (moveList.size() == 1)
        {
            states.push_back({});
            pos.do_move(*moveList.begin(), states.back());
            search.annotate_move(*moveList.begin());
            search.step();
        }
        else
            break;
    } 

    MoveList<LEGAL> moveList(pos);

    // Checkmate or Stalemate
    if (moveList.size() == 0) {
        if (pos.checkers() && pos.side_to_move() == !search.intended_winner())
            search.set_winnable();
        else
            search.set_unwinnable();
        return search.get_result();
    }

    // Insufficient material to win
    if (impossible_to_win(pos, search.intended_winner())) {
        search.set_unwinnable();
        return search.get_result();
    }

    search.set_flag(DYNAMIC::STATIC);

    if (SemiStatic::is_unwinnable(pos, search.intended_winner())) {
        search.set_unwinnable();
        return search.get_result();
    }

    // Check if the position is unwinnable in positions at depth 1 ply
    std::vector<ExtMove> undefinedBranches;

    for (auto& m : moveList) {
        StateInfo st;
        pos.do_move(m, st);

        if (!SemiStatic::is_unwinnable(pos, search.intended_winner()))
            undefinedBranches.push_back(m);

        pos.undo_move(m);
    }

    if (undefinedBranches.empty()) {
        search.set_unwinnable();
        return search.get_result();
    }

    search.set_flag(DYNAMIC::POST_STATIC);

    if (undefinedBranches.size() != moveList.size()) {
        int unwinnableCount = 0;
        for (const auto& m : undefinedBranches) {
            StateInfo st;
            pos.do_move(m, st);
            search.annotate_move(m);
            search.step();
            search.increase_cnt();

            TT.clear();

            // Apply iterative deepening (find_mate may look deeper than maxDepth on
            // rewarded variations)
            for (int maxDepth = 2; maxDepth <= 1000; maxDepth++) {
                // This choice seems empirically good
                uint64_t limit = 10000;
                search.set(maxDepth, search.actual_depth(), limit);
                bool mate = find_mate<DYNAMIC::FULL, DYNAMIC::ANY>(pos, search, 0, false, false);

                if (!search.is_interrupted() && !mate) {
                    unwinnableCount++;
                    break;
                }

                if (search.get_result() != DYNAMIC::UNDETERMINED ||
                       search.is_limit_reached())
                    break;
            }
            pos.undo_move(m);
            search.undo_step();

            if (search.get_result() == DYNAMIC::WINNABLE)
                break;
        }

        if (unwinnableCount == undefinedBranches.size())
            search.set_unwinnable();
    }
    else {
        TT.clear();

        // Apply iterative deepening (find_mate may look deeper than maxDepth on
        // rewarded variations)
        for (int maxDepth = 2; maxDepth <= 1000; maxDepth++) {
            // This choice seems empirically good
            uint64_t limit = 10000;
            search.set(maxDepth, search.actual_depth(), limit);
            bool mate = find_mate<DYNAMIC::FULL, DYNAMIC::ANY>(pos, search, 0, false, false);

            if (!search.is_interrupted() && !mate)
                search.set_unwinnable();

            if (search.get_result() != DYNAMIC::UNDETERMINED || 
                   search.is_limit_reached())
                break;
        }
    }

    return search.get_result();
}

[miguel-ambrona]

Thank you for this!

I guess you are talking about the following two positions:

8/8/8/8/8/1k6/b1b5/RKR5 w - -
8/8/8/8/8/2b1k1b1/8/3RKR2 w - -

I would not say they were misclassified. They are just illegal so we should not expect anything from the tool. To avoid this, I have sanitized the test vectors, removing all illegal positions.

With respect to your code. It's nice. Why don't you start a pull request and we iterate through it to incorporate your changes? Your routine is 4x slower than the current master though (on running the tests). We should work on that and get it at least as fast before we can merge it.

[viktpal]

I think that illegal positions are also useful for testing the algorithm.

My code focuses primarily on identifying unwinnable positions, so it can run significantly slower with typical positions. But on my computer this code with test vectors runs slightly faster than yours (110s vs 143s).

In order to make the algorithm work faster with typical positions, heuristics are needed to determine if we can skip the step analyzing all positions after the first move.

I've composed some dead positions that the tool can't solve:

-- B2b4/1b6/2k5/8/1p1p1p1p/1PpP1P1P/K1P4b/NB6 b - -

-B B2b4/1q6/2k5/8/1p1p1p1p/1PpP1P1P/K1P4b/NB6 b - -

I updated my code and it now solves these positions as well.

[miguel-ambrona]

After your PR was merged, should we close this issue?