chess engine: alpha beta pruning starts evaluating moves incorrectly

Question

I'm writing a simple chess engine in Go and have been running into some issues related to search. I'm currently using iterative deepening and alpha-beta search using the negamax pruning. My issue I think comes from alpha beta search.

For example, in the following position (engine trying to play black)

[FEN ""]
1. e4 a6 2. Bc4 a5 3. Qf3  

many moves lead to Scholar's mate. Putting this position into my engine like so

isready
readyok
position rnbqkbnr/1ppppppp/8/p7/2B1P3/5Q2/PPPP1PPP/RNB1K1NR b KQkq - 1 3

I get

info starting search at depth 1
info currmove a5a4 score 0 pv
info score cp 0 depth 1 nodes 1 pv a5a4
info currmove b7b6 score 0 pv
info currmove c7c6 score 0 pv
info currmove d7d6 score 0 pv
info currmove e7e6 score 0 pv
info currmove f7f6 score 0 pv
info currmove g7g6 score 0 pv
info currmove h7h6 score 0 pv
info currmove b7b5 score 0 pv
info currmove c7c5 score 0 pv
info currmove d7d5 score 0 pv
info currmove e7e5 score 0 pv
info currmove f7f5 score 0 pv
info currmove g7g5 score 0 pv
info currmove h7h5 score 0 pv
info currmove b8a6 score 0 pv
info currmove b8c6 score 0 pv
info currmove g8f6 score 0 pv
info currmove g8h6 score 0 pv
info currmove a8a6 score 0 pv
info currmove a8a7 score 0 pv
info score cp 0 depth 1 nodes 21 pv a5a4
info starting search at depth 2
info currmove a5a4 score -1 pv c4f7
info score cp -1 depth 2 nodes 64 pv a5a4 c4f7
info currmove b7b6 score -1 pv c4f7
info currmove c7c6 score -1 pv c4f7
info currmove d7d6 score -1 pv c4f7
info currmove e7e6 score -1 pv c4e6
info currmove f7f6 score -3 pv c4g8
info currmove g7g6 score -1 pv c4f7
info currmove h7h6 score -1 pv c4f7
info currmove b7b5 score -1 pv c4b5
info currmove c7c5 score -1 pv c4f7
info currmove d7d5 score -1 pv e4d5
info currmove e7e5 score -1 pv c4f7
info currmove f7f5 score -1 pv e4f5
info currmove g7g5 score -1 pv c4f7
info currmove h7h5 score -1 pv c4f7
info currmove b8a6 score -3 pv c4a6
info currmove b8c6 score -1 pv c4f7
info currmove g8f6 score -1 pv c4f7
info currmove g8h6 score -1 pv c4f7
info currmove a8a6 score -5 pv c4a6
info currmove a8a7 score -1 pv c4f7
info score cp -1 depth 2 nodes 605 pv a5a4 c4f7
info starting search at depth 3
info currmove a5a4 score -29997 pv c4f7
info score cp -29997 depth 3 nodes 708 pv a5a4 c4f7
info currmove b7b6 score -29997 pv c4f7
info currmove c7c6 score -29997 pv c4f7
info currmove d7d6 score -1 pv c4f7 e8d7
info score cp -1 depth 3 nodes 975 pv d7d6 c4f7 e8d7
info currmove e7e6 score 0 pv b2b3 a5a4
info score cp 0 depth 3 nodes 1133 pv e7e6 b2b3 a5a4
info currmove f7f6 score 0 pv a2a3 a5a4
info currmove g7g6 score 0 pv a2a3 a5a4
info currmove h7h6 score 0 pv a2a3 a5a4
info currmove b7b5 score 0 pv c4f1 a5a4
info currmove c7c5 score 0 pv a2a3 a5a4
info currmove d7d5 score 0 pv e4d5 d8d5
info currmove e7e5 score 0 pv b2b3 a5a4
info currmove f7f5 score 0 pv e4e5 a5a4
info currmove g7g5 score 0 pv a2a3 a5a4
info currmove h7h5 score 0 pv a2a3 a5a4
info currmove b8a6 score 0 pv a2a3 a5a4
info currmove b8c6 score 0 pv a2a3 a5a4
info currmove g8f6 score 0 pv e4e5 a5a4
info currmove g8h6 score 0 pv a2a3 a5a4
info currmove a8a6 score 0 pv a2a3 a5a4
info currmove a8a7 score 0 pv a2a3 a5a4
info score cp 0 depth 3 nodes 2275 pv e7e6 b2b3 a5a4
bestmove e7e6

