Building a Chess Engine: From Position Evaluation to Search Techniques

Chess engines are fascinating pieces of software that combine various computer science concepts: position evaluation, tree search, move generation, and optimization techniques. This guide will walk you through implementing a chess engine, with a particular focus on position evaluation and search strategies.

Part 1: Basic Position Representation

First, let’s implement a basic board representation. While FEN (Forsyth–Edwards Notation) is the standard for chess positions, we’ll use a more computation-friendly format internally.

package chess

// Piece constants
const (
    Empty = iota
    Pawn
    Knight
    Bishop
    Rook
    Queen
    King
)

// Color constants
const (
    White = 1
    Black = -1
)

// Position represents a chess position
type Position struct {
    Board    [64]int    // Piece type (0-6)
    Colors   [64]int    // Piece color (1 for white, -1 for black)
    ToMove   int        // Side to move
    CastlingRights int  // Castling availability
    EnPassant    int    // En passant target square
    HalfMoveClock int   // Halfmove clock for fifty-move rule
    FullMoveNumber int  // Fullmove number
}

// Square converts file (a-h) and rank (1-8) to board index
func Square(file byte, rank int) int {
    return (rank-1)*8 + int(file-'a')
}

// NewPosition creates a starting chess position
func NewPosition() *Position {
    pos := &Position{
        ToMove: White,
        CastlingRights: 0xF, // All castling rights available
    }
    
    // Initialize starting position
    // Back rank pieces
    backRank := []int{Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook}
    for i, piece := range backRank {
        // White pieces
        pos.Board[i] = piece
        pos.Colors[i] = White
        // Black pieces
        pos.Board[i+56] = piece
        pos.Colors[i+56] = Black
    }
    
    // Pawns
    for i := 0; i < 8; i++ {
        // White pawns
        pos.Board[i+8] = Pawn
        pos.Colors[i+8] = White
        // Black pawns
        pos.Board[i+48] = Pawn
        pos.Colors[i+48] = Black
    }
    
    return pos
}

Part 2: Position Evaluation

Position evaluation is crucial for a chess engine. We’ll implement several evaluation components:

  1. Material count
  2. Piece position tables
  3. Pawn structure evaluation
  4. King safety
  5. Mobility evaluation
// Piece values in centipawns
var pieceValues = map[int]int{
    Pawn:   100,
    Knight: 320,
    Bishop: 330,
    Rook:   500,
    Queen:  900,
    King:   20000,
}

// Piece-Square tables for position evaluation
var pawnTable = [64]int{
     0,  0,  0,  0,  0,  0,  0,  0,
    50, 50, 50, 50, 50, 50, 50, 50,
    10, 10, 20, 30, 30, 20, 10, 10,
     5,  5, 10, 25, 25, 10,  5,  5,
     0,  0,  0, 20, 20,  0,  0,  0,
     5, -5,-10,  0,  0,-10, -5,  5,
     5, 10, 10,-20,-20, 10, 10,  5,
     0,  0,  0,  0,  0,  0,  0,  0,
}

// Similar tables for other pieces...

type Evaluator struct {
    pos *Position
    stage GameStage
}

// Evaluate returns a position score in centipawns
// Positive scores favor White, negative scores favor Black
func (e *Evaluator) Evaluate() int {
    score := 0
    
    // Material evaluation
    score += e.evaluateMaterial()
    
    // Piece-square table evaluation
    score += e.evaluatePiecePositions()
    
    // Pawn structure evaluation
    score += e.evaluatePawnStructure()
    
    // King safety
    score += e.evaluateKingSafety()
    
    // Mobility
    score += e.evaluateMobility()
    
    return score * e.pos.ToMove
}

func (e *Evaluator) evaluateMaterial() int {
    score := 0
    for sq := 0; sq < 64; sq++ {
        if piece := e.pos.Board[sq]; piece != Empty {
            score += pieceValues[piece] * e.pos.Colors[sq]
        }
    }
    return score
}

