Staged move generation

[eligolf]

The development of my C# engine has now come to a point where I would like to implement staged move generation. Well technically I have already separated move generation to captures and quiets which is simple enough, this to be able to use only captures in Q-search. What I would like to do now is to not generate all moves in Negamax but only the ones necessary before getting a cut off. So what I want is:

1. First don't generate any move and just try hash move if exists.
2. Generate all capture moves and sort them with MVA/LVV (later maybe SEE and only the winning captures here) and try them all.
3. Try if we have first or second killer move and try them.
4. Generate all quiet moves and sort them according to my history heuristics (maybe later something smarter)

The problem is I have no clue how to implement this in my current framework. I have tried to search for examples but it is very hard to find any literature or posts about it. Very simplified I use code such as this now:

Code: Select all

public Move IterativeDeepening()
        { 
            // Reset killer, history, and PV collecting tables
            ResetSortingTables();
            ResetPVTables();
            
            for (int depth = 1; depth <= _maxDepth; depth++)
            {
                int score = Negamax(depth, ply, alpha, beta, true);
               
                if (!stopSearch)
                {                               
                    bestMove = pvTable[0][0];

                }
            }
            return bestMove;
        }        
        
private int Negamax(int depth, int ply, int alpha, int beta, bool nullMoveAllowed)
        {
            // Init variables
            int score;            
            Move _bestMove = Move.Empty;

            if (depth == 0)
            {
                score = QuiescenceSearch(ply, alpha, beta);
                return score;
            }
           
            if (boardState.CheckForDraw()) return 0;

           // Init PV table
            pvTable[ply][ply] = Move.Empty;
            pvLength[ply] = 0;

            // TT lookup
            if (Transpositions.ReadTT(boardState.ZobristKey, depth, ply, alpha, beta, out _bestMove, out int _score))
            {
                if (!isPV && ply != 0)
                {
                    return _score;
                }
            }
          
            // Move generation and sorting
            Move[] children = boardState.GetAllMoves();
            
            if (followPV) EnablePVScoring(ply, children);
            SortMoves(ply, children, _bestMove);

            // Loop through all moves
            int legalMoves = 0;
            foreach (Move move in children)
            {                            

               // Check if move is legal
                if (move == Move.Empty) break;
                if (!boardState.MakeMove(move)) continue;                

                legalMoves++;

               // PVS search
                if (foundPV)
                {
                    score = -Negamax(depth - 1, ply + 1, -alpha - 1, -alpha, true);
                    if ((score > alpha) && (score < beta))
                    {
                        score = -Negamax(depth - 1, ply + 1, -beta, -alpha, true);
                    }
                }
                else
                {
                    score = -Negamax(depth - 1, ply + 1, -beta, -alpha, true);
                }                

                // Unmake the move
                boardState.UnmakeMove(move);
              
                if (score > alpha)
                {
                    // Update variables
                    foundPV = true;
                    alpha = score;
                    _bestMove = move;

                    // Store history moves
                    if (!MoveFunctions.IsCapture(move.flag))
                    {
                        historyMoves[move.pieceMoved][move.toSquare] += depth;
                    }

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

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

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

                    // Fail hard beta cutoff (node fails high)
                    if (score >= beta)
                    {
                        // Store transposition tabel entry with score = beta
                        Transpositions.WriteTT(boardState.ZobristKey, depth, ply, alpha, beta, beta, _bestMove);

                        // Store killer moves
                        if (!MoveFunctions.IsCapture(move.flag))
                        {
                            killerMoves[1][ply] = killerMoves[0][ply];
                            killerMoves[0][ply] = move;
                        }

                        return beta;
                    }
                }              
            }

            // Check if we had any legal moves
            if (legalMoves == 0)
            {
                if (isInCheck)
                {
                    return -SearchConstants.mateValue + ply;
                }
                else
                {
                    return 0;
                }
            }

            // Write to transposition table wih score = alpha
            Transpositions.WriteTT(boardState.ZobristKey, depth, ply, alpha, beta, alpha, _bestMove);

            // Node fails low
            return alpha;
        }           
      

How would I set up a framework to test according to my list above? I have no clue at all about the concept of this so I am grateful for any guidance I know I can check if I have a has move and then test it, but how to know if that caused a cut and that I don't need to generate captures etc? Do I need to rebuild my "standard" negamax layout for this?

[lithander]

I have implemented that in C# in three different ways:

1.) The simple and stupid solution. Just do seperate loops. Generate captures, loop over captures. Still here? (no beta cutoff) Generate quiets and loop over them.

Here's an example:
https://github.com/lithander/Leorik/blo ... eSearch.cs
Look at the Evaluate() method

