Weird perft logic

[Sven]

So as not to completely lose my sanity, I started over using C# (and even got it to look not too ugly):

Code: Select all

        ulong Perft(Move* start, int depth)
        {
            Move* end = start;
            if (!AddMoves(ref end))
                return 0;
            if (depth == 0)
                return 1;
            ulong count = 0;
            for (Move* curr = start; curr != end; ++curr)
            {
                Make(*curr);
                count += Perft(end, depth - 1);
                Unmake(*curr);
            }
            return count;
        }

That works, but is obviously very slow.

However, as soon as I try to do it by the book (see? I even named the function the same!):

Code: Select all

        ulong Perft(Move* start, int depth)
        {
            Move* end = start;
            if (depth == 0)
                return 1;
            AddMoves(ref end);
            ulong count = 0;
            for (Move* curr = start; curr != end; ++curr)
            {
                Make(*curr);
                if (!IsInCheck())
                    count += Perft(end, depth - 1);
                Unmake(*curr);
            }
            return count;
        }

I am again getting perft(3) = 8890.

Is AddMoves() still based on the "king capture" principle? It seems so in the upper code snippet but not in the lower one ...

And again: perft(3) = 8890 looks pretty much like you are missing bishop captures ...

1.e4 a6 2.Bxa6
1.e4 Na6 Bxa6
1.e4 b5 2.Bxb5
1.d4 h6 2.Bxh6
1.d4 Nh6 2.Bxh6
1.d4 g5 2.Bxg5
and the same for 1.e3/1.d3 ... 8902 - 8890 = 12 ...

[leanchess]

Is AddMoves() still based on the "king capture" principle? It seems so in the upper code snippet but not in the lower one ...

I believe that shouldn't make a difference, since at the top level the move is legal, and IsInCheck() takes care of the rest.

And again: perft(3) = 8890 looks pretty much like you are missing bishop captures ...

1.e4 a6 2.Bxa6
1.e4 Na6 Bxa6
1.e4 b5 2.Bxb5
1.d4 h6 2.Bxh6
1.d4 Nh6 2.Bxh6
1.d4 g5 2.Bxg5
and the same for 1.e3/1.d3 ... 8902 - 8890 = 12 ...

All sliders in my code are the same, so that shouldn't be a problem (and it works fine without the check check).

P.S. I let it run in the first config and got perft(6)=119060538...

[Sven]

Is AddMoves() still based on the "king capture" principle? It seems so in the upper code snippet but not in the lower one ...

I believe that shouldn't make a difference, since at the top level the move is legal, and IsInCheck() takes care of the rest.

I already wrote that you should start with a correct perft() function. That might make no difference for perft(3), right, but it will do so for higher depths. Furthermore you are wrong: your IsInCheck() tests the current move in the loop for legality but not the previous move (that would be found as illegal by finding a king capture in AddMoves()). In a king-capture algorithm you do not check the current move for legality within the move loop.

So who is in check if your IsInCheck() returns true?

And again: perft(3) = 8890 looks pretty much like you are missing bishop captures ...

1.e4 a6 2.Bxa6
1.e4 Na6 Bxa6
1.e4 b5 2.Bxb5
1.d4 h6 2.Bxh6
1.d4 Nh6 2.Bxh6
1.d4 g5 2.Bxg5
and the same for 1.e3/1.d3 ... 8902 - 8890 = 12 ...

All sliders in my code are the same, so that shouldn't be a problem (and it works fine without the check check).

P.S. I let it run in the first config and got perft(6)=119060538...

"That shouldn't ..." sounds nice but you don't find the root cause of your problem by discussing ... Furthermore, I would not care about perft(6) while perft(3) is wrong.

[Sven]

Dmitry, please check your PM.

[leanchess]

Thanks to all your help, my final perft in C#:

Code: Select all

        private ulong Perft(Piece* board, Piece* pieces, Move* start, int depth)
        {
            Move* end = start;
            ulong count = 0;
            Color color = PlayerColor;
            AddMoves(board, pieces, OpponentColor, ref end);
            for (Move* curr = start; curr != end; ++curr)
            {
                Make(board, pieces, *curr);
                if (!IsInCheck(board, pieces, color))
                    count += depth > 1
                        ? Perft(board, pieces, end, depth - 1)
                        : 1;
                Unmake(board, pieces, *curr);
            }
            return count;
        }

0x88 board, 2x24 piece lists, no bounds checking. perft(5) takes almost a second (on a laptop, but still).

I'm using the latest and greatest .NET 6. Any ideas how to make it faster?

Edit: The depth was off by 1; fixed.

[mvanthoor]

I'm using the latest and greatest .NET 6. Any ideas how to make it faster?

Assuming you are using Visual Studio: run the profiler and try to improve the slowest part of the code. Test again... it should be faster. Run the profiler again and improve the next slowest part of the code (assuming the part you just improved is not the slowest anymore). Rinse, repeat.

Avoid memory allocations in the search. If you can, don't initialize the move list with zero's when you create the list, because on the next line you'll put moves in it. (This tiny tweak caused my engine to become 4x faster. In Rust, it requires a few lines of unsafe code. I don't know how you'd do this in C#.)

[leanchess]

As it turned out, I missed the bounds checking in vectors. Updated perft():

Code: Select all

        private ulong Perft(Piece* board, Piece* pieces, Vector* vectors, Move* start, int depth)
        {
            Move* end = start;
            ulong count = 0;
            Color color = PlayerColor;
            AddMoves(board, pieces, vectors, OpponentColor, ref end);
            for (Move* curr = start; curr != end; ++curr)
            {
                Make(board, pieces, *curr);
                if (!IsInCheck(board, pieces, vectors, color))
                    count += depth > 1
                        ? Perft(board, pieces, vectors, end, depth - 1)
                        : 1;
                Unmake(board, pieces, *curr);
            }
            return count;
        }

That sped it up, but not significantly...