Matt solver

By Jörg Oster Date 2021-09-20 23:10 Upvotes 3

Ich habe übrigens mal eine einfache Mattsuche innerhalb von Stockfish realisiert.
Mehr oder weniger spaßeshalber, weil sehr weit kommt man ohne weitere Pruning-Algorithmen nicht.

Zum Beispiel:

Code:

position fen 8/2Nb4/pp6/4rp1p/1Pp1pPkP/PpPpR3/1B1P2N1/1K6 w - -
go mate 5
info string no mate in 1 found
info string no mate in 2 found
info string no mate in 3 found
info string no mate in 4 found
info depth 9 seldepth 9 multipv 1 score mate 5 nodes 2282138 nps 3143440 tbhits 0 time 726 pv b1c1 d7a4 c1d1 a6a5 d1e1 a5b4 e1f2 b4c3 e3g3
bestmove b1c1 ponder d7a4

Mit diesem kurzzügigen Matt hat der normale SF so seine Probleme.

By Jörg Oster Date 2021-09-20 23:15 Upvotes 1

Und noch 2 Positionen, jeweils Matt in 6.
Dies veranschaulicht auch gut, wie groß die Unterschiede in den Lösungszeiten sein können.

Code:

position fen 1K1N1b2/RPp1pr2/1kP5/2p5/P7/4B1P1/4p1b1/6n1 w - -
go mate 6
info string no mate in 1 found
info string no mate in 2 found
info string no mate in 3 found
info string no mate in 4 found
info string no mate in 5 found
info depth 11 currmove a7a5 currmovenumber 4
info depth 11 currmove e3d4 currmovenumber 5
info depth 11 currmove a7a8 currmovenumber 6
info depth 11 currmove b8c8 currmovenumber 7
info depth 11 seldepth 11 multipv 1 score mate 6 nodes 30712883 nps 3368009 hashfull 0 tbhits 0 time 9119 pv b8c8 g2h3 g3g4 h3g4 c8b8 g4d7 c6d7 c7c6 b8a8 b6c7 b7b8q
bestmove b8c8 ponder g2h3

Code:

position fen 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -
go mate 6
info string no mate in 1 found
info string no mate in 2 found
info string no mate in 3 found
info string no mate in 4 found
info depth 9 currmove e5d6 currmovenumber 4
info depth 9 currmove e5f6 currmovenumber 5
info depth 9 currmove f4f5 currmovenumber 6
info depth 9 currmove g5f5 currmovenumber 7
info depth 9 currmove h5g7 currmovenumber 8
info depth 9 currmove e5g7 currmovenumber 9
info depth 9 currmove b8c6 currmovenumber 10
info depth 9 currmove e2c4 currmovenumber 11
info depth 9 currmove e5d4 currmovenumber 12
info depth 9 currmove e5c7 currmovenumber 13
info depth 9 currmove f4c4 currmovenumber 14
info depth 9 currmove f4d4 currmovenumber 15
info depth 9 currmove f4e4 currmovenumber 16
info depth 9 currmove d8c7 currmovenumber 17
info depth 9 currmove d8e8 currmovenumber 18
info depth 9 currmove d8c8 currmovenumber 19
info depth 9 currmove e2b5 currmovenumber 20
info depth 9 currmove h5g3 currmovenumber 21
info depth 9 currmove e2d3 currmovenumber 22
info depth 9 currmove e2f3 currmovenumber 23
info depth 9 currmove e5c3 currmovenumber 24
info depth 9 currmove f4f3 currmovenumber 25
info depth 9 currmove f4b4 currmovenumber 26
info depth 9 currmove a7a8q currmovenumber 27
info depth 9 currmove a7a8r currmovenumber 28
info depth 9 currmove a7a8b currmovenumber 29
info depth 9 currmove a7a8n currmovenumber 30
info depth 9 currmove f4a4 currmovenumber 31
info depth 9 currmove b8a6 currmovenumber 32
info depth 9 currmove e5b2 currmovenumber 33
info depth 9 currmove f4f2 currmovenumber 34
info depth 9 currmove e2d1 currmovenumber 35
info depth 9 currmove e2f1 currmovenumber 36
info depth 9 currmove e5a1 currmovenumber 37
info depth 9 currmove f4f1 currmovenumber 38
info string no mate in 5 found
info depth 11 currmove f4f6 currmovenumber 1
info depth 11 currmove h5f6 currmovenumber 2
info depth 11 currmove b8d7 currmovenumber 3
info depth 11 seldepth 11 multipv 1 score mate 6 nodes 299839182 nps 3194127 hashfull 0 tbhits 0 time 93872 pv b8d7 g2g1q e5c7 a2a1q e2f3 b1e4 f4f5 e4f3 f5e5 a1e5 g5e5
bestmove b8d7 ponder g2g1q

By Jörg Oster Date 2021-10-14 16:28 Upvotes 4

Ich konnte die Lösungszeiten weiter runter bringen.
Man beachte auch die wesentlich geringere Anzahl an nodes (Positionen), die zur Lösung benötigt wurden.
Leider drosselt das die nps auf ungefähr 1/3 des ursprünglichen Wertes.
Aber die Lösungszeit zählt hier nunmal.

Code:

position fen 1K1N1b2/RPp1pr2/1kP5/2p5/P7/4B1P1/4p1b1/6n1 w - -
go mate 6
info string no mate in 1 found
info string no mate in 2 found
info string no mate in 3 found
info string no mate in 4 found
info string no mate in 5 found
info depth 11 currmove e3d4 currmovenumber 5
info depth 11 currmove a7a8 currmovenumber 6
info depth 11 currmove b8c8 currmovenumber 7
info depth 11 seldepth 11 multipv 1 score mate 6 nodes 7058743 nps 1022709 hashfull 0 tbhits 0 time 6902 pv b8c8 g2h3 g3g4 h3g4 c8b8 g4d7 c6d7 c7c6 b8a8 b6c7 b7b8q
bestmove b8c8 ponder g2h3

Code:

