#!/usr/bin/env python3 """ chitti_python.py — single-file Python 3 chess agent Input : one FEN per line on stdin Output: best UCI move per line on stdout Architecture mirrors chitti-beta-d3507c52.js (Node.js original) plus: + Repetition detection (undo-stack hash scan) + 50-move rule draw + Pawn structure eval (doubled / isolated / passed pawns) + King safety (pawn-shield score) + Futility pruning (depth 1-2 quiet moves) + Countermove heuristic (4th quiet-move ordering tier) + Opening book (common first moves) + Smart time management (fewer moves → less time) """ import sys import random import time from array import array # ────────────────────────────────────────────── # 1. CONSTANTS # ────────────────────────────────────────────── EMPTY = 0 WHITE = 0 BLACK = 1 PAWN = 1; KNIGHT = 2; BISHOP = 3 ROOK = 4; QUEEN = 5; KING = 6 def piece(color, ptype): return (color << 3) | ptype def piece_color(p): return p >> 3 def piece_type(p): return p & 7 WP = piece(WHITE, PAWN); WN = piece(WHITE, KNIGHT); WB = piece(WHITE, BISHOP) WR = piece(WHITE, ROOK); WQ = piece(WHITE, QUEEN); WK = piece(WHITE, KING) BP = piece(BLACK, PAWN); BN = piece(BLACK, KNIGHT); BB = piece(BLACK, BISHOP) BR = piece(BLACK, ROOK); BQ = piece(BLACK, QUEEN); BK = piece(BLACK, KING) # ── 0x88 helpers ── def sq(rank, file): return (rank << 4) | file def sq_rank(s): return s >> 4 def sq_file(s): return s & 7 def on_board(s): return (s & 0x88) == 0 def alg_to_sq(a): return sq(ord(a[1]) - 49, ord(a[0]) - 97) def sq_to_alg(s): return chr(97 + sq_file(s)) + chr(49 + sq_rank(s)) # ── Move encoding (32-bit int) ── # bits 0-6 : from-square # bits 7-13 : to-square # bits 14-17 : flag FLAG_QUIET = 0 FLAG_CAPTURE = 1 FLAG_EP = 2 FLAG_CASTLE_K = 3 FLAG_CASTLE_Q = 4 FLAG_DPUSH = 5 FLAG_PROMO_N = 6 FLAG_PROMO_B = 7 FLAG_PROMO_R = 8 FLAG_PROMO_Q = 9 FLAG_PROMO_CN = 10 FLAG_PROMO_CB = 11 FLAG_PROMO_CR = 12 FLAG_PROMO_CQ = 13 def enc_move(f, t, flag): return f | (t << 7) | (flag << 14) def move_from(m): return m & 0x7F def move_to(m): return (m >> 7) & 0x7F def move_flag(m): return (m >> 14) & 0xF def move_is_capture(m): f = move_flag(m) return f == FLAG_CAPTURE or f == FLAG_EP or FLAG_PROMO_CN <= f <= FLAG_PROMO_CQ def promo_type(flag): if flag in (FLAG_PROMO_N, FLAG_PROMO_CN): return KNIGHT if flag in (FLAG_PROMO_B, FLAG_PROMO_CB): return BISHOP if flag in (FLAG_PROMO_R, FLAG_PROMO_CR): return ROOK return QUEEN def move_to_uci(m): f = move_flag(m) s = sq_to_alg(move_from(m)) + sq_to_alg(move_to(m)) if FLAG_PROMO_N <= f <= FLAG_PROMO_CQ: s += 'nbrq'[promo_type(f) - KNIGHT] return s # ────────────────────────────────────────────── # 2. ZOBRIST KEYS (initialised once at startup) # ────────────────────────────────────────────── def _rnd32(): return random.getrandbits(32) ZOB_PIECE = [[[_rnd32() for _ in range(128)] for _ in range(7)] for _ in range(2)] ZOB_CASTLE = [_rnd32() for _ in range(16)] ZOB_EP = [_rnd32() for _ in range(8)] ZOB_SIDE = _rnd32() # ────────────────────────────────────────────── # 3. PIECE-SQUARE TABLES (PeSTO) # ────────────────────────────────────────────── 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, -16, -1, -1, -11, 6, 0, 13, 8, 8, 10, 13, 0, 2, -13, 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, -6, -71, -19, -13, 1, 17, 16, 7, -37, -26, ] 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, ] MG_TABLE = [None, MG_PAWN, MG_KNIGHT, MG_BISHOP, MG_ROOK, MG_QUEEN, MG_KING] EG_TABLE = [None, EG_PAWN, EG_KNIGHT, EG_BISHOP, EG_ROOK, EG_QUEEN, EG_KING] MG_VALUE = [0, 82, 337, 365, 477, 1025, 0] EG_VALUE = [0, 94, 281, 297, 512, 936, 0] PIECE_VALUE = [0, 100, 320, 330, 500, 900, 20000] def pst_idx(s, color): r = sq_rank(s); f = sq_file(s) row = (7 - r) if color == WHITE else r return row * 8 + f # ────────────────────────────────────────────── # 4. BOARD STATE (module-level mutable globals) # ────────────────────────────────────────────── board = array('b', [0] * 128) # signed byte: piece values 0-14 fit fine castling = [0] # bits: 1=WK 2=WQ 4=BK 8=BQ ep_square = [-1] side_to_move = [WHITE] half_move = [0] full_move = [1] hash_key = [0] king_pos = [-1, -1] # king_pos[WHITE], king_pos[BLACK] undo_stack = [] def clear_board(): for i in range(128): board[i] = 0 castling[0] = 0 ep_square[0] = -1 side_to_move[0] = WHITE half_move[0] = 0 full_move[0] = 1 hash_key[0] = 0 king_pos[WHITE] = -1 king_pos[BLACK] = -1 undo_stack.clear() _PIECE_MAP = {'p': PAWN, 'n': KNIGHT, 'b': BISHOP, 'r': ROOK, 'q': QUEEN, 'k': KING} def parse_fen(fen): clear_board() parts = fen.strip().split() rows = parts[0].split('/') for r in range(8): row = rows[7 - r] # FEN is top-down, board is bottom-up f = 0 for c in row: if c.isdigit(): f += int(c) else: color = WHITE if c.isupper() else BLACK ptype = _PIECE_MAP[c.lower()] s = sq(r, f) p = piece(color, ptype) board[s] = p hash_key[0] ^= ZOB_PIECE[color][ptype][s] if ptype == KING: king_pos[color] = s f += 1 side_to_move[0] = WHITE if parts[1] == 'w' else BLACK if side_to_move[0] == BLACK: hash_key[0] ^= ZOB_SIDE cr = parts[2] if len(parts) > 2 else '-' cr_bits = (('K' in cr) | (('Q' in cr) << 1) | (('k' in cr) << 2) | (('q' in cr) << 3)) castling[0] = cr_bits hash_key[0] ^= ZOB_CASTLE[cr_bits] if len(parts) > 3 and parts[3] != '-': ep_square[0] = alg_to_sq(parts[3]) hash_key[0] ^= ZOB_EP[sq_file(ep_square[0])] half_move[0] = int(parts[4]) if len(parts) > 4 else 0 full_move[0] = int(parts[5]) if len(parts) > 5 else 1 # ────────────────────────────────────────────── # 5. ATTACK DETECTION # ────────────────────────────────────────────── KNIGHT_OFFSETS = (-33, -31, -18, -14, 14, 18, 31, 33) BISHOP_OFFSETS = (-17, -15, 15, 17) ROOK_OFFSETS = (-16, -1, 1, 16) KING_OFFSETS = (-17, -16, -15, -1, 1, 15, 16, 17) def is_attacked(s, by_color): # Pawn attacks p_dir = -1 if by_color == WHITE else 1 pl = s + p_dir * 16 - 1 pr = s + p_dir * 16 + 1 wp = piece(by_color, PAWN) if on_board(pl) and board[pl] == wp: return True if on_board(pr) and board[pr] == wp: return True # Knights wn = piece(by_color, KNIGHT) for d in KNIGHT_OFFSETS: t = s + d if on_board(t) and board[t] == wn: return True # Bishops / Queens (diagonals) wb = piece(by_color, BISHOP); wq = piece(by_color, QUEEN) for d in BISHOP_OFFSETS: t = s + d while on_board(t): bt = board[t] if bt != EMPTY: if bt == wb or bt == wq: return True break t += d # Rooks / Queens (straights) wr = piece(by_color, ROOK) for d in ROOK_OFFSETS: t = s + d while on_board(t): bt = board[t] if bt != EMPTY: if bt == wr or bt == wq: return True break t += d # King wk = piece(by_color, KING) for d in KING_OFFSETS: t = s + d if on_board(t) and board[t] == wk: return True return False # ────────────────────────────────────────────── # 6. MAKE / UNMAKE # ────────────────────────────────────────────── def make_move(m): from_sq = move_from(m); to_sq = move_to(m); flag = move_flag(m) moving = board[from_sq] captured = board[to_sq] mtype = piece_type(moving) mcolor = piece_color(moving) undo_stack.append(( from_sq, to_sq, flag, moving, captured, castling[0], ep_square[0], half_move[0], hash_key[0], king_pos[WHITE], king_pos[BLACK] )) # Hash-out old state hash_key[0] ^= ZOB_PIECE[mcolor][mtype][from_sq] if captured != EMPTY: hash_key[0] ^= ZOB_PIECE[piece_color(captured)][piece_type(captured)][to_sq] hash_key[0] ^= ZOB_CASTLE[castling[0]] if ep_square[0] >= 0: hash_key[0] ^= ZOB_EP[sq_file(ep_square[0])] board[from_sq] = EMPTY board[to_sq] = moving ep_square[0] = -1 half_move[0] += 1 if mtype == PAWN or flag == FLAG_CAPTURE or flag == FLAG_EP or flag >= FLAG_PROMO_CN: half_move[0] = 0 if flag == FLAG_EP: ep_cap = to_sq + (-16 if mcolor == WHITE else 16) hash_key[0] ^= ZOB_PIECE[1 - mcolor][PAWN][ep_cap] board[ep_cap] = EMPTY if flag == FLAG_DPUSH: ep_square[0] = from_sq + (16 if mcolor == WHITE else -16) hash_key[0] ^= ZOB_EP[sq_file(ep_square[0])] if flag == FLAG_CASTLE_K or flag == FLAG_CASTLE_Q: if flag == FLAG_CASTLE_K: rf = sq(0, 7) if mcolor == WHITE else sq(7, 7) rt = sq(0, 5) if mcolor == WHITE else sq(7, 5) else: rf = sq(0, 0) if mcolor == WHITE else sq(7, 0) rt = sq(0, 3) if mcolor == WHITE else sq(7, 3) rook = board[rf] hash_key[0] ^= ZOB_PIECE[mcolor][ROOK][rf] board[rf] = EMPTY board[rt] = rook hash_key[0] ^= ZOB_PIECE[mcolor][ROOK][rt] if FLAG_PROMO_N <= flag <= FLAG_PROMO_CQ: pt = promo_type(flag) board[to_sq] = piece(mcolor, pt) hash_key[0] ^= ZOB_PIECE[mcolor][pt][to_sq] else: hash_key[0] ^= ZOB_PIECE[mcolor][mtype][to_sq] if mtype == KING: king_pos[mcolor] = to_sq # Update castling rights cr = castling[0] if from_sq == sq(0,4) or from_sq == sq(0,0) or to_sq == sq(0,0): cr &= ~2 if from_sq == sq(0,4) or from_sq == sq(0,7) or to_sq == sq(0,7): cr &= ~1 if from_sq == sq(7,4) or from_sq == sq(7,0) or to_sq == sq(7,0): cr &= ~8 if from_sq == sq(7,4) or from_sq == sq(7,7) or to_sq == sq(7,7): cr &= ~4 castling[0] = cr hash_key[0] ^= ZOB_CASTLE[cr] side_to_move[0] ^= 1 hash_key[0] ^= ZOB_SIDE if side_to_move[0] == WHITE: full_move[0] += 1 def unmake_move(): (from_sq, to_sq, flag, moving, captured, prev_castling, prev_ep, prev_half, prev_hash, kw, kb) = undo_stack.pop() side_to_move[0] ^= 1 if side_to_move[0] == BLACK: full_move[0] -= 1 mcolor = piece_color(moving) board[from_sq] = moving board[to_sq] = captured if flag == FLAG_EP: ep_cap = to_sq + (-16 if mcolor == WHITE else 16) board[ep_cap] = piece(1 - mcolor, PAWN) if flag == FLAG_CASTLE_K or flag == FLAG_CASTLE_Q: if flag == FLAG_CASTLE_K: rf = sq(0, 7) if mcolor == WHITE else sq(7, 7) rt = sq(0, 5) if mcolor == WHITE else sq(7, 5) else: rf = sq(0, 0) if mcolor == WHITE else sq(7, 0) rt = sq(0, 3) if mcolor == WHITE else sq(7, 3) board[rf] = board[rt] board[rt] = EMPTY castling[0] = prev_castling ep_square[0] = prev_ep half_move[0] = prev_half hash_key[0] = prev_hash king_pos[WHITE] = kw king_pos[BLACK] = kb # ────────────────────────────────────────────── # 7. MOVE GENERATION # ────────────────────────────────────────────── _move_list = [0] * 4096 _move_count = [0] def gen_moves(color): opp = 1 - color pawn_dir = 1 if color == WHITE else -1 start_rank = 1 if color == WHITE else 6 promo_rank = 7 if color == WHITE else 0 mc = 0 for s in range(128): if not on_board(s) or board[s] == EMPTY: continue p = board[s] if piece_color(p) != color: continue pt = piece_type(p) # ── Pawn ── if pt == PAWN: fwd = s + pawn_dir * 16 if on_board(fwd) and board[fwd] == EMPTY: to_r = sq_rank(fwd) if to_r == promo_rank: for fl in (FLAG_PROMO_Q, FLAG_PROMO_R, FLAG_PROMO_B, FLAG_PROMO_N): _move_list[mc] = enc_move(s, fwd, fl); mc += 1 else: _move_list[mc] = enc_move(s, fwd, FLAG_QUIET); mc += 1 if sq_rank(s) == start_rank: dbl = fwd + pawn_dir * 16 if board[dbl] == EMPTY: _move_list[mc] = enc_move(s, dbl, FLAG_DPUSH); mc += 1 for df in (-1, 1): t = fwd + df if not on_board(t): continue to_r = sq_rank(t) if board[t] != EMPTY and piece_color(board[t]) == opp: if to_r == promo_rank: for fl in (FLAG_PROMO_CQ, FLAG_PROMO_CR, FLAG_PROMO_CB, FLAG_PROMO_CN): _move_list[mc] = enc_move(s, t, fl); mc += 1 else: _move_list[mc] = enc_move(s, t, FLAG_CAPTURE); mc += 1 elif ep_square[0] >= 0 and t == ep_square[0]: _move_list[mc] = enc_move(s, t, FLAG_EP); mc += 1 # ── Knight ── elif pt == KNIGHT: for d in KNIGHT_OFFSETS: t = s + d if not on_board(t): continue if board[t] == EMPTY: _move_list[mc] = enc_move(s, t, FLAG_QUIET); mc += 1 elif piece_color(board[t]) == opp: _move_list[mc] = enc_move(s, t, FLAG_CAPTURE); mc += 1 # ── Bishop / Queen (diagonals) ── if pt == BISHOP or pt == QUEEN: for d in BISHOP_OFFSETS: t = s + d while on_board(t): if board[t] == EMPTY: _move_list[mc] = enc_move(s, t, FLAG_QUIET); mc += 1 else: if piece_color(board[t]) == opp: _move_list[mc] = enc_move(s, t, FLAG_CAPTURE); mc += 1 break t += d # ── Rook / Queen (straights) ── if pt == ROOK or pt == QUEEN: for d in ROOK_OFFSETS: t = s + d while on_board(t): if board[t] == EMPTY: _move_list[mc] = enc_move(s, t, FLAG_QUIET); mc += 1 else: if piece_color(board[t]) == opp: _move_list[mc] = enc_move(s, t, FLAG_CAPTURE); mc += 1 break t += d # ── King ── if pt == KING: for d in KING_OFFSETS: t = s + d if not on_board(t): continue if board[t] == EMPTY: _move_list[mc] = enc_move(s, t, FLAG_QUIET); mc += 1 elif piece_color(board[t]) == opp: _move_list[mc] = enc_move(s, t, FLAG_CAPTURE); mc += 1 cr = castling[0] if color == WHITE and s == sq(0, 4): if (cr & 1) and board[sq(0,5)] == EMPTY and board[sq(0,6)] == EMPTY and \ not is_attacked(sq(0,4), opp) and not is_attacked(sq(0,5), opp) and \ not is_attacked(sq(0,6), opp): _move_list[mc] = enc_move(s, sq(0,6), FLAG_CASTLE_K); mc += 1 if (cr & 2) and board[sq(0,3)] == EMPTY and board[sq(0,2)] == EMPTY and \ board[sq(0,1)] == EMPTY and \ not is_attacked(sq(0,4), opp) and not is_attacked(sq(0,3), opp) and \ not is_attacked(sq(0,2), opp): _move_list[mc] = enc_move(s, sq(0,2), FLAG_CASTLE_Q); mc += 1 if color == BLACK and s == sq(7, 4): if (cr & 4) and board[sq(7,5)] == EMPTY and board[sq(7,6)] == EMPTY and \ not is_attacked(sq(7,4), opp) and not is_attacked(sq(7,5), opp) and \ not is_attacked(sq(7,6), opp): _move_list[mc] = enc_move(s, sq(7,6), FLAG_CASTLE_K); mc += 1 if (cr & 8) and board[sq(7,3)] == EMPTY and board[sq(7,2)] == EMPTY and \ board[sq(7,1)] == EMPTY and \ not is_attacked(sq(7,4), opp) and not is_attacked(sq(7,3), opp) and \ not is_attacked(sq(7,2), opp): _move_list[mc] = enc_move(s, sq(7,2), FLAG_CASTLE_Q); mc += 1 _move_count[0] = mc return mc def is_in_check(color): return is_attacked(king_pos[color], 1 - color) def legal_moves(color): gen_moves(color) legal = [] for i in range(_move_count[0]): m = _move_list[i] make_move(m) if not is_attacked(king_pos[color], 1 - color): legal.append(m) unmake_move() return legal # ────────────────────────────────────────────── # 8. EVALUATION (PeSTO + pawn structure + king safety) # ────────────────────────────────────────────── PHASE_MAX = 24 # 2*(1N+1B+2R+4Q) = 2*(1+1+4+16) = but standard is knight=1,bishop=1,rook=2,queen=4 → max 24 def _king_safety(king_s, color): """Pawn shield score for one king.""" direction = 1 if color == WHITE else -1 shield = 0 r = sq_rank(king_s); f = sq_file(king_s) wp = piece(color, PAWN) for df in (-1, 0, 1): ff = f + df if ff < 0 or ff > 7: continue front = sq(r + direction, ff) if on_board(front) and board[front] == wp: shield += 15 else: shield -= 10 return shield def evaluate(): mg = 0; eg = 0; phase = 0 w_bishops = 0; b_bishops = 0 w_pf = [0] * 8 # white pawn file counts b_pf = [0] * 8 # black pawn file counts for s in range(128): if not on_board(s): continue p = board[s] if p == EMPTY: continue c = piece_color(p) t = piece_type(p) pi = pst_idx(s, c) sg = 1 if c == WHITE else -1 mg += sg * (MG_VALUE[t] + MG_TABLE[t][pi]) eg += sg * (EG_VALUE[t] + EG_TABLE[t][pi]) if t == KNIGHT: phase += 1 elif t == BISHOP: phase += 1 if c == WHITE: w_bishops += 1 else: b_bishops += 1 elif t == ROOK: phase += 2 elif t == QUEEN: phase += 4 if t == PAWN: if c == WHITE: w_pf[sq_file(s)] += 1 else: b_pf[sq_file(s)] += 1 # ── Bishop pair ── if w_bishops >= 2: mg += 30; eg += 30 if b_bishops >= 2: mg -= 30; eg -= 30 # ── Pawn structure: doubled / isolated ── for f in range(8): if w_pf[f] > 1: mg -= 15 * (w_pf[f] - 1) eg -= 20 * (w_pf[f] - 1) if b_pf[f] > 1: mg += 15 * (b_pf[f] - 1) eg += 20 * (b_pf[f] - 1) if w_pf[f] > 0: if (f == 0 or w_pf[f-1] == 0) and (f == 7 or w_pf[f+1] == 0): mg -= 20; eg -= 25 if b_pf[f] > 0: if (f == 0 or b_pf[f-1] == 0) and (f == 7 or b_pf[f+1] == 0): mg += 20; eg += 25 # ── Passed pawns ── for s in range(128): if not on_board(s) or board[s] == EMPTY: continue p = board[s] if piece_type(p) != PAWN: continue c = piece_color(p); f = sq_file(s); r = sq_rank(s) passed = True fl = max(0, f - 1); fh = min(7, f + 1) if c == WHITE: for rr in range(r + 1, 8): for ff in range(fl, fh + 1): if board[sq(rr, ff)] == BP: passed = False; break if not passed: break if passed: bonus = 20 + (r - 1) * 15 mg += bonus; eg += bonus * 2 else: for rr in range(r - 1, -1, -1): for ff in range(fl, fh + 1): if board[sq(rr, ff)] == WP: passed = False; break if not passed: break if passed: bonus = 20 + (6 - r) * 15 mg -= bonus; eg -= bonus * 2 # ── King safety (only meaningful in middlegame) ── if phase > 8: mg += _king_safety(king_pos[WHITE], WHITE) mg -= _king_safety(king_pos[BLACK], BLACK) ph = min(phase, PHASE_MAX) score = (mg * ph + eg * (PHASE_MAX - ph)) // PHASE_MAX return score if side_to_move[0] == WHITE else -score # ────────────────────────────────────────────── # 9. TRANSPOSITION TABLE # ────────────────────────────────────────────── TT_SIZE = 1 << 20 # ~1 M entries TT_MASK = TT_SIZE - 1 TT_EXACT = 0; TT_ALPHA = 1; TT_BETA = 2 # Use typed arrays to minimise memory / overhead tt_key = array('i', [0] * TT_SIZE) # signed 32-bit tt_score = array('i', [0] * TT_SIZE) tt_depth = array('b', [0] * TT_SIZE) # signed byte (depth ≤ 64) tt_flag = array('b', [0] * TT_SIZE) tt_move = array('i', [0] * TT_SIZE) _HASH_MASK31 = 0x7FFFFFFF # keep key positive so it fits in signed int32 def tt_store(h, depth, score, flag, move): idx = h & TT_MASK tt_key[idx] = h & _HASH_MASK31 tt_depth[idx] = depth tt_score[idx] = score tt_flag[idx] = flag tt_move[idx] = move def tt_probe(h): idx = h & TT_MASK if tt_key[idx] == (h & _HASH_MASK31): return idx return -1 # ────────────────────────────────────────────── # 10. MOVE ORDERING # ────────────────────────────────────────────── MVV_LVA = [0] * (7 * 7) for _v in range(1, 7): for _a in range(1, 7): MVV_LVA[_v * 7 + _a] = PIECE_VALUE[_v] * 10 - PIECE_VALUE[_a] killers = [0] * (200 * 2) # 2 killers per ply, up to ply 100 hist_heuristic = [0] * (2 * 64 * 64) counter_move = [0] * (128 * 128) # indexed by [from*128+to] of the previous move def _hist_idx(color, from_s, to_s): return color * 4096 + (from_s & 63) * 64 + (to_s & 63) def _score_move(m, tt_best, ply, prev_move): if m == tt_best: return 2_000_000 if move_is_capture(m): vic = piece_type(board[move_to(m)]) atk = piece_type(board[move_from(m)]) return 1_000_000 + MVV_LVA[vic * 7 + atk] if killers[ply * 2] == m or killers[ply * 2 + 1] == m: return 900_000 if prev_move: cm_idx = move_from(prev_move) * 128 + move_to(prev_move) if counter_move[cm_idx] == m: return 850_000 return hist_heuristic[_hist_idx(side_to_move[0], move_from(m), move_to(m))] def sort_moves(moves, tt_best, ply, prev_move): moves.sort(key=lambda m: -_score_move(m, tt_best, ply, prev_move)) # ────────────────────────────────────────────── # 11. OPENING BOOK # ────────────────────────────────────────────── # Key = first 3 FEN fields (position + side + castling, no ep / clocks) OPENING_BOOK = { 'rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq': ['e2e4', 'd2d4', 'c2c4', 'g1f3'], 'rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq': ['e7e5', 'c7c5', 'e7e6', 'c7c6'], 'rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR b KQkq': ['d7d5', 'g8f6', 'e7e6', 'c7c5'], 'rnbqkbnr/pppppppp/8/8/2P5/8/PP1PPPPP/RNBQKBNR b KQkq': ['c7c5', 'e7e6', 'g8f6'], 'rnbqkbnr/pppppppp/8/8/8/5N2/PPPPPPPP/RNBQKB1R b KQkq': ['d7d5', 'g8f6', 'e7e6'], 'rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq': ['g1f3', 'f1c4', 'f1b5', 'd2d4'], 'rnbqkbnr/ppp1pppp/8/3p4/3P4/8/PPP1PPPP/RNBQKBNR w KQkq': ['c2c4', 'g1f3', 'e2e3'], 'rnbqkbnr/pppp1ppp/8/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R b KQkq': ['b8c6', 'g8f6', 'd7d6'], 'r1bqkbnr/pppp1ppp/2n5/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R w KQkq': ['f1b5', 'f1c4', 'd2d4'], 'rnbqkbnr/ppp1pppp/8/3p4/2PP4/8/PP2PPPP/RNBQKBNR b KQkq': ['e7e6', 'c7c6', 'g8f6', 'd5c4'], 'rnbqkb1r/pppp1ppp/5n2/4p3/2B1P3/8/PPPP1PPP/RNBQK1NR w KQkq': ['g1f3', 'd2d3', 'c2c3'], 'r1bqkbnr/pppp1ppp/2n5/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R w KQkq': ['f1b5'], } def get_book_move(fen): key = ' '.join(fen.strip().split()[:3]) moves = OPENING_BOOK.get(key) if moves: return random.choice(moves) return None # ────────────────────────────────────────────── # 12. SEARCH # ────────────────────────────────────────────── INF = 999_999 MATE = 900_000 _nodes = [0] _search_start = [0.0] _time_limit = [4500] # milliseconds def _time_up(): return (time.monotonic() * 1000 - _search_start[0]) > _time_limit[0] # ── Quiescence search ── def quiesce(alpha, beta): _nodes[0] += 1 stand = evaluate() if stand >= beta: return beta if stand > alpha: alpha = stand gen_moves(side_to_move[0]) captures = [] for i in range(_move_count[0]): mv = _move_list[i] if move_is_capture(mv): captures.append(mv) # Sort by MVV-LVA descending captures.sort( key=lambda a: PIECE_VALUE[piece_type(board[move_to(a)])] - PIECE_VALUE[piece_type(board[move_from(a)])] // 2, reverse=True ) for mv in captures: # Delta pruning gain = PIECE_VALUE[piece_type(board[move_to(mv)]) or 0] if stand + gain + 200 < alpha: continue make_move(mv) if is_attacked(king_pos[1 - side_to_move[0]], side_to_move[0]): unmake_move(); continue score = -quiesce(-beta, -alpha) unmake_move() if score >= beta: return beta if score > alpha: alpha = score return alpha # ── Repetition detection via undo-stack hash scan ── def _is_repetition(): cur = hash_key[0] # Walk back through undo entries; each entry stores the hash BEFORE that move, # so any match means the current position appeared earlier in this path. for u in undo_stack: if u[8] == cur: # index 8 = prev_hash field return True return False # ── Main negamax ── def negamax(depth, alpha, beta, ply, null_ok, prev_move=0): if (_nodes[0] & 2047) == 0 and _time_up(): return alpha _nodes[0] += 1 # ── Draw detection ── if half_move[0] >= 100: # 50-move rule return 0 if _is_repetition(): # position repetition return 0 # ── Transposition table probe ── h = hash_key[0] tt_idx = tt_probe(h) tt_best = 0 if tt_idx >= 0: tt_best = tt_move[tt_idx] if tt_depth[tt_idx] >= depth: s = tt_score[tt_idx]; f = tt_flag[tt_idx] if f == TT_EXACT: return s if f == TT_ALPHA and s <= alpha: return alpha if f == TT_BETA and s >= beta: return beta if depth <= 0: return quiesce(alpha, beta) in_check = is_in_check(side_to_move[0]) # ── Null-move pruning ── if null_ok and not in_check and depth >= 3: R = 3 if depth > 6 else 2 saved_ep = ep_square[0] saved_hash = hash_key[0] if ep_square[0] >= 0: hash_key[0] ^= ZOB_EP[sq_file(ep_square[0])] ep_square[0] = -1 side_to_move[0] ^= 1 hash_key[0] ^= ZOB_SIDE null_score = -negamax(depth - 1 - R, -beta, -beta + 1, ply + 1, False) side_to_move[0] ^= 1 hash_key[0] ^= ZOB_SIDE ep_square[0] = saved_ep hash_key[0] = saved_hash if ep_square[0] >= 0: hash_key[0] ^= ZOB_EP[sq_file(ep_square[0])] if null_score >= beta: return beta # ── Check extension ── ext_depth = depth + 1 if in_check else depth gen_moves(side_to_move[0]) moves = [_move_list[i] for i in range(_move_count[0])] sort_moves(moves, tt_best, ply, prev_move) legal_count = 0; best_move = 0; orig_alpha = alpha for i, mv in enumerate(moves): make_move(mv) if is_attacked(king_pos[1 - side_to_move[0]], side_to_move[0]): unmake_move(); continue legal_count += 1 # ── Futility pruning (depth 1-2 quiet moves) ── if depth <= 2 and not in_check and not move_is_capture(mv) and legal_count > 1: futility_margin = 200 if depth == 1 else 400 if evaluate() + futility_margin <= alpha: unmake_move(); continue # ── Late Move Reduction ── reduction = 0 if (depth >= 3 and i >= 4 and not in_check and not move_is_capture(mv) and move_flag(mv) != FLAG_DPUSH): reduction = 2 if depth >= 6 else 1 if reduction > 0: score = -negamax(ext_depth - 1 - reduction, -alpha - 1, -alpha, ply + 1, True, mv) if score > alpha: score = -negamax(ext_depth - 1, -beta, -alpha, ply + 1, True, mv) else: score = -negamax(ext_depth - 1, -beta, -alpha, ply + 1, True, mv) unmake_move() if (_nodes[0] & 2047) == 0 and _time_up(): return alpha if score > alpha: alpha = score; best_move = mv if score >= beta: # Update killers if not move_is_capture(mv): if killers[ply * 2] != mv: killers[ply * 2 + 1] = killers[ply * 2] killers[ply * 2] = mv hi = _hist_idx(side_to_move[0] ^ 1, move_from(mv), move_to(mv)) hist_heuristic[hi] += depth * depth if hist_heuristic[hi] > 1_000_000: for j in range(len(hist_heuristic)): hist_heuristic[j] >>= 1 # Countermove if prev_move: counter_move[move_from(prev_move) * 128 + move_to(prev_move)] = mv tt_store(h, depth, beta, TT_BETA, mv) return beta if legal_count == 0: return -(MATE - ply) if in_check else 0 # checkmate or stalemate tt_store(h, depth, alpha, TT_EXACT if alpha > orig_alpha else TT_ALPHA, best_move) return alpha # ── Iterative deepening with aspiration windows ── def search(): _search_start[0] = time.monotonic() * 1000 _nodes[0] = 0 for i in range(len(killers)): killers[i] = 0 # Quick legal-move check legal = legal_moves(side_to_move[0]) if not legal: return None if len(legal) == 1: return legal[0] # Smart time allocation _time_limit[0] = ( 1000 if len(legal) <= 3 else 2500 if len(legal) <= 8 else 4500 ) best_move = legal[0] prev_score = 0 for depth in range(1, 65): if _time_up(): break # Aspiration window if depth >= 5: alpha = prev_score - 50; beta = prev_score + 50 else: alpha = -INF; beta = INF while True: score = negamax(depth, alpha, beta, 0, False) if _time_up(): break if score <= alpha: alpha -= 100 elif score >= beta: beta += 100 else: break if not _time_up() or depth == 1: tt_idx = tt_probe(hash_key[0]) if tt_idx >= 0 and tt_move[tt_idx] != 0: best_move = tt_move[tt_idx] prev_score = score if _time_up(): break if score > MATE - 100: # forced mate found break return best_move # ────────────────────────────────────────────── # 13. I/O LOOP # ────────────────────────────────────────────── def main(): out = sys.stdout for line in sys.stdin: fen = line.strip() if not fen: continue try: # Opening book lookup (no tree search needed) book_move = get_book_move(fen) if book_move: out.write(book_move + '\n') out.flush() continue parse_fen(fen) best = search() if best is None or best == 0: out.write('0000\n') else: out.write(move_to_uci(best) + '\n') out.flush() except Exception as exc: sys.stderr.write(f'Error: {exc}\n') out.write('0000\n') out.flush() if __name__ == '__main__': main()