Get MoveGen errorfree

[Saturnus23]

How does one aproach the challenge of finding the bugs in movegen?
I find that my engine-to-be yields a perft 5 of 4,865,351 that should (appearantly) be 4,865,609.
So I am missing a worrysome 258 positions. Very open to suggestions
Or is it considered close enough? (cannot imagine that)

[kranium]

https://www.chessprogramming.org/Perft_Results
See the table entries for depth 5...
258 is the # of enpassant positions.
Check your enpassant detection routine, or add it if you don't have it.

Good luck

[Saturnus23]

Thanks. Very useful link!

[hgm]

To hunt down bugs in the move generator people use 'split perft', which does not just print the total value of perft(N), but also the perft(N-1) after each of the possible moves. Of course you should make your engine to that too, for comparison. Then you can immediately see which move is responsible for the wrong count, and then repeat the process (with a 1-lower perft) from the position after that. That quickly brings you to the (or a) position where it counts the wrong number of moves, and usually you can determine 'by hand' which move is missing (or extra) in that position.

You could use Qperft for generating a split perft from any position. Use the following command in a command-line window:

perft2 N -2 "FEN"

where N is the depth you want, and FEN the position. (Which is optional; if omitted it uses the FIDE start position.) The -2 parameter controls the depth at which it splits, and is also optional (for no split).

Note that the procedure does not always works: I have seen cases where the split perft indicated an error in a certain move. But perfting from the position after that move gave the correct total. The reason was that the engine did not pass e.p. rights correctly, but did read them correctly from a FEN. So the error occurred only in non-root positions.

I can add that perft never has been very useful to me; I almost never have a bug in my move generators. That is of course because I use mostly trivial move generators. And often they do not strictly follow FIDE rules either (e.g. no under-promotion, or just Q and N) so that the perft would not be correct by intention. And finally most of my engines play variants for which the correct perft numbers are not known to begin with. I have had plenty of move bugs in my engines, but not of the kind that would show up in perft. More things like losing moves during sorting, overwriting the killer slots too early, using hash moves without enough checking for key collisions... When I make a complex, error-prone move generator (like in The Mailbox Trials or Inferno) I always start writing a trivial one (triply-nested loop for cycling through board, directions and distances taken from a table), and add some code to compare the move list generated by the complex generator with the one generated by the trivial one, for use in the test phase.

[gflohr]

I've used Stockfish as a reference ("go perft N"). Don't look at the total number of nodes but at the number of nodes that Stockfish reports for each move. Say that you see that from the start position with perft 6, you have the wrong number of nodes for "e2e4". The next try is then:

Code: Select all

position startpos moves e2e4
go perft 5

That will give you the number of nodes for each move after "e2e4", and you can narrow down the error once again. At one point, you reach a position where Stockfish finds a different number of moves than your engine, and then you debug why. Of course, you don't need to start from the start position, but from wherever you want. If you want to check the correctness of your promotion code, then the start position of chess is probably not the optimal one.

The last bug that I had found and fixed was also related to en passant. I forgot that capturing en passant can discover a check, for example, in "8/8/8/K7/1R3p1k/8/6P1/8 w - - 0 1" after "g2g4".

[benvining]

I recommend perft tests and the test cases here: https://github.com/schnitzi/rampart

[Saturnus23]

Thanks all. Very helpful indeed!

[phhnguyen]

Recently, I have spent a significant amount of time working with Perft for Chinese chess. On the one hand, I want to rewrite, optimise, and speed up the move generator for my chess engine. On the other hand, I planned to calculate some new Perft results of high depths. To prepare for that task, I have added hash tables and multiple threads for my Perft code. There were many bugs to find and fix. I share here some of my experience for debugging Perft:

• You should test your Perft with a variety of chess positions, from the starting to the middle and endgames. That ensures your move generators can work well with almost all configurations. My one ran well with many positions, and I was happy with it for a long time. One day, I tried it with a new endgame position and discovered some serious errors in the algorithms, which led me to rewrite a lot of code

• Divide results play a vital role in debugging Perft. You should compare your Perft results with those from good reference sources (say, Stockfish). Compare all numbers of all root moves to find a different one, make that move for both your engine and the source, run them with Perft depth-1; repeat until depth=1; now you can look at the board and find out problems (typically they are missing or incorrect moves)