position fen 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -
go mate 6
info string no mate in 1 found
info string no mate in 2 found
info string no mate in 3 found
info string no mate in 4 found
info depth 9 currmove e5d6 currmovenumber 4
info depth 9 currmove e5f6 currmovenumber 5
info depth 9 currmove f4f5 currmovenumber 6
info depth 9 currmove g5f5 currmovenumber 7
info depth 9 currmove h5g7 currmovenumber 8
info depth 9 currmove e5g7 currmovenumber 9
info depth 9 currmove b8c6 currmovenumber 10
info depth 9 currmove e2c4 currmovenumber 11
info depth 9 currmove e5d4 currmovenumber 12
info depth 9 currmove e5c7 currmovenumber 13
info depth 9 currmove f4c4 currmovenumber 14
info depth 9 currmove f4d4 currmovenumber 15
info depth 9 currmove f4e4 currmovenumber 16
info depth 9 currmove d8e8 currmovenumber 17
info depth 9 currmove d8c8 currmovenumber 18
info depth 9 currmove e2b5 currmovenumber 19
info depth 9 currmove h5g3 currmovenumber 20
info depth 9 currmove e2d3 currmovenumber 21
info depth 9 currmove e2f3 currmovenumber 22
info depth 9 currmove e5c3 currmovenumber 23
info depth 9 currmove f4f3 currmovenumber 24
info depth 9 currmove f4b4 currmovenumber 25
info depth 9 currmove a7a8q currmovenumber 26
info depth 9 currmove a7a8r currmovenumber 27
info depth 9 currmove a7a8b currmovenumber 28
info depth 9 currmove a7a8n currmovenumber 29
info depth 9 currmove f4a4 currmovenumber 30
info depth 9 currmove b8a6 currmovenumber 31
info depth 9 currmove e5b2 currmovenumber 32
info depth 9 currmove f4f2 currmovenumber 33
info depth 9 currmove e2d1 currmovenumber 34
info depth 9 currmove e2f1 currmovenumber 35
info depth 9 currmove e5a1 currmovenumber 36
info depth 9 currmove f4f1 currmovenumber 37
info depth 9 currmove d8c7 currmovenumber 38
info string no mate in 5 found
info depth 11 currmove f4f6 currmovenumber 1
info depth 11 currmove h5f6 currmovenumber 2
info depth 11 currmove b8d7 currmovenumber 3
info depth 11 seldepth 11 multipv 1 score mate 6 nodes 77304335 nps 1084775 hashfull 0 tbhits 0 time 71263 pv b8d7 g2g1q e5c7 a2a1q e2f3 b1e4 f4f5 e4f3 f5e5 a1e5 g5e5
bestmove b8d7 ponder g2g1q

Jörg.

By Hauke Lutz Date 2021-10-14 18:40 Upvotes 2

Ich habe nicht erwartet, dass sich Topengines bei der Stellung so blöd anstellen würden.
Komodo-Dragon, Stockfish und Lc0 brauchen bei mir mit 12 Threads bzw. RTX 2070 sogar nach 1. Kc1 noch ewig.
Houdini 6.03 hatte nach 1. Kc1 immerhin nur 19 Sekunden gebraucht um das Matt zu finden.
Der Stockfish vom 09.10.2021 wurde nach 327 Sekunden fertig.
Meine Vermutung, dass Komodo-Dragon mit MCTS besser klar kommt hat sich trotz der kurzen Zugfolge nicht bestätigt.

Stellst du den Mattsucher als Download zur Verfügung?

By Jörg Oster Date 2021-10-15 11:36 Upvotes 1

Keine Ahnung, ehrlich gesagt.
Chest sollte doch in allen Belangen wesentlich schneller sein.

Außerdem wurde im CCC ein Multithreaded Mate Solver angekündigt https://talkchess.com/forum3/viewtopic.php?f=2&t=77332&sid=d926ceb0f4a52eeecb7acc66face7cab.
Mal abwarten, ob was draus wird.

By Max Siegfried Date 2021-10-15 11:57

Jörg Oster schrieb:

Keine Ahnung, ehrlich gesagt.
Chest sollte doch in allen Belangen wesentlich schneller sein.

Außerdem wurde im CCC ein Multithreaded Mate Solver angekündigt <a class='ura' href='https://talkchess.com/forum3/viewtopic.php?f=2&t=77332&sid=d926ceb0f4a52eeecb7acc66face7cab.'>https://talkchess.com/forum3/viewtopic.php?f=2&t=77332&sid=d926ceb0f4a52eeecb7acc66face7cab.</a>
Mal abwarten, ob was draus wird.

Das hört sich durchaus spannend an.
Stockfish könnte später von den Ideen profitieren.

By Hauke Lutz Date 2021-10-15 17:10 Upvotes 1

Danke für deine Antwort.
Ich bin gespannt was sich daraus ergibt!

By Roland Riener Date 2021-10-15 12:07 Upvotes 3

Crystal findet die Lösung auf meinem DualCore in 2 Sekunden:

8/2Nb4/pp6/4rp1p/1Pp1pPkP/PpPpR3/1B1P2N1/1K6 w - - 0 1

Analysis by Crystal 240621:
...
1.fxe5 f4 2.Txe4 Kf3 3.e6 Lxe6 4.Txf4+ Kxg2 5.Sxe6 b5 6.Sd4 Kg3 7.Te4 Kg2 8.Te6 Kg3 9.Txa6 Kxh4 10.Tg6 Kh3 11.Tg1 h4 12.Tg7
+- (14.61) Tiefe: 12/26   00:00:02 376kN

