engine.go

/*
Package chess implements a chess game engine that manages move generation,
position analysis, and game state validation.
The engine uses bitboard operations and lookup tables for efficient move
generation and position analysis. Move generation includes standard piece
moves, captures, castling, en passant, and pawn promotions.
Example usage:

	// Create a position
	pos := NewPosition()

	// Calculate legal moves for current position
	eng := engine{}
	moves := eng.CalcMoves(pos, false)

	// Check game status
	status := eng.Status(pos)
	if status == Checkmate {
		fmt.Println("Game Over - Checkmate")
	}
*/
package chess

import "sync"

// engine implements chess move generation and position analysis.
type engine struct{}

// CalcMoves returns all legal moves for the given position. If first is true,
// returns after finding the first legal move. This is useful for quick position
// validation.
//
// The moves are generated in the following order:
//  1. Standard piece moves and captures
//  2. Castling moves (if available)
//
// Each move is validated to ensure it doesn't leave the king in check
func (engine) CalcMoves(pos *Position, first bool) []Move {
	// generate possible moves
	moves := standardMoves(pos, first)
	// return moves including castles
	return append(moves, castleMoves(pos)...)
}

// Status returns the current game status (Checkmate, Stalemate, or NoMethod)
// based on the position.
//
// The status is determined by:
//   - Whether the side to move is in check
//   - Whether any legal moves exist
//
// If the position has cached valid moves in pos.validMoves, those will be
// used. Otherwise, moves will be calculated to determine the status.
func (engine) Status(pos *Position) Method {
	var hasMove bool
	if pos.validMoves != nil {
		hasMove = len(pos.validMoves) > 0
	} else {
		hasMove = len(engine{}.CalcMoves(pos, true)) > 0
	}
	if !pos.inCheck && !hasMove {
		return Stalemate
	} else if pos.inCheck && !hasMove {
		return Checkmate
	}
	return NoMethod
}

// TODO: don't use globals
//
//nolint:gochecknoglobals // this is a lookup table
var promoPieceTypes = []PieceType{Queen, Rook, Bishop, Knight}

const maxPossibleMoves = 218 // Maximum possible moves in any chess position

// movePool is a pool of Move arrays to reduce allocations
// in the standardMoves function.
//
//nolint:gochecknoglobals // this is a sync pool
var movePool = sync.Pool{
	New: func() interface{} {
		return &[maxPossibleMoves]Move{}
	},
}

// standardMoves generates all standard (non-castling) legal moves for the
// current position. If first is true, returns after finding the first
// legal move.
//
// The function uses a sync.Pool of move arrays to reduce allocations. Each
// move is validated to ensure it doesn't leave the king in check.
func standardMoves(pos *Position, first bool) []Move {
	moves, _ := movePool.Get().(*[maxPossibleMoves]Move)
	defer movePool.Put(moves)
	count := 0

	// Reuse a single Move struct for temporary operations
	var m Move

	bbAllowed := ^pos.board.whiteSqs
	if pos.Turn() == Black {
		bbAllowed = ^pos.board.blackSqs
	}

	for _, p := range allPieces {
		if pos.Turn() != p.Color() {
			continue
		}
		s1BB := pos.board.bbForPiece(p)
		if s1BB == 0 {
			continue
		}
		for s1 := range numOfSquaresInBoard {
			if s1BB&bbForSquare(Square(s1)) == 0 {
				continue
			}
			s2BB := bbForPossibleMoves(pos, p.Type(), Square(s1)) & bbAllowed
			if s2BB == 0 {
				continue
			}
			for s2 := range numOfSquaresInBoard {
				if s2BB&bbForSquare(Square(s2)) == 0 {
					continue
				}

				// Reuse move struct by setting fields directly
				m.s1 = Square(s1)
				m.s2 = Square(s2)
				m.tags = 0 // Reset tags

				if (p == WhitePawn && Square(s2).Rank() == Rank8) || (p == BlackPawn && Square(s2).Rank() == Rank1) {
					for _, pt := range promoPieceTypes {
						m.promo = pt
						addTags(&m, pos)
						if !m.HasTag(inCheck) {
							// Copy the valid move to the array
							moves[count] = m
							count++
							if first {
								// For single move, return fixed array of size 1
								var result [1]Move
								result[0] = moves[0]
								return result[:]
							}
						}
					}
				} else {
					m.promo = 0
					addTags(&m, pos)
					if !m.HasTag(inCheck) {
						moves[count] = m
						count++
						if first {
							var result [1]Move
							result[0] = moves[0]
							return result[:]
						}
					}
				}
			}
		}
	}

	// Need to copy since we're returning array to pool
	result := make([]Move, count)
	copy(result, moves[:count])
	return result
}