func (e *Evaluator) evaluatePawnStructure() int {
    score := 0
    
    // Evaluate doubled pawns
    for file := 0; file < 8; file++ {
        whitePawns := 0
        blackPawns := 0
        for rank := 0; rank < 8; rank++ {
            sq := rank*8 + file
            if e.pos.Board[sq] == Pawn {
                if e.pos.Colors[sq] == White {
                    whitePawns++
                } else {
                    blackPawns++
                }
            }
        }
        // Penalty for doubled pawns
        if whitePawns > 1 {
            score -= 20 * (whitePawns - 1)
        }
        if blackPawns > 1 {
            score += 20 * (blackPawns - 1)
        }
    }
    
    // Evaluate isolated pawns
    for file := 0; file < 8; file++ {
        hasWhitePawn := false
        hasBlackPawn := false
        for rank := 0; rank < 8; rank++ {
            sq := rank*8 + file
            if e.pos.Board[sq] == Pawn {
                if e.pos.Colors[sq] == White {
                    hasWhitePawn = true
                } else {
                    hasBlackPawn = true
                }
            }
        }
        
        if hasWhitePawn {
            isIsolated := true
            if file > 0 {
                // Check left file for pawns
                for rank := 0; rank < 8; rank++ {
                    sq := rank*8 + (file-1)
                    if e.pos.Board[sq] == Pawn && e.pos.Colors[sq] == White {
                        isIsolated = false
                        break
                    }
                }
            }
            if file < 7 && isIsolated {
                // Check right file for pawns
                for rank := 0; rank < 8; rank++ {
                    sq := rank*8 + (file+1)
                    if e.pos.Board[sq] == Pawn && e.pos.Colors[sq] == White {
                        isIsolated = false
                        break
                    }
                }
            }
            if isIsolated {
                score -= 15 // Penalty for isolated pawn
            }
        }
        
        // Similar check for black pawns...
    }
    
    return score
}

func (e *Evaluator) evaluateKingSafety() int {
    score := 0
    
    // Find king positions
    var whiteKingSq, blackKingSq int
    for sq := 0; sq < 64; sq++ {
        if e.pos.Board[sq] == King {
            if e.pos.Colors[sq] == White {
                whiteKingSq = sq
            } else {
                blackKingSq = sq
            }
        }
    }
    
    // Evaluate pawn shield
    score += e.evaluatePawnShield(whiteKingSq, White)
    score -= e.evaluatePawnShield(blackKingSq, Black)
    
    // Evaluate king tropism (enemy pieces' distance to king)
    score += e.evaluateKingTropism(whiteKingSq, blackKingSq)
    
    return score
}

func (e *Evaluator) evaluatePawnShield(kingSq, color int) int {
    score := 0
    rank := kingSq / 8
    file := kingSq % 8
    
    // Check pawns in front of king
    pawnShieldSquares := []int{
        Square(byte('a'+file-1), rank+1),
        Square(byte('a'+file), rank+1),
        Square(byte('a'+file+1), rank+1),
    }
    
    for _, sq := range pawnShieldSquares {
        if sq >= 0 && sq < 64 {
            if e.pos.Board[sq] == Pawn && e.pos.Colors[sq] == color {
                score += 10 // Bonus for each pawn shield
            }
        }
    }
    
    return score
}

Part 3: Search Implementation

Now let’s implement the search algorithm. We’ll use alpha-beta pruning with various enhancements:

  1. Principal Variation Search
  2. Quiescence Search
  3. Move Ordering
  4. Transposition Table
type SearchInfo struct {
    Depth      int
    NodesSearched int64
    StartTime  time.Time
    StopTime   time.Time
    Stopped    bool
}

type TranspositionEntry struct {
    Hash    uint64
    Depth   int
    Score   int
    Type    int // EXACT, ALPHA, or BETA
    Move    Move
}

const (
    EXACT = iota
    ALPHA
    BETA
)

func (e *Engine) Search(pos *Position, depth int) (bestMove Move, score int) {
    info := &SearchInfo{
        Depth:     depth,
        StartTime: time.Now(),
        StopTime:  time.Now().Add(5 * time.Second), // 5 second time control
    }
    
    alpha := -infinity
    beta := infinity
    
    // Iterative deepening
    for currentDepth := 1; currentDepth <= depth; currentDepth++ {
        score = e.alphaBeta(pos, currentDepth, alpha, beta, info)
        
        // Check if search should be stopped
        if info.Stopped {
            break
        }
        
        // Get best move from transposition table
        bestMove = e.tt.GetMove(pos.Hash())
    }
    
    return bestMove, score
}