1.Kc1 Te6 2.Kd1 Tc6 3.Ke1 Txc7 4.Kf2 a5 5.Tg3#
+- (#5) Tiefe: 13/27   00:00:02 1149kN
...
1.Kc1 Te6 2.Kd1 Tc6 3.Ke1 Txc7 4.Kf2 a5 5.Tg3#
+- (#5) Tiefe: 244/9   00:00:14 48852kN

Gruß, Roland

By Hauke Lutz Date 2021-10-15 17:09 Upvotes 2

Der Eindruck hat sich bei mir bestätigt.
Kennst du dich genug aus um zu sagen weshalb Crystal 240621 sogar ohne die Vorgabe von 1. Kc1 so schnell ist?

By Jörg Oster Date 2021-10-15 18:37 Upvotes 4

Ganz allgemein gesagt, weniger Pruning!

By Peter Martan Date 2021-10-15 21:20 Upvotes 4

Aber schon auch etwas spezieller Matefinder (Vorläufer von Crystal vom selben Autor Joseph Ellis)- Code, ja?
Nullmove setzt Crystal eher mehr ein als Matefinder, sag ich mal so.
Hat die Fortress Detection etwas mit Mattsuche zu tun?
Danke für die Infos und deine Mattsucher- Versuche, Jörg.

By Hauke Lutz Date 2021-10-16 17:03 Upvotes 1

Danke für die Erklärung.
Ich habe mich wegen der vielen Einstellmöglichkeiten mit Dragon 2.5 beschäftigt.
Den Pruning-Effekt konnte ich mit Dragon 2.5 wiederholen.
Mit dem kleinsten Pruningwert (Reduction -50 und ohne Late- und Null Move Pruning) schaffte Dragon das #5 in wenigen Sekunden.
Die Berechnungen stoppten nach 19 Sekunden.

By Roland Riener Date 2021-10-16 21:54 Upvotes 1

Auch der Gratis-Komodo 12 schafft es bei Herausnahme des Hakens "Null Move Pruning":

8/2Nb4/pp6/4rp1p/1Pp1pPkP/PpPpR3/1B1P2N1/1K6 w - - 0 1

Analysis by Komodo 12.1.1 64-bit:
...
1.fxe5 Lc6 2.e6 f4 3.Sxf4 Kxf4 4.e7 Ke5 5.e8D+ Lxe8 6.Sxe8 a5 7.Sg7 Kd5 8.Sxh5 Kc6 9.Sf6 Kb5 10.Sxe4 Ka4 11.h5 axb4 12.cxb4 Kb5
+- (12.57) Tiefe: 18   00:00:01 2540kN
1.Sxa6 Lc6 2.Kc1 Ta5 3.bxa5 bxa5 4.Sc7 a4 5.Kd1 Lb5 6.Sd5 Le8 7.Sf6#
+- (#7) Tiefe: 18   00:00:02 4872kN
1.Kc1 Lc6 2.Kd1 Lb5 3.Ke1 Lc6 4.Kf2 Te7 5.Tg3#
+- (#5) Tiefe: 18   00:00:02 4872kN

By Chess Player Date 2021-11-30 11:54 Upvotes 1

New game
8/2Nb4/pp6/4rp1p/1Pp1pPkP/PpPpR3/1B1P2N1/1K6 w - - 0 1

Analysis by Stockfish 12 neu:

1. +- (#5): 1.Kc1 Rc5 2.Kd1 Rxc7 3.Ke1 Ra7 4.Kf2 a5 5.Rg3#
2. +- (19.13): 1.fxe5 f4 2.Nxf4 Kxf4 3.e6 Ba4 4.e7 Bd7 5.e8B Bf5 6.Nd5+ Kg4 7.Nxb6 Kxh4 8.Nxc4 Kg5 9.Nd6 Bh7 10.Bc6 Kf4 11.Nxe4 Bg6 12.Nf2 Bf5 13.Bd5 h4 14.Bxb3 Kg5 15.Bc4 Bc8 16.Nxd3 Kf6

(Privat-PC, Privat 30.11.2021)

By Jörg Oster Date 2021-10-15 15:57 Upvotes 2

Im Vergleich dazu ChestUCI, nur die letzte Stellung #6:

Code:

position fen 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -
go mate 6
info string FEN: 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -   (11+13)
info string Stellungs-Analyse:  C0/R0/K1/P9/X34   W:8/38
info string Problem in Datenbank gefunden:  #6; 00:01;
info string Suche nach Matt in 10 ...  (Hash=64MB)
info depth 6 currmovenumber 11 currmove b8d7
info depth 6 time 238 score mate 6 pv b8d7
info depth 6 seldepth 6 currmovenumber 38 currmove d8c7 hashfull 42 nodes 610291 nps 692725
info string Suche abgeschlossen ...  (Zeit=0.88s)
info string Matt in 6 gefunden !  (1 L÷sung in 00:00)
info depth 6 seldepth 6 time 881 score mate 6 multipv 1 pv b8d7 g2g1q e5c7 a2a1q e2f3 d2d1q f4d4 g1d4 g5e5 d4e5 d7c5
bestmove b8d7

Inwieweit die vorhandene Datenbank hier die Lösungszeit beschleunigt, kann ich nicht sagen.

By Jörg Oster Date 2021-10-28 11:05 Upvotes 1

Update: hier die aktuelle Version.

Code:

position fen 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -
go mate 6
info string No mate in 1 found
info string No mate in 2 found
info string No mate in 3 found
info string No mate in 4 found
info depth 9 currmove e2c4 currmovenumber 17
info depth 9 currmove e5d4 currmovenumber 18
info depth 9 currmove f4b4 currmovenumber 19
info depth 9 currmove f4c4 currmovenumber 20
info depth 9 currmove f4d4 currmovenumber 21
info depth 9 currmove f4e4 currmovenumber 22
info depth 9 currmove h5g3 currmovenumber 23
info depth 9 currmove e2d3 currmovenumber 24
info depth 9 currmove e2f3 currmovenumber 25
info depth 9 currmove e5c3 currmovenumber 26
info depth 9 currmove f4f3 currmovenumber 27
info depth 9 currmove e5b2 currmovenumber 28
info depth 9 currmove f4f2 currmovenumber 29
info depth 9 currmove e2d1 currmovenumber 30
info depth 9 currmove e2f1 currmovenumber 31
info depth 9 currmove e5a1 currmovenumber 32
info depth 9 currmove f4f1 currmovenumber 33
info depth 9 currmove d8c8 currmovenumber 34
info depth 9 currmove d8e8 currmovenumber 35
info depth 9 currmove h5g7 currmovenumber 36
info depth 9 currmove e5g7 currmovenumber 37
info depth 9 currmove d8c7 currmovenumber 38
info string No mate in 5 found
info depth 11 currmove f4f6 currmovenumber 1
info depth 11 currmove e2b5 currmovenumber 2
info depth 11 currmove f4a4 currmovenumber 3
info depth 11 currmove a7a8q currmovenumber 4
info depth 11 currmove a7a8r currmovenumber 5
info depth 11 currmove a7a8b currmovenumber 6
info depth 11 currmove a7a8n currmovenumber 7
info depth 11 currmove b8d7 currmovenumber 8
info string Success! Mate in 6 found!
info depth 11 seldepth 11 multipv 1 score mate 6 nodes 27548385 nps 1062372 hashfull 0 tbhits 0 time 25931 pv b8d7 g2g1q e5c7 a2a1q e2f3 d2d1q f4d4 a1d4 d7c5 d4c5 g5e5
bestmove b8d7 ponder g2g1q

Die schnellere Lösungszeit resultiert maßgeblich von der besseren Zugsortierung.

By Jörg Oster Date 2021-10-28 11:16 Upvotes 4

Ich stelle hier auch mal den Code der eigentlichen Suche rein.
Was fehlt, ist das Handling der Ausgangsposition (Root) um zu vermeiden, dass dies alles
gleich von anderen übernommen werden kann.
Sobald/Falls ich ein Release mache, steht der Code natürlich öffentlich auf Github.

Code:

  // Plain alpha-beta search function in negamax style,
  // fail-soft framework.

  Value search_mate(Position& pos, BasicStack* ss, Value alpha, Value beta, Depth depth) {

    StateInfo st;
    Value bestValue, value;
    bool inCheck = !!pos.checkers();
    int moveCount;
    Color us = pos.side_to_move();

    assert(alpha < beta);

    // Start with a fresh pv
    ss->pv.clear();

    // At the leaf, we simply either return a mate score
    // or zero. No evaluation needed!
    if (depth == 0)
    {
        if (inCheck && !MoveList<LEGAL>(pos).size())
            return mated_in(ss->ply);
        else
            return VALUE_DRAW;
    }

    // Check for draw by repetition and 50-move rule
    if (pos.is_draw(ss->ply))
        return VALUE_DRAW;

    // TODO: Tablebase probe
    // For the root color we can immediately return on
    // TB draws or losses

    bestValue = -VALUE_INFINITE;
    moveCount = 0;
    auto rankThisMove = 0;

    // Search all legal moves
    std::vector<RankedMove> legalMoves;
    legalMoves.reserve(64); // avoid reallocations

    auto king = pos.square<KING>(~us); // Square of the opponent's king

    for (const auto& m : MoveList<LEGAL>(pos))
    {
        if (pos.gives_check(m))
            rankThisMove += 2000 - 100 * distance(king, to_sq(m)); // Top priority!

        else if (pos.capture(m))
            rankThisMove += 200; // TODO MVV/LVA

        else
            rankThisMove += 20 * relative_rank(us, to_sq(m));

        // Add this ranked move
        legalMoves.emplace_back(RankedMove(m, rankThisMove));

        rankThisMove = 0; // Reset for the next move
    }

    std::stable_sort(legalMoves.begin(), legalMoves.end(),
        [](const RankedMove &rm1, const RankedMove &rm2) { return rm1.rank > rm2.rank; });

    for (auto& rm : legalMoves)
    {
        moveCount++;

        // At frontier nodes we can skip all non-checking moves
        if (   depth == 1
            && rm.rank < 1000)
            break;

        pos.do_move(rm.move, st);
        value = -search_mate(pos, ss+1, -beta, -alpha, depth-1);
        pos.undo_move(rm.move);

        // Do we have a new best value?
        if (value > bestValue)
        {
            // Beta-cutoff?
            if (value >= beta)
                return value;

            bestValue = value;

            if (value > alpha)
            {
                // Update alpha
                alpha = value;

                // Reset PV and insert current best move
                ss->pv.clear();
                ss->pv.push_back(rm.move);

                // Append child pv
                for (auto& m : (ss+1)->pv)
                    ss->pv.push_back(m);
            }
        }
    }

    if (Threads.stop.load(std::memory_order_relaxed))
        return VALUE_ZERO;

    // No moves? Must be Mate or Stalemate!
    if (!moveCount)
        bestValue = inCheck ? mated_in(ss->ply) // Checkmate!
                            : VALUE_DRAW;       // Stalemate!

    assert(-VALUE_INFINITE < bestValue && bestValue < VALUE_INFINITE);

    return bestValue;
  }

Und noch die beiden benötigten Structs.

Code:

struct BasicStack {

  BasicStack() {
    pv.reserve(8);
    ply = 0;
  }

  std::vector<Move> pv;
  int ply;
};

struct RankedMove {

  RankedMove(Move m, int r) : move(m), rank(r) {}

  Move move;
  int rank;
};

By Jörg Oster Date 2021-10-28 15:01 Upvotes 4

Was sind die Unterschiede zu einer "normalen" Alpha-Beta-Suche?

Die Suche ist relativ kompakt.
Es wird keine Bewertung benötigt!
Es kommen keinerlei herkömmlichen Pruning-Algorithmen zum Einsatz.
Kein Null-Move, Futility, Razoring oder Probcut, etc.

Ausnahme: vor dem letzten Ply werden nur Schachzüge berücksichtigt,
denn nur diese können Matt setzen! Andere Züge werden nicht untersucht.

By Jörg Oster Date 2021-10-29 12:11 Upvotes 2

Zur Zugsortierung:
Schachzüge werden zuvorderst gereiht, je näher am König desto besser,
danach Schlagzüge (MVV/LVA Sortierung muss ich noch implementieren),
danach dann alle restlichen Züge, sortiert nach der Reihe des Zielfeldes.

By Jörg Oster Date 2021-10-29 16:57 Upvotes 2

Die meisten hier werden wohl denken, schön und gut, aber was soll das?

Nun, zum einen beantworte ich gerne Fragen zum Code, falls jemand welche hat.
Und zum anderen erhoffe ich mir ein paar Anregungen/Ideen aus dem Forum.

Zum Beispiel zur Zugsortierung.
Macht es z. B. Sinn Springerzüge höher zu sortieren als Läuferzüge? Im Allgemeinen.
Man bedenke, wir reden hier von einem Mattlöseprogramm, nicht von einem normalen Schachprogramm.
Welche Ideen gibt es noch?

Welche Möglichkeiten zum Pruning gibt es noch?
Welche Einstellmöglichkeiten hat hier Chest zu bieten?
Hat wer entsprechende FENs auf Lager für entsprechende Tests?

Welche Art der Parallelisierung macht eurer Meinung nach Sinn?

Hat vielleicht gar einer einen Tipp, wie man die Zuggenerierung beschleunigen kann?
Wie man sieht, benutze ich einzig MoveList<LEGAL>(pos).

Bin gespannt auf eure Vorschläge.

By Frank Brenner Date 2021-10-29 19:41 Edited 2021-10-29 19:44 Upvotes 1

Die Zugsortierung ist am aller wichtigsten, d.h. es ist wichtig dass der beste Zug an den Anfang kommt. So häufig wie möglich.
Wenn der beste Zug am Anfang steht, ist die Reihenfolge der restlichen Züge egal.

Der normale Stockfish findet die meisten Matts bereits sehr schnell. Aber:
+ die meisten Mattdistanzen die Sf findet sind zu lang; es gibt kürzere.

+ manchmal ist Stockfisch blind und findet den richtigen Zug erst Stunden später oder sogar nie
(vor ein paar Monaten hatte ich mal eine Stellung hier gepostet, die jeder 1400 ELO Spieler löst, aber nicht Stockfisch)

Auf den unteren Ebenen im Baum kannst du dir sogar exorbitant viel Zeit nehmen für die Sortierung.
Je höher (oder Tiefer) du im Baum bist umso schneller muss die Sortierung erfolgen

Hintergrund ist: Für ein matt in 11 mußt du 21 Halbzüge tief rechnen.
Die Verweildauer des Matesolvers in den ersten 5 Tiefen beträgt dann nur 0.000001% der Gesamtzeit. (geraten)
Da aber gerade hier die Zugsortierung so wichtig ist, kannst du Dir ruhig 10000 mal mehr Zeit pro Knoten nehmen für eine gute Zugsortierung wie zb oben auf den höchsten drei Tiefen (am Ende der Äste)

Beispiele für Zugsortierungen sind:

+ Zug ausführen und Stellungsbewertung vom normalen Stockfish ermitteln, (NNUE oder die classic Bewertung)
und dann den besten Zug an den Anfang setzen.

Ich glaube die classic Bewertung wird hier hilfreicher sein.

In den ersten Suchtiefen, also ganz am Anfang wo der Baum noch klein ist, da kannst du sogar den Standard-Stockfish mit "iterative deepening" im 2-best Modus starten um
mit größtmöglicher wahrscheinlichkeit den besten Zug an die erste Stelle zu finden.
Für den aller ersten zug kannst du sogar eine Stockfish Suche mit Tiefe 14 machen.

Durch die Bewertung des zweitbesten Zugs kannst du das iterative deepening ggf frühzeitig abbrechen wenn der zweitbeste Zug deutlich schlechter ist .

Bei den ständigen Aufrufen von Standard-Stockfisch muß Stockfisch fleißig die Hashtabellen füllen. So kann der Mate-Solver dann vorher in den Hashtabellen nachgucken ob in der aktuellen Position im früheren Verlauf bereits eine Standard-Iterative-Deepening-Stockfisch Suche durchgeführt wurde und dann den besten Zug aus der Hasthtabelle nehmen.

Nur auf den höchsten Suchtiefen kann der Matesolver natürlich keine Stockfisch Suche mehr indurchführen. Dort nimmst du dann adhoc Kriterien wie zb MVV/LVA

By Benno Hartwig Date 2021-10-29 19:47 Edited 2021-10-29 19:51 Upvotes 1

> d.h. es ist wichtig dass der beste Zug an den Anfang kommt.

Wichtig ist nur, dass ein ausreichend guter Zug (möglichst) an erster Stelle kommt.
Mal sollte das bitte der bestmögliche Antwortzug sein, mal reicht aber auch eine mäßig gute Erwiederung.
Im a-b-Algorithmus ist ein sehr große Anzahl der Züge schlecht, und es reicht dann, möglichst sofort irgendeine Widerlegung zu spielen, nicht unbedingt die allerstärkste.

By Frank Brenner Date 2021-10-29 19:53 Upvotes 1

Zitat:

Wichtig ist nur, dass ein ausreichend guter Zug (möglichst) an erster Stelle kommt.

Irrtum: Deine Aussage gilt für eine heuristische suche bei der es nicht um perfekte Ergebisse geht, sondern nur darum einen möglichst guten Zug zu finden.

Der Matesolver muß das am Ende doch das kürzestmögliche Matt finden und nicht irgendein Matt.

Hierzu muß möglichst häufig der (einzige und kürzeste) Lösungszug an erster Stelle gefunden werden.

Für den Verteidiger muß jeder Zug in Betracht gezogen werden. Hier kann sogar auf eine Zugsortierung verzichtet werden.

By Frank Brenner Date 2021-10-29 20:23 Edited 2021-10-29 20:37 Upvotes 1

Eine Mattsuche braucht kein a,b Fenster. Hier wird das Fenster geschlossen. Es ist von anfang an Zu-.

Also um es einmal zu konkretisieren:

Wir haben eine Stellung die wir darauf prüfen wollen ob Weiß in 12 Zügen Mattsetzen kann.

Alle vorherigen Suchen Matt in 1.. Matt in 11 sind bereits vergebens gewesen.

Wir befinden uns nun in der Matt-in-12 SUche irgendwo mitten im Suchbaum und

1.) weiß am Zug:

Wir rufen die heuristische Suche auf und ermitteln (auf unteren tiefen sogar mit sehr viel Aufwand) den möglicherweise besten weißen Zug und führen diesen aus und rufen den matesolver rekursiv auf.
Kommt dann das entsprechende gesuchte Matt zurück (oder ein kürzeres), waren wir erfolgreich und machen den "Cut" und kehren zurück in die vorhergehende Tiefe, wo Schwarz dann weitere Alternativen ausprobieren muss.

Haben wir Pech und haben eine schlechte Zugvosortierung durchgeführt die uns kein Mattgewinn in 12 beschert hat so müssen wir noch weitere weiße Züge durchackern. (exponentieller Zeitanstieg)

2. Schwarz am Zug:
Wir müssen tatsächlich alle Züge von Schwarz ermitteln, ausführen und die rekursive Mate-Solver Suche aufrufen. Cuts wird es hier nicht geben und die Reihenfolge in der wir die schwarzen Züge durchlaufen ist egal.

By Frank Brenner Date 2021-10-29 20:33 Edited 2021-10-29 20:55 Upvotes 1

Langzügige Matträtsel von berühmten Komponisten haben oft die Eigenschaft, daß wenn Weiß die Mattkombination richtig ausspielt und immer den richtigen Zug findet und schwarz dagegen nicht die beste Verteidigung findet (für den langzügigsten Verlust), daß Weiß dann blitzschnell (also in sehr wenigen Zügen) Mattsetzen kann.

Durch diese Eigenschaft, wird unser Mattsolver dann selbst bei Matt-In-30 Stellungen sehr schnell sein - vorausgesetzt ein Orakel (der heuristische Stockfisch) - flüstert dem Mattsolver möglichst oft den besten Zug von Weiß vor.

Also was ich damit sagen will, wir müssen zwar dann stets alle (im Schnitt) 25 Züge von Schwarz ohne Cut durchackern, aber zum glück nicht bis Tiefe 59, weil weiß bei suboptimalen Verteidigungszügen blitzschnell gewinnen kann)

Der Aufwand bei languzügigen Matträtseln (zb Matt in 30) wäre dann also nicht

- nicht 25 hoch 59 ( wie bei reinem Minimax)
- und auch nicht 25 hoch (59/2) (wie bei der AB Suche bei perfekter beidseitiger Sortierung, in normalen Stellungen wo lediglich ein guter Zug gesucht wird)

Sondern im Extremfall sogar nur ein linearer Zeitaufwand, wenn zb bei einem Matt in 70 Weiß in allen Nebenvarianten in denen Schwarz sich nicht bestmöglich verteidigt in weniger als 1-4 Zügen blitzschnell gewinnen kann.

By Benno Hartwig Date 2021-10-29 23:10 Upvotes 1

> Irrtum: Deine Aussage gilt für eine heuristische suche bei der es nicht um perfekte Ergebisse geht, sondern nur darum einen möglichst guten Zug zu finden.

Ich denke, du irrst.
Wenn ich ein Matt in 5 suche und einen Zug teste der das nicht leistet, reicht beispielsweise, einen Antwortzug zu finden, der das Matt verhindert. Das führt bereits zum beta-cut.
Ich brauche nicht den stärksten Antwortzug, beispielsweise einen Zug, mit dem ich selbst mattgesetzt werde.
Regelmäßig brauche ich immer nur einen Zug, der meinen nicht-optimalen Zug widerlegt.
Die Forderung nach immer dem stärksten Antwortzug wäre deutlich zu stark.

By Frank Brenner Date 2021-10-29 23:58 Edited 2021-10-30 00:01 Upvotes 1

Ich glaube ein bißchen hast du Recht, ich hab nochmal genauer überlegt:

Also:

Wenn Weiß in einer Stellung den besten Zug findet und in der Baumsuche ausführt, dann muß in der nächsten Tiefe Schwarz alle seine Züge durchlaufen, egal in welcher Reihenfolge und die Baumsuche kann dann im Schwarz-Knoten keinen "cut" erleben. In dem Fall wäre die Reihenfolge der schwarzen Züge egal. Aber:

Wenn dagegen Weiß in einer Stellung eine nicht perfekte Zugsortierung macht und einen Zug als ersten auswählt der zwar eine Dame erobert aber nicht das gesuchte Matt erzielt, so ist es hilfreich, wenn in der nächsten Tiefe die schwarzen Antwortzüge einigermaßen sortiert sind und es findet dann sofort ein Cut statt, sobald Schwarz einen Zug findet der das Matt vereitelt (bei Jörg Oster wird dann ein VALUE_DRAW zurückgegeben). Dieses führt dann sofort bei Schwarz zum Cut und es wird zurückgegangen und Weiß muß den nächsten Zug aus seiner Zugliste liste nehmen. In dem Fall reicht für schwarz eine einfache und nicht optimale sortierung völlig aus.

Tatsächlich ändert das aber nichts an der Tatsache: Für ein Mate-Solver ist die Zugsortierung der weißen Züge (wir gehen davon aus, daß die Ausgangsstellung eine Weiß-Gewinnt Stellung ist), viel wichtiger und es sollte sehr viel Mühe aufgewendet werden so oft wie möglich wirklich den besten Zug (in Studien oft der Einzige) als erster auszuwählen.

Für diese Güte ist es sinnvoll in den ersten Halbzügen im Suchbaum tatsächlich sich zig-tausend mal so viel Zeit zu nehmen für die Ermittlung des wahrscheinlich besten Zuges für weiß.

Bei den Schwarzen Knoten - also da wo Schwarz am Zug ist - , braucht für die Sortierung nicht so viel aufwand betrieben werden. Hier reicht es einen mittleren guten Schwarzen Zug an den anfang zu setzen. Wenn weiß vorher den "richtigen" zug gefunden hat, so ist die Sortierung sogar egal.

Wenn es sich hierbei nicht um Schach handeln würde, wäre ein Mate-Solver eine spannende Challenge für mich.

Ich bin mir aber sicher, daß der Mate-Sovler von Jörg Oster so richtig einen "Boost" bekommt, wenn in den unteren Tiefen eine aufwendige Sortierung der weißen Züge durchgeführt würde (also zb Sortierung entsprechend der Stockfish Bewertung)

By Frank Brenner Date 2021-10-29 19:49 Upvotes 1

Also letztlich ist ein guter Matesolver eine Kombination aus lückenloser Suche und eingebetteter (extrem selektiver) heuristischer Suche . Die Zeitaufwendige heuristische Suche dient dazu dem dem Matesolver möglichst häufig den besten Zug an erster Stelle zu geben.

By Jörg Oster Date 2021-10-29 22:25 Upvotes 1

Hallo Frank,

Frank Brenner schrieb:

das stimmt.

Frank Brenner schrieb:

Der normale Stockfish findet die meisten Matts bereits sehr schnell. Aber:
+ die meisten Mattdistanzen die Sf findet sind zu lang; es gibt kürzere.

+ manchmal ist Stockfisch blind und findet den richtigen Zug erst Stunden später oder sogar nie
(vor ein paar Monaten hatte ich mal eine Stellung hier gepostet, die jeder 1400 ELO Spieler löst, aber nicht Stockfisch)

Deshalb ja der Mattlöser, der immer ein/das kürzestes Matt findet.

Frank Brenner schrieb:

Auf den unteren Ebenen im Baum kannst du dir sogar exorbitant viel Zeit nehmen für die Sortierung.
Je höher (oder Tiefer) du im Baum bist umso schneller muss die Sortierung erfolgen

Hintergrund ist: Für ein matt in 11 mußt du 21 Halbzüge tief rechnen.
Die Verweildauer des Matesolvers in den ersten 5 Tiefen beträgt dann nur 0.000001% der Gesamtzeit. (geraten)
Da aber gerade hier die Zugsortierung so wichtig ist, kannst du Dir ruhig 10000 mal mehr Zeit pro Knoten nehmen für eine gute Zugsortierung wie zb oben auf den höchsten drei Tiefen (am Ende der Äste)

Beispiele für Zugsortierungen sind:

+ Zug ausführen und Stellungsbewertung vom normalen Stockfish ermitteln, (NNUE oder die classic Bewertung)
und dann den besten Zug an den Anfang setzen.

Ich glaube die classic Bewertung wird hier hilfreicher sein.

In den ersten Suchtiefen, also ganz am Anfang wo der Baum noch klein ist, da kannst du sogar den Standard-Stockfish mit "iterative deepening" im 2-best Modus starten um
mit größtmöglicher wahrscheinlichkeit den besten Zug an die erste Stelle zu finden.
Für den aller ersten zug kannst du sogar eine Stockfish Suche mit Tiefe 14 machen.

Durch die Bewertung des zweitbesten Zugs kannst du das iterative deepening ggf frühzeitig abbrechen wenn der zweitbeste Zug deutlich schlechter ist .

Bei den ständigen Aufrufen von Standard-Stockfisch muß Stockfisch fleißig die Hashtabellen füllen. So kann der Mate-Solver dann vorher in den Hashtabellen nachgucken ob in der aktuellen Position im früheren Verlauf bereits eine Standard-Iterative-Deepening-Stockfisch Suche durchgeführt wurde und dann den besten Zug aus der Hasthtabelle nehmen.

Nur auf den höchsten Suchtiefen kann der Matesolver natürlich keine Stockfisch Suche mehr indurchführen. Dort nimmst du dann adhoc Kriterien wie zb MVV/LVA

Es kommt keinerlei Bewertung zum Einsatz, und auch kein Aufruf der herkömmlichen Stockfish-Suche.
Siehe auch meine Antwort an Hauke und Lothar.

Einer der nächsten Schritte ist wahrscheinlich das Verwenden einer abgespeckten Version der Hashtabelle
im Vergleich zum Original in SF.
Das muss ich mir aber erstmal genau durch den Kopf gehen lassen

Schön wäre es natürlich, wenn der Mattsucher alle möglichen Matts ausspucken würde, sofern mehrere Mattwege existieren.
Das ist auf den ersten Blick aber alles andere als trivial.

Gruß,
Jörg.

By Frank Brenner Date 2021-10-30 00:10 Upvotes 1

Zitat:

Schön wäre es natürlich, wenn der Mattsucher alle möglichen Matts ausspucken würde, sofern mehrere Mattwege existieren.
Das ist auf den ersten Blick aber alles andere als trivial.

Ja, wenn du alle Matts suchst, also auch alle Varianten finden möchtest... (nicht nur unterschiedliche Ausgangszüge) dann näherst du Dich ja der vollständigen Baumsuche an.

Eine clevere Suchtechik macht viele Cuts, und genau die kannst du dann in den weißen Knoten nicht mehr machen. (Wenn die Ausgangsstellung eine Weiß-Gewinnt Stellung ist)

By Frank Brenner Date 2021-10-30 00:51 Upvotes 1

Zitat:

Es kommt keinerlei Bewertung zum Einsatz, und auch kein Aufruf der herkömmlichen Stockfish-Suche.

Für die mate-solver Suche wird natürlich keine Bewertung aufgerufen. Es sollte als Ergebnis nur sowas wie "Success" oder ein "Failure" als Bewertung zurück geliefert werden, so geschieht es ja auch in deiner Suche.

Die Bewertungsfunktion von Stockfish kann aber für die Zugsortierung benutzt werden.

By Lothar Jung Date 2021-10-29 19:57 Edited 2021-10-29 20:08 Upvotes 1

Hallo Jörg,

danke das Du das Thema hier praxisnah rüberbringst.
Ich bin leider in Frankreich nur mit einem IPAD ausgestattet.

Aber ganz allgemein, würde ich die Bewertungskriterien für die Königssicherheit, umgekehrt für den Mattangriff anwenden.
Bei der Zugsortierung würde ich den Springer höher bewerten, da er gefährlicher, über die Schutzbauern hinweg, agieren kann.
Ein vorrückender h-Bauer ist auch für den Königsschutz sehr gefährlich. Ähnliches, aber abgeschwächt, gilt dies auch für g- und f-Bauern.
Läufer und Türme mit freien Diagonalen/Graden auf die Königsstellung sind auch für die Priorität der Zugsortierung zu berücksichtigen.
Zur Bewertung der Königsstellung fand ich diesen Beitrag sehr interessant:

https://chessmood.com/blog/evaluate-chess-position

Bitboards beschleunigen die Zuggenerierung.
FENs mit Bezug auf den Mattangriff gibt es in den einschlägigen Datenbanken zu Hauf.

Just my two Cents

Lothar

By Jörg Oster Date 2021-10-29 22:06 Upvotes 1

Lothar Jung schrieb:

Hallo Jörg,

danke das Du das Thema hier praxisnah rüberbringst.
Ich bin leider in Frankreich nur mit einem IPAD ausgestattet.

Aber ganz allgemein, würde ich die Bewertungskriterien für die Königssicherheit, umgekehrt für den Mattangriff anwenden.
Bei der Zugsortierung würde ich den Springer höher bewerten, da er gefährlicher, über die Schutzbauern hinweg, agieren kann.
Ein vorrückender h-Bauer ist auch für den Königsschutz sehr gefährlich. Ähnliches, aber abgeschwächt, gilt dies auch für g- und f-Bauern.
Läufer und Türme mit freien Diagonalen/Graden auf die Königsstellung sind auch für die Priorität der Zugsortierung zu berücksichtigen.
Zur Bewertung der Königsstellung fand ich diesen Beitrag sehr interessant:

<a class='ura' href='https://chessmood.com/blog/evaluate-chess-position'>https://chessmood.com/blog/evaluate-chess-position</a>

Bitboards beschleunigen die Zuggenerierung.
FENs mit Bezug auf den Mattangriff gibt es in den einschlägigen Datenbanken zu Hauf.

Just my two Cents

Lothar

Hallo Lothar,

SF verwendet ja schon Bitboards.
Ansonsten auch zu dir, es wird keinerlei Bewertung benötigt bzw. verwendet.
Siehe auch meine Antwort an Hauke Lutz.

Du hast dir selbst den von dir im Ausgangsposting verlinkten Artikel nicht durchgelesen. Stimmts?
Soll kein Vorwurf sein.

Gruß rüber nach Frankreich,
Jörg.

By Lothar Jung Date 2021-10-30 11:00 Upvotes 1

Hallo Jörg,

den einleitenden Artikel habe ich aufgenommen, da er PseudoCode enthielt.

Meine Vorschläge betreffen eigentlich den Königsangriff.

Grüße

Lothar

By Hauke Lutz Date 2021-10-29 20:24 Upvotes 1

Hallo Jörg,

der Gedanke ist wahrscheinlich einfach gedacht, aber würde es nicht bereits ausreichen beherrschte Felder in unmittelbarer Nähe des Königs deutlich besser zu bewerten?
Dadurch baut sich meiner Meinung nach das Mattnetz von selbst.
Das wäre möglicherweise sogar für einen normalen Stockfish anwendbar.
Falls es das in dieser Form schon gibt braucht der Bonus nur stark angehoben zu werden.

Gruß
Hauke

By Jörg Oster Date 2021-10-29 22:01 Edited 2021-10-29 22:31 Upvotes 1

Hauke Lutz schrieb:

Hallo Hauke,

gut gemeint, aber es kommt überhaupt keine Bewertung zum Einsatz.
Siehe auch https://www.chessprogramming.org/Mate_Search.

Besonders:

Zitat:

The main difference lies in the absence of the evaluation function. Mate finders only look for forced mates, but not for any material/positional advances. So any other evaluations than a mate-inspection are useless.

Gruß,
Jörg.

By Hauke Lutz Date 2021-10-30 18:57 Upvotes 2

Ok, dann formuliere ich den Gedanken so um das er passt.
Ist es eine Option die Anzahl der nutzbaren Fluchtfelder der Könige als eine Art Mobilität der Könige zählen zu lassen?
Ein König der nicht flüchten kann ist leicht Matt zu setzen.

By Jörg Oster Date 2021-11-01 11:08 Upvotes 3

Hauke Lutz schrieb:

Ja, das macht schon mehr Sinn.
Gibt es diese Art der Begrenzung der "Fluchtfelder" auch in Chest?

Eine weitere und naheliegende Begrenzung der Suche ist, nur Schachzüge für die mattsetzende Seite zu erlauben.

Die Frage ist halt, inwieweit man dies vorher schon weiß?!

Ich arbeite jetzt übrigens weiter daran und denke, dass ich in ein paar Tagen eine erste Version releasen werde.

By Hauke Lutz Date 2021-11-01 11:36 Upvotes 1

Bei Code bin ich ahnungslos. Ich habe nur so überlegt was Sinn machen könnte.
So ähnlich wie Kaufman bei Komodo, aber natürlich leider auf geringerem Niveau.

Die Idee mit den Schachzügen klingt interessant.
Dazu fällt mir gerade nichts ein.

Auf dein Release bin ich gespannt. Auch darauf, ob/wann+wie du die Fluchtfelder berücksichtigst.

By Jörg Oster Date 2022-11-07 11:57 Upvotes 2

Nur um mal den Stand der Entwicklung aufzuzeigen ...

Code:

position fen 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -
go mate 6
info depth 1 seldepth 1 multipv 1 score cp 0 nodes 2 nps 2000 tbhits 0 time 1 pv f4f6
info depth 3 seldepth 3 multipv 1 score cp 0 nodes 4399 nps 879800 tbhits 0 time 5 pv f4f6
info depth 7 seldepth 7 multipv 1 score cp 0 nodes 272546 nps 1222179 tbhits 0 time 223 pv f4f6
info currmove b8d7 currmovenumber 6
info string Success! Mate in 6 found!
info depth 9 seldepth 11 multipv 1 score mate 6 nodes 864765 nps 1219696 tbhits 0 time 709 pv b8d7 g2g1q e5c7 a2a1q e2f3 h8h5 g5e5 h5e5 f4f6 e7f6 d7f8
bestmove b8d7 ponder g2g1q

... von ursprünglich mal knapp 94 Sekunden runter zu weniger als einer. Nicht schlecht!
Aber: Entwicklung braucht Zeit!

By Jörg Oster Date 2023-09-15 12:23 Upvotes 1

Und jetzt kann Matefish auch Proof-Number Search!

Beispiel:

Code:

position fen k1r2q2/ppp5/6Qp/2P5/B7/5n2/5P2/1R5K w - -
go mate 4
Root move g6g1   PN: 30   DN: 1
Root move g6c2   PN: 30   DN: 1
Root move g6g2   PN: 30   DN: 1
Root move g6d3   PN: 30   DN: 1
Root move g6g3   PN: 30   DN: 1
Root move g6e4   PN: 50   DN: 39
Root move g6g4   PN: 30   DN: 1
Root move g6f5   PN: 65   DN: 21
Root move g6g5   PN: 31   DN: 1
Root move g6h5   PN: 30   DN: 30
Root move g6a6   PN: 0   DN: 10000000
Root move g6b6   PN: 30   DN: 1
Root move g6c6   PN: 29   DN: 507
Root move g6d6   PN: 30   DN: 1
Root move g6e6   PN: 30   DN: 1
Root move g6f6   PN: 65   DN: 21
Root move g6h6   PN: 30   DN: 1
Root move g6f7   PN: 61   DN: 21
Root move g6g7   PN: 30   DN: 1
Root move g6h7   PN: 30   DN: 1
Root move g6e8   PN: 29   DN: 1
Root move g6g8   PN: 29   DN: 1
Root move b1a1   PN: 30   DN: 1
Root move b1c1   PN: 30   DN: 1
Root move b1d1   PN: 30   DN: 1
Root move b1e1   PN: 30   DN: 1
Root move b1f1   PN: 30   DN: 1
Root move b1g1   PN: 30   DN: 1
Root move b1b2   PN: 30   DN: 1
Root move b1b3   PN: 30   DN: 1
Root move b1b4   PN: 30   DN: 1
Root move b1b5   PN: 29   DN: 1
Root move b1b6   PN: 30   DN: 1
Root move b1b7   PN: 29   DN: 36
Root move a4d1   PN: 30   DN: 1
Root move a4c2   PN: 30   DN: 1
Root move a4b3   PN: 30   DN: 1
Root move a4b5   PN: 29   DN: 1
Root move a4c6   PN: 29   DN: 40
Root move a4d7   PN: 30   DN: 1
Root move a4e8   PN: 29   DN: 1
Root move c5c6   PN: 32   DN: 1
Root move h1g2   PN: 30   DN: 1
info string Success! Mate in 4 found!
info time 5 multipv 1 depth 7 seldepth 7 nodes 6836 nps 1367200 tbhits 0 score mate 4 pv g6a6 c8b8 a4c6 f8f5 a6a7 a8a7 b1a1
bestmove g6a6 ponder c8b8

Code:

position fen 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -
go mate 6
Root move b8a6   PN: 216   DN: 259
Root move b8c6   PN: 233   DN: 267
Root move b8d7   PN: 0   DN: 10000000
Root move h5g3   PN: 245   DN: 67
Root move h5f6   PN: 233   DN: 36
Root move h5g7   PN: 215   DN: 177
Root move g5f5   PN: 215   DN: 117
Root move f4f1   PN: 215   DN: 91
Root move f4f2   PN: 225   DN: 132
Root move f4f3   PN: 225   DN: 142
Root move f4a4   PN: 215   DN: 11162
Root move f4b4   PN: 215   DN: 2104
Root move f4c4   PN: 215   DN: 3850
Root move f4d4   PN: 215   DN: 1319
Root move f4e4   PN: 215   DN: 4285
Root move f4f5   PN: 215   DN: 152
Root move f4f6   PN: 215   DN: 131
Root move e5a1   PN: 221   DN: 392
Root move e5b2   PN: 215   DN: 429
Root move e5c3   PN: 215   DN: 570
Root move e5d4   PN: 215   DN: 715
Root move e5d6   PN: 215   DN: 287
Root move e5f6   PN: 232   DN: 165
Root move e5c7   PN: 217   DN: 3427
Root move e5g7   PN: 216   DN: 202
Root move e2d1   PN: 228   DN: 99
Root move e2f1   PN: 230   DN: 84
Root move e2d3   PN: 222   DN: 337
Root move e2f3   PN: 215   DN: 1608
Root move e2c4   PN: 215   DN: 7803
Root move e2b5   PN: 215   DN: 3397
Root move a7a8q   PN: 215   DN: 177
Root move a7a8r   PN: 225   DN: 179
Root move a7a8b   PN: 215   DN: 309
Root move a7a8n   PN: 225   DN: 982
Root move d8c7   PN: 241   DN: 14
Root move d8e8   PN: 240   DN: 86
Root move d8c8   PN: 215   DN: 88
info string Success! Mate in 6 found!
info time 6682 multipv 1 depth 11 seldepth 11 nodes 10160763 nps 1520617 tbhits 0 score mate 6 pv b8d7 d5d4 f4f6 e6d5 e5h2 b1f5 h5f4 d5e4 f6e6 f5e6 g5e5
bestmove b8d7 ponder d5d4

In manchen Stellungen ist PNS richtig flott, in anderen langsamer als die AB-Suche.
In der nächsten Version kann man dann ProofNumberSearch als optionale Suche wählen.

Der Hauptnachteil ist natürlich der viel größere Speicherbedarf, da der ganze Suchbaum im Speicher gehalten wird,
und dass diese Suche erstmal nur single-threaded ist.
Die gezeigten Zahlen sind dann beim nächsten Release verschwunden; diese dienen mir hier nur zur Überprüfung.

By Olaf Jenkner Date 2021-11-05 19:11 Upvotes 5

Im Hinblick auf die Zugsortierung bin ich ganz anderer Meinung.

1) Das Sortieren von weißen Zügen bringt nur wenig.
2) Das Sortieren von schwarzen Zügen bringt nur wenig,
3) ABER: Den stärksten schwarzen Zug zu ermitteln, bringt sehr viel.