// addTags updates a move's tags based on the resulting position.
// Tags include:
//   - Capture: The move captures an opponent's piece
//   - EnPassant: The move is an en passant capture
//   - Check: The move puts the opponent in check
//   - inCheck: The move leaves the moving side's king in check (illegal)
func addTags(m *Move, pos *Position) {
	p := pos.board.Piece(m.s1)
	if pos.board.isOccupied(m.s2) {
		m.AddTag(Capture)
	} else if m.s2 == pos.enPassantSquare && p.Type() == Pawn {
		m.AddTag(EnPassant)
	}
	// determine if in check after move (makes move invalid)
	cp := pos.copy()
	cp.board.update(m)
	if isInCheck(cp) {
		m.AddTag(inCheck)
	}
	// determine if opponent in check after move
	cp.turn = cp.turn.Other()
	if isInCheck(cp) {
		m.AddTag(Check)
	}
}

// isInCheck returns true if the side to move is in check in the given position.
func isInCheck(pos *Position) bool {
	kingSq := pos.board.whiteKingSq
	if pos.Turn() == Black {
		kingSq = pos.board.blackKingSq
	}
	// king should only be missing in tests / examples
	if kingSq == NoSquare {
		return false
	}
	return squaresAreAttacked(pos, kingSq)
}

// squaresAreAttacked returns true if any of the given squares are attacked
// by the opponent in the given position.
//
// The function checks attacks from:
//   - Sliding pieces (queen, rook, bishop)
//   - Knights
//   - Pawns
//   - King
//
//nolint:mnd // this is a formula to determine if a square is attacked
func squaresAreAttacked(pos *Position, sqs ...Square) bool {
	otherColor := pos.Turn().Other()
	occ := ^pos.board.emptySqs
	for _, sq := range sqs {
		// hot path check to see if attack vector is possible
		s2BB := pos.board.blackSqs
		if pos.Turn() == Black {
			s2BB = pos.board.whiteSqs
		}
		if ((diaAttack(occ, sq)|hvAttack(occ, sq))&s2BB)|(bbKnightMoves[sq]&s2BB) == 0 {
			continue
		}
		// check queen attack vector
		queenBB := pos.board.bbForPiece(NewPiece(Queen, otherColor))
		bb := (diaAttack(occ, sq) | hvAttack(occ, sq)) & queenBB
		if bb != 0 {
			return true
		}
		// check rook attack vector
		rookBB := pos.board.bbForPiece(NewPiece(Rook, otherColor))
		bb = hvAttack(occ, sq) & rookBB
		if bb != 0 {
			return true
		}
		// check bishop attack vector
		bishopBB := pos.board.bbForPiece(NewPiece(Bishop, otherColor))
		bb = diaAttack(occ, sq) & bishopBB
		if bb != 0 {
			return true
		}
		// check knight attack vector
		knightBB := pos.board.bbForPiece(NewPiece(Knight, otherColor))
		bb = bbKnightMoves[sq] & knightBB
		if bb != 0 {
			return true
		}
		// check pawn attack vector
		if pos.Turn() == White {
			capRight := (pos.board.bbBlackPawn & ^bbFileH & ^bbRank1) << 7
			capLeft := (pos.board.bbBlackPawn & ^bbFileA & ^bbRank1) << 9
			bb = (capRight | capLeft) & bbForSquare(sq)
			if bb != 0 {
				return true
			}
		} else {
			capRight := (pos.board.bbWhitePawn & ^bbFileH & ^bbRank8) >> 9
			capLeft := (pos.board.bbWhitePawn & ^bbFileA & ^bbRank8) >> 7
			bb = (capRight | capLeft) & bbForSquare(sq)
			if bb != 0 {
				return true
			}
		}
		// check king attack vector
		kingBB := pos.board.bbForPiece(NewPiece(King, otherColor))
		bb = bbKingMoves[sq] & kingBB
		if bb != 0 {
			return true
		}
	}
	return false
}

