search.go

package ai

import (
	"blunder/engine"
	"fmt"
	"time"
)

const (
	SearchDepth             = 20
	NullMove    engine.Move = 0

	// These scores are selected to put
	// killer moves ahead of quiet moves
	// but behind captures.
	FirstKillerMoveScore  = 10
	SecondKillerMoveScore = 9
)

// A struct to hold state during a search
type Searcher struct {
	Board           engine.Board
	nodesExplored   int
	killerMoves     [SearchDepth + 1][2]engine.Move
	searchStartTime time.Time
	timeForMove     int64
	stopSearch      bool
}

// Search for the best move for the side to move in the given position.
// Implemented using iterative deepening.
func (s *Searcher) Search(timeLeft, increment int64) engine.Move {
	bestMove, bestScore := NullMove, NegInf
	var totalSearchTime int64 = 0

	timeForMove := getTimeForMove(timeLeft, increment, s.Board.FullMoveCounter)
	s.timeForMove = timeForMove

	for depth := 1; depth <= SearchDepth; depth++ {
		start := time.Now()
		s.searchStartTime = start

		move, score := s.rootNegamax(depth)
		if s.stopSearch {
			s.stopSearch = false
			break
		}
		bestMove, bestScore = move, score

		timeTaken := int64(time.Since(start) / time.Millisecond)
		totalSearchTime += timeTaken

		printSearchInfo(depth, timeTaken, bestScore, s.nodesExplored)
		if totalSearchTime >= timeForMove {
			break
		}

	}
	return bestMove
}

// The top-level function for negamax, which returns a move and a score.
func (s *Searcher) rootNegamax(depth int) (engine.Move, int) {
	s.nodesExplored = 0
	moves := engine.GenPseduoLegalMoves(&s.Board)

	bestMove := NullMove
	alpha, beta := NegInf, PosInf
	for index := range moves {
		s.orderMoves(index, depth, &moves)
		move := moves[index]

		s.Board.DoMove(move, true)
		if engine.SqIsAttacked(&s.Board, s.Board.ColorToMove^1, s.Board.KingPos[s.Board.ColorToMove^1]) {
			s.Board.UndoMove(move)
			continue
		}
		score := -s.negamax(depth-1, -beta, -alpha)
		s.Board.UndoMove(move)

		if score == PosInf {
			s.storeKillerMove(depth, move)
			return move, beta
		}
		if score > alpha {
			alpha = score
			bestMove = move
		}
	}
	return bestMove, alpha
}

// The primary negamax function, which only returns a score and no best move.
func (s *Searcher) negamax(depth, alpha, beta int) int {
	if int64(time.Since(s.searchStartTime)/time.Millisecond) > s.timeForMove || s.stopSearch {
		s.stopSearch = true
		return 0
	}

	s.nodesExplored++
	if depth == 0 {
		return s.quiescence(alpha, beta)
	}

	moves := engine.GenPseduoLegalMoves(&s.Board)
	noMoves := true

	for index := range moves {
		s.orderMoves(index, depth, &moves)
		move := moves[index]

		s.Board.DoMove(move, true)
		if engine.SqIsAttacked(&s.Board, s.Board.ColorToMove^1, s.Board.KingPos[s.Board.ColorToMove^1]) {
			s.Board.UndoMove(move)
			continue
		}

		score := -s.negamax(depth-1, -beta, -alpha)
		s.Board.UndoMove(move)
		noMoves = false

		if score >= beta {
			s.storeKillerMove(depth, move)
			return beta
		}
		if score > alpha {
			alpha = score
		}
	}

	if noMoves {
		if engine.SqIsAttacked(&s.Board, s.Board.ColorToMove, s.Board.KingPos[s.Board.ColorToMove]) {
			return NegInf + (SearchDepth - depth - 1)
		}
		return 0
	}

	return alpha
}

// An implementation of a quiesence search algorithm.
func (s *Searcher) quiescence(alpha, beta int) int {
	if int64(time.Since(s.searchStartTime)/time.Millisecond) > s.timeForMove || s.stopSearch {
		s.stopSearch = true
		return 0
	}

	s.nodesExplored++
	standPat := evaluateBoard(&s.Board)

	if standPat >= beta {
		return beta
	}

	if alpha < standPat {
		alpha = standPat
	}

	moves := engine.GenPseduoLegalMoves(&s.Board)
	for index := range moves {
		if engine.MoveType(moves[index]) == engine.Attack || engine.MoveType(moves[index]) == engine.AttackEP {
			s.orderMoves(index, 0, &moves)
			move := moves[index]

			s.Board.DoMove(move, true)
			if engine.SqIsAttacked(&s.Board, s.Board.ColorToMove^1, s.Board.KingPos[s.Board.ColorToMove^1]) {
				s.Board.UndoMove(move)
				continue
			}

			score := -s.quiescence(-beta, -alpha)
			s.Board.UndoMove(move)

			if score >= beta {
				return beta
			}
			if score > alpha {
				alpha = score
			}
		}
	}
	return alpha
}

// Store a killer move in the killer move table
func (s *Searcher) storeKillerMove(depth int, move engine.Move) {
	if !movesAreSame(move, s.killerMoves[depth][0]) {
		s.killerMoves[depth][1] = s.killerMoves[depth][0]
		s.killerMoves[depth][0] = move
	}
}

// Find the highest scoring move in the moves list, and put it first
// in the list.
func (s *Searcher) orderMoves(index, depth int, moves *engine.Moves) {
	bestIndex := index
	bestScore := engine.MoveScore((*moves)[bestIndex])
	for index := bestIndex; index < len(*moves); index++ {

		if movesAreSame((*moves)[index], s.killerMoves[depth][0]) {
			(*moves)[index] = changeScore((*moves)[index], FirstKillerMoveScore)
		} else if movesAreSame((*moves)[index], s.killerMoves[depth][1]) {
			(*moves)[index] = changeScore((*moves)[index], SecondKillerMoveScore)
		}

		if engine.MoveScore((*moves)[index]) > bestScore {
			bestIndex = index
			bestScore = engine.MoveScore((*moves)[index])
		}
	}

	tempMove := (*moves)[index]
	(*moves)[index] = (*moves)[bestIndex]
	(*moves)[bestIndex] = tempMove
}

// Print search info for the GUI
func printSearchInfo(depth int, timeTaken int64, bestScore int, nodes int) {
	var movesToMate int
	if bestScore > (PosInf-SearchDepth) && bestScore <= PosInf {
		// If we're getting a huge number for the score, we're mating,
		// and shoud return mate in however many moves down we found it.
		movesToMate = (PosInf - bestScore) / 2
	} else if bestScore < (NegInf+SearchDepth) && bestScore >= NegInf {
		// Otherwise if we get a huge negative number, we're getting mated
		// soon and should report the score as negative.
		movesToMate = (NegInf - bestScore) / 2
	}

	if movesToMate != 0 {
		fmt.Printf("info depth %d score mate %d time %d nodes %d\n", depth, movesToMate, timeTaken, nodes)
	} else {
		fmt.Printf("info depth %d score cp %d time %d nodes %d\n", depth, bestScore, timeTaken, nodes)
	}
}

// Change the score of a move, from the default
// MvvLva given during move generation.
func changeScore(move engine.Move, newScore int) engine.Move {
	return (move & ^engine.ScoreMask) | uint32(newScore<<10)
}

// A helper function to compare if two moves are equal. The
// score is not relevant here, so it is masked out.
func movesAreSame(m1, m2 engine.Move) bool {
	return (m1 & ^engine.ScoreMask) == (m2 & ^engine.ScoreMask)
}