""" UCI Chess Engine - Part 1: Board representation, move generation, evaluation tables. Pure Python, stdlib only. """ import sys import time import math import random import collections # --------------------------------------------------------------------------- # Piece and color constants # --------------------------------------------------------------------------- P, N, B, R, Q, K = 0, 1, 2, 3, 4, 5 WHITE, BLACK = 0, 1 _FEN_MODE = False # set True in FEN loop; redirects info lines to stderr PIECE_NONE = 6 # Castling rights bits WK_CASTLE = 1 WQ_CASTLE = 2 BK_CASTLE = 4 BQ_CASTLE = 8 # Move flags MF_QUIET = 0 MF_DOUBLE = 1 MF_CASTLE_K = 2 MF_CASTLE_Q = 3 MF_CAPTURE = 4 MF_EP = 5 MF_PROMO_N = 8 MF_PROMO_B = 9 MF_PROMO_R = 10 MF_PROMO_Q = 11 MF_PROMO_NC = 12 MF_PROMO_BC = 13 MF_PROMO_RC = 14 MF_PROMO_QC = 15 # Direction indices N_DIR = 0 NE_DIR = 1 E_DIR = 2 SE_DIR = 3 S_DIR = 4 SW_DIR = 5 W_DIR = 6 NW_DIR = 7 _DIR_DELTAS = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)] # --------------------------------------------------------------------------- # Bitboard utilities # --------------------------------------------------------------------------- def lsb(b): return (b & -b).bit_length() - 1 def msb(b): return b.bit_length() - 1 def popcount(b): count = 0 while b: b &= b - 1 count += 1 return count def bb_iter(b): while b: sq = (b & -b).bit_length() - 1 yield sq b &= b - 1 # --------------------------------------------------------------------------- # Pre-computed attack tables # --------------------------------------------------------------------------- KNIGHT_ATK = [0] * 64 KING_ATK = [0] * 64 PAWN_ATK = [[0]*64, [0]*64] RAYS = [[0]*64 for _ in range(8)] def _build_attack_tables(): for sq in range(64): rank = sq >> 3 file = sq & 7 # Knight attacks bb = 0 for dr, df in [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]: r2, f2 = rank+dr, file+df if 0 <= r2 < 8 and 0 <= f2 < 8: bb |= 1 << (r2*8+f2) KNIGHT_ATK[sq] = bb # King attacks bb = 0 for dr in (-1,0,1): for df in (-1,0,1): if dr == 0 and df == 0: continue r2, f2 = rank+dr, file+df if 0 <= r2 < 8 and 0 <= f2 < 8: bb |= 1 << (r2*8+f2) KING_ATK[sq] = bb # Pawn attacks # WHITE pawn on sq attacks sq+7 (file>0,rank<7) and sq+9 (file<7,rank<7) bb = 0 if file > 0 and rank < 7: bb |= 1 << (sq + 7) if file < 7 and rank < 7: bb |= 1 << (sq + 9) PAWN_ATK[WHITE][sq] = bb # BLACK pawn on sq attacks sq-9 (file>0,rank>0) and sq-7 (file<7,rank>0) bb = 0 if file > 0 and rank > 0: bb |= 1 << (sq - 9) if file < 7 and rank > 0: bb |= 1 << (sq - 7) PAWN_ATK[BLACK][sq] = bb # Ray attacks for d, (dr, df) in enumerate(_DIR_DELTAS): bb = 0 r2, f2 = rank+dr, file+df while 0 <= r2 < 8 and 0 <= f2 < 8: bb |= 1 << (r2*8+f2) r2 += dr f2 += df RAYS[d][sq] = bb _build_attack_tables() # --------------------------------------------------------------------------- # Sliding piece attacks # --------------------------------------------------------------------------- def bishop_attacks(sq, occ): att = 0 for d in (NE_DIR, NW_DIR): ray = RAYS[d][sq] bl = ray & occ att |= (ray ^ RAYS[d][lsb(bl)]) if bl else ray for d in (SE_DIR, SW_DIR): ray = RAYS[d][sq] bl = ray & occ att |= (ray ^ RAYS[d][msb(bl)]) if bl else ray return att def rook_attacks(sq, occ): att = 0 for d in (N_DIR, E_DIR): ray = RAYS[d][sq] bl = ray & occ att |= (ray ^ RAYS[d][lsb(bl)]) if bl else ray for d in (S_DIR, W_DIR): ray = RAYS[d][sq] bl = ray & occ att |= (ray ^ RAYS[d][msb(bl)]) if bl else ray return att def queen_attacks(sq, occ): return bishop_attacks(sq, occ) | rook_attacks(sq, occ) # --------------------------------------------------------------------------- # sq_attacked_by # --------------------------------------------------------------------------- def sq_attacked_by(sq, color, pieces, occ): if PAWN_ATK[color ^ 1][sq] & pieces[color][P]: return True if KNIGHT_ATK[sq] & pieces[color][N]: return True if KING_ATK[sq] & pieces[color][K]: return True if bishop_attacks(sq, occ) & (pieces[color][B] | pieces[color][Q]): return True if rook_attacks(sq, occ) & (pieces[color][R] | pieces[color][Q]): return True return False def any_sq_attacked(squares, by_color, pieces, occ): for sq in squares: if sq_attacked_by(sq, by_color, pieces, occ): return True return False # --------------------------------------------------------------------------- # Zobrist hashing # --------------------------------------------------------------------------- random.seed(0xDEADBEEF) ZOB_PIECE = [[[random.getrandbits(64) for _ in range(64)] for _ in range(6)] for _ in range(2)] ZOB_CASTLE = [random.getrandbits(64) for _ in range(16)] ZOB_EP = [random.getrandbits(64) for _ in range(8)] ZOB_SIDE = random.getrandbits(64) # --------------------------------------------------------------------------- # PeSTO piece values # --------------------------------------------------------------------------- MG_PIECE_VAL = [82, 337, 365, 477, 1025, 0] EG_PIECE_VAL = [94, 281, 297, 512, 936, 0] _MG_PAWN = [ 0, 0, 0, 0, 0, 0, 0, 0, 98, 134, 61, 95, 68, 126, 34, -11, -6, 7, 26, 31, 65, 56, 25, -20, -14, 13, 6, 21, 23, 12, 17, -23, -27, -2, -5, 12, 17, 6, 10, -25, -26, -4, -4, -10, 3, 3, 33, -12, -35, -1, -20, -23, -15, 24, 38, -22, 0, 0, 0, 0, 0, 0, 0, 0] _EG_PAWN = [ 0, 0, 0, 0, 0, 0, 0, 0, 178, 173, 158, 134, 147, 132, 165, 187, 94, 100, 85, 67, 56, 53, 82, 84, 32, 24, 13, 5, -2, 4, 17, 17, 13, 9, -3, -7, -7, -8, 3, -1, 4, 7, -6, 1, 0, -5, -1, -8, 13, 8, 8, 10, 13, 0, 2, -7, 0, 0, 0, 0, 0, 0, 0, 0] _MG_KNIGHT = [ -167, -89, -34, -49, 61, -97, -15, -107, -73, -41, 72, 36, 23, 62, 7, -17, -47, 60, 37, 65, 84, 129, 73, 44, -9, 17, 19, 53, 37, 69, 18, 22, -13, 4, 16, 13, 28, 19, 21, -8, -23, -9, 12, 10, 19, 17, 25, -16, -29, -53, -12, -3, -1, 18, -14, -19, -105, -21, -58, -33, -17, -28, -19, -23] _EG_KNIGHT = [ -58, -38, -13, -28, -31, -27, -63, -99, -25, -8, -25, -2, -9, -25, -24, -52, -24, -20, 10, 9, -1, -9, -19, -41, -17, 3, 22, 22, 22, 11, 8, -18, -18, -6, 16, 25, 16, 17, 4, -18, -23, -3, -1, 15, 10, -3, -20, -22, -42, -20, -10, -5, -2, -20, -23, -44, -29, -51, -23, -15, -22, -18, -50, -64] _MG_BISHOP = [ -29, 4, -82, -37, -25, -42, 7, -8, -26, 16, -18, -13, 30, 59, 18, -47, -16, 37, 43, 40, 35, 50, 37, -2, -4, 5, 19, 50, 37, 37, 7, -2, -6, 13, 13, 26, 34, 12, 10, 4, 0, 15, 15, 15, 14, 27, 18, 10, 4, 15, 16, 0, 7, 21, 33, 1, -33, -3, -14, -21, -13, -12, -39, -21] _EG_BISHOP = [ -14, -21, -11, -8, -7, -9, -17, -24, -8, -4, 7, -12, -3, -13, -4, -14, 2, -8, 0, -1, -2, 6, 0, 4, -3, 9, 12, 9, 14, 10, 3, 2, -6, 3, 13, 19, 7, 10, -3, -9, -12, -3, 8, 10, 13, 3, -7, -15, -14, -18, -7, -1, 4, -9, -15, -27, -23, -9, -23, -5, -9, -16, -5, -17] _MG_ROOK = [ 32, 42, 32, 51, 63, 9, 31, 43, 27, 32, 58, 62, 80, 67, 26, 44, -5, 19, 26, 36, 17, 45, 61, 16, -24, -11, 7, 26, 24, 35, -8, -20, -36, -26, -12, -1, 9, -7, 6, -23, -45, -25, -16, -17, 3, 0, -5, -33, -44, -16, -20, -9, -1, 11, -5, -45, -16, -27, 15, 25, 12, -6, 3, -21] _EG_ROOK = [ 13, 10, 18, 15, 12, 12, 8, 5, 11, 13, 13, 11, -3, 3, 8, 3, 7, 7, 7, 5, 4, -3, -5, -3, 4, 3, 13, 1, 2, 1, -1, 2, 3, 5, 8, 4, -5, -6, -8, -11, -4, 0, -5, -1, -7, -12, -8, -16, -6, -6, 0, 2, -9, -9, -11, -3, -9, 2, 3, -1, -5, -13, 4, -20] _MG_QUEEN = [ -28, 0, 29, 12, 59, 44, 43, 45, -24, -39, -5, 1, -16, 57, 28, 54, -13, -17, 7, 8, 29, 56, 47, 57, -27, -27, -16, -16, -1, 17, -2, 1, -9, -26, -9, -10, -2, -4, 3, -3, -14, 2, -11, -2, -5, 2, 14, 5, -35, -8, 11, 2, 8, 15, -3, 1, -1, -18, -9, 10, -15, -25, -31, -50] _EG_QUEEN = [ -9, 22, 22, 27, 27, 19, 10, 20, -17, 20, 32, 41, 58, 25, 30, 0, -20, 6, 9, 49, 47, 35, 19, 9, 3, 22, 24, 45, 57, 40, 57, 36, -18, 28, 19, 47, 31, 34, 39, 23, -16, -27, 15, 6, 9, 17, 10, 5, -22, -23, -30, -16, -16, -23, -36, -32, -33, -28, -22, -43, -5, -32, -20, -41] _MG_KING = [ -65, 23, 16, -15, -56, -34, 2, 13, 29, -1, -20, -7, -8, -4, -38, -29, -9, 24, 2, -16, -20, 6, 22, -22, -17, -20, -12, -27, -30, -25, -14, -36, -49, -1, -27, -39, -46, -44, -33, -51, -14, -14, -22, -46, -44, -30, -15, -27, 1, 7, -8, -64, -43, -16, 9, 8, -15, 36, 12, -54, 8, -28, 24, 14] _EG_KING = [ -74, -35, -18, -18, -11, 15, 4, -17, -12, 17, 14, 17, 17, 38, 23, 11, 10, 17, 23, 15, 20, 45, 44, 13, -8, 22, 24, 27, 26, 33, 26, 3, -18, -4, 21, 24, 27, 23, 9, -11, -19, -3, 11, 21, 23, 16, 7, -9, -27, -11, 4, 13, 14, 4, -5, -17, -53, -34, -21, -11, -28, -14, -24, -43] _RAW_TABLES_MG = [_MG_PAWN, _MG_KNIGHT, _MG_BISHOP, _MG_ROOK, _MG_QUEEN, _MG_KING] _RAW_TABLES_EG = [_EG_PAWN, _EG_KNIGHT, _EG_BISHOP, _EG_ROOK, _EG_QUEEN, _EG_KING] # Build PST tables: MG_PST[color][piece][sq], EG_PST[color][piece][sq] MG_PST = [[None]*6 for _ in range(2)] EG_PST = [[None]*6 for _ in range(2)] def _build_pst(): for pt in range(6): mg_raw = _RAW_TABLES_MG[pt] eg_raw = _RAW_TABLES_EG[pt] mg_w = [0]*64 eg_w = [0]*64 for sq in range(64): # pesto_index maps sq (rank0=a1 side) to the raw table (rank7=a8 side first) pesto_idx = (7 - (sq >> 3)) * 8 + (sq & 7) mg_w[sq] = MG_PIECE_VAL[pt] + mg_raw[pesto_idx] eg_w[sq] = EG_PIECE_VAL[pt] + eg_raw[pesto_idx] MG_PST[WHITE][pt] = mg_w EG_PST[WHITE][pt] = eg_w # Black mirrors vertically: sq^56 mg_b = [0]*64 eg_b = [0]*64 for sq in range(64): mg_b[sq] = MG_PST[WHITE][pt][sq ^ 56] eg_b[sq] = EG_PST[WHITE][pt][sq ^ 56] MG_PST[BLACK][pt] = mg_b EG_PST[BLACK][pt] = eg_b _build_pst() # --------------------------------------------------------------------------- # Board class # --------------------------------------------------------------------------- class Board: __slots__ = ['pieces','occ','side','castling','ep','halfmove','fullmove', 'zobrist','undo_stack','piece_map'] def __init__(self): # pieces[color][piece_type] = bitboard self.pieces = [[0]*6 for _ in range(2)] # occ[WHITE], occ[BLACK], occ[2]=all self.occ = [0, 0, 0] self.side = WHITE self.castling = 0 self.ep = -1 self.halfmove = 0 self.fullmove = 1 self.zobrist = 0 self.undo_stack = [] # piece_map[sq] = color*6 + pt, or -1 if empty self.piece_map = [-1] * 64 def _update_occ(self): w = 0 for pt in range(6): w |= self.pieces[WHITE][pt] b = 0 for pt in range(6): b |= self.pieces[BLACK][pt] self.occ[WHITE] = w self.occ[BLACK] = b self.occ[2] = w | b def _update_piece_map(self): pm = self.piece_map for sq in range(64): pm[sq] = -1 for color in range(2): for pt in range(6): bb = self.pieces[color][pt] while bb: sq = (bb & -bb).bit_length() - 1 pm[sq] = color * 6 + pt bb &= bb - 1 def piece_at(self, sq): v = self.piece_map[sq] if v < 0: return (None, PIECE_NONE) return (v // 6, v % 6) def in_check(self): king_bb = self.pieces[self.side][K] if not king_bb: return False king_sq = (king_bb & -king_bb).bit_length() - 1 return sq_attacked_by(king_sq, self.side ^ 1, self.pieces, self.occ[2]) def compute_zobrist(self): z = 0 for color in range(2): for pt in range(6): bb = self.pieces[color][pt] while bb: sq = (bb & -bb).bit_length() - 1 z ^= ZOB_PIECE[color][pt][sq] bb &= bb - 1 z ^= ZOB_CASTLE[self.castling] if self.ep >= 0: z ^= ZOB_EP[self.ep & 7] if self.side == BLACK: z ^= ZOB_SIDE return z def set_fen(self, fen): parts = fen.strip().split() # Reset self.pieces = [[0]*6 for _ in range(2)] self.piece_map = [-1] * 64 piece_chars = {'P':(WHITE,P),'N':(WHITE,N),'B':(WHITE,B), 'R':(WHITE,R),'Q':(WHITE,Q),'K':(WHITE,K), 'p':(BLACK,P),'n':(BLACK,N),'b':(BLACK,B), 'r':(BLACK,R),'q':(BLACK,Q),'k':(BLACK,K)} rank = 7 file = 0 for ch in parts[0]: if ch == '/': rank -= 1 file = 0 elif ch.isdigit(): file += int(ch) else: color, pt = piece_chars[ch] sq = rank * 8 + file self.pieces[color][pt] |= 1 << sq self.piece_map[sq] = color * 6 + pt file += 1 self.side = WHITE if parts[1] == 'w' else BLACK self.castling = 0 if len(parts) > 2: if 'K' in parts[2]: self.castling |= WK_CASTLE if 'Q' in parts[2]: self.castling |= WQ_CASTLE if 'k' in parts[2]: self.castling |= BK_CASTLE if 'q' in parts[2]: self.castling |= BQ_CASTLE self.ep = -1 if len(parts) > 3 and parts[3] != '-': ep_file = ord(parts[3][0]) - ord('a') ep_rank = int(parts[3][1]) - 1 self.ep = ep_rank * 8 + ep_file self.halfmove = int(parts[4]) if len(parts) > 4 else 0 self.fullmove = int(parts[5]) if len(parts) > 5 else 1 self._update_occ() self.zobrist = self.compute_zobrist() self.undo_stack = [] # --------------------------------------------------------------------------- # Move encoding helpers # --------------------------------------------------------------------------- def make_move_int(from_sq, to_sq, flags): return from_sq | (to_sq << 6) | (flags << 12) def move_from(m): return m & 63 def move_to(m): return (m >> 6) & 63 def move_flags(m): return (m >> 12) & 15 def is_capture(m): return bool(m & (4 << 12)) def is_promo(m): return bool(m & (8 << 12)) def is_ep(m): return (m >> 12) & 15 == MF_EP def is_castle(m): return (m >> 12) & 14 == 2 def move_to_uci(m): files = 'abcdefgh' frm = m & 63 to = (m >> 6) & 63 flags = (m >> 12) & 15 s = files[frm & 7] + str((frm >> 3) + 1) + files[to & 7] + str((to >> 3) + 1) if flags & 8: s += 'nbrq'[flags & 3] return s def uci_to_move(uci, board): legal = generate_legal_moves(board) for m in legal: if move_to_uci(m) == uci: return m return None # --------------------------------------------------------------------------- # make_move # --------------------------------------------------------------------------- def make_move(board, move): frm = move & 63 to = (move >> 6) & 63 flags = (move >> 12) & 15 side = board.side opp = side ^ 1 # Save undo info prev_castling = board.castling prev_ep = board.ep prev_halfmove = board.halfmove prev_zobrist = board.zobrist captured_pt = PIECE_NONE captured_color = opp z = board.zobrist # Remove old castling/ep contribution z ^= ZOB_CASTLE[board.castling] if board.ep >= 0: z ^= ZOB_EP[board.ep & 7] # Remove side (will re-add at end) if side == BLACK: z ^= ZOB_SIDE # Determine moving piece moving_pt = board.piece_map[frm] % 6 # piece_map[frm] = side*6 + pt # Handle captures if flags == MF_EP: # En-passant capture cap_sq = to - 8 if side == WHITE else to + 8 captured_pt = P captured_color = opp board.pieces[opp][P] &= ~(1 << cap_sq) board.piece_map[cap_sq] = -1 z ^= ZOB_PIECE[opp][P][cap_sq] elif flags >= MF_CAPTURE: # Regular capture (including promo-captures) cap_v = board.piece_map[to] if cap_v >= 0: captured_pt = cap_v % 6 captured_color = cap_v // 6 board.pieces[captured_color][captured_pt] &= ~(1 << to) z ^= ZOB_PIECE[captured_color][captured_pt][to] # piece_map[to] will be overwritten below # Save undo tuple board.undo_stack.append((move, captured_pt, captured_color, prev_castling, prev_ep, prev_halfmove, prev_zobrist)) # Move the piece board.pieces[side][moving_pt] &= ~(1 << frm) z ^= ZOB_PIECE[side][moving_pt][frm] # Handle promotions if flags & 8: promo_pt = [N, B, R, Q][flags & 3] board.pieces[side][promo_pt] |= 1 << to board.piece_map[to] = side * 6 + promo_pt z ^= ZOB_PIECE[side][promo_pt][to] else: board.pieces[side][moving_pt] |= 1 << to board.piece_map[to] = side * 6 + moving_pt z ^= ZOB_PIECE[side][moving_pt][to] board.piece_map[frm] = -1 # Handle castling rook moves if flags == MF_CASTLE_K: if side == WHITE: board.pieces[WHITE][R] &= ~(1 << 7) board.pieces[WHITE][R] |= (1 << 5) board.piece_map[7] = -1 board.piece_map[5] = WHITE * 6 + R z ^= ZOB_PIECE[WHITE][R][7] ^ ZOB_PIECE[WHITE][R][5] else: board.pieces[BLACK][R] &= ~(1 << 63) board.pieces[BLACK][R] |= (1 << 61) board.piece_map[63] = -1 board.piece_map[61] = BLACK * 6 + R z ^= ZOB_PIECE[BLACK][R][63] ^ ZOB_PIECE[BLACK][R][61] elif flags == MF_CASTLE_Q: if side == WHITE: board.pieces[WHITE][R] &= ~(1 << 0) board.pieces[WHITE][R] |= (1 << 3) board.piece_map[0] = -1 board.piece_map[3] = WHITE * 6 + R z ^= ZOB_PIECE[WHITE][R][0] ^ ZOB_PIECE[WHITE][R][3] else: board.pieces[BLACK][R] &= ~(1 << 56) board.pieces[BLACK][R] |= (1 << 59) board.piece_map[56] = -1 board.piece_map[59] = BLACK * 6 + R z ^= ZOB_PIECE[BLACK][R][56] ^ ZOB_PIECE[BLACK][R][59] # Update halfmove clock if moving_pt == P or (flags >= MF_CAPTURE and flags != MF_DOUBLE): board.halfmove = 0 else: board.halfmove += 1 # Update fullmove if side == BLACK: board.fullmove += 1 # Update en passant square if flags == MF_DOUBLE: board.ep = frm + 8 if side == WHITE else frm - 8 else: board.ep = -1 # Update castling rights _CASTLING_MASK = [ # indexed by square: which castling bits to clear if piece moves from/to that square 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, ] # a1=0: WQ, h1=7: WK, a8=56: BQ, h8=63: BK _CASTLING_MASK[0] = ~WQ_CASTLE & 0xF _CASTLING_MASK[7] = ~WK_CASTLE & 0xF _CASTLING_MASK[56] = ~BQ_CASTLE & 0xF _CASTLING_MASK[63] = ~BK_CASTLE & 0xF # e1=4: both white, e8=60: both black _CASTLING_MASK[4] = ~(WK_CASTLE | WQ_CASTLE) & 0xF _CASTLING_MASK[60] = ~(BK_CASTLE | BQ_CASTLE) & 0xF board.castling &= _CASTLING_MASK[frm] & _CASTLING_MASK[to] # Add new castling/ep contribution z ^= ZOB_CASTLE[board.castling] if board.ep >= 0: z ^= ZOB_EP[board.ep & 7] # Flip side z ^= ZOB_SIDE # always XOR: if side was WHITE, new side is BLACK so add ZOB_SIDE board.zobrist = z board.side = opp # Update occupancy board._update_occ() # Precompute castling mask at module level for use in make_move _CASTLING_MASK = [0xF] * 64 _CASTLING_MASK[0] = ~WQ_CASTLE & 0xF _CASTLING_MASK[7] = ~WK_CASTLE & 0xF _CASTLING_MASK[56] = ~BQ_CASTLE & 0xF _CASTLING_MASK[63] = ~BK_CASTLE & 0xF _CASTLING_MASK[4] = ~(WK_CASTLE | WQ_CASTLE) & 0xF _CASTLING_MASK[60] = ~(BK_CASTLE | BQ_CASTLE) & 0xF # Rewrite make_move to use the precomputed table (cleaner version) def make_move(board, move): frm = move & 63 to = (move >> 6) & 63 flags = (move >> 12) & 15 side = board.side opp = side ^ 1 prev_castling = board.castling prev_ep = board.ep prev_halfmove = board.halfmove prev_zobrist = board.zobrist captured_pt = PIECE_NONE captured_color = opp z = board.zobrist z ^= ZOB_CASTLE[board.castling] if board.ep >= 0: z ^= ZOB_EP[board.ep & 7] if side == BLACK: z ^= ZOB_SIDE moving_pt = board.piece_map[frm] % 6 from_bb = 1 << frm to_bb = 1 << to # En-passant capture if flags == MF_EP: cap_sq = to - 8 if side == WHITE else to + 8 captured_pt = P cap_bb = 1 << cap_sq board.pieces[opp][P] &= ~cap_bb board.piece_map[cap_sq] = -1 z ^= ZOB_PIECE[opp][P][cap_sq] board.occ[opp] ^= cap_bb board.occ[2] ^= cap_bb elif flags & 4: # any capture flag cap_v = board.piece_map[to] if cap_v >= 0: captured_pt = cap_v % 6 captured_color = cap_v // 6 board.pieces[captured_color][captured_pt] &= ~to_bb z ^= ZOB_PIECE[captured_color][captured_pt][to] board.occ[opp] ^= to_bb # occ[2] at to stays set — our piece lands there board.undo_stack.append((move, captured_pt, captured_color, prev_castling, prev_ep, prev_halfmove, prev_zobrist)) # Remove piece from source board.pieces[side][moving_pt] &= ~from_bb z ^= ZOB_PIECE[side][moving_pt][frm] board.piece_map[frm] = -1 board.occ[side] ^= from_bb board.occ[2] ^= from_bb # Place piece at destination (handle promotion) if flags & 8: land_pt = [N, B, R, Q][flags & 3] else: land_pt = moving_pt board.pieces[side][land_pt] |= to_bb board.piece_map[to] = side * 6 + land_pt z ^= ZOB_PIECE[side][land_pt][to] board.occ[side] ^= to_bb if flags == MF_EP or not (flags & 4): # landing on empty square board.occ[2] ^= to_bb # Castling: move the rook if flags == MF_CASTLE_K: if side == WHITE: rook_frm, rook_to = 7, 5 else: rook_frm, rook_to = 63, 61 board.pieces[side][R] &= ~(1 << rook_frm) board.pieces[side][R] |= (1 << rook_to) board.piece_map[rook_frm] = -1 board.piece_map[rook_to] = side * 6 + R z ^= ZOB_PIECE[side][R][rook_frm] ^ ZOB_PIECE[side][R][rook_to] board.occ[side] ^= (1 << rook_frm) | (1 << rook_to) board.occ[2] ^= (1 << rook_frm) | (1 << rook_to) elif flags == MF_CASTLE_Q: if side == WHITE: rook_frm, rook_to = 0, 3 else: rook_frm, rook_to = 56, 59 board.pieces[side][R] &= ~(1 << rook_frm) board.pieces[side][R] |= (1 << rook_to) board.piece_map[rook_frm] = -1 board.piece_map[rook_to] = side * 6 + R z ^= ZOB_PIECE[side][R][rook_frm] ^ ZOB_PIECE[side][R][rook_to] board.occ[side] ^= (1 << rook_frm) | (1 << rook_to) board.occ[2] ^= (1 << rook_frm) | (1 << rook_to) # Halfmove clock if moving_pt == P or (flags & 4): board.halfmove = 0 else: board.halfmove += 1 # Fullmove if side == BLACK: board.fullmove += 1 # En passant square if flags == MF_DOUBLE: board.ep = frm + 8 if side == WHITE else frm - 8 else: board.ep = -1 # Castling rights update board.castling &= _CASTLING_MASK[frm] & _CASTLING_MASK[to] z ^= ZOB_CASTLE[board.castling] if board.ep >= 0: z ^= ZOB_EP[board.ep & 7] # new side is opp; if opp==BLACK, add ZOB_SIDE if opp == BLACK: z ^= ZOB_SIDE board.zobrist = z board.side = opp def unmake_move(board): move, captured_pt, captured_color, prev_castling, prev_ep, prev_halfmove, prev_zobrist = board.undo_stack.pop() frm = move & 63 to = (move >> 6) & 63 flags = (move >> 12) & 15 # side that made the move (currently board.side^1 since we already flipped) side = board.side ^ 1 opp = board.side # current board.side = opponent of the side that moved board.side = side # Determine what piece is currently at 'to' land_v = board.piece_map[to] land_pt = land_v % 6 if land_v >= 0 else PIECE_NONE # For promotions, moving piece was a pawn if flags & 8: moving_pt = P # Remove the promoted piece from 'to' board.pieces[side][land_pt] &= ~(1 << to) else: moving_pt = land_pt board.pieces[side][moving_pt] &= ~(1 << to) board.piece_map[to] = -1 # Restore moving piece to source board.pieces[side][moving_pt] |= 1 << frm board.piece_map[frm] = side * 6 + moving_pt # Restore captured piece if flags == MF_EP: cap_sq = to - 8 if side == WHITE else to + 8 board.pieces[opp][P] |= 1 << cap_sq board.piece_map[cap_sq] = opp * 6 + P elif captured_pt != PIECE_NONE: board.pieces[captured_color][captured_pt] |= 1 << to board.piece_map[to] = captured_color * 6 + captured_pt # Restore castling rook if flags == MF_CASTLE_K: if side == WHITE: rook_frm, rook_to = 7, 5 else: rook_frm, rook_to = 63, 61 board.pieces[side][R] &= ~(1 << rook_to) board.pieces[side][R] |= (1 << rook_frm) board.piece_map[rook_to] = -1 board.piece_map[rook_frm] = side * 6 + R elif flags == MF_CASTLE_Q: if side == WHITE: rook_frm, rook_to = 0, 3 else: rook_frm, rook_to = 56, 59 board.pieces[side][R] &= ~(1 << rook_to) board.pieces[side][R] |= (1 << rook_frm) board.piece_map[rook_to] = -1 board.piece_map[rook_frm] = side * 6 + R # Restore board state board.castling = prev_castling board.ep = prev_ep board.halfmove = prev_halfmove board.zobrist = prev_zobrist if side == BLACK: board.fullmove -= 1 # Incremental occupancy restore (reverse of make_move) from_bb = 1 << frm to_bb = 1 << to board.occ[side] ^= from_bb ^ to_bb # piece moves back: gains frm, loses to if flags == MF_EP: cap_sq = to - 8 if side == WHITE else to + 8 cap_bb = 1 << cap_sq board.occ[opp] ^= cap_bb board.occ[2] ^= from_bb ^ to_bb ^ cap_bb elif captured_pt != PIECE_NONE: board.occ[opp] ^= to_bb # restore captured piece at to board.occ[2] ^= from_bb # to stays occupied; only frm changes else: board.occ[2] ^= from_bb ^ to_bb if flags == MF_CASTLE_K: if side == WHITE: rook_frm, rook_to = 7, 5 else: rook_frm, rook_to = 63, 61 board.occ[side] ^= (1 << rook_frm) | (1 << rook_to) board.occ[2] ^= (1 << rook_frm) | (1 << rook_to) elif flags == MF_CASTLE_Q: if side == WHITE: rook_frm, rook_to = 0, 3 else: rook_frm, rook_to = 56, 59 board.occ[side] ^= (1 << rook_frm) | (1 << rook_to) board.occ[2] ^= (1 << rook_frm) | (1 << rook_to) def make_null_move(board): prev_ep = board.ep prev_zobrist = board.zobrist board.undo_stack.append((0, PIECE_NONE, board.side ^ 1, board.castling, prev_ep, board.halfmove, prev_zobrist)) z = board.zobrist if board.ep >= 0: z ^= ZOB_EP[board.ep & 7] board.ep = -1 z ^= ZOB_SIDE # flip side board.zobrist = z board.side ^= 1 def unmake_null_move(board): _, _, _, _, prev_ep, _, prev_zobrist = board.undo_stack.pop() board.side ^= 1 board.ep = prev_ep board.zobrist = prev_zobrist # --------------------------------------------------------------------------- # Move generation # --------------------------------------------------------------------------- def generate_moves(board): moves = [] side = board.side opp = side ^ 1 occ = board.occ[2] occ_side = board.occ[side] occ_opp = board.occ[opp] _mk = make_move_int # Pawns pbb = board.pieces[side][P] if side == WHITE: while pbb: sq = (pbb & -pbb).bit_length() - 1 rank = sq >> 3 # Single push to = sq + 8 if not (occ >> to & 1): if rank == 6: # promotion moves.append(_mk(sq, to, MF_PROMO_Q)) moves.append(_mk(sq, to, MF_PROMO_R)) moves.append(_mk(sq, to, MF_PROMO_B)) moves.append(_mk(sq, to, MF_PROMO_N)) else: moves.append(_mk(sq, to, MF_QUIET)) # Double push from rank 1 if rank == 1: to2 = sq + 16 if not (occ >> to2 & 1): moves.append(_mk(sq, to2, MF_DOUBLE)) # Captures atk = PAWN_ATK[WHITE][sq] & occ_opp while atk: cap_sq = (atk & -atk).bit_length() - 1 cap_rank = cap_sq >> 3 if cap_rank == 7: moves.append(_mk(sq, cap_sq, MF_PROMO_QC)) moves.append(_mk(sq, cap_sq, MF_PROMO_RC)) moves.append(_mk(sq, cap_sq, MF_PROMO_BC)) moves.append(_mk(sq, cap_sq, MF_PROMO_NC)) else: moves.append(_mk(sq, cap_sq, MF_CAPTURE)) atk &= atk - 1 # En passant if board.ep >= 0 and (PAWN_ATK[WHITE][sq] >> board.ep & 1): moves.append(_mk(sq, board.ep, MF_EP)) pbb &= pbb - 1 else: # BLACK while pbb: sq = (pbb & -pbb).bit_length() - 1 rank = sq >> 3 to = sq - 8 if not (occ >> to & 1): if rank == 1: # promotion moves.append(_mk(sq, to, MF_PROMO_Q)) moves.append(_mk(sq, to, MF_PROMO_R)) moves.append(_mk(sq, to, MF_PROMO_B)) moves.append(_mk(sq, to, MF_PROMO_N)) else: moves.append(_mk(sq, to, MF_QUIET)) if rank == 6: to2 = sq - 16 if not (occ >> to2 & 1): moves.append(_mk(sq, to2, MF_DOUBLE)) atk = PAWN_ATK[BLACK][sq] & occ_opp while atk: cap_sq = (atk & -atk).bit_length() - 1 cap_rank = cap_sq >> 3 if cap_rank == 0: moves.append(_mk(sq, cap_sq, MF_PROMO_QC)) moves.append(_mk(sq, cap_sq, MF_PROMO_RC)) moves.append(_mk(sq, cap_sq, MF_PROMO_BC)) moves.append(_mk(sq, cap_sq, MF_PROMO_NC)) else: moves.append(_mk(sq, cap_sq, MF_CAPTURE)) atk &= atk - 1 if board.ep >= 0 and (PAWN_ATK[BLACK][sq] >> board.ep & 1): moves.append(_mk(sq, board.ep, MF_EP)) pbb &= pbb - 1 # Knights nbb = board.pieces[side][N] while nbb: sq = (nbb & -nbb).bit_length() - 1 atk = KNIGHT_ATK[sq] & ~occ_side while atk: to = (atk & -atk).bit_length() - 1 flag = MF_CAPTURE if (occ_opp >> to & 1) else MF_QUIET moves.append(_mk(sq, to, flag)) atk &= atk - 1 nbb &= nbb - 1 # Bishops bbb = board.pieces[side][B] while bbb: sq = (bbb & -bbb).bit_length() - 1 atk = bishop_attacks(sq, occ) & ~occ_side while atk: to = (atk & -atk).bit_length() - 1 flag = MF_CAPTURE if (occ_opp >> to & 1) else MF_QUIET moves.append(_mk(sq, to, flag)) atk &= atk - 1 bbb &= bbb - 1 # Rooks rbb = board.pieces[side][R] while rbb: sq = (rbb & -rbb).bit_length() - 1 atk = rook_attacks(sq, occ) & ~occ_side while atk: to = (atk & -atk).bit_length() - 1 flag = MF_CAPTURE if (occ_opp >> to & 1) else MF_QUIET moves.append(_mk(sq, to, flag)) atk &= atk - 1 rbb &= rbb - 1 # Queens qbb = board.pieces[side][Q] while qbb: sq = (qbb & -qbb).bit_length() - 1 atk = queen_attacks(sq, occ) & ~occ_side while atk: to = (atk & -atk).bit_length() - 1 flag = MF_CAPTURE if (occ_opp >> to & 1) else MF_QUIET moves.append(_mk(sq, to, flag)) atk &= atk - 1 qbb &= qbb - 1 # King king_sq = (board.pieces[side][K] & -board.pieces[side][K]).bit_length() - 1 if board.pieces[side][K]: atk = KING_ATK[king_sq] & ~occ_side while atk: to = (atk & -atk).bit_length() - 1 flag = MF_CAPTURE if (occ_opp >> to & 1) else MF_QUIET moves.append(_mk(king_sq, to, flag)) atk &= atk - 1 # Castling pieces = board.pieces if side == WHITE: if board.castling & WK_CASTLE: # F1=5, G1=6 must be empty; E1=4, F1=5, G1=6 not attacked if not (occ & 0x60) and not any_sq_attacked([4, 5, 6], BLACK, pieces, occ): moves.append(_mk(4, 6, MF_CASTLE_K)) if board.castling & WQ_CASTLE: # D1=3, C1=2, B1=1 must be empty; E1=4, D1=3, C1=2 not attacked if not (occ & 0xE) and not any_sq_attacked([4, 3, 2], BLACK, pieces, occ): moves.append(_mk(4, 2, MF_CASTLE_Q)) else: if board.castling & BK_CASTLE: # F8=61, G8=62 must be empty; E8=60, F8=61, G8=62 not attacked if not (occ & (0x60 << 56)) and not any_sq_attacked([60, 61, 62], WHITE, pieces, occ): moves.append(_mk(60, 62, MF_CASTLE_K)) if board.castling & BQ_CASTLE: # D8=59, C8=58, B8=57 must be empty; E8=60, D8=59, C8=58 not attacked if not (occ & (0xE << 56)) and not any_sq_attacked([60, 59, 58], WHITE, pieces, occ): moves.append(_mk(60, 58, MF_CASTLE_Q)) return moves def generate_legal_moves(board): legal = [] for move in generate_moves(board): make_move(board, move) moving_side = board.side ^ 1 king_bb = board.pieces[moving_side][K] if king_bb: king_sq = (king_bb & -king_bb).bit_length() - 1 if not sq_attacked_by(king_sq, board.side, board.pieces, board.occ[2]): legal.append(move) board.undo_stack # already appended in make_move unmake_move(board) return legal # === SEARCH AND UCI === # --------------------------------------------------------------------------- # Evaluation # --------------------------------------------------------------------------- FILE_BB = [0]*8 RANK_BB = [0]*8 for _s in range(64): FILE_BB[_s & 7] |= 1 << _s RANK_BB[_s >> 3] |= 1 << _s PHASE_WEIGHTS = [0, 1, 1, 2, 4, 0] # P N B R Q K MAX_PHASE = 24 # 4N+4B+4R+2Q = 4+4+8+8=24 (full MG) # Passed pawn masks: PASSED_MASK[color][sq] = squares that must have no enemy pawns PASSED_MASK = [[0]*64 for _ in range(2)] for _sq in range(64): _r, _f = _sq >> 3, _sq & 7 _mask_w = 0 _mask_b = 0 for _ff in range(max(0, _f-1), min(8, _f+2)): for _rk in range(_r+1, 8): _mask_w |= 1 << (_rk*8 + _ff) for _rk in range(0, _r): _mask_b |= 1 << (_rk*8 + _ff) PASSED_MASK[WHITE][_sq] = _mask_w PASSED_MASK[BLACK][_sq] = _mask_b # Passed pawn rank bonuses (0-indexed rank, from own side): MG, EG _PASSED_BONUS = [(0, 0), (0, 10), (10, 20), (20, 40), (40, 70), (70, 120), (120, 200), (0, 0)] # King safety: tropism weight per attacking piece type (P N B R Q K) _KS_TROPISM_WEIGHT = [0, 0, 4, 3, 3, 5, 0] # King safety: MG bonus for 0-3 friendly pawns in king zone _KS_SHELTER_BONUS = [0, 15, 25, 30] def evaluate(board): """Returns score from side-to-move perspective (tapered PeSTO + bonus terms).""" mg = [0, 0] eg = [0, 0] phase = 0 for color in (WHITE, BLACK): for pt in range(6): bb = board.pieces[color][pt] phase += popcount(bb) * PHASE_WEIGHTS[pt] while bb: sq = lsb(bb) mg[color] += MG_PST[color][pt][sq] eg[color] += EG_PST[color][pt][sq] bb &= bb - 1 # Bishop pair bonus for color in (WHITE, BLACK): if popcount(board.pieces[color][B]) >= 2: mg[color] += 30 eg[color] += 50 # Passed pawns for color in (WHITE, BLACK): enemy_pawns = board.pieces[color ^ 1][P] bb = board.pieces[color][P] while bb: sq = lsb(bb) if not (PASSED_MASK[color][sq] & enemy_pawns): rank = sq >> 3 if color == WHITE else 7 - (sq >> 3) mg[color] += _PASSED_BONUS[rank][0] eg[color] += _PASSED_BONUS[rank][1] bb &= bb - 1 # Rooks on open/semi-open files all_pawns = board.pieces[WHITE][P] | board.pieces[BLACK][P] for color in (WHITE, BLACK): bb = board.pieces[color][R] while bb: sq = lsb(bb) file_mask = FILE_BB[sq & 7] if not (file_mask & all_pawns): mg[color] += 20 # fully open file eg[color] += 15 elif not (file_mask & board.pieces[color][P]): mg[color] += 10 # semi-open file (no own pawns) eg[color] += 8 bb &= bb - 1 # King safety: pawn shelter + enemy piece tropism for color in (WHITE, BLACK): if not board.pieces[color][K]: continue opp = color ^ 1 king_sq = lsb(board.pieces[color][K]) king_file = king_sq & 7 king_rank = king_sq >> 3 # Pawn shelter: friendly pawns adjacent to king (MG bonus) shelter = min(3, popcount(board.pieces[color][P] & KING_ATK[king_sq])) mg[color] += _KS_SHELTER_BONUS[shelter] # Enemy tropism: penalize enemy pieces close to our king tropism = 0 for pt in (N, B, R, Q): bb = board.pieces[opp][pt] while bb: sq = lsb(bb) dist = max(abs((sq & 7) - king_file), abs((sq >> 3) - king_rank)) tropism += _KS_TROPISM_WEIGHT[pt] * max(0, 7 - dist) bb &= bb - 1 mg[color] -= tropism eg[color] -= tropism // 2 phase = min(phase, MAX_PHASE) mg_score = mg[WHITE] - mg[BLACK] eg_score = eg[WHITE] - eg[BLACK] score = (mg_score * phase + eg_score * (MAX_PHASE - phase)) // MAX_PHASE return score if board.side == WHITE else -score # --------------------------------------------------------------------------- # Transposition table # --------------------------------------------------------------------------- TT_EXACT = 0 TT_LOWER = 1 TT_UPPER = 2 TT_SIZE = 1 << 22 # ~4M entries TT = [None] * TT_SIZE # --------------------------------------------------------------------------- # Move ordering # --------------------------------------------------------------------------- _MVV = [100, 320, 330, 500, 900, 20000] # piece values for MVV-LVA (P,N,B,R,Q,K) def score_move(move, tt_move, board, killers, history): if move == tt_move: return 10_000_000 flags = (move >> 12) & 15 if flags & 4: # capture to_sq = (move >> 6) & 63 from_sq = move & 63 victim_val = 100 if flags == MF_EP else ( _MVV[board.piece_map[to_sq] % 6] if board.piece_map[to_sq] >= 0 else 100) attacker_val = _MVV[board.piece_map[from_sq] % 6] if board.piece_map[from_sq] >= 0 else 100 return 1_000_000 + victim_val * 10 - attacker_val if flags & 8: # quiet promotion return 900_000 + ((flags & 3) == 3) * 100 if move in killers: return 800_000 from_sq = move & 63 to_sq = (move >> 6) & 63 return history[board.side][from_sq][to_sq] def is_repetition(board): """2-fold repetition check via undo_stack (same side to move).""" z = board.zobrist stack = board.undo_stack i = len(stack) - 2 while i >= 0: entry = stack[i] if entry[6] == z: return True if entry[5] == 0: # prev_halfmove was 0 = irreversible move, stop break i -= 2 return False # --------------------------------------------------------------------------- # Static Exchange Evaluation (SEE) # --------------------------------------------------------------------------- def _see_least_attacker(to_sq, side, pieces, occ): """Return (sq, pt) of side's least valuable attacker of to_sq given occ, or (-1, -1).""" # Pawns bb = PAWN_ATK[side ^ 1][to_sq] & pieces[side][P] & occ if bb: return lsb(bb), P # Knights bb = KNIGHT_ATK[to_sq] & pieces[side][N] & occ if bb: return lsb(bb), N # Bishops bb = bishop_attacks(to_sq, occ) & pieces[side][B] & occ if bb: return lsb(bb), B # Rooks bb = rook_attacks(to_sq, occ) & pieces[side][R] & occ if bb: return lsb(bb), R # Queens bb = queen_attacks(to_sq, occ) & pieces[side][Q] & occ if bb: return lsb(bb), Q # King bb = KING_ATK[to_sq] & pieces[side][K] & occ if bb: return lsb(bb), K return -1, -1 def see(board, move): """Static Exchange Evaluation. Returns net material gain for the capturing side.""" flags = (move >> 12) & 15 to_sq = (move >> 6) & 63 from_sq = move & 63 if flags == MF_EP: return _MVV[P] # captures a pawn, no recapture on to_sq cap_v = board.piece_map[to_sq] if cap_v < 0: return 0 moving_pt = board.piece_map[from_sq] % 6 target_pt = cap_v % 6 gain = [0] * 32 gain[0] = _MVV[target_pt] occ = board.occ[2] ^ (1 << from_sq) # remove first attacker side = board.side ^ 1 # opponent recaptures first d = 0 while True: d += 1 gain[d] = _MVV[moving_pt] - gain[d - 1] # Futility: even if we capture everything from here, it won't help if max(-gain[d - 1], gain[d]) < 0: break sq, moving_pt = _see_least_attacker(to_sq, side, board.pieces, occ) if sq < 0: break occ ^= 1 << sq # remove this attacker (may expose X-ray) side ^= 1 # Minimax the gain array while d > 1: d -= 1 gain[d - 1] = -max(-gain[d - 1], gain[d]) return gain[0] # --------------------------------------------------------------------------- # Quiescence search # --------------------------------------------------------------------------- _QS_HISTORY = [[[0]*64 for _ in range(64)] for _ in range(2)] # static empty history for qsearch def quiescence(board, alpha, beta, ply): in_check = board.in_check() if not in_check: stand_pat = evaluate(board) if stand_pat >= beta: return beta if stand_pat > alpha: alpha = stand_pat moves = [m for m in generate_moves(board) if is_capture(m) and see(board, m) >= 0] moves.sort(key=lambda m: score_move(m, -1, board, [], _QS_HISTORY), reverse=True) else: # In check: must search all evasions, cannot stand pat moves = generate_moves(board) found_legal = False for move in moves: if not in_check: # Delta pruning only when not in check cap_v = board.piece_map[(move >> 6) & 63] if cap_v >= 0 and stand_pat + _MVV[cap_v % 6] + 200 < alpha: continue make_move(board, move) moving_side = board.side ^ 1 king_bb = board.pieces[moving_side][K] if king_bb: king_sq = lsb(king_bb) if sq_attacked_by(king_sq, board.side, board.pieces, board.occ[2]): unmake_move(board) continue found_legal = True score = -quiescence(board, -beta, -alpha, ply + 1) unmake_move(board) if score >= beta: return beta if score > alpha: alpha = score if in_check and not found_legal: return -(MATE_SCORE - ply) return alpha # --------------------------------------------------------------------------- # Main negamax search # --------------------------------------------------------------------------- INF = 10_000_000 MATE_SCORE = 9_000_000 _NODES = [0] _FUTILITY_MARGIN = [0, 150, 300, 500] # indexed by depth def negamax(board, alpha, beta, depth, ply, killers, history, stop_time): _NODES[0] += 1 if time.time() >= stop_time: return 0 # Repetition / 50-move draw if ply > 0 and (is_repetition(board) or board.halfmove >= 100): return 0 # TT lookup tt_move = None entry = TT[board.zobrist % TT_SIZE] if entry is not None and entry[0] == board.zobrist: _, tt_depth, tt_flag, tt_score, tt_move = entry if tt_depth >= depth: if tt_flag == TT_EXACT: return tt_score elif tt_flag == TT_LOWER and tt_score >= beta: return tt_score elif tt_flag == TT_UPPER and tt_score <= alpha: return tt_score if depth <= 0: return quiescence(board, alpha, beta, ply) in_check = board.in_check() # Reverse futility pruning (static null move) if not in_check and depth <= 3 and ply > 0: static_eval = evaluate(board) if static_eval - _FUTILITY_MARGIN[depth] >= beta: return static_eval # Null move pruning if depth >= 3 and not in_check and ply > 0: has_pieces = any(board.pieces[board.side][pt] for pt in (N, B, R, Q)) if has_pieces: make_null_move(board) R_reduction = 3 if depth >= 6 else 2 null_score = -negamax(board, -beta, -beta + 1, depth - 1 - R_reduction, ply + 1, killers, history, stop_time) unmake_null_move(board) if null_score >= beta: return beta moves = generate_legal_moves(board) if not moves: if in_check: return -(MATE_SCORE - ply) return 0 # stalemate ply_killers = killers[ply] if ply < len(killers) else [] # Sort moves by score descending moves.sort(key=lambda m: score_move(m, tt_move, board, ply_killers, history), reverse=True) original_alpha = alpha best_score = -INF best_move = moves[0] for i, move in enumerate(moves): make_move(board, move) # Check extension gives_check = board.in_check() ext = 1 if gives_check else 0 new_depth = depth - 1 + ext if i == 0: # PVS: first move searched with full window score = -negamax(board, -beta, -alpha, new_depth, ply + 1, killers, history, stop_time) else: # Determine reduction for LMR if (i >= 4 and depth >= 3 and not is_capture(move) and not is_promo(move) and not in_check and not gives_check): R_lmr = max(1, int(math.log(depth) * math.log(i + 1) / 2.0)) search_depth = new_depth - R_lmr else: search_depth = new_depth # PVS: null window for all moves after the first score = -negamax(board, -alpha - 1, -alpha, search_depth, ply + 1, killers, history, stop_time) # Re-search at full depth if null window fails high if score > alpha: score = -negamax(board, -beta, -alpha, new_depth, ply + 1, killers, history, stop_time) unmake_move(board) if score > best_score: best_score = score best_move = move if score > alpha: alpha = score if alpha >= beta: # Update killers and history heuristics if not is_capture(move): if ply < len(killers): killers[ply] = [move] + [m for m in killers[ply] if m != move][:1] frm = move & 63 to = (move >> 6) & 63 history[board.side][frm][to] = min( history[board.side][frm][to] + depth * depth, 1_000_000 ) break # Store result in TT if best_score <= original_alpha: flag = TT_UPPER elif best_score >= beta: flag = TT_LOWER else: flag = TT_EXACT TT[board.zobrist % TT_SIZE] = (board.zobrist, depth, flag, best_score, best_move) return best_score # --------------------------------------------------------------------------- # Iterative deepening with aspiration windows # --------------------------------------------------------------------------- def search(board, movetime=4500): stop_time = time.time() + movetime / 1000.0 search_start = time.time() killers = [[] for _ in range(64)] history = [[[0] * 64 for _ in range(64)] for _ in range(2)] _NODES[0] = 0 best_move = None prev_score = 0 for depth in range(1, 100): if time.time() >= stop_time: break if depth <= 4: score = negamax(board, -INF, INF, depth, 0, killers, history, stop_time) else: delta = 50 alpha = prev_score - delta beta = prev_score + delta while True: score = negamax(board, alpha, beta, depth, 0, killers, history, stop_time) if time.time() >= stop_time: break if score <= alpha: alpha -= delta delta *= 2 elif score >= beta: beta += delta delta *= 2 else: break if time.time() >= stop_time: break # Retrieve best move from TT entry = TT[board.zobrist % TT_SIZE] if entry is not None and entry[0] == board.zobrist and entry[4] is not None: best_move = entry[4] prev_score = score elapsed = max(1, int((time.time() - search_start) * 1000)) nps = int(_NODES[0] / max(elapsed, 1) * 1000) info = f"info depth {depth} score cp {score} nodes {_NODES[0]} nps {nps} time {elapsed}" print(info, file=sys.stderr if _FEN_MODE else sys.stdout, flush=True) if abs(score) >= MATE_SCORE - 100: break return best_move # --------------------------------------------------------------------------- # FEN loop (platform mode) # --------------------------------------------------------------------------- def _fen_loop(board, first_fen): def handle(fen): board.set_fen(fen) best = search(board, 4800) if best is None: legal = generate_legal_moves(board) best = legal[0] if legal else None if best is not None: print(move_to_uci(best), flush=True) else: print("0000", flush=True) handle(first_fen) for line in sys.stdin: fen = line.strip() if fen: handle(fen) # --------------------------------------------------------------------------- # UCI loop # --------------------------------------------------------------------------- def main(): board = Board() first_line = sys.stdin.readline() if not first_line: return first_line = first_line.strip() # Auto-detect platform FEN mode: FEN strings always contain '/' if '/' in first_line: global _FEN_MODE _FEN_MODE = True _fen_loop(board, first_line) return board.set_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1") lines = [first_line] def next_line(): if lines: return lines.pop(0) return sys.stdin.readline() while True: line = next_line() if not line: break cmd = line.strip().split() if not cmd: continue if cmd[0] == 'uci': print("id name ChessAgent") print("id author Agent") print("uciok", flush=True) elif cmd[0] == 'isready': print("readyok", flush=True) elif cmd[0] == 'ucinewgame': board.set_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1") global TT TT = [None] * TT_SIZE elif cmd[0] == 'position': if 'startpos' in cmd: board.set_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1") moves_idx = cmd.index('moves') + 1 if 'moves' in cmd else len(cmd) elif 'fen' in cmd: fen_idx = cmd.index('fen') + 1 if 'moves' in cmd: moves_idx = cmd.index('moves') + 1 fen_end = moves_idx - 1 else: moves_idx = len(cmd) fen_end = len(cmd) fen = ' '.join(cmd[fen_idx:fen_end]) board.set_fen(fen) else: moves_idx = len(cmd) for uci in cmd[moves_idx:]: move = uci_to_move(uci, board) if move is not None: make_move(board, move) elif cmd[0] == 'go': movetime = 4500 # default 4.5s if 'movetime' in cmd: idx = cmd.index('movetime') movetime = max(100, int(cmd[idx + 1]) - 100) elif board.side == WHITE and 'wtime' in cmd: idx = cmd.index('wtime') wtime = int(cmd[idx + 1]) movetime = min(4500, max(100, wtime // 20)) elif board.side == BLACK and 'btime' in cmd: idx = cmd.index('btime') btime = int(cmd[idx + 1]) movetime = min(4500, max(100, btime // 20)) best = search(board, movetime) if best is None: legal = generate_legal_moves(board) best = legal[0] if legal else None if best is not None: print(f"bestmove {move_to_uci(best)}", flush=True) else: print("bestmove 0000", flush=True) elif cmd[0] == 'quit': break if __name__ == '__main__': main()