import sys, time, random from array import array WHITE = 0 BLACK = 1 INF = 10**9 MATE = 30000 EMPTY = '.' FILES = 'abcdefgh' RANKS = '12345678' WK, WQ, BK, BQ = 1, 2, 4, 8 PIECES = 'PNBRQKpnbrqk' PIECE_TO_INDEX = {p: i for i, p in enumerate(PIECES)} PIECE_VALUES = { 'P': 100, 'N': 320, 'B': 335, 'R': 500, 'Q': 900, 'K': 0, 'p': 100, 'n': 320, 'b': 335, 'r': 500, 'q': 900, 'k': 0, } PHASE_WEIGHT = {'N':1, 'B':1, 'R':2, 'Q':4, 'n':1, 'b':1, 'r':2, 'q':4} KNIGHT_DIRS = (-33, -31, -18, -14, 14, 18, 31, 33) BISHOP_DIRS = (-17, -15, 15, 17) ROOK_DIRS = (-16, -1, 1, 16) QUEEN_DIRS = BISHOP_DIRS + ROOK_DIRS KING_DIRS = QUEEN_DIRS PROMO_NONE = 0 PROMO_N = 1 PROMO_B = 2 PROMO_R = 3 PROMO_Q = 4 FLAG_NONE = 0 FLAG_EP = 1 FLAG_CASTLE = 2 FLAG_DOUBLE = 4 PROMO_CHARS_W = {PROMO_N:'N', PROMO_B:'B', PROMO_R:'R', PROMO_Q:'Q'} PROMO_CHARS_B = {PROMO_N:'n', PROMO_B:'b', PROMO_R:'r', PROMO_Q:'q'} PROMO_UCI = {PROMO_N:'n', PROMO_B:'b', PROMO_R:'r', PROMO_Q:'q'} def encode_move(frm, to, promo=0, flags=0): return frm | (to << 7) | (promo << 14) | (flags << 17) def move_from(m): return m & 0x7F def move_to(m): return (m >> 7) & 0x7F def move_promo(m): return (m >> 14) & 0x7 def move_flags(m): return (m >> 17) & 0x7 def square_name(sq): return FILES[sq & 7] + RANKS[sq >> 4] def parse_square(s): if s == '-' or len(s) != 2: return -1 file = ord(s[0]) - 97 rank = ord(s[1]) - 49 if not (0 <= file < 8 and 0 <= rank < 8): return -1 return rank * 16 + file def move_to_uci(m): u = square_name(move_from(m)) + square_name(move_to(m)) p = move_promo(m) if p: u += PROMO_UCI[p] return u def color_of(piece): if piece == EMPTY: return -1 return WHITE if 'A' <= piece <= 'Z' else BLACK def piece_type(piece): return piece.upper() def mirror_rank(rank): return 7 - rank # Zobrist _rng = random.Random(20260414) Z_PIECE = [[_rng.getrandbits(64) for _ in range(128)] for _ in range(12)] Z_CASTLE = [_rng.getrandbits(64) for _ in range(16)] Z_EP = [_rng.getrandbits(64) for _ in range(8)] Z_SIDE = _rng.getrandbits(64) # Principal variation / TT flags EXACT = 0 LOWER = 1 UPPER = 2 # Piece-square heuristics (formula-based, compact and original) def center_score(file, rank): df = abs(file - 3.5) dr = abs(rank - 3.5) return int(14 - 4 * (df + dr)) def manhattan_from_center(file, rank): return abs(file - 3.5) + abs(rank - 3.5) def mg_psqt(piece, sq): file = sq & 7 rank = sq >> 4 if piece.islower(): rank = 7 - rank pt = piece.upper() c = center_score(file, rank) if pt == 'P': # reward advance but keep some central preference return rank * 10 + c * 2 + (3 - abs(file - 3)) * 2 if pt == 'N': return c * 5 - rank * 2 if pt == 'B': return c * 4 + rank if pt == 'R': return int(rank * 3 + (4 - abs(file - 3.5)) * 2) if pt == 'Q': return c * 2 + rank if pt == 'K': # middlegame: prefer safety at home / corners shelter = -c * 3 - rank * 8 if file in (1, 6): shelter += 8 if file in (0, 7): shelter += 12 return int(shelter) return 0 def eg_psqt(piece, sq): file = sq & 7 rank = sq >> 4 if piece.islower(): rank = 7 - rank pt = piece.upper() c = center_score(file, rank) if pt == 'P': return rank * 18 + c if pt == 'N': return c * 3 if pt == 'B': return c * 3 + rank if pt == 'R': return rank * 4 if pt == 'Q': return c * 2 if pt == 'K': # endgame king activity return c * 6 + rank * 2 return 0 class Position: __slots__ = ( 'board', 'side', 'castling', 'ep', 'halfmove', 'fullmove', 'king_sq', 'key' ) def __init__(self, fen=None): self.board = [EMPTY] * 128 self.side = WHITE self.castling = 0 self.ep = -1 self.halfmove = 0 self.fullmove = 1 self.king_sq = [0, 0] self.key = 0 if fen: self.set_fen(fen) def set_fen(self, fen): parts = fen.strip().split() if len(parts) < 4: raise ValueError('invalid FEN') self.board = [EMPTY] * 128 rows = parts[0].split('/') if len(rows) != 8: raise ValueError('invalid FEN rows') for i, row in enumerate(rows): rank = 7 - i file = 0 for ch in row: if ch.isdigit(): file += ord(ch) - 48 else: sq = rank * 16 + file self.board[sq] = ch if ch == 'K': self.king_sq[WHITE] = sq elif ch == 'k': self.king_sq[BLACK] = sq file += 1 if file != 8: raise ValueError('invalid FEN row width') self.side = WHITE if parts[1] == 'w' else BLACK self.castling = 0 if parts[2] != '-': if 'K' in parts[2]: self.castling |= WK if 'Q' in parts[2]: self.castling |= WQ if 'k' in parts[2]: self.castling |= BK if 'q' in parts[2]: self.castling |= BQ self.ep = parse_square(parts[3]) self.halfmove = int(parts[4]) if len(parts) > 4 else 0 self.fullmove = int(parts[5]) if len(parts) > 5 else 1 self.key = self.compute_key() def compute_key(self): k = 0 sq = 0 board = self.board while sq < 128: if sq & 0x88: sq += 8 continue p = board[sq] if p != EMPTY: k ^= Z_PIECE[PIECE_TO_INDEX[p]][sq] sq += 1 k ^= Z_CASTLE[self.castling] if self.ep != -1: k ^= Z_EP[self.ep & 7] if self.side == BLACK: k ^= Z_SIDE return k def is_attacked(self, sq, by_color): board = self.board if by_color == WHITE: for d in (-17, -15): s = sq + d if not (s & 0x88) and board[s] == 'P': return True else: for d in (17, 15): s = sq + d if not (s & 0x88) and board[s] == 'p': return True knight = 'N' if by_color == WHITE else 'n' for d in KNIGHT_DIRS: s = sq + d if not (s & 0x88) and board[s] == knight: return True bishop = 'B' if by_color == WHITE else 'b' rook = 'R' if by_color == WHITE else 'r' queen = 'Q' if by_color == WHITE else 'q' king = 'K' if by_color == WHITE else 'k' for d in BISHOP_DIRS: s = sq + d while not (s & 0x88): p = board[s] if p != EMPTY: if p == bishop or p == queen: return True break s += d for d in ROOK_DIRS: s = sq + d while not (s & 0x88): p = board[s] if p != EMPTY: if p == rook or p == queen: return True break s += d for d in KING_DIRS: s = sq + d if not (s & 0x88) and board[s] == king: return True return False def in_check(self, color=None): if color is None: color = self.side return self.is_attacked(self.king_sq[color], color ^ 1) def generate_pseudo_moves(self, captures_only=False): board = self.board us = self.side sq = 0 while sq < 128: if sq & 0x88: sq += 8 continue p = board[sq] if p == EMPTY or color_of(p) != us: sq += 1 continue pt = p.upper() if pt == 'P': forward = 16 if us == WHITE else -16 start_rank = 1 if us == WHITE else 6 promo_from_rank = 6 if us == WHITE else 1 rank = sq >> 4 if not captures_only: one = sq + forward if not (one & 0x88) and board[one] == EMPTY: if rank == promo_from_rank: yield encode_move(sq, one, PROMO_Q) yield encode_move(sq, one, PROMO_R) yield encode_move(sq, one, PROMO_B) yield encode_move(sq, one, PROMO_N) else: yield encode_move(sq, one) if rank == start_rank: two = one + forward if board[two] == EMPTY: yield encode_move(sq, two, 0, FLAG_DOUBLE) for side_step in (forward - 1, forward + 1): to = sq + side_step if to & 0x88: continue target = board[to] if target != EMPTY and color_of(target) != us: if rank == promo_from_rank: yield encode_move(sq, to, PROMO_Q) yield encode_move(sq, to, PROMO_R) yield encode_move(sq, to, PROMO_B) yield encode_move(sq, to, PROMO_N) else: yield encode_move(sq, to) elif to == self.ep: yield encode_move(sq, to, 0, FLAG_EP) elif pt == 'N': for d in KNIGHT_DIRS: to = sq + d if to & 0x88: continue target = board[to] if target == EMPTY: if not captures_only: yield encode_move(sq, to) elif color_of(target) != us: yield encode_move(sq, to) elif pt == 'B' or pt == 'R' or pt == 'Q': dirs = BISHOP_DIRS if pt == 'B' else ROOK_DIRS if pt == 'R' else QUEEN_DIRS for d in dirs: to = sq + d while not (to & 0x88): target = board[to] if target == EMPTY: if not captures_only: yield encode_move(sq, to) else: if color_of(target) != us: yield encode_move(sq, to) break to += d elif pt == 'K': for d in KING_DIRS: to = sq + d if to & 0x88: continue target = board[to] if target == EMPTY: if not captures_only: yield encode_move(sq, to) elif color_of(target) != us: yield encode_move(sq, to) if not captures_only and not self.in_check(us): if us == WHITE: if (self.castling & WK) and board[5] == EMPTY and board[6] == EMPTY and board[7] == 'R': if not self.is_attacked(5, BLACK) and not self.is_attacked(6, BLACK): yield encode_move(4, 6, 0, FLAG_CASTLE) if (self.castling & WQ) and board[1] == EMPTY and board[2] == EMPTY and board[3] == EMPTY and board[0] == 'R': if not self.is_attacked(3, BLACK) and not self.is_attacked(2, BLACK): yield encode_move(4, 2, 0, FLAG_CASTLE) else: if (self.castling & BK) and board[117] == EMPTY and board[118] == EMPTY and board[119] == 'r': if not self.is_attacked(117, WHITE) and not self.is_attacked(118, WHITE): yield encode_move(116, 118, 0, FLAG_CASTLE) if (self.castling & BQ) and board[113] == EMPTY and board[114] == EMPTY and board[115] == EMPTY and board[112] == 'r': if not self.is_attacked(115, WHITE) and not self.is_attacked(114, WHITE): yield encode_move(116, 114, 0, FLAG_CASTLE) sq += 1 def make_move(self, move): board = self.board frm = move_from(move) to = move_to(move) promo = move_promo(move) flags = move_flags(move) piece = board[frm] if piece == EMPTY: return None us = self.side them = us ^ 1 captured = board[to] old_castling = self.castling old_ep = self.ep old_halfmove = self.halfmove old_fullmove = self.fullmove old_key = self.key old_king_w = self.king_sq[WHITE] old_king_b = self.king_sq[BLACK] # remove old state contributions key = self.key ^ Z_CASTLE[old_castling] if old_ep != -1: key ^= Z_EP[old_ep & 7] if us == BLACK: key ^= Z_SIDE # will flip to white else: key ^= Z_SIDE # will flip to black at end too # remove moving piece from source key ^= Z_PIECE[PIECE_TO_INDEX[piece]][frm] board[frm] = EMPTY cap_sq = to if flags & FLAG_EP: cap_sq = to - 16 if us == WHITE else to + 16 captured = board[cap_sq] board[cap_sq] = EMPTY if captured != EMPTY: key ^= Z_PIECE[PIECE_TO_INDEX[captured]][cap_sq] elif captured != EMPTY: key ^= Z_PIECE[PIECE_TO_INDEX[captured]][to] # castling rook move if flags & FLAG_CASTLE: if to == 6: rook_from, rook_to = 7, 5 elif to == 2: rook_from, rook_to = 0, 3 elif to == 118: rook_from, rook_to = 119, 117 else: rook_from, rook_to = 112, 115 rook = board[rook_from] board[rook_from] = EMPTY board[rook_to] = rook key ^= Z_PIECE[PIECE_TO_INDEX[rook]][rook_from] key ^= Z_PIECE[PIECE_TO_INDEX[rook]][rook_to] # place moved/promoted piece placed = piece if promo: placed = PROMO_CHARS_W[promo] if us == WHITE else PROMO_CHARS_B[promo] board[to] = placed key ^= Z_PIECE[PIECE_TO_INDEX[placed]][to] # update kings if piece == 'K': self.king_sq[WHITE] = to self.castling &= ~(WK | WQ) elif piece == 'k': self.king_sq[BLACK] = to self.castling &= ~(BK | BQ) # rook move / rook capture castling rights if frm == 0 or to == 0: self.castling &= ~WQ if frm == 7 or to == 7: self.castling &= ~WK if frm == 112 or to == 112: self.castling &= ~BQ if frm == 119 or to == 119: self.castling &= ~BK # ep self.ep = -1 if piece.upper() == 'P' and (flags & FLAG_DOUBLE): self.ep = frm + 16 if us == WHITE else frm - 16 # clocks if piece.upper() == 'P' or captured != EMPTY: self.halfmove = 0 else: self.halfmove = old_halfmove + 1 if us == BLACK: self.fullmove = old_fullmove + 1 # finish hash state key ^= Z_CASTLE[self.castling] if self.ep != -1: key ^= Z_EP[self.ep & 7] self.side = them self.key = key # illegal? if self.is_attacked(self.king_sq[us], them): self.side = us self.castling = old_castling self.ep = old_ep self.halfmove = old_halfmove self.fullmove = old_fullmove self.key = old_key self.king_sq[WHITE] = old_king_w self.king_sq[BLACK] = old_king_b board[frm] = piece board[to] = captured if not (flags & FLAG_EP) else EMPTY if flags & FLAG_EP: board[cap_sq] = captured if flags & FLAG_CASTLE: board[rook_from] = board[rook_to] board[rook_to] = EMPTY return None return (move, piece, captured, old_castling, old_ep, old_halfmove, old_fullmove, old_key, old_king_w, old_king_b) def unmake_move(self, undo): (move, piece, captured, old_castling, old_ep, old_halfmove, old_fullmove, old_key, old_king_w, old_king_b) = undo board = self.board frm = move_from(move) to = move_to(move) promo = move_promo(move) flags = move_flags(move) self.side ^= 1 self.castling = old_castling self.ep = old_ep self.halfmove = old_halfmove self.fullmove = old_fullmove self.key = old_key self.king_sq[WHITE] = old_king_w self.king_sq[BLACK] = old_king_b board[frm] = piece if flags & FLAG_EP: board[to] = EMPTY cap_sq = to - 16 if self.side == WHITE else to + 16 board[cap_sq] = captured else: board[to] = captured if flags & FLAG_CASTLE: if to == 6: rook_from, rook_to = 7, 5 elif to == 2: rook_from, rook_to = 0, 3 elif to == 118: rook_from, rook_to = 119, 117 else: rook_from, rook_to = 112, 115 board[rook_from] = board[rook_to] board[rook_to] = EMPTY def legal_moves(self, captures_only=False): for m in self.generate_pseudo_moves(captures_only=captures_only): u = self.make_move(m) if u is not None: self.unmake_move(u) yield m def evaluate(self): # Positive for side to move board = self.board mg = 0 eg = 0 phase = 0 pawn_files_w = [0] * 8 pawn_files_b = [0] * 8 bishop_count = [0, 0] material_no_pawns = [0, 0] sq = 0 while sq < 128: if sq & 0x88: sq += 8 continue p = board[sq] if p != EMPTY: sign = 1 if p.isupper() else -1 pt = p.upper() if pt == 'P': if p.isupper(): pawn_files_w[sq & 7] += 1 else: pawn_files_b[sq & 7] += 1 if pt == 'B': bishop_count[WHITE if p.isupper() else BLACK] += 1 if pt != 'P' and pt != 'K': material_no_pawns[WHITE if p.isupper() else BLACK] += PIECE_VALUES[p] mg += sign * (PIECE_VALUES[p] + mg_psqt(p, sq)) eg += sign * (PIECE_VALUES[p] + eg_psqt(p, sq)) phase += PHASE_WEIGHT.get(p, 0) sq += 1 # Pawn structure and passed pawns sq = 0 while sq < 128: if sq & 0x88: sq += 8 continue p = board[sq] if p == 'P': f = sq & 7 r = sq >> 4 if pawn_files_w[f] > 1: mg -= 10 * (pawn_files_w[f] - 1) eg -= 14 * (pawn_files_w[f] - 1) if (f == 0 or pawn_files_w[f - 1] == 0) and (f == 7 or pawn_files_w[f + 1] == 0): mg -= 12 eg -= 10 passed = True for ff in (f - 1, f, f + 1): if 0 <= ff < 8: rr = r + 1 while rr < 8: if board[rr * 16 + ff] == 'p': passed = False rr = 8 rr += 1 if passed: bonus = (r - 1) * 14 mg += bonus eg += bonus * 2 elif p == 'p': f = sq & 7 r = 7 - (sq >> 4) if pawn_files_b[f] > 1: mg += 10 * (pawn_files_b[f] - 1) eg += 14 * (pawn_files_b[f] - 1) if (f == 0 or pawn_files_b[f - 1] == 0) and (f == 7 or pawn_files_b[f + 1] == 0): mg += 12 eg += 10 passed = True orig_rank = sq >> 4 for ff in (f - 1, f, f + 1): if 0 <= ff < 8: rr = orig_rank - 1 while rr >= 0: if board[rr * 16 + ff] == 'P': passed = False rr = -1 rr -= 1 if passed: bonus = (r - 1) * 14 mg -= bonus eg -= bonus * 2 sq += 1 # Bishop pair if bishop_count[WHITE] >= 2: mg += 30 eg += 40 if bishop_count[BLACK] >= 2: mg -= 30 eg -= 40 # Rooks on open / semi-open files for side, rook_char, own_files, opp_files, sign in ( (WHITE, 'R', pawn_files_w, pawn_files_b, 1), (BLACK, 'r', pawn_files_b, pawn_files_w, -1), ): sq = 0 while sq < 128: if sq & 0x88: sq += 8 continue if board[sq] == rook_char: f = sq & 7 if own_files[f] == 0 and opp_files[f] == 0: mg += sign * 18 eg += sign * 10 elif own_files[f] == 0: mg += sign * 10 eg += sign * 6 sq += 1 # Mobility (pseudo attacks to empty/enemy, light and compact) mobility = 0 sq = 0 while sq < 128: if sq & 0x88: sq += 8 continue p = board[sq] if p == EMPTY: sq += 1 continue sign = 1 if p.isupper() else -1 pt = p.upper() if pt == 'N': count = 0 for d in KNIGHT_DIRS: to = sq + d if not (to & 0x88): t = board[to] if t == EMPTY or color_of(t) != color_of(p): count += 1 mobility += sign * count * 4 elif pt == 'B': count = 0 for d in BISHOP_DIRS: to = sq + d while not (to & 0x88): t = board[to] count += 1 if t != EMPTY: break to += d mobility += sign * count * 2 elif pt == 'R': count = 0 for d in ROOK_DIRS: to = sq + d while not (to & 0x88): t = board[to] count += 1 if t != EMPTY: break to += d mobility += sign * count elif pt == 'Q': count = 0 for d in QUEEN_DIRS: to = sq + d while not (to & 0x88): t = board[to] count += 1 if t != EMPTY: break to += d mobility += sign * count sq += 1 mg += mobility eg += mobility // 2 # King distance in simple endgames if material_no_pawns[WHITE] + material_no_pawns[BLACK] <= 1400: wk = self.king_sq[WHITE] bk = self.king_sq[BLACK] dist = abs((wk & 7) - (bk & 7)) + abs((wk >> 4) - (bk >> 4)) if mg + eg > 0: eg += (14 - dist) * 2 elif mg + eg < 0: eg -= (14 - dist) * 2 if phase > 24: phase = 24 score = (mg * phase + eg * (24 - phase)) // 24 return score if self.side == WHITE else -score class SearchTimeout(Exception): pass class TranspositionTable: __slots__ = ('mask', 'keys', 'data') def __init__(self, bits=19): size = 1 << bits self.mask = size - 1 self.keys = array('Q', [0]) * size self.data = array('Q', [0]) * size @staticmethod def _pack(depth, score, flag, move): if score < -32768: score = -32768 elif score > 32767: score = 32767 return (depth & 0xFF) | ((flag & 0x3) << 8) | ((move & 0xFFFFF) << 10) | (((score + 32768) & 0xFFFF) << 30) @staticmethod def _unpack(value): depth = value & 0xFF flag = (value >> 8) & 0x3 move = (value >> 10) & 0xFFFFF score = ((value >> 30) & 0xFFFF) - 32768 return depth, score, flag, move def probe(self, key): idx = key & self.mask if self.keys[idx] == key: return self._unpack(self.data[idx]) return None def store(self, key, depth, score, flag, move): idx = key & self.mask cur_key = self.keys[idx] if cur_key == key: cur_depth = self.data[idx] & 0xFF cur_flag = (self.data[idx] >> 8) & 0x3 if depth < cur_depth and flag != EXACT and cur_flag == EXACT: return self.keys[idx] = key self.data[idx] = self._pack(depth, score, flag, move) class Engine: __slots__ = ( 'tt', 'history', 'killers1', 'killers2', 'node_count', 'stop_time', 'check_mask', 'root_best', 'root_score', 'max_depth_reached' ) def __init__(self): self.tt = TranspositionTable(19) self.history = [array('I', [0]) * (128 * 128), array('I', [0]) * (128 * 128)] self.killers1 = [0] * 256 self.killers2 = [0] * 256 self.node_count = 0 self.stop_time = 0.0 self.check_mask = 511 self.root_best = 0 self.root_score = -INF self.max_depth_reached = 0 def move_score(self, pos, move, ply, tt_move): if move == tt_move: return 10_000_000 frm = move_from(move) to = move_to(move) flags = move_flags(move) promo = move_promo(move) piece = pos.board[frm] target = pos.board[to] if flags & FLAG_EP: target = 'p' if pos.side == WHITE else 'P' if target != EMPTY: return 1_000_000 + 16 * PIECE_VALUES[target] - PIECE_VALUES[piece] if promo: bonus = {PROMO_Q: 900, PROMO_R: 500, PROMO_B: 330, PROMO_N: 320}[promo] return 900_000 + bonus if move == self.killers1[ply]: return 800_000 if move == self.killers2[ply]: return 799_000 idx = (frm << 7) | to return self.history[pos.side][idx] def ordered_moves(self, pos, ply, tt_move=0, captures_only=False): moves = list(pos.generate_pseudo_moves(captures_only=captures_only)) if not moves: return moves scored = [] for m in moves: scored.append((self.move_score(pos, m, ply, tt_move), m)) scored.sort(reverse=True) return [m for _, m in scored] def qsearch(self, pos, alpha, beta, ply): self.node_count += 1 if (self.node_count & self.check_mask) == 0 and time.perf_counter() >= self.stop_time: raise SearchTimeout in_check = pos.in_check() if pos.halfmove >= 100: return 0 stand = -INF if not in_check: stand = pos.evaluate() if stand >= beta: return stand if stand > alpha: alpha = stand legal = 0 tt_entry = self.tt.probe(pos.key) tt_move = tt_entry[3] if tt_entry else 0 for move in self.ordered_moves(pos, ply, tt_move, captures_only=not in_check): if not in_check: # delta prune obvious losing captures/promotions target = pos.board[move_to(move)] if move_flags(move) & FLAG_EP: target = 'p' if pos.side == WHITE else 'P' gain = PIECE_VALUES.get(target, 0) if move_promo(move): gain += 700 if alpha > -MATE and stand + gain + 100 < alpha: continue undo = pos.make_move(move) if undo is None: continue legal += 1 score = -self.qsearch(pos, -beta, -alpha, ply + 1) pos.unmake_move(undo) if score > alpha: alpha = score if alpha >= beta: return alpha if legal == 0: if in_check: return -MATE + ply # No tactical moves. Distinguish ordinary quiet nodes from stalemate. for move in pos.generate_pseudo_moves(captures_only=False): undo = pos.make_move(move) if undo is not None: pos.unmake_move(undo) return stand return 0 return alpha def search(self, pos, depth, alpha, beta, ply, allow_null=True): self.node_count += 1 if (self.node_count & self.check_mask) == 0 and time.perf_counter() >= self.stop_time: raise SearchTimeout self.max_depth_reached = max(self.max_depth_reached, ply) if pos.halfmove >= 100: return 0 in_check = pos.in_check() if depth <= 0: return self.qsearch(pos, alpha, beta, ply) orig_alpha = alpha tt_entry = self.tt.probe(pos.key) tt_move = 0 if tt_entry is not None: tt_depth, tt_score, tt_flag, tt_move = tt_entry if tt_depth >= depth: if tt_flag == EXACT: return tt_score if tt_flag == LOWER and tt_score >= beta: return tt_score if tt_flag == UPPER and tt_score <= alpha: return tt_score # Null move pruning if allow_null and depth >= 3 and not in_check: material = 0 sq = 0 b = pos.board while sq < 128: if sq & 0x88: sq += 8 continue p = b[sq] if p != EMPTY and color_of(p) == pos.side and p.upper() not in ('P', 'K'): material += PIECE_VALUES[p] sq += 1 if material >= 500: old_ep = pos.ep old_side = pos.side old_key = pos.key if old_ep != -1: pos.key ^= Z_EP[old_ep & 7] pos.ep = -1 pos.side ^= 1 pos.key ^= Z_SIDE score = -self.search(pos, depth - 1 - 2, -beta, -beta + 1, ply + 1, allow_null=False) pos.side = old_side pos.ep = old_ep pos.key = old_key if score >= beta: return score best_score = -INF best_move = 0 legal = 0 moves = self.ordered_moves(pos, ply, tt_move, captures_only=False) if not moves: return -MATE + ply if in_check else 0 for i, move in enumerate(moves): quiet = pos.board[move_to(move)] == EMPTY and not (move_flags(move) & FLAG_EP) and not move_promo(move) undo = pos.make_move(move) if undo is None: continue legal += 1 new_depth = depth - 1 reduction = 0 if depth >= 4 and i >= 3 and quiet and not in_check: reduction = 1 if i >= 8: reduction = 2 if move == self.killers1[ply] or move == self.killers2[ply]: reduction -= 1 if reduction < 1: reduction = 1 if i == 0: score = -self.search(pos, new_depth, -beta, -alpha, ply + 1) else: score = -self.search(pos, new_depth - reduction, -alpha - 1, -alpha, ply + 1) if score > alpha and score < beta: score = -self.search(pos, new_depth, -beta, -alpha, ply + 1) pos.unmake_move(undo) if score > best_score: best_score = score best_move = move if ply == 0: self.root_best = move self.root_score = score if score > alpha: alpha = score if alpha >= beta: if quiet: self.killers2[ply] = self.killers1[ply] self.killers1[ply] = move idx = (move_from(move) << 7) | move_to(move) self.history[pos.side][idx] += depth * depth if self.history[pos.side][idx] > 1_000_000: arr = self.history[pos.side] for j in range(len(arr)): arr[j] //= 2 break if legal == 0: return -MATE + ply if in_check else 0 flag = EXACT if best_score <= orig_alpha: flag = UPPER elif best_score >= beta: flag = LOWER self.tt.store(pos.key, depth, best_score, flag, best_move) return best_score def choose_move(self, fen, max_time=4.5): pos = Position(fen) legal = list(pos.legal_moves()) if not legal: return '0000' self.node_count = 0 self.stop_time = time.perf_counter() + max_time self.root_best = legal[0] self.root_score = -INF self.max_depth_reached = 0 # Move from TT if legal tt_entry = self.tt.probe(pos.key) if tt_entry: tt_move = tt_entry[3] if tt_move in legal: self.root_best = tt_move # Iterative deepening with aspiration windows best_move = self.root_best best_score = -INF prev_score = 0 depth = 1 try: while depth <= 64: alpha = -INF beta = INF if depth >= 3: window = 40 alpha = prev_score - window beta = prev_score + window while True: try: score = self.search(pos, depth, alpha, beta, 0) except SearchTimeout: raise if score <= alpha: alpha -= window window *= 2 continue if score >= beta: beta += window window *= 2 continue break else: score = self.search(pos, depth, alpha, beta, 0) prev_score = score best_score = score best_move = self.root_best depth += 1 except SearchTimeout: pass if best_move not in legal: best_move = legal[0] return move_to_uci(best_move) ENGINE = Engine() def choose_best_move(fen): return ENGINE.choose_move(fen) def main(): for line in sys.stdin: fen = line.strip() if not fen: continue try: move = choose_best_move(fen) except Exception: # Always try to return a legal move if the FEN is valid. try: pos = Position(fen) legal = next(pos.legal_moves(), None) move = move_to_uci(legal) if legal is not None else '0000' except Exception: move = '0000' sys.stdout.write(move + '\n') sys.stdout.flush() if __name__ == '__main__': main()