// bbForPossibleMoves returns a bitboard with 1s in positions where the piece
// of the given type at the given square can potentially move, without considering
// whether the moves would be legal (e.g., leave the king in check).
//
// The function handles movement patterns for:
//   - King: One square in any direction
//   - Queen: Sliding moves in all directions
//   - Rook: Sliding moves horizontally and vertically
//   - Bishop: Sliding moves diagonally
//   - Knight: L-shaped jumps
//   - Pawn: Forward moves and captures, including en passant
func bbForPossibleMoves(pos *Position, pt PieceType, sq Square) bitboard {
	switch pt {
	case King:
		return bbKingMoves[sq]
	case Queen:
		return diaAttack(^pos.board.emptySqs, sq) | hvAttack(^pos.board.emptySqs, sq)
	case Rook:
		return hvAttack(^pos.board.emptySqs, sq)
	case Bishop:
		return diaAttack(^pos.board.emptySqs, sq)
	case Knight:
		return bbKnightMoves[sq]
	case Pawn:
		return pawnMoves(pos, sq)
	}
	return bitboard(0)
}

// castleMoves returns all legal castling moves for the current position.
//
// A castling move is legal if:
//   - The king has castling rights in that direction
//   - The squares between king and rook are empty
//   - The king is not in check
//   - The king does not pass through check
func castleMoves(pos *Position) []Move {
	var moves [2]Move // Maximum of 2 possible castle moves (king side and queen side)
	count := 0

	kingSide := pos.castleRights.CanCastle(pos.Turn(), KingSide)
	queenSide := pos.castleRights.CanCastle(pos.Turn(), QueenSide)

	// white king side
	if pos.turn == White && kingSide &&
		(^pos.board.emptySqs&(bbForSquare(F1)|bbForSquare(G1))) == 0 &&
		!squaresAreAttacked(pos, F1, G1) &&
		!pos.inCheck {
		m := Move{s1: E1, s2: G1}
		m.AddTag(KingSideCastle)
		addTags(&m, pos)
		moves[count] = m
		count++
	}

	// white queen side
	if pos.turn == White && queenSide &&
		(^pos.board.emptySqs&(bbForSquare(B1)|bbForSquare(C1)|bbForSquare(D1))) == 0 &&
		!squaresAreAttacked(pos, C1, D1) &&
		!pos.inCheck {
		m := Move{s1: E1, s2: C1}
		m.AddTag(QueenSideCastle)
		addTags(&m, pos)
		moves[count] = m
		count++
	}

	// black king side
	if pos.turn == Black && kingSide &&
		(^pos.board.emptySqs&(bbForSquare(F8)|bbForSquare(G8))) == 0 &&
		!squaresAreAttacked(pos, F8, G8) &&
		!pos.inCheck {
		m := Move{s1: E8, s2: G8}
		m.AddTag(KingSideCastle)
		addTags(&m, pos)
		moves[count] = m
		count++
	}

	// black queen side
	if pos.turn == Black && queenSide &&
		(^pos.board.emptySqs&(bbForSquare(B8)|bbForSquare(C8)|bbForSquare(D8))) == 0 &&
		!squaresAreAttacked(pos, C8, D8) &&
		!pos.inCheck {
		m := Move{s1: E8, s2: C8}
		m.AddTag(QueenSideCastle)
		addTags(&m, pos)
		moves[count] = m
		count++
	}

	return moves[:count]
}