Here something strange is going on because at the start of searching at depth 3, it correctly evaluates a5a4 as leading to checkmate. However, once it finds a move that avoids instant checkmate, in this case first identifying d7d6 and then e7e6, all further moves then have their score capped to the best move found so far. For example, a8a7, which leads to checkmate, is evaluated to have a score of 0. As far as I understand, although the alpha value stores the best value that we can guarantee, this shouldn't affect the evaluations of each move.

Things get stranger with even deeper searches. Here for example is the end of the search at depth 7:

info starting search at depth 7
info time 3000 ndes 3729598 nps 1243199 score 0
info time 4000 ndes 4916163 nps 1229040 score 0
info currmove a5a4 score -29997 pv c4f7
info score cp -29997 depth 7 nodes 5572093 pv a5a4 c4f7
info time 5000 ndes 6105741 nps 1221148 score 0
info time 6000 ndes 7218855 nps 1203142 score 3
info currmove b7b6 score -29997 pv c4f7
info time 7000 ndes 8430976 nps 1204425 score 0
info time 8000 ndes 9647996 nps 1205999 score -9
info time 9000 ndes 10866782 nps 1207420 score -1
info currmove c7c6 score -29995 pv c4e6 a5a4 e6f7
info score cp -29995 depth 7 nodes 12123230 pv c7c6 c4e6 a5a4 e6f7
info currmove d7d6 score 0 pv a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
info score cp 0 depth 7 nodes 12123237 pv d7d6 a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
info currmove e7e6 score 0 pv a2a3 a5a4 b2b3 e6e5 c2c3 b7b6
info currmove f7f6 score 0 pv a2a3 a5a4 b2b3 f6f5 c2c3 f5f4
info currmove g7g6 score 0 pv a2a3 a5a4 b2b3 g6g5 c2c3 g5g4
info currmove h7h6 score 0 pv a2a3 a5a4 b2b3 h6h5 c2c3 h5h4
info currmove b7b5 score 0 pv a2a3 a5a4 b2b3 b5b4 c2c3 c7c6
info currmove c7c5 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
info currmove d7d5 score 0 pv a2a3 a5a4 b2b3 d5d4 c2c3 d4d3
info currmove e7e5 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
info time 10000 ndes 12123300 nps 1212330 score 0
info currmove f7f5 score 0 pv a2a3 a5a4 b2b3 f5f4 c2c3 b7b6
info currmove g7g5 score 0 pv a2a3 a5a4 b2b3 g5g4 c2c3 g4g3
info currmove h7h5 score 0 pv a2a3 a5a4 b2b3 h5h4 c2c3 h4h3
info currmove b8a6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
info currmove b8c6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
info currmove g8f6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
info currmove g8h6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
info currmove a8a6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
info currmove a8a7 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
info score cp 0 depth 7 nodes 12123356 pv d7d6 a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
bestmove d7d6

Now all the outputted principle variations seem to just be in lexiographical order. I can't spot in my code where there might be an issue but am worried that I'm missing something obvious. My code is as follows:

func (s *AlphaBetaSearch) Root() error {
    var pv pvList      // Holds the principle variation
    var childPV pvList // Holds the principle variation of the position after the first move is made

    childPV.new()

    for request := range s.requests {
        pos := request.pos // Position we are searching

        s.startTime = time.Now()    // Record start time so we know to stop if time is up
        s.nextTime = time.Now()     // Record next time as a counter so we can periodically print information
        s.nodeCount = 0             // Record number of nodes so we can stop after searching a certain number of nodes
        s.options = request.options // Store options in the search struct so we don't have to explicitly pass around.
        s.options.Stop = false      // Make sure we don't stop straight away if we were told to stop previously

        // Keep track of the best move found so far. This is outside the loop so that we can return the best move found
        // if we are asked to stop searching at a particular depth.
        bestMove := position.NoMove

        // Generate legal moves and annotate them with the evaluation after they've taken place so we can improve
        // move ordering in the search.
        legalMoves := pos.MovesLegalWithEvaluation(position.EvalSimple)

        // For loop for iterative deepening
        for depth := uint(1); depth <= s.options.Depth; depth++ {
            // Sort legal moves by the evaluation calculated above
            legalMoves.Sort()

            // Best score for a move found so far
            bestScore := position.NoEval

            // Alpha and beta
            // Alpha here is the best score we can be guaranteed to achieve
            // Beta here is the best score the opposing player can achieve
            alpha, beta := position.MinEval, position.MaxEval

            for _, move := range legalMoves.AsSlice() {
                // Clear the child PV so it can be used again for this move
                childPV.clear()

                // Make move, evaluate score of this position, and then undo move.
                pos.MakeMove(move)
                score := -s.search(-beta, -alpha, depth-1, 1, &childPV, pos)
                pos.UndoMove(move)

                s.responses <- fmt.Sprintf("info currmove %s score %d pv %s", move.String(), score, childPV.String())

                // Store evaluation of this move so that on the next iteration the move ordering is more effective
                move.SetEval(position.ScoreFromPerspective(score, pos.SideToMove))

                // If this is the best move we've seen so far...
                if score > bestScore {
                    // Update bestScore to reflect this
                    bestScore = score

                    // Update the principle variation to use this move instead
                    pv.clear()
                    pv.catenate(move, &childPV)

                    // Record this as the best move
                    bestMove = move

                    // Set alpha to this score
                    alpha = score

                    s.responses <- fmt.Sprintf("info score cp %v depth %v nodes %v pv %s", bestScore, depth, s.nodeCount, pv.String())
                }
            }

            s.responses <- fmt.Sprintf("info score cp %v depth %v nodes %v pv %s", bestScore, depth, s.nodeCount, pv.String())
        }

        s.responses <- fmt.Sprintf("bestmove %s", bestMove.String())
    }

    return nil
}

func (s *AlphaBetaSearch) search(alpha int16, beta int16, depth uint, ply int, pv *pvList, pos *position.Position) int16 {
    s.nodeCount++

    // If we're at depth 0, stop recursing and instead return a static evaluation of this position.
    if depth <= 0 {
        return position.ScoreFromPerspective(position.EvalSimple(pos), pos.SideToMove) // TODO: make more customisable
    }

    // Clear the principle variation
    pv.clear()

    // Generate all legal moves in this position
    legalMoves := pos.MovesLegal()

    // Initialise bestMove and bestScore to hold the best move found so far.
    bestMove, bestScore := position.NoMove, position.NoEval

    // TODO: doesn't yet understand draw by threefold repetition

    var childPV pvList

    for _, move := range legalMoves.AsSlice() {
        childPV.clear()

        pos.MakeMove(move)
        score := -s.search(-beta, -alpha, depth-1, ply+1, &childPV, pos)
        pos.UndoMove(move)

        // If this is the best score we've found so far...
        if score > bestScore {
            // Update bestScore and bestMove to track this (might not need bestMove)
            bestScore = score
            bestMove = move
            _ = bestMove

            // Add this to the principle variation
            pv.catenate(move, &childPV)

            // Beta cutoff:
            // The opposing player can guarantee a better position for themselves, so there's no point pursuing this position.
            if score >= beta {
                return score
            }

            // If this is better than the best score we can guarantee so far, then update alpha to reflect this
            if score > alpha {
                alpha = score
            }

        }

        // Print info if required
        if time.Since(s.nextTime) >= time.Second {
            diff := time.Since(s.startTime)
            s.responses <- fmt.Sprintf("info time %v ndes %v nps %v score %d", diff.Milliseconds(), s.nodeCount, s.nodeCount/int(diff.Seconds()), bestScore)
            s.nextTime = time.Now()
        }

        // If required to stop early, return alpha since this is the best we can do.
        if s.options.Stop || time.Since(s.startTime) > s.options.MoveTime {
            return alpha
        }

    }

    // If we have no moves available, it's either checkmate or stalemate, so return values
    // that reflect this.
    if legalMoves.Len() == 0 {
        if pos.KingInCheck(pos.SideToMove) {
            // Checkmate
            return -30000 + int16(ply) + 1
        }

        // Stalemate
        return 0 // TODO: return contempt value instead?
    }

    return bestScore
}