2.) Use a C#'s iterator feature to write a move generator that generates moves in distinct stages but when invoked you get to iterate over all the results in one big loop. The client does not know where one stage ends and the next starts. So it's convenient to use and still in order and you will pay only the price for the stages you have reached before cutoff.

Here's an example of such an iterator based staged move generator:
https://github.com/lithander/MinimalChe ... aymaker.cs
...and here is how it get's used in practice:
https://github.com/lithander/MinimalChe ... eSearch.cs

The iterator feature with the 'yield' keyword is very comfortable to use. But... there are runtime allocations so it's not the fastest implementation possible and that brings us to the most complicated solution:

3.) If you want maximum performance you can also implement something that behaves exactly like the iterator but without dynamic allocations.

Here's an example:
https://github.com/lithander/Leorik/blo ... eSearch.cs

Code: Select all

PlayState playState = InitPlay(ref moveGen, ref bestMove);
while (Play(ply, ref playState, ref moveGen))
{
                //Do search!

                if (score >= beta)
            
                    return beta;
}

The InitPlay creates a PlayState object that keeps track of the current state of the staged move generation process between calls to Play. Each time you call Play a new move is played so that afterwards you can search it. But the details of how that move is played depend on the values in the PlayState object.

Code: Select all

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private bool Play(int ply, ref PlayState state, ref MoveGen moveGen)
        {
            BoardState current = Positions[ply];
            BoardState next = Positions[ply + 1];
            
            while(true)
            {
                if (state.Next == moveGen.Next)
                {
                    switch (state.Stage)
                    {
                        case Stage.New:
                            state.Next = moveGen.CollectCaptures(current);
                            state.Stage = Stage.Captures;
                            continue;
                        case Stage.Captures:
                            state.Next = moveGen.CollectPlayableKillers(current, _killers.GetSpan(ply));
                            state.Stage = Stage.Killers;
                            continue;
                        case Stage.Killers:
                            state.Next = moveGen.CollectQuiets(current);
                            state.Stage = Stage.Quiets;
                            continue;
                        case Stage.Quiets:
                            return false;
                    }
                }

                if (state.Stage == Stage.Captures)
                    PickBestMove(state.Next, moveGen.Next);

                if (next.Play(current, ref Moves[state.Next++]))
                {
                    state.PlayedMoves++;
                    return true;
                }
            }
        }

If you have already generated quite moves and you still haven't played them all the call to Play() does only this part:

Code: Select all

                if (next.Play(current, ref Moves[state.Next++]))
                {
                    state.PlayedMoves++;
                    return true;
                }

But if you are in the capture stage then also the best next move is picked. And if you have run out of moves in one stage the next stage is invoked.


I like this solution a lot because it encapsulates all the details from the search well AND it's fast and allocation free. But it took me a night of hard concentration to implement it and that's *after* I had all the previous solutions already working and understood. I suggest you only use code in your engine that you can come up with and write yourself otherwise debugging of your engine is going to be hell at some point. Rather write something simple than something buggy I'd say.

[tcusr]

imo you shouldn't worry about it until later on, it's much work for not so much elo.
there are even 3000+ engines that don't use it (like demolito)

if you really want it though a common approach is use a big switch and handle the stages in there, e.g. https://github.com/TerjeKir/weiss/blob/ ... cker.c#L74

[mvanthoor]

I have implemented that in C# in three different ways:

Maybe this is exactly what you did (I don't read C# very well yet), but I implement to just do something like this:

Code: Select all

for s in stages {
    match s {
        Stage::TTMOVE => { create move list with only tt move }
        Stage::Captures => { create move list with Captures }
        ... and so on
    }
    
    for m in moves.iter() {
        // Existing search here
        
        // One change: make sure moves that were tried are passed
        // in a "skip-list" to pick_move(); for example, the TT_move
        // could be generated in the captures list, so it doesn't
        // need to be searched.
        
        if score >= beta { return beta; }
    }
}

[eligolf]

I have implemented that in C# in three different ways:

Maybe this is exactly what you did (I don't read C# very well yet), but I implement to just do something like this:

Code: Select all

for s in stages {
    match s {
        Stage::TTMOVE => { create move list with only tt move }
        Stage::Captures => { create move list with Captures }
        ... and so on
    }
    
    for m in moves.iter() {
        // Existing search here
        
        // One change: make sure moves that were tried are passed
        // in a "skip-list" to pick_move(); for example, the TT_move
        // could be generated in the captures list, so it doesn't
        // need to be searched.
        
        if score >= beta { return beta; }
    }
}

I (think) I tried your solution since I am too dumb to understand what is going on in Leorik This however slowed down my code significantly which is strange. I used exactly the same as before but right before the moves loop I made another loop with stages and then put the move loop inside this one. I also check if I have the _bestMove (TT move) when I am not checking for that and same for killer moves. Something like this:

Code: Select all

            int legalMoves = 0;

            for (int stage = 0; stage < 4; stage++)
            {
                Move[] children;

                // TT
                if (stage == 0)
                {
                    if (_bestMove == Move.Empty) continue;
                    children = new Move[] { _bestMove };
                }
                // Captures
                else if (stage == 1)
                {
                    children = boardState.GetCaptureMoves(true);
                    SortCaptureMoves(children);
                }
                // Killers
                else if (stage == 2)
                {
                    children = new Move[] { killerMoves[0][ply], killerMoves[1][ply] };
                }
                // Quiet
                else
                {
                    children = boardState.GetQuietMoves(true);
                    SortQuietMoves(ply, children);
                }

                // Loop through the moves
                foreach (Move move in children)
                {
                    //  Check for move legality
                    if (move == Move.Empty) break; // End of moves list
                    if (stage != 0 && move == _bestMove) continue;
                    if (stage != 2 && move == killerMoves[0][ply]) continue;
                    if (stage != 2 && move == killerMoves[1][ply]) continue;

                    // Try if move is legal and not makes us end up in check. 
                    if (!boardState.MakeMove(move)) continue;
                    
                    // .... Normal negamax just as before after here ...

It also gives me errors in some positions which is strange. I have no clue what is going on

[mvanthoor]

It also gives me errors in some positions which is strange. I have no clue what is going on

Staged move generation will be in version 5 of my engine (next version is 4, right now). Maybe I'll write the staged move generation a bit early, because I'm not going to touch the alpha/beta-function in version 4. I'm curious to see what happens. It would slow the code a bit because of the match statement, but the savings of moves not being generated should more than compensate for that.

Dit you take into account what I wrote about skipping moves? If your TT move is a capture but does NOT generate a cutoff for some reason, you will search the move again in the capture stage. If the killers don't generate a cutoff, they will be searched AGAIN in the quiet section. That WILL slow down your code; your stages can cause the engine to search some moves twice. (And come to the conclusion that they don't cause a cutoff; twice.)

If you search the killers, first do a check:
- piece in the killer move is the piece on the square
- the to-square does not have a friendly piece

A killer move is a move that "kills" opponent replies on the same depth. It is not linked to a specific position, so it is not guaranteed to be available for every position. You'll have to check if the move can actually be played.

[lithander]

If the killers don't generate a cutoff, they will be searched AGAIN in the quiet section. That WILL slow down your code; your stages can cause the engine to search some moves twice. (And come to the conclusion that they don't cause a cutoff; twice.)

2nd time they should be in the TT though!

[Pio]

If the killers don't generate a cutoff, they will be searched AGAIN in the quiet section. That WILL slow down your code; your stages can cause the engine to search some moves twice. (And come to the conclusion that they don't cause a cutoff; twice.)

2nd time they should be in the TT though!

Only if the TT is big enough. For TT sizes smaller than the search tree, it should be much better to check that you have not already searched the moves.

[eligolf]

I can get it to work if I just use capture and then non capture moves with the following general code structure:

Code: Select all

private int Negamax(....)

	    // Generate captures
            moves = boardState.GetCaptureMoves(true);
            moves = ScoreCaptureMoves(moves);
            moveCount = moves.Length;
            hasGeneratedAttacks = true;

            // If no attacks, generate quiets instead
            if (moveCount == 0)
            {
                moves = boardState.GetQuietMoves(true);
                moves = ScoreQuietMoves(ply, moves);
                moveCount = moves.Length;
                hasGeneratedQuiets = true;
            }

            for (int moveIndex = 0; moveIndex < moveCount; moveIndex++)
            {
                // Get the next best move in line and place it first
                SortNextMove(moves, moveCount, moveIndex);
                Move move = moves[moveIndex];

                // Check if move is legal
                if (boardState.MakeMove(move))  
                {
                    // Make, negamax, unmake etc here
                }                  

                // No more moves of the current type, check for quiets and restart loop
                if (moveIndex >= moveCount - 1 && !hasGeneratedQuiets)
                {
                    moves = boardState.GetQuietMoves(true);
                    moves = ScoreQuietMoves(ply, moves);
                    moveCount = moves.Length;
                    hasGeneratedQuiets = true;
                    moveIndex = -1;
                }          
            }
                      
            if (legalMoves == 0)
            {
                if (isInCheck)
                {
                    return -SearchConstants.mateValue + ply;
                }
                else
                {
                    return 0;
                }
            }

            // Write to transposition table wih score = alpha
            Transpositions.WriteTT(boardState.ZobristKey, depth, ply, alpha, beta, alpha, hashMove);

            return alpha;
        }