// pawnMoves returns a bitboard with 1s in positions where the pawn at the
// given square can potentially move.
//
// The function considers:
//   - Single and double forward moves
//   - Diagonal captures
//   - En passant captures
//
//nolint:mnd // this is a formula to determine the color of a square
func pawnMoves(pos *Position, sq Square) bitboard {
	bb := bbForSquare(sq)
	var bbEnPassant bitboard
	if pos.enPassantSquare != NoSquare {
		bbEnPassant = bbForSquare(pos.enPassantSquare)
	}
	if pos.Turn() == White {
		capRight := ((bb & ^bbFileH & ^bbRank8) >> 9) & (pos.board.blackSqs | bbEnPassant)
		capLeft := ((bb & ^bbFileA & ^bbRank8) >> 7) & (pos.board.blackSqs | bbEnPassant)
		upOne := ((bb & ^bbRank8) >> 8) & pos.board.emptySqs
		upTwo := ((upOne & bbRank3) >> 8) & pos.board.emptySqs
		return capRight | capLeft | upOne | upTwo
	}
	capRight := ((bb & ^bbFileH & ^bbRank1) << 7) & (pos.board.whiteSqs | bbEnPassant)
	capLeft := ((bb & ^bbFileA & ^bbRank1) << 9) & (pos.board.whiteSqs | bbEnPassant)
	upOne := ((bb & ^bbRank1) << 8) & pos.board.emptySqs
	upTwo := ((upOne & bbRank6) << 8) & pos.board.emptySqs
	return capRight | capLeft | upOne | upTwo
}

// diaAttack returns a bitboard representing possible diagonal moves for a
// sliding piece, considering occupied squares as blocking further movement.
func diaAttack(occupied bitboard, sq Square) bitboard {
	pos := bbForSquare(sq)
	dMask := bbDiagonals[sq]
	adMask := bbAntiDiagonals[sq]
	return linearAttack(occupied, pos, dMask) | linearAttack(occupied, pos, adMask)
}

// hvAttack returns a bitboard representing possible horizontal and vertical
func hvAttack(occupied bitboard, sq Square) bitboard {
	pos := bbForSquare(sq)
	rankMask := bbRanks[sq.Rank()]
	fileMask := bbFiles[sq.File()]
	return linearAttack(occupied, pos, rankMask) | linearAttack(occupied, pos, fileMask)
}

// linearAttack returns a bitboard representing possible moves in a single
// direction (rank, file, or diagonal) for a sliding piece, considering
// occupied squares as blocking further movement.
func linearAttack(occupied, pos, mask bitboard) bitboard {
	oInMask := occupied & mask
	return ((oInMask - 2*pos) ^ (oInMask.Reverse() - 2*pos.Reverse()).Reverse()) & mask
}

const (
	bbFileA bitboard = 9259542123273814144
	bbFileB bitboard = 4629771061636907072
	bbFileC bitboard = 2314885530818453536
	bbFileD bitboard = 1157442765409226768
	bbFileE bitboard = 578721382704613384
	bbFileF bitboard = 289360691352306692
	bbFileG bitboard = 144680345676153346
	bbFileH bitboard = 72340172838076673

	bbRank1 bitboard = 18374686479671623680
	bbRank2 bitboard = 71776119061217280
	bbRank3 bitboard = 280375465082880
	bbRank4 bitboard = 1095216660480
	bbRank5 bitboard = 4278190080
	bbRank6 bitboard = 16711680
	bbRank7 bitboard = 65280
	bbRank8 bitboard = 255
)

// TODO make method on Square
func bbForSquare(sq Square) bitboard {
	return bbSquares[sq]
}