func (e *Engine) alphaBeta(pos *Position, depth, alpha, beta int, info *SearchInfo) int {
    info.NodesSearched++
    
    // Check for time
    if time.Now().After(info.StopTime) {
        info.Stopped = true
        return 0
    }
    
    // Check transposition table
    if entry, found := e.tt.Get(pos.Hash()); found {
        if entry.Depth >= depth {
            if entry.Type == EXACT {
                return entry.Score
            }
            if entry.Type == ALPHA && entry.Score <= alpha {
                return alpha
            }
            if entry.Type == BETA && entry.Score >= beta {
                return beta
            }
        }
    }
    
    // Base case: evaluate position
    if depth == 0 {
        return e.quiescence(pos, alpha, beta, info)
    }
    
    moves := e.generateMoves(pos)
    moves = e.orderMoves(pos, moves) // Order moves for better pruning
    
    bestScore := -infinity
    for _, move := range moves {
        newPos := pos.MakeMove(move)
        score := -e.alphaBeta(newPos, depth-1, -beta, -alpha, info)
        
        if score > bestScore {
            bestScore = score
            
            // Update transposition table
            e.tt.Store(pos.Hash(), TranspositionEntry{
                Hash:  pos.Hash(),
                Depth: depth,
                Score: score,
                Type:  EXACT,
                Move:  move,
            })
        }
        
        alpha = max(alpha, score)
        if alpha >= beta {
            break // Beta cutoff
        }
    }
    
    return bestScore
}

func (e *Engine) quiescence(pos *Position, alpha, beta int, info *SearchInfo) int {
    info.NodesSearched++
    
    standPat := e.evaluate(pos)
    if standPat >= beta {
        return beta
    }
    if alpha < standPat {
        alpha = standPat
    }
    
    // Generate capturing moves only
    captures := e.generateCaptures(pos)
    captures = e.orderMoves(pos, captures)
    
    for _, move := range captures {
        newPos := pos.MakeMove(move)
        score := -e.quiescence(newPos, -beta, -alpha, info)
        
        if score >= beta {
            return beta
        }
        if score > alpha {
            alpha = score
        }
    }
    
    return alpha
}

func (e *Engine) orderMoves(pos *Position, moves []Move) []Move {
    // Score moves for ordering
    type ScoredMove struct {
        move  Move
        score int
    }
    
    scoredMoves := make([]ScoredMove, len(moves))
    for i, move := range moves {
        score := 0
        
        // TTMove bonus
        if ttMove, found := e.tt.GetMove(pos.Hash()); found && move == ttMove {
            score += 10000
        }
        
        // MVV/LVA (Most Valuable Victim / Least Valuable Attacker)
        if move.IsCapture() {
            victim := pos.Board[move.To()]
            attacker := pos.Board[move.From()]
            score += pieceValues[victim] - pieceValues[attacker]/10
        }
        
        // Killer move bonus
        if e.isKillerMove(move, pos.Ply()) {
            score += 900
        }
        
        // History heuristic
        score += e.history[move.From()][move.To()]
        
        scoredMoves[i] = ScoredMove{move, score}
    }
    
    // Sort moves by score
    sort.Slice(scoredMoves, func(i, j int) bool {
        return scoredMoves[i].score > scoredMoves[j].score
    })
    
    // Extract sorted moves
    sortedMoves := make([]Move, len(moves))
    for i, sm := range scoredMoves {
        sortedMoves[i] = sm.move
    }
    
    return sortedMoves
}

Part 4: Advanced Evaluation Features

Let’s enhance our evaluation with more sophisticated features:

func (e *Evaluator) evaluateMobility() int {
    score := 0
    
    // Piece mobility bonuses/penalties
func (e *Evaluator) evaluateMobility() int {
    score := 0
    
    // Mobility weights for each piece type
    mobilityWeights := map[int]int{
        Knight: 4,
        Bishop: 5,
        Rook:   2,
        Queen:  1,
    }
    
    // Calculate mobility for both sides
    for sq := 0; sq < 64; sq++ {
        piece := e.pos.Board[sq]
        color := e.pos.Colors[sq]
        
        if piece == Empty || piece == Pawn || piece == King {
            continue
        }
        
        moves := e.generatePieceMoves(sq)
        mobilityScore := len(moves) * mobilityWeights[piece]
        score += mobilityScore * color
    }
    
    return score
}

// Helper function to check piece attacks
func (e *Evaluator) isSquareAttacked(sq, byColor int) bool {
    // Check pawn attacks
    pawnDir := -byColor // Pawns move in opposite direction of their color
    for _, offset := range []int{7, 9} {
        attackSq := sq + pawnDir*8 + offset
        if attackSq >= 0 && attackSq < 64 {
            if e.pos.Board[attackSq] == Pawn && e.pos.Colors[attackSq] == byColor {
                return true
            }
        }
    }
    
    // Check knight attacks
    knightOffsets := []int{-17, -15, -10, -6, 6, 10, 15, 17}
    for _, offset := range knightOffsets {
        attackSq := sq + offset
        if attackSq >= 0 && attackSq < 64 {
            if e.pos.Board[attackSq] == Knight && e.pos.Colors[attackSq] == byColor {
                return true
            }
        }
    }
    
    // Check sliding piece attacks (Bishop, Rook, Queen)
    directions := [][]int{
        {-1, -1}, {-1, 1}, {1, -1}, {1, 1},  // Bishop/Queen directions
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},    // Rook/Queen directions
    }
    
    for _, dir := range directions {
        dx, dy := dir[0], dir[1]
        x, y := sq%8, sq/8
        
        for i := 1; i < 8; i++ {
            newX, newY := x+dx*i, y+dy*i
            if newX < 0 || newX >= 8 || newY < 0 || newY >= 8 {
                break
            }
            
            attackSq := newY*8 + newX
            piece := e.pos.Board[attackSq]
            if piece != Empty {
                if e.pos.Colors[attackSq] == byColor {
                    // Check if piece can move in this direction
                    if piece == Queen ||
                        (piece == Rook && (dx == 0 || dy == 0)) ||
                        (piece == Bishop && dx != 0 && dy != 0) {
                        return true
                    }
                }
                break
            }
        }
    }
    
    return false
}

Part 5: Advanced Search Techniques

Let’s implement some advanced search techniques to improve the engine’s strength:

// Null Move Pruning
func (e *Engine) alphaBetaWithNullMove(pos *Position, depth, alpha, beta int, info *SearchInfo) int {
    if depth >= 3 && !pos.InCheck() && pos.HasNonPawnMaterial() {
        // Make null move
        newPos := pos.MakeNullMove()
        
        // Reduced depth for null move search
        R := 2 + depth/4
        
        // Recursive search with reduced depth
        score := -e.alphaBeta(newPos, depth-R-1, -beta, -beta+1, info)
        
        if score >= beta {
            return beta // Null move cutoff
        }
    }
    
    // Continue with regular alpha-beta search...
    return e.alphaBeta(pos, depth, alpha, beta, info)
}

// Late Move Reduction
func (e *Engine) alphaBetaWithLMR(pos *Position, depth, alpha, beta int, moveCount int, info *SearchInfo) int {
    if depth >= 3 && moveCount >= 4 && !pos.InCheck() {
        // Reduce depth for late moves
        reduction := 1
        if moveCount >= 6 {
            reduction++
        }
        
        // Reduced depth search
        score := -e.alphaBeta(pos, depth-reduction-1, -alpha-1, -alpha, info)
        
        // If reduced search fails high, do a full depth search
        if score > alpha {
            return -e.alphaBeta(pos, depth-1, -beta, -alpha, info)
        }
        
        return score
    }
    
    // Continue with regular search...
    return -e.alphaBeta(pos, depth-1, -beta, -alpha, info)
}

// Aspiration Windows
func (e *Engine) searchWithAspirationWindows(pos *Position, depth int, info *SearchInfo) int {
    score := 0
    alpha := -infinity
    beta := infinity
    window := 50 // Initial window size in centipawns
    
    // First search with full window
    score = e.alphaBeta(pos, depth, alpha, beta, info)
    
    // Subsequent searches with aspiration windows
    for currentDepth := 2; currentDepth <= depth; currentDepth++ {
        alpha = score - window
        beta = score + window
        
        score = e.alphaBeta(pos, currentDepth, alpha, beta, info)
        
        if score <= alpha || score >= beta {
            // Window failed, retry with larger window
            window *= 2
            score = e.alphaBeta(pos, currentDepth, -infinity, infinity, info)
        }
        
        window = 50 // Reset window size for next iteration
    }
    
    return score
}

