#!/usr/bin/env python3 """ Chess agent - reads FEN from stdin, writes UCI move to stdout. Persistent process: loops on stdin so the worker can reuse it. Techniques: - 0x88 mailbox board (fast move gen without bitboards) - Iterative deepening alpha-beta with aspiration windows - Transposition table (Zobrist hashing) - Principal variation search (PVS) - Quiescence search with delta pruning - Null-move pruning - Late move reductions (LMR) - Futility pruning - Move ordering: TT move, MVV-LVA captures, killers, history heuristic - Evaluation: material + PST + mobility + king safety + pawn structure """ import sys import random import time # ---------- Board representation (0x88) ---------- # Squares 0..127, valid when (sq & 0x88) == 0 # a1 = 0, h1 = 7, a8 = 112, h8 = 119 EMPTY = 0 WP, WN, WB, WR, WQ, WK = 1, 2, 3, 4, 5, 6 BP, BN, BB, BR, BQ, BK = 9, 10, 11, 12, 13, 14 PIECE_CHAR = ".PNBRQK??pnbrqk" CHAR_PIECE = {c: i for i, c in enumerate(PIECE_CHAR) if c != "?"} WHITE, BLACK = 0, 1 def color_of(p): return BLACK if p >= 8 else WHITE def is_white(p): return 0 < p < 8 def is_black(p): return p >= 8 def piece_type(p): return p & 7 # Directions N, S, E, W = 16, -16, 1, -1 NE, NW, SE, SW = 17, 15, -15, -17 KNIGHT_DIRS = (-33, -31, -18, -14, 14, 18, 31, 33) BISHOP_DIRS = (NE, NW, SE, SW) ROOK_DIRS = (N, S, E, W) KING_DIRS = (N, S, E, W, NE, NW, SE, SW) # Castling rights bits CR_WK, CR_WQ, CR_BK, CR_BQ = 1, 2, 4, 8 # ---------- Piece-square tables (middlegame) ---------- # From white's perspective, a1 at index 0, h8 at 63 — we'll map to 0x88. PST_PAWN_MG = [ 0, 0, 0, 0, 0, 0, 0, 0, 5, 10, 10, -20, -20, 10, 10, 5, 5, -5, -10, 0, 0, -10, -5, 5, 0, 0, 0, 20, 20, 0, 0, 0, 5, 5, 10, 25, 25, 10, 5, 5, 10, 10, 20, 30, 30, 20, 10, 10, 50, 50, 50, 50, 50, 50, 50, 50, 0, 0, 0, 0, 0, 0, 0, 0, ] PST_PAWN_EG = [ 0, 0, 0, 0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 20, 20, 20, 20, 20, 20, 20, 20, 35, 35, 35, 35, 35, 35, 35, 35, 60, 60, 60, 60, 60, 60, 60, 60, 100, 100, 100, 100, 100, 100, 100, 100, 0, 0, 0, 0, 0, 0, 0, 0, ] PST_KNIGHT = [ -50,-40,-30,-30,-30,-30,-40,-50, -40,-20, 0, 5, 5, 0,-20,-40, -30, 5, 10, 15, 15, 10, 5,-30, -30, 0, 15, 20, 20, 15, 0,-30, -30, 5, 15, 20, 20, 15, 5,-30, -30, 0, 10, 15, 15, 10, 0,-30, -40,-20, 0, 0, 0, 0,-20,-40, -50,-40,-30,-30,-30,-30,-40,-50, ] PST_BISHOP = [ -20,-10,-10,-10,-10,-10,-10,-20, -10, 5, 0, 0, 0, 0, 5,-10, -10, 10, 10, 10, 10, 10, 10,-10, -10, 0, 10, 10, 10, 10, 0,-10, -10, 5, 5, 10, 10, 5, 5,-10, -10, 0, 5, 10, 10, 5, 0,-10, -10, 0, 0, 0, 0, 0, 0,-10, -20,-10,-10,-10,-10,-10,-10,-20, ] PST_ROOK = [ 0, 0, 5, 10, 10, 5, 0, 0, -5, 0, 0, 0, 0, 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, -5, 5, 10, 10, 10, 10, 10, 10, 5, 0, 0, 0, 0, 0, 0, 0, 0, ] PST_QUEEN = [ -20,-10,-10, -5, -5,-10,-10,-20, -10, 0, 5, 0, 0, 0, 0,-10, -10, 5, 5, 5, 5, 5, 0,-10, 0, 0, 5, 5, 5, 5, 0, -5, -5, 0, 5, 5, 5, 5, 0, -5, -10, 0, 5, 5, 5, 5, 0,-10, -10, 0, 0, 0, 0, 0, 0,-10, -20,-10,-10, -5, -5,-10,-10,-20, ] PST_KING_MG = [ 20, 30, 10, 0, 0, 10, 30, 20, 20, 20, 0, 0, 0, 0, 20, 20, -10,-20,-20,-20,-20,-20,-20,-10, -20,-30,-30,-40,-40,-30,-30,-20, -30,-40,-40,-50,-50,-40,-40,-30, -30,-40,-40,-50,-50,-40,-40,-30, -30,-40,-40,-50,-50,-40,-40,-30, -30,-40,-40,-50,-50,-40,-40,-30, ] PST_KING_EG = [ -50,-30,-30,-30,-30,-30,-30,-50, -30,-30, 0, 0, 0, 0,-30,-30, -30,-10, 20, 30, 30, 20,-10,-30, -30,-10, 30, 40, 40, 30,-10,-30, -30,-10, 30, 40, 40, 30,-10,-30, -30,-10, 20, 30, 30, 20,-10,-30, -30,-20,-10, 0, 0,-10,-20,-30, -50,-40,-30,-20,-20,-30,-40,-50, ] PIECE_VALUE_MG = [0, 82, 337, 365, 477, 1025, 20000, 0, 0, 82, 337, 365, 477, 1025, 20000, 0] PIECE_VALUE_EG = [0, 94, 281, 297, 512, 936, 20000, 0, 0, 94, 281, 297, 512, 936, 20000, 0] # Phase weights for tapered eval PHASE_W = [0, 0, 1, 1, 2, 4, 0, 0, 0, 0, 1, 1, 2, 4, 0, 0] MAX_PHASE = 24 # 4 knights + 4 bishops + 4 rooks*2 + 2 queens*4 def sq_to_64(sq): # 0x88 square to 0..63 (file + rank*8) return (sq & 7) + ((sq >> 4) << 3) def flip64(i): return i ^ 56 # Precompute 0x88 -> PST lookups for each piece type, each color PST_MG = [[0]*128 for _ in range(16)] PST_EG = [[0]*128 for _ in range(16)] def _init_pst(): tables_mg = { WP: PST_PAWN_MG, WN: PST_KNIGHT, WB: PST_BISHOP, WR: PST_ROOK, WQ: PST_QUEEN, WK: PST_KING_MG, } tables_eg = { WP: PST_PAWN_EG, WN: PST_KNIGHT, WB: PST_BISHOP, WR: PST_ROOK, WQ: PST_QUEEN, WK: PST_KING_EG, } for sq in range(128): if sq & 0x88: continue i64 = sq_to_64(sq) for p, t in tables_mg.items(): PST_MG[p][sq] = t[i64] bp = p | 8 PST_MG[bp][sq] = -t[flip64(i64)] for p, t in tables_eg.items(): PST_EG[p][sq] = t[i64] bp = p | 8 PST_EG[bp][sq] = -t[flip64(i64)] _init_pst() # ---------- Zobrist hashing ---------- random.seed(0xC0FFEE) ZOB_PIECE = [[random.getrandbits(64) for _ in range(128)] for _ in range(16)] ZOB_SIDE = random.getrandbits(64) ZOB_CASTLE = [random.getrandbits(64) for _ in range(16)] ZOB_EP = [random.getrandbits(64) for _ in range(128)] # ---------- Board state ---------- class Board: __slots__ = ("sq", "side", "castle", "ep", "halfmove", "fullmove", "king_sq", "hash", "history") def __init__(self): self.sq = [0]*128 self.side = WHITE self.castle = 0 self.ep = -1 self.halfmove = 0 self.fullmove = 1 self.king_sq = [-1, -1] self.hash = 0 self.history = [] def compute_hash(self): h = 0 for s in range(128): if s & 0x88: continue p = self.sq[s] if p: h ^= ZOB_PIECE[p][s] if self.side == BLACK: h ^= ZOB_SIDE h ^= ZOB_CASTLE[self.castle] if self.ep >= 0: h ^= ZOB_EP[self.ep] self.hash = h # File/rank helpers def sq_file(s): return s & 7 def sq_rank(s): return s >> 4 def sq_from_name(name): f = ord(name[0]) - ord('a') r = int(name[1]) - 1 return (r << 4) | f def sq_to_name(s): return chr(ord('a') + sq_file(s)) + str(sq_rank(s) + 1) # ---------- FEN parsing ---------- def parse_fen(fen): b = Board() parts = fen.strip().split() while len(parts) < 6: parts.append("-" if len(parts) < 4 else "0" if len(parts) < 5 else "1") placement, stm, castle, ep, half, full = parts[:6] rank = 7 file = 0 for c in placement: if c == '/': rank -= 1 file = 0 elif c.isdigit(): file += int(c) else: s = (rank << 4) | file p = CHAR_PIECE[c] b.sq[s] = p if p == WK: b.king_sq[WHITE] = s elif p == BK: b.king_sq[BLACK] = s file += 1 b.side = WHITE if stm == 'w' else BLACK b.castle = 0 if 'K' in castle: b.castle |= CR_WK if 'Q' in castle: b.castle |= CR_WQ if 'k' in castle: b.castle |= CR_BK if 'q' in castle: b.castle |= CR_BQ b.ep = sq_from_name(ep) if ep != '-' else -1 try: b.halfmove = int(half) except: b.halfmove = 0 try: b.fullmove = int(full) except: b.fullmove = 1 b.compute_hash() return b # ---------- Move encoding ---------- # move = (from << 14) | (to << 7) | flags # flags: 0=quiet, 1=capture, 2=double pawn push, 3=ep, 4=castle, # 5=promo-N, 6=promo-B, 7=promo-R, 8=promo-Q, # 9=promo-capture-N, 10=promo-capture-B, 11=promo-capture-R, 12=promo-capture-Q F_QUIET = 0 F_CAP = 1 F_DPP = 2 F_EP = 3 F_CASTLE = 4 F_PN, F_PB, F_PR, F_PQ = 5, 6, 7, 8 F_CPN, F_CPB, F_CPR, F_CPQ = 9, 10, 11, 12 def mk_move(f, t, flag): return (f << 14) | (t << 7) | flag def mv_from(m): return (m >> 14) & 0x7F def mv_to(m): return (m >> 7) & 0x7F def mv_flag(m): return m & 0x7F def is_capture(flag): return flag == F_CAP or flag == F_EP or flag >= F_CPN def is_promo(flag): return flag >= F_PN def promo_piece_white(flag): # Returns white piece for promo flag m = flag if flag <= F_PQ else flag - 4 return [None, None, None, None, None, WN, WB, WR, WQ][m] def move_to_uci(m): f, t, fl = mv_from(m), mv_to(m), mv_flag(m) s = sq_to_name(f) + sq_to_name(t) if is_promo(fl): m2 = fl if fl <= F_PQ else fl - 4 s += "nbrq"[m2 - F_PN] return s # ---------- Attack detection ---------- def sq_attacked(board, sq, by_side): sqs = board.sq if by_side == WHITE: # pawn attacks from white for d in (-15, -17): f = sq + d if not (f & 0x88) and sqs[f] == WP: return True for d in KNIGHT_DIRS: f = sq + d if not (f & 0x88) and sqs[f] == WN: return True for d in KING_DIRS: f = sq + d if not (f & 0x88) and sqs[f] == WK: return True for d in BISHOP_DIRS: f = sq + d while not (f & 0x88): p = sqs[f] if p: if p == WB or p == WQ: return True break f += d for d in ROOK_DIRS: f = sq + d while not (f & 0x88): p = sqs[f] if p: if p == WR or p == WQ: return True break f += d else: for d in (15, 17): f = sq + d if not (f & 0x88) and sqs[f] == BP: return True for d in KNIGHT_DIRS: f = sq + d if not (f & 0x88) and sqs[f] == BN: return True for d in KING_DIRS: f = sq + d if not (f & 0x88) and sqs[f] == BK: return True for d in BISHOP_DIRS: f = sq + d while not (f & 0x88): p = sqs[f] if p: if p == BB or p == BQ: return True break f += d for d in ROOK_DIRS: f = sq + d while not (f & 0x88): p = sqs[f] if p: if p == BR or p == BQ: return True break f += d return False def in_check(board, side=None): if side is None: side = board.side return sq_attacked(board, board.king_sq[side], side ^ 1) # ---------- Move generation ---------- def gen_moves(board, captures_only=False): moves = [] sqs = board.sq side = board.side ep = board.ep if side == WHITE: for s in range(128): if s & 0x88: continue p = sqs[s] if not p or p >= 8: continue if p == WP: # captures for d in (15, 17): t = s + d if t & 0x88: continue tp = sqs[t] if tp and tp >= 8: if sq_rank(t) == 7: for fl in (F_CPQ, F_CPR, F_CPB, F_CPN): moves.append(mk_move(s, t, fl)) else: moves.append(mk_move(s, t, F_CAP)) elif t == ep: moves.append(mk_move(s, t, F_EP)) if captures_only: continue # pushes t = s + 16 if not (t & 0x88) and sqs[t] == 0: if sq_rank(t) == 7: for fl in (F_PQ, F_PR, F_PB, F_PN): moves.append(mk_move(s, t, fl)) else: moves.append(mk_move(s, t, F_QUIET)) if sq_rank(s) == 1: t2 = s + 32 if sqs[t2] == 0: moves.append(mk_move(s, t2, F_DPP)) elif p == WN: for d in KNIGHT_DIRS: t = s + d if t & 0x88: continue tp = sqs[t] if not tp: if not captures_only: moves.append(mk_move(s, t, F_QUIET)) elif tp >= 8: moves.append(mk_move(s, t, F_CAP)) elif p == WK: for d in KING_DIRS: t = s + d if t & 0x88: continue tp = sqs[t] if not tp: if not captures_only: moves.append(mk_move(s, t, F_QUIET)) elif tp >= 8: moves.append(mk_move(s, t, F_CAP)) if not captures_only and s == 4: # e1 if (board.castle & CR_WK) and sqs[5] == 0 and sqs[6] == 0: if not sq_attacked(board, 4, BLACK) and not sq_attacked(board, 5, BLACK) and not sq_attacked(board, 6, BLACK): moves.append(mk_move(4, 6, F_CASTLE)) if (board.castle & CR_WQ) and sqs[3] == 0 and sqs[2] == 0 and sqs[1] == 0: if not sq_attacked(board, 4, BLACK) and not sq_attacked(board, 3, BLACK) and not sq_attacked(board, 2, BLACK): moves.append(mk_move(4, 2, F_CASTLE)) else: # sliders if p == WB: dirs = BISHOP_DIRS elif p == WR: dirs = ROOK_DIRS else: dirs = KING_DIRS # queen for d in dirs: t = s + d while not (t & 0x88): tp = sqs[t] if not tp: if not captures_only: moves.append(mk_move(s, t, F_QUIET)) else: if tp >= 8: moves.append(mk_move(s, t, F_CAP)) break t += d else: for s in range(128): if s & 0x88: continue p = sqs[s] if not p or p < 8: continue if p == BP: for d in (-15, -17): t = s + d if t & 0x88: continue tp = sqs[t] if tp and tp < 8: if sq_rank(t) == 0: for fl in (F_CPQ, F_CPR, F_CPB, F_CPN): moves.append(mk_move(s, t, fl)) else: moves.append(mk_move(s, t, F_CAP)) elif t == ep: moves.append(mk_move(s, t, F_EP)) if captures_only: continue t = s - 16 if not (t & 0x88) and sqs[t] == 0: if sq_rank(t) == 0: for fl in (F_PQ, F_PR, F_PB, F_PN): moves.append(mk_move(s, t, fl)) else: moves.append(mk_move(s, t, F_QUIET)) if sq_rank(s) == 6: t2 = s - 32 if sqs[t2] == 0: moves.append(mk_move(s, t2, F_DPP)) elif p == BN: for d in KNIGHT_DIRS: t = s + d if t & 0x88: continue tp = sqs[t] if not tp: if not captures_only: moves.append(mk_move(s, t, F_QUIET)) elif tp < 8: moves.append(mk_move(s, t, F_CAP)) elif p == BK: for d in KING_DIRS: t = s + d if t & 0x88: continue tp = sqs[t] if not tp: if not captures_only: moves.append(mk_move(s, t, F_QUIET)) elif tp < 8: moves.append(mk_move(s, t, F_CAP)) if not captures_only and s == 116: # e8 if (board.castle & CR_BK) and sqs[117] == 0 and sqs[118] == 0: if not sq_attacked(board, 116, WHITE) and not sq_attacked(board, 117, WHITE) and not sq_attacked(board, 118, WHITE): moves.append(mk_move(116, 118, F_CASTLE)) if (board.castle & CR_BQ) and sqs[115] == 0 and sqs[114] == 0 and sqs[113] == 0: if not sq_attacked(board, 116, WHITE) and not sq_attacked(board, 115, WHITE) and not sq_attacked(board, 114, WHITE): moves.append(mk_move(116, 114, F_CASTLE)) else: if p == BB: dirs = BISHOP_DIRS elif p == BR: dirs = ROOK_DIRS else: dirs = KING_DIRS for d in dirs: t = s + d while not (t & 0x88): tp = sqs[t] if not tp: if not captures_only: moves.append(mk_move(s, t, F_QUIET)) else: if tp < 8: moves.append(mk_move(s, t, F_CAP)) break t += d return moves # ---------- Make / unmake ---------- # Castling rights update mask per square CASTLE_MASK = [15]*128 CASTLE_MASK[0] = 15 ^ CR_WQ # a1 CASTLE_MASK[4] = 15 ^ (CR_WK | CR_WQ) # e1 CASTLE_MASK[7] = 15 ^ CR_WK # h1 CASTLE_MASK[112] = 15 ^ CR_BQ # a8 CASTLE_MASK[116] = 15 ^ (CR_BK | CR_BQ) # e8 CASTLE_MASK[119] = 15 ^ CR_BK # h8 def make_move(board, m): f = mv_from(m); t = mv_to(m); fl = mv_flag(m) sqs = board.sq piece = sqs[f] captured = sqs[t] undo = (m, captured, board.castle, board.ep, board.halfmove, board.hash) board.history.append(undo) h = board.hash # remove piece from f h ^= ZOB_PIECE[piece][f] # ep old if board.ep >= 0: h ^= ZOB_EP[board.ep] # castle old h ^= ZOB_CASTLE[board.castle] board.halfmove += 1 if piece_type(piece) == WP or captured: board.halfmove = 0 if fl == F_EP: cap_sq = t - 16 if board.side == WHITE else t + 16 cap_piece = sqs[cap_sq] h ^= ZOB_PIECE[cap_piece][cap_sq] sqs[cap_sq] = 0 captured = cap_piece # store for unmake via undo_extra # rewrite undo with ep capture info board.history[-1] = (m, cap_piece, undo[2], undo[3], undo[4], undo[5]) elif captured: h ^= ZOB_PIECE[captured][t] # move piece if is_promo(fl): # flag maps to piece type if fl == F_PN or fl == F_CPN: new_p = WN elif fl == F_PB or fl == F_CPB: new_p = WB elif fl == F_PR or fl == F_CPR: new_p = WR else: new_p = WQ if board.side == BLACK: new_p |= 8 sqs[t] = new_p sqs[f] = 0 h ^= ZOB_PIECE[new_p][t] else: sqs[t] = piece sqs[f] = 0 h ^= ZOB_PIECE[piece][t] # castle: move rook if fl == F_CASTLE: if t == 6: sqs[5] = sqs[7]; sqs[7] = 0 h ^= ZOB_PIECE[WR][7]; h ^= ZOB_PIECE[WR][5] elif t == 2: sqs[3] = sqs[0]; sqs[0] = 0 h ^= ZOB_PIECE[WR][0]; h ^= ZOB_PIECE[WR][3] elif t == 118: sqs[117] = sqs[119]; sqs[119] = 0 h ^= ZOB_PIECE[BR][119]; h ^= ZOB_PIECE[BR][117] elif t == 114: sqs[115] = sqs[112]; sqs[112] = 0 h ^= ZOB_PIECE[BR][112]; h ^= ZOB_PIECE[BR][115] # update king square pt = piece_type(piece) if pt == WK: board.king_sq[board.side] = t # castle rights board.castle &= CASTLE_MASK[f] & CASTLE_MASK[t] h ^= ZOB_CASTLE[board.castle] # ep new if fl == F_DPP: new_ep = (f + t) >> 1 board.ep = new_ep h ^= ZOB_EP[new_ep] else: board.ep = -1 # side board.side ^= 1 h ^= ZOB_SIDE board.hash = h def unmake_move(board): m, captured, castle, ep, half, hsh = board.history.pop() f = mv_from(m); t = mv_to(m); fl = mv_flag(m) sqs = board.sq board.side ^= 1 board.castle = castle board.ep = ep board.halfmove = half board.hash = hsh moved = sqs[t] if is_promo(fl): moved = WP if board.side == WHITE else BP sqs[f] = moved sqs[t] = 0 if fl == F_EP: cap_sq = t - 16 if board.side == WHITE else t + 16 sqs[cap_sq] = captured elif captured: sqs[t] = captured if fl == F_CASTLE: if t == 6: sqs[7] = sqs[5]; sqs[5] = 0 elif t == 2: sqs[0] = sqs[3]; sqs[3] = 0 elif t == 118: sqs[119] = sqs[117]; sqs[117] = 0 elif t == 114: sqs[112] = sqs[115]; sqs[115] = 0 if piece_type(moved) == WK: board.king_sq[board.side] = f def make_null(board): undo = (board.ep, board.hash) h = board.hash if board.ep >= 0: h ^= ZOB_EP[board.ep] board.ep = -1 board.side ^= 1 h ^= ZOB_SIDE board.hash = h return undo def unmake_null(board, undo): board.ep, board.hash = undo board.side ^= 1 # ---------- Evaluation ---------- def evaluate(board): mg = 0; eg = 0; phase = 0 sqs = board.sq white_pawns_on_file = [0]*8 black_pawns_on_file = [0]*8 white_pawn_ranks = [[] for _ in range(8)] black_pawn_ranks = [[] for _ in range(8)] for s in range(128): if s & 0x88: continue p = sqs[s] if not p: continue mg += PIECE_VALUE_MG[p] * (1 if p < 8 else -1) eg += PIECE_VALUE_EG[p] * (1 if p < 8 else -1) mg += PST_MG[p][s] eg += PST_EG[p][s] phase += PHASE_W[p] pt = piece_type(p) if pt == WP: f = sq_file(s); r = sq_rank(s) if p == WP: white_pawns_on_file[f] += 1 white_pawn_ranks[f].append(r) else: black_pawns_on_file[f] += 1 black_pawn_ranks[f].append(r) # Pawn structure: doubled, isolated, passed for f in range(8): if white_pawns_on_file[f] > 1: mg -= 10 * (white_pawns_on_file[f] - 1) eg -= 20 * (white_pawns_on_file[f] - 1) if black_pawns_on_file[f] > 1: mg += 10 * (black_pawns_on_file[f] - 1) eg += 20 * (black_pawns_on_file[f] - 1) left = white_pawns_on_file[f-1] if f > 0 else 0 right = white_pawns_on_file[f+1] if f < 7 else 0 if white_pawns_on_file[f] and not left and not right: mg -= 15; eg -= 20 left = black_pawns_on_file[f-1] if f > 0 else 0 right = black_pawns_on_file[f+1] if f < 7 else 0 if black_pawns_on_file[f] and not left and not right: mg += 15; eg += 20 # passed pawns for r in white_pawn_ranks[f]: blocked = False for ff in (f-1, f, f+1): if 0 <= ff < 8: for br in black_pawn_ranks[ff]: if br > r: blocked = True; break if blocked: break if not blocked: bonus = [0, 5, 10, 20, 35, 60, 100, 0][r] mg += bonus // 2 eg += bonus for r in black_pawn_ranks[f]: blocked = False for ff in (f-1, f, f+1): if 0 <= ff < 8: for wr in white_pawn_ranks[ff]: if wr < r: blocked = True; break if blocked: break if not blocked: bonus = [0, 100, 60, 35, 20, 10, 5, 0][r] mg -= bonus // 2 eg -= bonus # Bishop pair wb = 0; bb = 0 for s in range(128): if s & 0x88: continue if sqs[s] == WB: wb += 1 elif sqs[s] == BB: bb += 1 if wb >= 2: mg += 30; eg += 50 if bb >= 2: mg -= 30; eg -= 50 # King safety: pawn shield in middlegame wk = board.king_sq[WHITE] bk = board.king_sq[BLACK] if wk >= 0: wkf = sq_file(wk) shield = 0 for df in (-1, 0, 1): ff = wkf + df if 0 <= ff < 8: if sqs[(1 << 4) | ff] == WP: shield += 1 elif sqs[(2 << 4) | ff] == WP: shield += 1 mg += shield * 10 if bk >= 0: bkf = sq_file(bk) shield = 0 for df in (-1, 0, 1): ff = bkf + df if 0 <= ff < 8: if sqs[(6 << 4) | ff] == BP: shield += 1 elif sqs[(5 << 4) | ff] == BP: shield += 1 mg -= shield * 10 if phase > MAX_PHASE: phase = MAX_PHASE score = (mg * phase + eg * (MAX_PHASE - phase)) // MAX_PHASE return score if board.side == WHITE else -score # ---------- Search ---------- INF = 1_000_000 MATE = 100_000 MAX_PLY = 64 # Transposition table TT_EXACT, TT_LOWER, TT_UPPER = 0, 1, 2 TT_SIZE = 1 << 19 # ~500k entries tt = [None] * TT_SIZE def tt_probe(hash_): entry = tt[hash_ & (TT_SIZE - 1)] if entry and entry[0] == hash_: return entry return None def tt_store(hash_, depth, score, flag, move): idx = hash_ & (TT_SIZE - 1) existing = tt[idx] if existing is None or existing[1] <= depth or existing[0] != hash_: tt[idx] = (hash_, depth, score, flag, move) # Killer moves & history killers = [[0, 0] for _ in range(MAX_PLY)] history = [[0]*128 for _ in range(16)] class SearchAbort(Exception): pass class Searcher: def __init__(self): self.nodes = 0 self.start_time = 0 self.time_limit = 0 self.stop = False self.best_move_root = 0 self.ply = 0 def check_time(self): if self.nodes & 4095 == 0: if time.time() - self.start_time > self.time_limit: self.stop = True raise SearchAbort() def score_move(self, board, m, tt_move, ply): if m == tt_move: return 10_000_000 fl = mv_flag(m) if is_capture(fl): f = mv_from(m); t = mv_to(m) victim = board.sq[t] if fl == F_EP: victim = WP if board.side == BLACK else BP attacker = board.sq[f] return 1_000_000 + PIECE_VALUE_MG[victim & 7] * 10 - PIECE_VALUE_MG[attacker & 7] if is_promo(fl): return 900_000 if ply < MAX_PLY: if m == killers[ply][0]: return 800_000 if m == killers[ply][1]: return 700_000 f = mv_from(m); t = mv_to(m) return history[board.sq[f]][t] def quiesce(self, board, alpha, beta): self.nodes += 1 self.check_time() stand_pat = evaluate(board) if stand_pat >= beta: return beta if stand_pat > alpha: alpha = stand_pat # delta pruning BIG_DELTA = 975 if stand_pat + BIG_DELTA < alpha: return alpha moves = gen_moves(board, captures_only=True) scored = [(self.score_move(board, m, 0, 0), m) for m in moves] scored.sort(reverse=True) for _, m in scored: # SEE-lite via delta fl = mv_flag(m) t = mv_to(m) victim = board.sq[t] if fl == F_EP: victim_val = PIECE_VALUE_MG[WP] else: victim_val = PIECE_VALUE_MG[victim & 7] if victim else 0 if stand_pat + victim_val + 200 < alpha and not is_promo(fl): continue make_move(board, m) if in_check(board, board.side ^ 1): unmake_move(board) continue score = -self.quiesce(board, -beta, -alpha) unmake_move(board) if score >= beta: return beta if score > alpha: alpha = score return alpha def search(self, board, depth, alpha, beta, ply, allow_null=True): self.nodes += 1 self.check_time() if ply > 0 and board.halfmove >= 100: return 0 # Repetition if ply > 0: cnt = 0 for u in board.history: if u[5] == board.hash: cnt += 1 if cnt >= 1: return 0 in_chk = in_check(board) if in_chk: depth += 1 if depth <= 0: return self.quiesce(board, alpha, beta) # TT probe tt_move = 0 entry = tt_probe(board.hash) if entry: _, d, s, fl, mv = entry tt_move = mv if ply > 0 and d >= depth: if fl == TT_EXACT: return s if fl == TT_LOWER and s >= beta: return s if fl == TT_UPPER and s <= alpha: return s static_eval = evaluate(board) if not in_chk else 0 # Null move pruning if (allow_null and not in_chk and depth >= 3 and ply > 0 and static_eval >= beta): # Check we have non-pawn material has_material = False for s in range(128): if s & 0x88: continue p = board.sq[s] if p and piece_type(p) > 1 and piece_type(p) < 6: if (p < 8) == (board.side == WHITE): has_material = True; break if has_material: undo = make_null(board) R = 2 + depth // 4 score = -self.search(board, depth - 1 - R, -beta, -beta + 1, ply + 1, False) unmake_null(board, undo) if score >= beta: return beta # Futility pruning threshold futility = False if depth <= 3 and not in_chk and abs(alpha) < MATE - 1000: margins = [0, 100, 300, 500] if static_eval + margins[depth] <= alpha: futility = True moves = gen_moves(board) scored = [(self.score_move(board, m, tt_move, ply), m) for m in moves] scored.sort(reverse=True) best_score = -INF best_move = 0 legal_count = 0 orig_alpha = alpha tried_quiets = [] for idx, (_, m) in enumerate(scored): fl = mv_flag(m) is_tactical = is_capture(fl) or is_promo(fl) or in_chk make_move(board, m) if in_check(board, board.side ^ 1): unmake_move(board) continue gives_check = in_check(board) legal_count += 1 # Futility if futility and legal_count > 1 and not is_tactical and not gives_check: unmake_move(board) continue # LMR reduction = 0 if depth >= 3 and legal_count > 3 and not is_tactical and not gives_check: reduction = 1 if legal_count > 6: reduction = 2 if legal_count == 1: score = -self.search(board, depth - 1, -beta, -alpha, ply + 1) else: score = -self.search(board, depth - 1 - reduction, -alpha - 1, -alpha, ply + 1) if score > alpha and reduction > 0: score = -self.search(board, depth - 1, -alpha - 1, -alpha, ply + 1) if score > alpha and score < beta: score = -self.search(board, depth - 1, -beta, -alpha, ply + 1) unmake_move(board) if score > best_score: best_score = score best_move = m if ply == 0: self.best_move_root = m if score > alpha: alpha = score if score >= beta: # Killer & history if not is_capture(fl) and not is_promo(fl): if ply < MAX_PLY: if killers[ply][0] != m: killers[ply][1] = killers[ply][0] killers[ply][0] = m f = mv_from(m); t = mv_to(m) history[board.sq[f]][t] += depth * depth for qm in tried_quiets: qf = mv_from(qm); qt = mv_to(qm) history[board.sq[qf]][qt] -= depth tt_store(board.hash, depth, beta, TT_LOWER, m) return beta if not is_capture(fl) and not is_promo(fl): tried_quiets.append(m) if legal_count == 0: if in_chk: return -MATE + ply return 0 if best_score > orig_alpha: tt_store(board.hash, depth, best_score, TT_EXACT, best_move) else: tt_store(board.hash, depth, best_score, TT_UPPER, best_move) return best_score def go(self, board, time_limit): self.nodes = 0 self.start_time = time.time() self.time_limit = time_limit self.stop = False self.best_move_root = 0 # Clear killers for this search for i in range(MAX_PLY): killers[i][0] = 0; killers[i][1] = 0 # Soft-decay history for i in range(16): for j in range(128): history[i][j] //= 4 # Get a legal move first, no matter what legal = [] for m in gen_moves(board): make_move(board, m) if not in_check(board, board.side ^ 1): legal.append(m) unmake_move(board) if not legal: return 0 self.best_move_root = legal[0] best_score = 0 try: for depth in range(1, 64): # Aspiration window if depth >= 4: window = 50 alpha = best_score - window beta = best_score + window while True: score = self.search(board, depth, alpha, beta, 0) if self.stop: break if score <= alpha: alpha -= window; window *= 2 elif score >= beta: beta += window; window *= 2 else: best_score = score break if window > 1000: score = self.search(board, depth, -INF, INF, 0) if not self.stop: best_score = score break else: score = self.search(board, depth, -INF, INF, 0) if not self.stop: best_score = score if self.stop: break # If we've used more than half our time, probably won't finish next iter elapsed = time.time() - self.start_time if elapsed > self.time_limit * 0.5: break except SearchAbort: pass return self.best_move_root # ---------- Main loop ---------- def main(): searcher = Searcher() for line in sys.stdin: line = line.strip() if not line: continue try: board = parse_fen(line) # Use ~4.5s to leave safety margin move = searcher.go(board, 4.5) if move == 0: # No legal moves — shouldn't normally happen; fallback print("0000", flush=True) else: print(move_to_uci(move), flush=True) except Exception as e: # Last-ditch: try to emit any legal move try: board = parse_fen(line) for m in gen_moves(board): make_move(board, m) if not in_check(board, board.side ^ 1): unmake_move(board) print(move_to_uci(m), flush=True) break unmake_move(board) else: print("0000", flush=True) except Exception: print("0000", flush=True) if __name__ == "__main__": main()