zu 1)
Wenn die Zugzahl bis zum Matt nicht bekannt ist, muß die Suche bei Matt in 1 beginnen und die Tiefe stets um einen Zug erhöht werden.
Wenn die richtige Tiefe noch nicht erreicht wurde, müssen alle weißen Züge untersucht werden, die Reihenfolge ist also egal.
Einen kleinen Vorteil gibt es in Varianten, bei denen durch schwache schwarze Züge ein Matt möglich ist. Schachbietende Züge sollten deshalb zuerst untersucht werden,
aber weiteren Aufwand in die Zugsortierung zu stecken, dürfte kontraproduktiv sein. Ohne großen Aufwand kann man aber den letzten erfolgreichen weißen Zug als erstes nehmen,
denn wenn Schwarz doch ein Matt zugelassen hatte, dann könnte der nächste schwarze Zug mit demselben weißen widerlegt werden. Man kann durch Heuristiken Züge weglassen,
damit erreicht man schneller höhere Suchtiefen, aber mit Zugsortierung hat das nichts zu tun. Für die übrig gebliebenen Zügen gilt das oben Gesagte.

zu 2)
99,9 Prozent der Zeit verbringt das Programm mit der Suche in aussichtslosen Stellungen. Für besonders lange Analysen kann man noch ein paar Neunen hinter dem Komma anhängen.
Es werden also fast nur Positionen berechnet, bei denen es kein Matt gibt und wo fast alle schwarzen Züge ausreichend verteidigen. Eine Sortierung nützt nichts, wenn nur ein
Zug benötigt wird.