But as soon as I try to add the hashMove to the mix I get errors:

Code: Select all

        private int Negamax()
        {
            // Init variables
            Move hashMove;        

            // -------------------------------------------------------------
            //                      TT lookup
            // -------------------------------------------------------------
            // TT lookup (not in PV nodes, not when ply == 0 and not when we don't have an entry)
            if (Transpositions.ReadTT(boardState.ZobristKey, depth, ply, alpha, beta, out hashMove, out int _score))
            {
                if (!isPV && ply != 0)
                {
                    // Give history bonus to TT move if giving beta cutoff and if 
                    // it is not a capturing move.
                    if (_score >= beta && !MoveFunctions.IsCapture(hashMove.flag))
                    {
                        historyMoves[hashMove.pieceMoved][hashMove.toSquare] += depth;
                    }

                    return _score;
                }
            }

            // Move generation
            Move[] moves;
            int legalMoves = 0;
            bool hasGeneratedAttacks = false;
            bool hasGeneratedQuiets = false;
            int moveCount;

            // Check if we don't have a hash move, if so just generated the capture moves
            if (hashMove == Move.Empty)
            {
                moves = boardState.GetCaptureMoves(true);
                moves = ScoreCaptureMoves(moves);
                moveCount = moves.Length;
                hasGeneratedAttacks = true;

                // If no capture moves available, generate quiet moves
                if (moveCount == 0)
                {
                    moves = boardState.GetQuietMoves(true);
                    moves = ScoreQuietMoves(ply, moves);
                    moveCount = moves.Length;
                    hasGeneratedQuiets = true;
                }
            }
            else
            {
                moves = new Move[1] { hashMove };
                moveCount = 1;
            }           

            for (int moveIndex = 0; moveIndex < moveCount; moveIndex++)
            {
                // Get the next best move in line and place it first
                SortNextMove(moves, moveCount, moveIndex);
                Move move = moves[moveIndex];

                // If we are searching none hash moves and we find hash move again, skip it
                if (hasGeneratedAttacks && move == hashMove)
                {
                    goto EndOfLoopChecks;
                }

                // Check for legal move
                if (boardState.MakeMove(move))  
                {
                   // make, negamax, unmake etc
                }                  

            EndOfLoopChecks:

                // If searching hash move and attacks are not yet generated, then generate and restart loop
                if (!hasGeneratedAttacks)
                {
                    moves = boardState.GetCaptureMoves(true);
                    moves = ScoreCaptureMoves(moves);
                    moveCount = moves.Length;
                    moveIndex = -1;
                    hasGeneratedAttacks = true;

                    // If no attacks, generate quiets straight away
                    if (moveCount == 0)
                    {
                        moves = boardState.GetQuietMoves(true);
                        moves = ScoreQuietMoves(ply, moves);
                        moveCount = moves.Length;
                        hasGeneratedQuiets = true;
                    }
                }
            // If we ran out of moves and has generated attacks but not yet quiet moves, then generate quiets and restart loop
                if (moveIndex >= moveCount - 1 && hasGeneratedAttacks && !hasGeneratedQuiets)
                {
                    moves = boardState.GetQuietMoves(true);
                    moves = ScoreQuietMoves(ply, moves);
                    moveCount = moves.Length;
                    hasGeneratedQuiets = true;
                    moveIndex = -1;
                }          
            }

            if (legalMoves == 0)
            {
                if (isInCheck)
                {
                    return -SearchConstants.mateValue + ply;
                }
                else
                {
                    return 0;
                }
            }
            // -------------------------------------------------------------

            // Write to transposition table wih score = alpha
            Transpositions.WriteTT(boardState.ZobristKey, depth, ply, alpha, beta, alpha, hashMove);

            return alpha;
        }

Any ideas why this would fail? Am I thinking something wrong here?

[mvanthoor]

Any ideas why this would fail? Am I thinking something wrong here?

I've seen messages that the hash move also needs to be checked for validity.

I've always found that a bit strange, because the hash move was played in a certain position, and and saved with that position; so if it was valid when it was saved, it should be valid when retrieved. I could be wrong though, that there's some finesse I (yet) don't know about.

But... there are positions that don't give you a hash move. (If I remember correctly, those are the positions which evaluation doesn't even get to alpha during the search; the ones between alpha and beta are PV nodes, and the ones from beta and up are cut nodes, and both should give you a hash move.) Do you check if you actually _HAVE_ a hash move before you try to play it?

edit: seems you do; at least as far as I understand. You check if you _don't_ have a TT-move and then jump to the captures instead of checking if you _do_ have a hash move. Personally I prefer to put the "what to do if..." in the first part of the "if" if possible.