Can anybody spot what might be the mistake here?

---

EDIT: Here's the evaluation logic:

const (
    MaxEval  int16 = 30_000
    MinEval  int16 = -MaxEval
    MateEval int16 = MaxEval + 1
    NoEval   int16 = MinEval - 1
)

// Evaluator decides the numerical value of a position.
// An int16 is used so that evaluations can be packed into moves compactly.
// TODO: Consider refactoring into seperate package
type Evaluator func(p *Position) int16

var EvaluatorInfo = map[string]Evaluator{
    "simple": EvalSimple,
}

// GetEvaluator looks up an evaluator by name.
func GetEvaluator(name string) Evaluator {
    return EvaluatorInfo[name]
}

// ScoreFromPerspective takes in a score where negative scores represent good positions for black and positive positions
// for white, and takes in a side to move, and returns a positive evaluation from their perspective.
func ScoreFromPerspective(score int16, sideToMove Color) int16 {
    if sideToMove == Black {
        return -score
    }

    return score
}

var simpleEvalTable = map[Piece]int16{
    Pawn:   1,
    Knight: 3,
    Bishop: 4,
    Rook:   5,
    Queen:  9,
    King:   1_000,
}

// EvalSimple evaluates the position using a simple material count.
// TODO: This could definitely be sped up by using bitboards instead of the pos.Squares.
func EvalSimple(pos *Position) int16 {
    overall := int16(0)

    for i := 0; i < 64; i++ {
        curr := pos.Squares[i]

        switch curr.Color() {
        case White:
            overall += simpleEvalTable[curr.Colorless()]
        case Black:
            overall -= simpleEvalTable[curr.Colorless()]
        }
    }

    return overall
}

and the movement code:

// MakeMove makes a move on the chess board, or returns an error if it is invalid.
// Bitboards for occupation and piece locations are updated through the setSquare function.
func (p *Position) MakeMove(m Move) bool {
    // Need to handle 6 special cases:
    // - White king moving
    // - Black king moving
    // (These two cases can move two pieces at once and disable castling)

    // - White rook moving
    // - Black rook moving
    // (These two cases mean some castling privileges may be lost)

    // - White pawn moving forward two squares onto an empty square
    // - Black pawn moving forward two squares onto an empty square
    // (These two cases either perform an en passant capture or set the en passant target square)

    movingPiece := p.Squares[m.From()]
    var newEnPassantTarget uint8 = NoEnPassant

    switch {
    case movingPiece == WhiteKing:
        // Disable any type of castling for the white king as they have moved.
        p.Castling.off(longW | shortW)

        // The king has moved two squares and so it is known they have castled.
        // Here we only need to worry about moving the rook, as the king is moved by the general code outside of the switch.
        if abs(int(m.From())-int(m.To())) == 2 {
            // Determine if they have castled long or short.
            if m.To() == SquareG1 { // Short castle
                p.setSquare(SquareF1, WhiteRook)
                p.setSquare(SquareH1, Empty)
            } else { // Long castle
                p.setSquare(SquareD1, WhiteRook)
                p.setSquare(SquareA1, Empty)
            }
        }
    case movingPiece == BlackKing:
        // Disable any type of castling for the black king as they have moved.
        p.Castling.off(longB | shortB)

        // The king has moved two squares and so it is known they have castled.
        // Here we only need to worry about moving the rook, as the king is moved by the general code outside of the switch.
        if abs(int(m.From())-int(m.To())) == 2 {
            // Determine if they have castled long or short.
            if m.To() == SquareG8 { // Short castle
                p.setSquare(SquareF8, BlackRook)
                p.setSquare(SquareH8, Empty)
            } else { // Long castle
                p.setSquare(SquareD8, BlackRook)
                p.setSquare(SquareA8, Empty)
            }
        }
    case movingPiece == WhiteRook:
        // Disable castling for the king on the side where the rook has moved.
        if m.From() == SquareA1 {
            p.Castling.off(longW)
        } else if m.From() == SquareH1 {
            p.Castling.off(shortW)
        }
    case movingPiece == BlackRook:
        // Disable castling for the king on the side where the rook has moved.
        if m.From() == SquareA8 {
            p.Castling.off(longB)
        } else if m.From() == SquareH8 {
            p.Castling.off(shortB)
        }
    case p.Squares[m.To()] == WhiteRook:
        // Disable castling when a white rook is taken.
        if m.To() == SquareA1 {
            p.Castling.off(longW)
        } else if m.To() == SquareH1 {
            p.Castling.off(shortW)
        }
    case p.Squares[m.To()] == BlackRook:
        // Disable castling when a black rook is taken.
        if m.To() == SquareA8 {
            p.Castling.off(longB)
        } else if m.To() == SquareH8 {
            p.Castling.off(shortB)
        }
    case movingPiece == WhitePawn && p.Squares[m.To()] == Empty:
        if m.To()-m.From() == 16 {
            // The pawn has moved two full squares onto an empty square.
            // Therefore there is a new en passant target on the rank between its original position and its new position.
            newEnPassantTarget = m.From() + 8
        } else if m.To()-m.From() == 7 || m.To()-m.From() == 9 {
            // The pawn has moved diagonally onto an empty square -- this must be an en passant capture.
            p.setSquare(p.EnPassant-8, Empty)
        }
    case movingPiece == BlackPawn && p.Squares[m.To()] == Empty:
        if m.From()-m.To() == 16 {
            // The pawn has moved two full squares onto an empty square.
            // Therefore there is a new en passant target on the rank between its original position and its new position.
            newEnPassantTarget = m.To() + 8
        } else if m.From()-m.To() == 7 || m.From()-m.To() == 9 {
            // The pawn has moved diagonally onto an empty square -- this must be an en passant capture.
            p.setSquare(p.EnPassant+8, Empty)
        }
    }

    p.EnPassant = newEnPassantTarget
    p.setSquare(m.From(), Empty)

    if m.Promotion() == None {
        p.setSquare(m.To(), movingPiece)
    } else {
        p.setSquare(m.To(), m.Promotion().OfColor(p.SideToMove))
    }

    p.SideToMove = p.SideToMove.Invert()

    if p.KingInCheck(p.SideToMove.Invert()) {
        p.UndoMove(m)
        return false
    }

    // If the side to move is now white, we can update the fullmove clock.
    if p.SideToMove == White {
        p.FullMoves += 1
    }

    // If there has been no capture and it's not a pawn move, then we need to increment the halfmove clock.
    if movingPiece != WhitePawn && movingPiece != BlackPawn && p.Squares[m.To()] != Empty {
        p.HalfmoveClock += 1
    } else {
        p.HalfmoveClock = 0
    }

    return true
}

Answer 1

I ended up finding the issue -- the move sorting wasn't working correctly. This meant that at the start of every iteration for iterative deepening, a bad move would be considered first and so set as the best move by default. Then when search time was up, this bad move would be returned as the best move to play.