reviving old c# codebase engine, 0x88

[spirch]

also, i saw your link in your signature, i don't know if you ever did a profiling run on your engine, here is one with peft 5

i don't know anything about the code but first thing i would say, remove the recursive call to perft, there is a cost there but you can also look at some hotspot and see if there anything to do there to optimize it

Thanks for taking the time to look into my code! Much appreciated. What tool are you using for the profiling?

I'm using Visual Studio IDE and of course I did a few profiling runs every now and then. That my perft runs only at 10M Nodes/s is not any fault of the C# language but comes down to a few design decisions motivated by my pledge to write code that's simple and easy to understand.

For example you may notice that CollectMoves takes twice as long as AddMoves. What *else* is it spending time on if not adding moves?? It's scanning the board looking for pieces of the active color. Piece lists could speed this up but other then speeding up the search it doesn't really *add* any value, it just makes things faster and more complicated. Also it would make the board instance "fatter" and I make a *lot* of copies of board instances. (Also visible in your profiler)

Your profiler doesn't add these values up but Consider is actually called on *each* pseudo-legal move to make sure it's legal. How do you make sure of that? You play the move and look if it puts your king in check. That's costly. You have to create a new Board instance (because I also didn't implement Undo for above state reasons) play the Move, scan the board for the king and test if the square he's on is attacked. Once you have that boolean result you let the Garbage Collector mop up the mess because there's a whole board instance created that noone needs anymore. Poor thing.

The garbage collector is good at it though. The process doesn't exceed 18MB of allocated memory. So it's not really a memory leak or anything, it's how C# is supposed to be used. 10M Nodes/s is nothing to brag about, though, and if you care about performance don't do it like me!

When I started I didn't know that the chess programming community would be so competitive about speed. I like it. But I won't try to optimize Minimal Chess retroactively for speed because there *is* a price to be paid for every optimization. It doesn't fit my vision for it. My next chess engine, if I stick with this surprisingly addictive hobby, will be more ambitious in that regard.

i'm using the tool DotTrace

i also use visual studio, still under .net framework, i should move to .net core one day

