Costruire un motore scacchistico - dalla valutazione della posizione alle tecniche di ricerca

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
}

// 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
}

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
}

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
}

// 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
}

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)
}

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
}