• It will be easier if you integrate a reference source into your code. In my case, I already have a chess source code using mailbox representation. It is slow but simple, trustworthy for (almost) all positions. When creating a new chess engine (using bitboards), I integrated the mailbox code into the new one, added some code to run Perft for both. They will auto-compare the results and narrow down to the caused positions. All run auto and are very fast

• You may use other (external) chess engines as Perft references, such as Stockfish. However, manually comparing results may be a nightmare, especially when you have to do that continuously for a few days. Typically, the results are long lists of moves with huge numbers. They may take a lot of time, labour and be frustrated. I suggest creating a script or a simple app to compare them. Results can be saved to files, or you may copy and paste them into the app

• Another solution to compare Perft results is to sort them first (sort as strings) before printing out, both yours and the reference engines. Manually comparing two sorted lists is easy and quick. You need to modify and recompile all involved engines.

Below is the modified code for the function perft() of Stockfish (it is in the file search.cpp) to sort and print results

Code: Select all

  // perft() is our utility to verify move generation. All the leaf nodes up
  // to the given depth are generated and counted, and the sum is returned.
  template<bool Root>
  uint64_t perft(Position& pos, Depth depth) {

    StateInfo st;
    ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize);

    uint64_t cnt, nodes = 0;
    const bool leaf = (depth == 2);
      
    uint64_t start;
    std::vector<std::string> rootMoves;
    if (Root) {
        start = std::chrono::duration_cast<std::chrono::milliseconds>
        (std::chrono::steady_clock::now().time_since_epoch()).count();
    }
      
    for (const auto& m : MoveList<LEGAL>(pos))
    {
        if (Root && depth <= 1)
            cnt = 1, nodes++;
        else
        {
            pos.do_move(m, st);
            cnt = leaf ? MoveList<LEGAL>(pos).size() : perft<false>(pos, depth - 1);
            nodes += cnt;
            pos.undo_move(m);
        }
        if (Root) {
            std::string str = UCI::move(m, pos.is_chess960()) + ": " + std::to_string(cnt);
            rootMoves.push_back(str);
            //sync_cout << str << sync_endl; // uncomment this line if you want to display results when running
        }
    }

    if (Root) {
        std::sort(rootMoves.begin(), rootMoves.end());
        for(auto && s : rootMoves) {
            sync_cout << s << sync_endl;
        }
        
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>
        (std::chrono::steady_clock::now().time_since_epoch()).count() - start;
        sync_cout << "\nElapsed: " << elapsed << " ms" << sync_endl;
    }
    return nodes;
  }

Perft 5 of Stockfish is printed as below. They are sorted alphabetically and include elapsed time.

Code: Select all

go perft 5
a2a3: 181046
a2a4: 217832
b1a3: 198572
b1c3: 234656
b2b3: 215255
b2b4: 216145
c2c3: 222861
c2c4: 240082
d2d3: 328511
d2d4: 361790
e2e3: 402988
e2e4: 405385
f2f3: 178889
f2f4: 198473
g1f3: 233491
g1h3: 198502
g2g3: 217210
g2g4: 214048
h2h3: 181044
h2h4: 218829

Elapsed: 20 ms

Nodes searched: 4865609

[hgm]

In Linux I simply use the 'sort' uitility to sort all lines in a file alphabetically, and write them to another file. By making my engine print the moves in exactly the same format as the reference engine I can then do 'strobiscopic comparison' of the lists: I open both sorted files in an application that displays them in tabs (e.g. gedit or a web browser), scrol them such that I view exactly the smae part, and then alternate between the two by clicking the tabs. If they are identical, you see nothing happen on switching between them. But any difference shows up as a motion in the otherwise still picture, and since human brains process such things in parallel for an entire image at once, you can litterally compare the counts for hundreds of moves in a second or so to spot a single difference.

[benvining]

There's no reason to spend the effort verifying the results manually, these tests are quite easy to automate. See https://github.com/benthevining/BenBot/ ... ts/rampart and https://github.com/benthevining/BenBot/ ... ests/perft