zu 3)
Als stärksten schwarzen Zug meine ich einen Zug, der den weißen Suchbaum maximal einschränkt. Das wäre z.B. ein Schachgebot oder das Schlagen einer starken weißen Figur.
Um den stärksten Zug zu ermitteln, lohnt sich auch eine weitere Baumsuche. Der hinzunehmende Aufwand hängt ab von der Zugzahl bis zum Matt, denn je mehr Züge noch auszuführen
sind, desto größer ist die Einsparung durch den richtigen schwarzen Zug.

Für Schachaufgaben funktioniert diese Herangehensweise sehr gut. Es ist möglich, daß die beschriebenen Effekte bei Partiestellungen geringer sind.

By Lothar Jung Date 2021-11-05 22:35 Edited 2021-11-05 22:42 Upvotes 1

Ich hatte mich auch dahingehend geäußert, das Problem von der angegriffenen Seite zu betrachten und in die Suche einzubauen. Also Fluchtfelder. Kein “Matt Solver“ sondern Königsangriff. Das läßt sich auch in bestehenden allgemeinen Engines einbauen.

Lothar

By Jörg Oster Date 2021-11-06 18:29 Upvotes 1

Olaf Jenkner schrieb:

Ich nehme mal an, das ist als Antwort auf einen Beitrag von mir gedacht?!

Genau das mache ich ja mit der Zugsortierung.
Zuerst die schachgebenden Züge, dann Schlagzüge, dann die restlichen.
Wie berichtet, ergab dies eine drastische Reduzierung des Suchbaums.

Hashtabellen habe ich noch keine, das ist aber etwas, was ich definitiv noch ausprobieren werde.

By Lothar Jung Date 2021-11-08 16:17 Upvotes 1

Hier die Veröffentlichung von MateFish von Jörg Oster heute im Hauptforum:

„Source und Windows Release hier https://github.com/joergoster/Stockfish/tree/matefish

Threads auf talkchess
https://talkchess.com/forum3/viewtopic.php?f=2&t=76209&start=860#p911186
https://talkchess.com/forum3/viewtopic.php?f=2&t=78595#p911153“