Sorting ulong moves based on their score

[eligolf]

Hi,

I have gotten into the part of scoring/sorting moves and I find that with the approach of having the move as a ulong it makes it very consuming to score and sort the moves. It gives barely no difference in speed, when it gave wonders in speed when I didn't use bitboards in my previous engine.

The approach of sorting is something like this at the moment, taken basically straight from my previous engine:

Code: Select all

private static List<ulong> SortMoves(int ply, List<ulong> moves)
        {
            // Assign a score to each move
            List<int> scoreList = new List<int>();
            foreach (ulong move in moves)
            {
                scoreList.Add(ScoreMove(ply, move));
            }

            // Sort the moves based on their score
            List<ulong> sortedMoves = moves.Zip(scoreList,
                                      (move, score) => (Move: move, Score: score))
                                      .OrderByDescending(move => move.Score)
                                      .Select(move => move.Move)
                                      .ToList();

            // Return the new list of moves
            return sortedMoves;
        }        

        private static int ScoreMove(int ply, ulong move)
        {
            // PV scoring if allowed
            if (scorePV)
            {
                // Make sure we have a PV move
                if (pvTable[0][ply] == move)
                {
                    // Disable PV flag and return the PV score
                    scorePV = false;
                    return SearchConstants.pvScore;
                }
            }

            // Capture moves (or enpassants)
            if (Move.IsCapture((int)Move.GetMoveFlag(move)) || Move.IsEnPassant((int)Move.GetMoveFlag(move)))
            {
                int _pieceCaptured = -1;
                if (Move.IsEnPassant((int)Move.GetMoveFlag(move)))
                {
                    _pieceCaptured = Piece.Pawn;
                }
                else
                {
                    // Loop over other sides bitboards to find the piece
                    int toSquare = (int)Move.GetToSquare(move);
                    for (int piece = Piece.Pawn; piece <= Piece.King; piece++)
                    {
                        if (BitOperations.GetBit(boardState.Pieces[Color.Invert(boardState.ColorToMove)][piece], toSquare) != 0)
                        {
                            _pieceCaptured = piece;
                            break;
                        }
                    }
                }

                return SearchConstants.MVV_LVA + 
                       SearchConstants.MVV_LVA_Values[_pieceCaptured] -
                       SearchConstants.MVV_LVA_Values[(int)Move.GetPieceMoved(move)];
            }
            // Quiet moves
            else
            {
                // Killer move 1 or 2, else return the history move
                if (killerMoves[0][ply] == move) return SearchConstants.firstKillerMove;
                else if (killerMoves[1][ply] == move) return SearchConstants.secondKilleRMove;
                else return historyMoves[(int)Move.GetPieceMoved(move)][(int)Move.GetToSquare(move)];

            }

If needed, this is how I store the different moves in my Negamax loop:

Code: Select all

private static float Negamax(int depth, int ply, float alpha, float beta)
        {
            float score;
            bool foundPV = false;

            // Init PV
            pvTable[ply][ply] = 0ul;
            pvLength[ply] = 0;

            // Find if it is a 3 fold repetition
            if (boardState.CheckForDraw()) return 0;

            // Check if we reached depth 0
            if (depth == 0)
            {
                score = Evaluate.EvaluateOnlyMaterial(boardState);
                return score;
            }

            // Get legal moves
            boardState.GetAllMoves();
            List<ulong> children = new List<ulong>(boardState.PossibleMoves);

            // Sort moves
            children = SortMoves(ply, children);

            // If we are following PV line we want to enable PV scoring
            if (followPV) EnablePVScoring(ply, children);

            // Init number of legal moves and moves searched
            int legalMoves = 0;

            // Negamax loop
            foreach (ulong move in children)
            {
                // Try if move is legal
                if (boardState.MakeMove(move))
                {
                    // Increase legal moves and node count
                    legalMoves++;
                    nodes++;

                    // Do a normal search
                    score = -Negamax(depth - 1, ply + 1, -beta, -alpha);

                    // Unmake the move
                    boardState.UnmakeMove(move);

                    // Found a better move
                    if (score > alpha)
                    {
                        foundPV = true;
                        alpha = score;

                        // History moves (non capturing and not enpassant)
                        if (!Move.IsCapture((int)Move.GetMoveFlag(move)) && !Move.IsEnPassant((int)Move.GetMoveFlag(move)))
                        {
                            historyMoves[(int)Move.GetPieceMoved(move)][(int)Move.GetToSquare(move)] += depth;
                        }

                        // Write PV move to PV table for the given ply
                        pvTable[ply][ply] = move;

                        // Loop over the next ply
                        for (int i = 0; i < pvLength[ply + 1]; i++)
                        {
                            // Copy move from deeper ply into current ply's line
                            pvTable[ply][ply + 1 + i] = pvTable[ply + 1][ply + 1 + i];
                        }

                        // Adjust PV lenght
                        pvLength[ply] = 1 + pvLength[ply + 1];

                        // Fail hard beta cutoff (node fails high)
                        if (score >= beta)
                        {
                            // Store killer moves (non capturing and not enpassant)
                            if (!Move.IsCapture((int)Move.GetMoveFlag(move)) && !Move.IsEnPassant((int)Move.GetMoveFlag(move)))
                            {
                                killerMoves[1][ply] = killerMoves[0][ply];
                                killerMoves[0][ply] = move;
                            }

                            return beta;
                        }
                    }
                }                
            }

I think what is taking time is I create a separate list of the scores, then sort the moves list based on the values in the scores list. When I had my moves as a Class I could just save the score values and sort the list without creating a separate list.

Another thing is on all the places where I need to check if the move is capture or enpassant. Also I need to loop over the enemy bitboards to find the captured piece since I don't store this either somewhere.

I am a bit stuck on how to do the sorting the fastest way possible. Any general ideas or inspiration that you can give me? How to think of scoring/sorting moves when they are represented as a ulong?

[lithander]

I am a bit stuck on how to do the sorting the fastest way possible. Any general ideas or inspiration that you can give me? How to think of scoring/sorting moves when they are represented as a ulong?

Code: Select all

            // Sort the moves based on their score
            List<ulong> sortedMoves = moves.Zip(scoreList,
                                      (move, score) => (Move: move, Score: score))
                                      .OrderByDescending(move => move.Score)
                                      .Select(move => move.Move)
                                      .ToList();

If you would look at this on the IL level or at the machine code level you'd realize that there is an incredible amount of overhead here. Lot's of dynamic allocations. Any efficiency that you might get from encoding all data in just one ulong is going to drown in the noise form invoking LINQ, creating iterators, invoking delegates and just doing a dozen method calls where Ideally you'd invoke none.

If you want to stick to ideomatic C# code and OOP you can try a special struct that combines the Move (ulong) and the Score (int) and implements an IComparable interface like this:

Code: Select all

    public struct SortedMove : IComparable<SortedMove>
    {
        public int Score;
        public ulong Move;
        public int CompareTo(SortedMove other) => other.Score.CompareTo(Score);
        public static implicit operator Move(SortedMove m) => m.Move;
    }

Now you can just stuff that into a list and call the List's Sort() method. That should already help some.

Another realization that many chess programmers have had is that you don't really need all your moves sorted in perfect order as usually you are only going to play the first couple of moves before receiving a cut-off. This is why many will use lazy sorting wich means just extract the best move one at a time and leave the rest in unsorted order.

[eligolf]

Thanks, just the answer I was hoping for It seems to store it in a struct is slower (the way I implemented it at least), but I found another solution that worked faster:

Code: Select all

            ulong[] movesArray = moves.ToArray();
            Array.Sort(scoreList, movesArray, Comparer<int>.Create((a, b) => b.CompareTo(a)));
            List<ulong> movesTest = movesArray.ToList();

Maybe I should keep all the lists as arrays instead to make everything faster.

[lithander]

Maybe I should keep all the lists as arrays instead to make everything faster.

That's what I do in Leorik. There are no dynamic allocations during search!

[dangi12012]

Thanks, just the answer I was hoping for It seems to store it in a struct is slower (the way I implemented it at least), but I found another solution that worked faster:

Code: Select all

            ulong[] movesArray = moves.ToArray();
            Array.Sort(scoreList, movesArray, Comparer<int>.Create((a, b) => b.CompareTo(a)));
            List<ulong> movesTest = movesArray.ToList();

Maybe I should keep all the lists as arrays instead to make everything faster.

You should have literally no allocations ever - except the first TT setup.
Heap allocation is also expensive when everything else is optimized.

If you have recursion you can also tranform things to a loop where the "stack" is just a pointer in an array with your local vars.
Keep in mind that twice the speed is like transforming your quadcore into a octacore cpu for free. Probably even slightly better.

What I can see in your code is List->Array->List. Just have an array to begin with and never resize it.

[eligolf]

Yes, I think it is good to change things like this early.
So when getting all possible moves I do something like this?

Code: Select all

ulong possibleMoves = new ulong[256];
int movesAdded = 0;

// if finding move....
possibleMoves[movesAdded] = newMove;
movesAdded++;

Sorry about all these newbie questions, I am not a very good C# programmer, I am so used to Python
And how do I loop through this list in Negamax? I don't want to loop over all possible moves that are 256 in this case, I only want to use the ones I added in the list.

[tcusr]

Yes, I think it is good to change things like this early.
So when getting all possible moves I do something like this?

Code: Select all

ulong possibleMoves = new ulong[256];
int movesAdded = 0;

// if finding move....
possibleMoves[movesAdded] = newMove;
movesAdded++;

Sorry about all these newbie questions, I am not a very good C# programmer, I am so used to Python
And how do I loop through this list in Negamax? I don't want to loop over all possible moves that are 256 in this case, I only want to use the ones I added in the list.

?

Code: Select all

for (int i = 0; i < movesAdded; ++i) {
   ulong m = possibleMoves[i];
}

[Mergi]

It is wasteful trying to sort the whole array, especially if you are not using staged move generator and/or generating a lot of pseudo-legal moves as well. Usually the preferred approach is to first generate the moves, then score them and finally when you need to pick the best move, you just go through the whole array and pick the one with the highest score and shift the last one to it's place. Depending on how many and how quickly you are able to cut nodes, you might be able to save a lot of time by not always sorting the whole array. Some kind of partial sort, when you are picking the best move, might also work well in some cases (it never did for me though).

[lithander]

Sorry about all these newbie questions, I am not a very good C# programmer, I am so used to Python

My two chess engines are both written in C# and the main difference is that the first time I was embracing C# as a managed language that put's a few abstraction layers between the programmer and the machine executing the code. You communicate intend and let the Runtime deal with the details. You use generic containers like List<T> and LINQ and iterator patterns and don't worry about dynamic allocations because there's a garbage collector to clean up after you.

But if you really care about the performance of your engine then you can also write code in C# that is fast. But that's a bit tricky tbh. You need to know a lot more about the details of the language and it's runtime. It also means that your C# code starts to look more and more like C. Without ever allowing you to fully close the performance gap to C/C++.

You are not a bad C# programmer if you chose not to do that. And if you really care about performance you could also consider just using C/C++ directly instead of C# because at that point almost all the advantages C# has are not advantages to you anymore.

[eligolf]

Thanks for the input, lots to consider. I do care about performance but I also want to understand what is going on. I know I won't make any competitive engine which is fine, I mostly want to have fun and learn more about C# and programming in general