// Lookup tables for piece movement patterns and board masks.
//
//nolint:gochecknoglobals // this is a lookup table
var (
	bbFiles = [8]bitboard{bbFileA, bbFileB, bbFileC, bbFileD, bbFileE, bbFileF, bbFileG, bbFileH} // bbFiles contains masks for each file (A-H)
	bbRanks = [8]bitboard{bbRank1, bbRank2, bbRank3, bbRank4, bbRank5, bbRank6, bbRank7, bbRank8} // bbRanks contains masks for each rank (1-8)

	bbDiagonals = [64]bitboard{9241421688590303745, 4620710844295151872, 2310355422147575808, 1155177711073755136, 577588855528488960, 288794425616760832, 144396663052566528, 72057594037927936, 36099303471055874, 9241421688590303745, 4620710844295151872, 2310355422147575808, 1155177711073755136, 577588855528488960, 288794425616760832, 144396663052566528, 141012904183812, 36099303471055874, 9241421688590303745, 4620710844295151872, 2310355422147575808, 1155177711073755136, 577588855528488960, 288794425616760832, 550831656968, 141012904183812, 36099303471055874, 9241421688590303745, 4620710844295151872, 2310355422147575808, 1155177711073755136, 577588855528488960, 2151686160, 550831656968, 141012904183812, 36099303471055874, 9241421688590303745, 4620710844295151872, 2310355422147575808, 1155177711073755136, 8405024, 2151686160, 550831656968, 141012904183812, 36099303471055874, 9241421688590303745, 4620710844295151872, 2310355422147575808, 32832, 8405024, 2151686160, 550831656968, 141012904183812, 36099303471055874, 9241421688590303745, 4620710844295151872, 128, 32832, 8405024, 2151686160, 550831656968, 141012904183812, 36099303471055874, 9241421688590303745}

	bbAntiDiagonals = [64]bitboard{9223372036854775808, 4647714815446351872, 2323998145211531264, 1161999622361579520, 580999813328273408, 290499906672525312, 145249953336295424, 72624976668147840, 4647714815446351872, 2323998145211531264, 1161999622361579520, 580999813328273408, 290499906672525312, 145249953336295424, 72624976668147840, 283691315109952, 2323998145211531264, 1161999622361579520, 580999813328273408, 290499906672525312, 145249953336295424, 72624976668147840, 283691315109952, 1108169199648, 1161999622361579520, 580999813328273408, 290499906672525312, 145249953336295424, 72624976668147840, 283691315109952, 1108169199648, 4328785936, 580999813328273408, 290499906672525312, 145249953336295424, 72624976668147840, 283691315109952, 1108169199648, 4328785936, 16909320, 290499906672525312, 145249953336295424, 72624976668147840, 283691315109952, 1108169199648, 4328785936, 16909320, 66052, 145249953336295424, 72624976668147840, 283691315109952, 1108169199648, 4328785936, 16909320, 66052, 258, 72624976668147840, 283691315109952, 1108169199648, 4328785936, 16909320, 66052, 258, 1}

	bbKnightMoves = [64]bitboard{9077567998918656, 4679521487814656, 38368557762871296, 19184278881435648, 9592139440717824, 4796069720358912, 2257297371824128, 1128098930098176, 2305878468463689728, 1152939783987658752, 9799982666336960512, 4899991333168480256, 2449995666584240128, 1224997833292120064, 576469569871282176, 288234782788157440, 4620693356194824192, 11533718717099671552, 5802888705324613632, 2901444352662306816, 1450722176331153408, 725361088165576704, 362539804446949376, 145241105196122112, 18049583422636032, 45053588738670592, 22667534005174272, 11333767002587136, 5666883501293568, 2833441750646784, 1416171111120896, 567348067172352, 70506185244672, 175990581010432, 88545054707712, 44272527353856, 22136263676928, 11068131838464, 5531918402816, 2216203387392, 275414786112, 687463207072, 345879119952, 172939559976, 86469779988, 43234889994, 21609056261, 8657044482, 1075839008, 2685403152, 1351090312, 675545156, 337772578, 168886289, 84410376, 33816580, 4202496, 10489856, 5277696, 2638848, 1319424, 659712, 329728, 132096}

	bbBishopMoves = [64]bitboard{18049651735527937, 45053622886727936, 22667548931719168, 11334324221640704, 5667164249915392, 2833579985862656, 1416240237150208, 567382630219904, 4611756524879479810, 11529391036782871041, 5764696068147249408, 2882348036221108224, 1441174018118909952, 720587009051099136, 360293502378066048, 144117404414255168, 2323857683139004420, 1197958188344280066, 9822351133174399489, 4911175566595588352, 2455587783297826816, 1227793891648880768, 577868148797087808, 288793334762704928, 1161999073681608712, 581140276476643332, 326598935265674242, 9386671504487645697, 4693335752243822976, 2310639079102947392, 1155178802063085600, 577588851267340304, 580999811184992272, 290500455356698632, 145390965166737412, 108724279602332802, 9241705379636978241, 4620711952330133792, 2310355426409252880, 1155177711057110024, 290499906664153120, 145249955479592976, 72625527495610504, 424704217196612, 36100411639206946, 9241421692918565393, 4620710844311799048, 2310355422147510788, 145249953336262720, 72624976676520096, 283693466779728, 1659000848424, 141017232965652, 36099303487963146, 9241421688590368773, 4620710844295151618, 72624976668147712, 283691315142656, 1108177604608, 6480472064, 550848566272, 141012904249856, 36099303471056128, 9241421688590303744}

	bbRookMoves = [64]bitboard{9187484529235886208, 13781085504453754944, 16077885992062689312, 17226286235867156496, 17800486357769390088, 18087586418720506884, 18231136449196065282, 18302911464433844481, 9259260648297103488, 4665518383679160384, 2368647251370188832, 1220211685215703056, 645993902138460168, 358885010599838724, 215330564830528002, 143553341945872641, 9259541023762186368, 4629910699613634624, 2315095537539358752, 1157687956502220816, 578984165983651848, 289632270724367364, 144956323094725122, 72618349279904001, 9259542118978846848, 4629771607097753664, 2314886351157207072, 1157443723186933776, 578722409201797128, 289361752209228804, 144681423712944642, 72341259464802561, 9259542123257036928, 4629771063767613504, 2314885534022901792, 1157442769150545936, 578721386714368008, 289360695496279044, 144680349887234562, 72340177082712321, 9259542123273748608, 4629771061645230144, 2314885530830970912, 1157442765423841296, 578721382720276488, 289360691368494084, 144680345692602882, 72340172854657281, 9259542123273813888, 4629771061636939584, 2314885530818502432, 1157442765409283856, 578721382704674568, 289360691352369924, 144680345676217602, 72340172838141441, 9259542123273814143, 4629771061636907199, 2314885530818453727, 1157442765409226991, 578721382704613623, 289360691352306939, 144680345676153597, 72340172838076926}

	bbQueenMoves = [64]bitboard{9205534180971414145, 13826139127340482880, 16100553540994408480, 17237620560088797200, 17806153522019305480, 18090419998706369540, 18232552689433215490, 18303478847064064385, 13871017173176583298, 16194909420462031425, 8133343319517438240, 4102559721436811280, 2087167920257370120, 1079472019650937860, 575624067208594050, 287670746360127809, 11583398706901190788, 5827868887957914690, 12137446670713758241, 6068863523097809168, 3034571949281478664, 1517426162373248132, 722824471891812930, 361411684042608929, 10421541192660455560, 5210911883574396996, 2641485286422881314, 10544115227674579473, 5272058161445620104, 2600000831312176196, 1299860225776030242, 649930110732142865, 9840541934442029200, 4920271519124312136, 2460276499189639204, 1266167048752878738, 9820426766351346249, 4910072647826412836, 2455035776296487442, 1227517888139822345, 9550042029937901728, 4775021017124823120, 2387511058326581416, 1157867469641037908, 614821794359483434, 9530782384287059477, 4765391190004401930, 2382695595002168069, 9404792076610076608, 4702396038313459680, 2315169224285282160, 1157444424410132280, 578862399937640220, 325459994840333070, 9386102034266586375, 4693051017133293059, 9332167099941961855, 4630054752952049855, 2314886638996058335, 1157442771889699055, 578721933553179895, 289501704256556795, 180779649147209725, 9313761861428380670}

	bbKingMoves = [64]bitboard{4665729213955833856, 11592265440851656704, 5796132720425828352, 2898066360212914176, 1449033180106457088, 724516590053228544, 362258295026614272, 144959613005987840, 13853283560024178688, 16186183351374184448, 8093091675687092224, 4046545837843546112, 2023272918921773056, 1011636459460886528, 505818229730443264, 216739030602088448, 54114388906344448, 63227278716305408, 31613639358152704, 15806819679076352, 7903409839538176, 3951704919769088, 1975852459884544, 846636838289408, 211384331665408, 246981557485568, 123490778742784, 61745389371392, 30872694685696, 15436347342848, 7718173671424, 3307175149568, 825720045568, 964771708928, 482385854464, 241192927232, 120596463616, 60298231808, 30149115904, 12918652928, 3225468928, 3768639488, 1884319744, 942159872, 471079936, 235539968, 117769984, 50463488, 12599488, 14721248, 7360624, 3680312, 1840156, 920078, 460039, 197123, 49216, 57504, 28752, 14376, 7188, 3594, 1797, 770}

	bbSquares = [64]bitboard{}
)

// TODO: remove this init function
//
//nolint:gochecknoinits // will be removed
func init() {
	const numOfSquaresInBoard = 64
	for sq := range numOfSquaresInBoard {
		bbSquares[sq] = bitboard(uint64(1) << (uint8(63) - uint8(sq)))
	}
}