Part 6: Time Management

Proper time management is crucial for tournament play:

type TimeManager struct {
    InitialTime  time.Duration
    Increment    time.Duration
    MovesToGo    int
    MaxMoveTime  time.Duration
}

func NewTimeManager(initialTime, increment time.Duration, movesToGo int) *TimeManager {
    return &TimeManager{
        InitialTime: initialTime,
        Increment:   increment,
        MovesToGo:   movesToGo,
        MaxMoveTime: initialTime / 20, // Don't use more than 5% of total time
    }
}

func (tm *TimeManager) allocateTime(pos *Position) time.Duration {
    // Basic time allocation
    baseTime := tm.InitialTime / time.Duration(tm.MovesToGo)
    
    // Adjust based on game phase
    gamePhase := evaluateGamePhase(pos)
    switch {
    case gamePhase < 0.3: // Opening
        baseTime *= 8/10
    case gamePhase > 0.7: // Endgame
        baseTime *= 12/10
    }
    
    // Add increment
    allocatedTime := baseTime + tm.Increment*8/10
    
    // Never exceed maximum move time
    if allocatedTime > tm.MaxMoveTime {
        allocatedTime = tm.MaxMoveTime
    }
    
    return allocatedTime
}

func evaluateGamePhase(pos *Position) float64 {
    // Count material to determine game phase
    totalMaterial := 0
    maxMaterial := 0
    
    for sq := 0; sq < 64; sq++ {
        piece := pos.Board[sq]
        if piece != Empty && piece != King {
            totalMaterial += pieceValues[piece]
            maxMaterial += pieceValues[piece]
        }
    }
    
    // Return value between 0 (opening) and 1 (endgame)
    return 1.0 - float64(totalMaterial)/float64(maxMaterial)
}

Part 7: Opening Book and Endgame Tablebases

For completeness, let’s add support for opening books and endgame tablebases:

type OpeningBook struct {
    positions map[uint64][]BookMove
}

type BookMove struct {
    Move   Move
    Weight int
}

func (book *OpeningBook) GetBookMove(pos *Position) (Move, bool) {
    moves, exists := book.positions[pos.Hash()]
    if !exists {
        return Move{}, false
    }
    
    // Select move based on weights
    totalWeight := 0
    for _, m := range moves {
        totalWeight += m.Weight
    }
    
    // Random selection weighted by frequency
    r := rand.Intn(totalWeight)
    currentWeight := 0
    for _, m := range moves {
        currentWeight += m.Weight
        if r < currentWeight {
            return m.Move, true
        }
    }
    
    return moves[0].Move, true
}

type Tablebase struct {
    cache map[uint64]TablebaseEntry
}

type TablebaseEntry struct {
    Score    int
    BestMove Move
    DTM     int // Distance to mate
}

func (tb *Tablebase) Probe(pos *Position) (TablebaseEntry, bool) {
    // Probe tablebase cache
    if entry, exists := tb.cache[pos.Hash()]; exists {
        return entry, true
    }
    
    // Only probe for positions with 6 or fewer pieces
    if pos.PieceCount() > 6 {
        return TablebaseEntry{}, false
    }
    
    // Here you would implement actual tablebase probing
    // This typically involves accessing Syzygy or Gaviota tablebases
    
    return TablebaseEntry{}, false
}

Conclusion

Building a chess engine involves multiple complex components working together:

  1. Board Representation: Efficient position storage and move generation
  2. Evaluation: Material, piece placement, pawn structure, king safety, and mobility
  3. Search: Alpha-beta pruning with enhancements (null move, LMR, aspiration windows)
  4. Time Management: Adaptive time allocation based on position and game phase
  5. Opening/Endgame: Book moves and tablebase access for perfect play

Future improvements could include:

  • Neural network evaluation
  • Multi-threaded search
  • Supervised learning from master games
  • NNUE (Efficiently Updatable Neural Network) evaluation
  • Advanced pruning techniques (Futility pruning, SEE, etc.)
  • Contempt factor for tournament play

Remember that chess programming is an iterative process. Start with the basics and gradually add more sophisticated features while testing against other engines to measure improvement.

References