my "collectmoves" method are my "pseudoPiece" methods(these one take a from X and collect all the moves), the ".check." namespace/methods are the one that verify if the king is in check or not, the check method call the "legalmove" methods(these one take a from X to Y and make sure it's 100% valid)

while the perft is running, i create zero instance of anything on my side, i didn't go oriented object

I got a few helper array that I update while perft is running, i have one that know the position of each pieces so i don't need to loop through the board, i know where are the king, i know which piece could attack the kings

i should replace my pseudoPiece method with array that have pre-calculated move, that should speed up thing... hmm i might try that

[spirch]

how I currently check if a peusdo move is legal or not, i have 3 methods, this is the "generic" one, the other two are for king and pawn:

Code: Select all

        internal static bool Move(Board board, long PosFrom, long PosTo)
        {
           //some helper variable, not needed
            long[] SQ = board.SQ;
            long[] Check = board.Check;

            //get the king position from the array
            long k = board.KP[SQ[PosFrom] & Piece.Colors];

            //backup what is in the from / to square
            long backup = (SQ[PosFrom] << bit.PieceFromShift) |
                          (SQ[PosTo] << bit.PieceToShift);

            //do the actual move
            SQ[PosTo] = backup >> bit.PieceFromShift & bit.Piece; //faster to read the backup than reading the array
            SQ[PosFrom] = Piece.None;

           //for each piece that can attack my king
            for (long i = Check[0]; i > 0; --i)
            {
                // try to reach my king
                if (ChessEngine.Move.Legal(board, Check[i], k, true))
                {
                    //undo move
                    SQ[PosFrom] = backup >> bit.PieceFromShift & bit.Piece;
                    SQ[PosTo] = backup >> bit.PieceToShift & bit.Piece;
                    
                    //king got attacked, invalid move
                    return false;
                }
            }

            //undo move
            SQ[PosFrom] = backup >> bit.PieceFromShift & bit.Piece;
            SQ[PosTo] = backup >> bit.PieceToShift & bit.Piece;
            
            //king is safe, valid move
            return true;
        }

[mvanthoor]

visually this is how my perft work
...

But that is not breadth-first, it's still depth-first. But granted, you can change the algorithm to go depth-first too, without recursion. Only, in most programming languages this is slower, because you have to extend the list of moves you still have to search, either by sticking the next depth in front, or in the back.

[spirch]

visually this is how my perft work
...

But that is not breadth-first, it's still depth-first. But granted, you can change the algorithm to go depth-first too, without recursion. Only, in most programming languages this is slower, because you have to extend the list of moves you still have to search, either by sticking the next depth in front, or in the back.

I have an array of single dimension, initialized at 500 items (never crashed so far with out of bound), that I use to keep all moves from all depths, i pass it in my pseudo move method (array in c# are by reference)
the pseudo move just add at the end of the array
i have a int counter that know how many move are in the array, this one follow the array and get incremented by the pseudo move

in the perft, i loop/decrease until that counter == 0

pseudo code look like this

Code: Select all

        public static long StartFull(int d, Board b)
        {
            long[] moveList = new long[501];
            int cMoves = 0;
            
            {//first depth
                Move.Pseudo(moveList,cMoves)  //get new move
            }

            while (cMoves > 0)
            {
                // get the move

                move = moveList[cMoves]

                //do move
                cMoves = cMoves -1
                
                if //not last depth
                {
                    {// get move
                        Move.Pseudo(moveList, cMoves)  //get new move
                    }
                }
                else // last depth
                {
                    //count move
                }
            }
            
            //return total count
        }

[spirch]

so I finally removed something that was bothering me a lot

the UptCheck method(look at earlier screenshot of profiling), this one was expensive like hell

reminder, BEFORE

Code: Select all

  A B C D E F G H
1 R N B Q K B N R  Kind of perft: Full Perft
2 P P P P P P P P  Started 6 depths at 2021-03-06 00:11:17 finished at 2021-03-06 00:11:23
3 ■ ■ ■ ■ ■ ■ ■ ■  FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
4 ■ ■ ■ ■ ■ ■ ■ ■
5 ■ ■ ■ ■ ■ ■ ■ ■  Expected Moves   : 119,060,324
6 ■ ■ ■ ■ ■ ■ ■ ■  Total Moves Done : 119,060,324
7 p p p p p p p p  Time Taken       : 5,656ms
8 r n b q k b n r  Moves per second : 21,050,269

now this is what it look like

Code: Select all

  A B C D E F G H
1 R N B Q K B N R  Kind of perft: Full Perft
2 P P P P P P P P  Started 6 depths at 2021-03-22 23:22:36 finished at 2021-03-22 23:22:40
3 ■ ■ ■ ■ ■ ■ ■ ■  FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
4 ■ ■ ■ ■ ■ ■ ■ ■
5 ■ ■ ■ ■ ■ ■ ■ ■  Expected Moves   : 119,060,324
6 ■ ■ ■ ■ ■ ■ ■ ■  Total Moves Done : 119,060,324
7 p p p p p p p p  Time Taken       : 4,209ms
8 r n b q k b n r  Moves per second : 28,287,081

i call that a nice speed up, i can still optimize my changes but that is the first result of "after"

and this is multithreaded (12 core / 24 thread) (don't forget what i said earlier in this thread, this is a quick implementation so the speed is still not optimal, if i take the proper time it should add about 250 to 300m moves/sec)

Code: Select all

  A B C D E F G H
1 R N B Q K B N R  Kind of perft: Full Perft
2 P P P P P P P P  Started 6 depths at 2021-03-22 23:30:17 finished at 2021-03-22 23:30:17
3 ■ ■ ■ ■ ■ ■ ■ ■  FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
4 ■ ■ ■ ■ ■ ■ ■ ■
5 ■ ■ ■ ■ ■ ■ ■ ■  Expected Moves   : 119,060,324
6 ■ ■ ■ ■ ■ ■ ■ ■  Total Moves Done : 119,060,324
7 p p p p p p p p  Time Taken       : 312ms
8 r n b q k b n r  Moves per second : 381,603,602

[lithander]

Nice increase! ~30M Nodes/s... now I know what to aim for with the next engine, eh?^^

What did UptCheck do?

[spirch]

Nice increase! ~30M Nodes/s... now I know what to aim for with the next engine, eh?^^

What did UptCheck do?

i know perft speed is just for bragging right for some but i see this as my foundation of the engine, if it's slow, the overall engine will be slow and wont find good move fast enough

so...

it seem basic for some but that method was keeping a list of piece that could attack the king, this list is used to do legal move

it was resetting / re-scanning from scratch on every move

my changes, it's now an incremental updates, on a move / unmove, it only check what changed on the board and keep that list up to date

[hgm]

Making the pin test incremental is something I never considered before, but it seems a good idea, and easy enough. What I normally do is run through the slider section of the piece list, and test for alignment with the enemy King through the relative location to it. But similar to NNUE update, the set of pieces that test positive on this can easily be kept track of incrementally, as long as the King doesn't move. Just do the alignment test only on the piece you move in its new location, and use the result to set or clear a bit in a word where each bit corresponds to a slider, or a specific move direction of a slider. (With Q + 2R + 2B you would have 24 such move directions; with a 32-bit int for this you can even accomodate a super-numerary Queen.)

Instead of running through all sliders for testing whether these are present and aligned, you would then simply extract bits from the aligned set, and a thus recovered bit number would give you the step in that direction from a table.

Only on the occasional King move you would have to re-examine all slider alignments with the new King location. But that is not more work than what you would otherwise do in every node.

[Edit] The aligned[] table elements could have the same format as the set of aligned piece-direction combinations. Each piece could then have a mask associated with it (in the piece list) to indicate the piece-direction bits that belong to it. The incremental update would then be

alignedSet &= ~sliderMask[piece];
alignedSet |= sliderMask[piece] & aligned[toSqr - location[opponent+KING]];

[spirch]

Only on the occasional King move you would have to re-examine all slider alignments with the new King location. But that is not more work than what you would otherwise do in every node.

yes, when the king move, i use what i had before on the opposite side

but i do also incremental when it's a castle, the rook could now attack the opposite king

so;
if white turn, king move, scan all black piece to see if they can reach white king new position
and if castle, check if white rook can reach black king

[spirch]

[Edit] The aligned[] table elements could have the same format as the set of aligned piece-direction combinations. Each piece could then have a mask associated with it (in the piece list) to indicate the piece-direction bits that belong to it. The incremental update would then be

alignedSet &= ~sliderMask[piece];
alignedSet |= sliderMask[piece] & aligned[toSqr - location[opponent+KING]];

can you tell what kind of % speed increase you got with your engine? if any