#!/usr/bin/env python3
"""
Claudius v2 - Super-Strong UCI Chess Engine
Advanced alpha-beta with SEE, counter-moves, singular extensions, king safety,
passed pawns, outpost bonuses, and comprehensive evaluation.
"""

import random, sys, time

INFINITY = 10000000
MAX_DEPTH = 64
HASH_SIZE = 16777216

PIECE_VALUES = [100, 320, 330, 500, 900, 0]

# Piece-square tables (mg [0] and eg [1])
PST = {
    'P': (
        [0,0,0,0,0,0,0,0,50,50,50,50,50,50,50,50,10,10,20,30,30,20,10,10,5,5,10,25,25,10,5,5,0,0,0,20,20,0,0,0,5,-5,-10,0,0,-10,-5,5,5,10,10,-20,-20,10,10,5,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    ),
    'N': (
        [-50,-40,-30,-30,-30,-30,-40,-50,-40,-20,0,0,0,0,-20,-40,-30,0,10,15,15,10,0,-30,-30,5,15,20,20,15,5,-30,-30,0,15,20,20,15,0,-30,-30,5,10,15,15,10,5,-30,-40,-20,0,5,5,0,-20,-40,-50,-40,-30,-30,-30,-30,-40,-50],
        [-50,-40,-30,-30,-30,-30,-40,-50,-40,-20,0,0,0,0,-20,-40,-30,0,10,15,15,10,0,-30,-30,5,15,20,20,15,5,-30,-30,0,15,20,20,15,0,-30,-30,5,10,15,15,10,5,-30,-40,-20,0,5,5,0,-20,-40,-50,-40,-30,-30,-30,-30,-40,-50]
    ),
    'B': (
        [-20,-10,-10,-10,-10,-10,-10,-20,-10,0,0,0,0,0,0,-10,-10,0,5,10,10,5,0,-10,-10,5,5,10,10,5,5,-10,-10,0,10,10,10,10,0,-10,-10,10,10,10,10,10,10,-10,-10,5,0,0,0,0,5,-10,-20,-10,-10,-10,-10,-10,-10,-20],
        [-40,-30,-20,-20,-20,-20,-30,-40,-30,0,0,0,0,0,0,-30,-20,0,5,5,5,5,0,-20,-20,0,5,5,5,5,0,-20,-20,0,5,5,5,5,0,-20,-20,0,5,5,5,5,0,-20,-20,0,0,0,0,0,0,-20,-40,-30,-20,-20,-20,-20,-30,-40]
    ),
    'R': (
        [0,0,0,0,0,0,0,0,5,10,10,10,10,10,10,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,0,0,0,0,0,0,-5,0,0,0,5,5,0,0,0,0,0,0,0,0,0,0,0,0],
        [-20,-10,-10,-10,-10,-10,-10,-10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-10]
    ),
    'Q': (
        [-20,-10,-10,-5,-5,-10,-10,-20,-10,0,0,0,0,0,0,-10,-10,0,5,5,5,5,0,-10,-5,0,5,5,5,5,0,-5,0,0,5,5,5,5,0,-5,-10,5,5,5,5,5,0,-10,-10,0,5,0,0,0,0,-10,-20,-10,-10,-5,-5,-10,-10,-20],
        [-20,-10,-10,-5,-5,-10,-10,-20,-10,0,0,0,0,0,0,-10,-10,0,5,5,5,5,0,-10,-5,0,5,5,5,5,0,-5,0,0,5,5,5,5,0,-5,-10,5,5,5,5,5,0,-10,-10,0,5,0,0,0,0,-10,-20,-10,-10,-5,-5,-10,-10,-20]
    ),
    'K': (
        [-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,-20,-30,-30,-40,-40,-30,-30,-20,-10,-20,-20,-20,-20,-20,-20,-10,20,30,10,0,0,10,30,20,20,30,10,0,0,10,30,20],
        [-50,-40,-30,-20,-20,-30,-40,-50,-30,-20,-10,0,0,-10,-20,-30,-30,-10,0,0,0,0,-10,-30,-30,-10,0,0,0,0,-10,-30,-20,-10,0,0,0,0,-10,-20,-30,-20,-10,0,0,0,0,-10,-20,-30,-30,-10,0,0,0,0,-10,-30,-30,-20,-10,0,0,0,0,-10,-30,-50,-40,-30,-20,-20,-30,-40,-50]
    )
}
PST_MIRROR = {p: (PST[p][0][::-1], PST[p][1][::-1]) for p in PST}

TYPE_NORMAL = 0
TYPE_PROMOTION = 1
TYPE_EN_PASSANT = 2
TYPE_CASTLE = 3

N_OFFSETS = [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]
K_OFFSETS = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

# Pawn attack tables for each color (indexed by square, gives bitboard of squares pawn attacks)
def build_pawn_attacks():
    white = [0] * 64
    black = [0] * 64
    for sq in range(64):
        r, c = sq // 8, sq % 8
        if c > 0 and r > 0: white[sq] |= 1 << ((r - 1) * 8 + (c - 1))
        if c < 7 and r > 0: white[sq] |= 1 << ((r - 1) * 8 + (c + 1))
        if c > 0 and r < 7: black[sq] |= 1 << ((r + 1) * 8 + (c - 1))
        if c < 7 and r < 7: black[sq] |= 1 << ((r + 1) * 8 + (c + 1))
    return white, black

PAWN_ATTACKS_WHITE, PAWN_ATTACKS_BLACK = build_pawn_attacks()

# Sliding piece attack masks
def build_sliding_masks():
    rook_mask = [0] * 64
    bishop_mask = [0] * 64
    for sq in range(64):
        r, c = sq // 8, sq % 8
        # Rook rays
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r + dr, c + dc
            while 0 <= nr < 8 and 0 <= nc < 8:
                rook_mask[sq] |= 1 << (nr * 8 + nc)
                nr += dr; nc += dc
        # Bishop rays
        for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
            nr, nc = r + dr, c + dc
            while 0 <= nr < 8 and 0 <= nc < 8:
                bishop_mask[sq] |= 1 << (nr * 8 + nc)
                nr += dr; nc += dc
    return rook_mask, bishop_mask

ROOK_MASK, BISHOP_MASK = build_sliding_masks()

class Move:
    __slots__ = ['from_sq','to_sq','piece','captured','promotion','type','score']
    def __init__(self, fs, ts, p=0, c=0, promo=0, t=TYPE_NORMAL):
        self.from_sq, self.to_sq, self.piece, self.captured = fs, ts, p, c
        self.promotion, self.type = promo, t
        self.score = 0
    def uci(self):
        f = chr(97 + (self.from_sq & 7)) + str(8 - (self.from_sq >> 3))
        t = chr(97 + (self.to_sq & 7)) + str(8 - (self.to_sq >> 3))
        return f + t + ('qrbn'[self.promotion - 2] if self.type == TYPE_PROMOTION else '')
    def __eq__(self, other):
        return self.from_sq == other.from_sq and self.to_sq == other.to_sq
    def __hash__(self):
        return (self.from_sq << 6) | self.to_sq

class Entry:
    __slots__ = ['key','depth','score','flag','best']
    def __init__(self):
        self.key = self.depth = self.score = self.flag = 0
        self.best = None

class TranspositionTable:
    __slots__ = ['entries','size']
    def __init__(self, size):
        self.entries = [Entry() for _ in range(size)]
        self.size = size
    def probe(self, key, d, a, b):
        e = self.entries[key % self.size]
        if e.key == key and e.depth >= d:
            if e.flag == 0: return e.score
            if e.flag == 1 and e.score >= b: return e.score
            if e.flag == 2 and e.score <= a: return e.score
        return None
    def store(self, key, d, score, flag, best=None):
        i = key % self.size
        e = self.entries[i]
        if e.key != key or e.depth <= d:
            e.key, e.depth, e.score, e.flag, e.best = key, d, score, flag, best
    def clear(self):
        for e in self.entries: e.key = e.depth = e.score = e.flag = 0; e.best = None

class Board:
    __slots__ = ('colors','pieces','side','castle','ep_sq','hash_key','king_sq','material','zobrist','zobrist_side','zobrist_castle','zobrist_ep','pawns','attack_tables')

    def __init__(self):
        self.colors = [0] * 64
        self.pieces = [[], [], [], [], [], []]
        self.side = 1
        self.castle = 0
        self.ep_sq = -1
        self.hash_key = 0
        self.king_sq = [0, 0]
        self.material = [0, 0]
        self.pawns = [0, 0]  # bitboards for white/black pawns
        self.attack_tables = None

    def init_zobrist(self):
        random.seed(42)
        self.zobrist = [random.getrandbits(64) for _ in range(768)]
        self.zobrist_side = random.getrandbits(64)
        self.zobrist_castle = [random.getrandbits(64) for _ in range(16)]
        self.zobrist_ep = [random.getrandbits(64) for _ in range(8)]
        self.compute_hash()

    def set_fen(self, fen):
        self.pieces = [[], [], [], [], [], []]
        self.colors = [0] * 64
        self.pawns = [0, 0]
        parts = fen.split()
        rows = parts[0].split('/')
        for r, row in enumerate(rows):
            col = 0
            for c in row:
                if c.isdigit():
                    col += int(c)
                elif col < 8:
                    sq = r * 8 + col
                    color = 1 if c.isupper() else 2
                    self.colors[sq] = color
                    idx = 'PNBRQK'.index(c.upper())
                    self.pieces[idx].append(sq)
                    if idx == 0:
                        if color == 1: self.pawns[0] |= 1 << sq
                        else: self.pawns[1] |= 1 << sq
                    if idx == 5: self.king_sq[color - 1] = sq
                    col += 1
        self.side = 1 if parts[1] == 'w' else 2
        self.castle = 0
        for c in parts[2]:
            if c == 'K': self.castle |= 1
            elif c == 'Q': self.castle |= 2
            elif c == 'k': self.castle |= 4
            elif c == 'q': self.castle |= 8
        self.ep_sq = -1
        if len(parts) > 3 and parts[3] != '-':
            self.ep_sq = (ord(parts[3][0]) - 97) + (int(parts[3][1]) - 1) * 8
        self.compute_material()
        self.compute_hash()

    def compute_material(self):
        self.material = [0, 0]
        for sq in range(64):
            c = self.colors[sq]
            if c:
                idx = (c - 1) % 6
                val = PIECE_VALUES[idx]
                if c == 2: val = -val
                self.material[(c - 1) % 2] += val

    def compute_hash(self):
        self.hash_key = 0
        for sq in range(64):
            c = self.colors[sq]
            if c: self.hash_key ^= self.zobrist[c * 64 + sq]
        if self.side == 2: self.hash_key ^= self.zobrist_side
        self.hash_key ^= self.zobrist_castle[self.castle]
        if self.ep_sq >= 0: self.hash_key ^= self.zobrist_ep[self.ep_sq & 7]

    def is_attacked(self, sq, by_color):
        dir = -1 if by_color == 1 else 1
        for df in [-1, 1]:
            s = sq + dir * 8 + df
            if 0 <= s < 64 and self.colors[s] == by_color and s in self.pieces[0]: return True
        for dr, dc in N_OFFSETS:
            s = sq + dr * 8 + dc
            if 0 <= s < 64 and self.colors[s] == by_color and s in self.pieces[1]: return True
        for dr, dc in K_OFFSETS:
            s = sq + dr * 8 + dc
            if 0 <= s < 64 and self.colors[s] == by_color and s in self.pieces[5]: return True
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            r, c = sq // 8 + dr, sq % 8 + dc
            while 0 <= r < 8 and 0 <= c < 8:
                s = r * 8 + c
                if self.colors[s]:
                    if self.colors[s] == by_color and s in self.pieces[3]: return True
                    if self.colors[s] == by_color and s in self.pieces[4]: return True
                    break
                r += dr; c += dc
        for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
            r, c = sq // 8 + dr, sq % 8 + dc
            while 0 <= r < 8 and 0 <= c < 8:
                s = r * 8 + c
                if self.colors[s]:
                    if self.colors[s] == by_color and s in self.pieces[2]: return True
                    if self.colors[s] == by_color and s in self.pieces[4]: return True
                    break
                r += dr; c += dc
        return False

    # SEE - Static Exchange Evaluation (returns gain)
    def see(self, move):
        if move.type == TYPE_CASTLE or move.type == TYPE_EN_PASSANT: return 0
        if not move.captured: return 0
        gain = [PIECE_VALUES[(move.captured - 1) % 6]]
        from_sq, to_sq = move.from_sq, move.to_sq
        color = self.side
        enemy = 3 - color
        # Simulate capture
        captured = self.colors[to_sq]
        moving_piece = self.colors[from_sq]
        self.colors[to_sq] = moving_piece
        self.colors[from_sq] = 0
        if move.type == TYPE_PROMOTION:
            gain[0] = PIECE_VALUES[move.promotion - 2] - 100
            for i, s in enumerate(self.pieces[0]):
                if s == to_sq: self.pieces[0][i] = -1; break
            self.pieces[move.promotion - 2].append(to_sq)
        else:
            for i, s in enumerate(self.pieces[(moving_piece - 1) % 6]):
                if s == from_sq: self.pieces[(moving_piece - 1) % 6][i] = to_sq; break
        # Determine attackers
        sq = to_sq
        while True:
            color = 3 - color
            enemy = 3 - color
            # Pawn attacks
            atk_dir = -1 if color == 1 else 1
            found = False
            for df in [-1, 1]:
                s = sq + atk_dir * 8 + df
                if 0 <= s < 64 and self.colors[s] == color and s in self.pieces[0]:
                    gain.append(100)
                    self.colors[s] = 0
                    sq = s
                    found = True
                    break
            if found: continue
            # Knight
            for dr, dc in N_OFFSETS:
                s = sq + dr * 8 + dc
                if 0 <= s < 64 and self.colors[s] == color and s in self.pieces[1]:
                    gain.append(320)
                    self.colors[s] = 0
                    sq = s
                    found = True
                    break
            if found: continue
            # Bishop/slider
            for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
                r, c = sq // 8 + dr, sq % 8 + dc
                while 0 <= r < 8 and 0 <= c < 8:
                    s = r * 8 + c
                    if self.colors[s]:
                        if self.colors[s] == color and s in self.pieces[2]:
                            gain.append(330)
                            self.colors[s] = 0
                            sq = s
                            found = True
                        break
                    r += dr; c += dc
            if found: continue
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                r, c = sq // 8 + dr, sq % 8 + dc
                while 0 <= r < 8 and 0 <= c < 8:
                    s = r * 8 + c
                    if self.colors[s]:
                        if self.colors[s] == color and s in self.pieces[3]:
                            gain.append(500)
                            self.colors[s] = 0
                            sq = s
                            found = True
                        break
                    r += dr; c += dc
            if found: continue
            break
        # Restore board
        self.colors[from_sq] = moving_piece
        self.colors[to_sq] = captured
        for i, s in enumerate(self.pieces[(moving_piece - 1) % 6]):
            if s == to_sq: self.pieces[(moving_piece - 1) % 6][i] = from_sq; break
        if move.type == TYPE_PROMOTION:
            for i, s in enumerate(self.pieces[move.promotion - 2]):
                if s == to_sq: self.pieces[move.promotion - 2].remove(to_sq); break
            for i, s in enumerate(self.pieces[0]):
                if s == -1: self.pieces[0][i] = to_sq; break
        # Score from perspective of the side making the original move
        see_val = 0
        for i in range(len(gain) - 1, -1, -1):
            see_val = max(0, gain[i] - see_val) if i == len(gain) - 1 else max(0, gain[i] - see_val)
        return see_val

    def generate_moves(self, legal=True):
        moves = []
        color = self.side
        enemy = 3 - color
        for piece_idx, sq_list in enumerate(self.pieces):
            for sq in sq_list[:]:
                if self.colors[sq] != color: continue
                if piece_idx == 0:
                    dir = -8 if color == 1 else 8
                    start_r = 6 if color == 1 else 1
                    promo_r = 7 if color == 1 else 0
                    ns = sq + dir
                    if 0 <= ns < 64 and self.colors[ns] == 0:
                        if ns // 8 == promo_r:
                            for promo in [4, 3, 2, 1]:
                                moves.append(Move(sq, ns, 0, 0, promo, TYPE_PROMOTION))
                        else:
                            moves.append(Move(sq, ns))
                            if sq // 8 == start_r:
                                ns2 = sq + dir * 2
                                if self.colors[ns2] == 0: moves.append(Move(sq, ns2))
                    for df in [-1, 1]:
                        ns = sq + dir + df
                        if 0 <= ns < 64:
                            if self.colors[ns] == enemy:
                                if ns // 8 == promo_r:
                                    for promo in [4, 3, 2, 1]:
                                        moves.append(Move(sq, ns, 0, enemy, promo, TYPE_PROMOTION))
                                else: moves.append(Move(sq, ns, 0, enemy))
                            elif ns == self.ep_sq: moves.append(Move(sq, ns, 0, enemy, 0, TYPE_EN_PASSANT))
                elif piece_idx == 1:
                    for dr, dc in N_OFFSETS:
                        ns = sq + dr * 8 + dc
                        if 0 <= ns < 64 and self.colors[ns] != color: moves.append(Move(sq, ns, 0, self.colors[ns]))
                elif piece_idx == 2:
                    for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
                        r, c = sq // 8 + dr, sq % 8 + dc
                        while 0 <= r < 8 and 0 <= c < 8:
                            ns = r * 8 + c
                            if self.colors[ns]:
                                if self.colors[ns] == enemy: moves.append(Move(sq, ns, 0, enemy))
                                break
                            moves.append(Move(sq, ns)); r += dr; c += dc
                elif piece_idx == 3:
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        r, c = sq // 8 + dr, sq % 8 + dc
                        while 0 <= r < 8 and 0 <= c < 8:
                            ns = r * 8 + c
                            if self.colors[ns]:
                                if self.colors[ns] == enemy: moves.append(Move(sq, ns, 0, enemy))
                                break
                            moves.append(Move(sq, ns)); r += dr; c += dc
                elif piece_idx == 4:
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]:
                        r, c = sq // 8 + dr, sq % 8 + dc
                        while 0 <= r < 8 and 0 <= c < 8:
                            ns = r * 8 + c
                            if self.colors[ns]:
                                if self.colors[ns] == enemy: moves.append(Move(sq, ns, 0, enemy))
                                break
                            moves.append(Move(sq, ns)); r += dr; c += dc
                elif piece_idx == 5:
                    for dr, dc in K_OFFSETS:
                        ns = sq + dr * 8 + dc
                        if 0 <= ns < 64 and self.colors[ns] != color: moves.append(Move(sq, ns, 0, self.colors[ns]))
        cr = self.castle
        if color == 1:
            if (cr & 1) and self.colors[61] == 0 and self.colors[62] == 0:
                if not self.is_attacked(60, 2) and not self.is_attacked(61, 2) and not self.is_attacked(62, 2):
                    moves.append(Move(60, 62, 0, 0, 0, TYPE_CASTLE))
            if (cr & 2) and self.colors[57] == 0 and self.colors[58] == 0 and self.colors[59] == 0:
                if not self.is_attacked(60, 2) and not self.is_attacked(59, 2) and not self.is_attacked(58, 2):
                    moves.append(Move(60, 58, 0, 0, 0, TYPE_CASTLE))
        else:
            if (cr & 4) and self.colors[5] == 0 and self.colors[6] == 0:
                if not self.is_attacked(4, 1) and not self.is_attacked(5, 1) and not self.is_attacked(6, 1):
                    moves.append(Move(4, 6, 0, 0, 0, TYPE_CASTLE))
            if (cr & 8) and self.colors[1] == 0 and self.colors[2] == 0 and self.colors[3] == 0:
                if not self.is_attacked(4, 1) and not self.is_attacked(3, 1) and not self.is_attacked(2, 1):
                    moves.append(Move(4, 2, 0, 0, 0, TYPE_CASTLE))
        if legal: moves = [m for m in moves if self.is_legal(m)]
        return moves

    def is_legal(self, move):
        if move.type == TYPE_CASTLE: return True
        color = self.side
        from_sq, to_sq = move.from_sq, move.to_sq
        moving_piece = self.colors[from_sq]
        captured = self.colors[to_sq]
        saved_ep = saved_pp = -1
        if move.type == TYPE_EN_PASSANT:
            ep_sq = to_sq - (8 if color == 1 else -8)
            saved_ep = self.colors[ep_sq]
            self.colors[ep_sq] = 0
        if move.type == TYPE_PROMOTION:
            for i, s in enumerate(self.pieces[0]):
                if s == to_sq: saved_pp = i; self.pieces[0][i] = -1; break
            self.pieces[move.promotion - 2].append(to_sq)
        for i, s in enumerate(self.pieces[(moving_piece - 1) % 6]):
            if s == from_sq: self.pieces[(moving_piece - 1) % 6][i] = to_sq; break
        self.colors[to_sq] = moving_piece
        self.colors[from_sq] = 0
        king_sq = self.king_sq[color - 1]
        if from_sq == king_sq: king_sq = to_sq
        legal = not self.is_attacked(king_sq, 3 - color)
        self.colors[from_sq] = moving_piece
        self.colors[to_sq] = captured
        for i, s in enumerate(self.pieces[(moving_piece - 1) % 6]):
            if s == to_sq: self.pieces[(moving_piece - 1) % 6][i] = from_sq; break
        if move.type == TYPE_EN_PASSANT:
            ep_sq = to_sq - (8 if color == 1 else -8)
            self.colors[ep_sq] = saved_ep
        if move.type == TYPE_PROMOTION:
            self.pieces[move.promotion - 2].remove(to_sq)
            self.pieces[0][saved_pp] = to_sq
        return legal

    def make_move(self, move):
        from_sq, to_sq = move.from_sq, move.to_sq
        color = self.side
        enemy = 3 - color
        moving_piece = self.colors[from_sq]
        piece_idx = (moving_piece - 1) % 6
        saved_cap = captured_idx = -1
        saved_pp = None
        # Handle captures
        if move.type == TYPE_EN_PASSANT:
            ep_sq = to_sq - (8 if color == 1 else -8)
            for i, s in enumerate(self.pieces[0]):
                if s == ep_sq: captured_idx = i; self.pieces[0][i] = -1; break
            self.material[enemy % 2] -= 100
            if color == 1: self.pawns[0] &= ~(1 << ep_sq)
            else: self.pawns[1] &= ~(1 << ep_sq)
        elif self.colors[to_sq]:
            cap_idx = (self.colors[to_sq] - 1) % 6
            for i, s in enumerate(self.pieces[cap_idx]):
                if s == to_sq: captured_idx = i; self.pieces[cap_idx][i] = -1; break
            self.material[enemy % 2] -= PIECE_VALUES[cap_idx]
        # Update position
        self.colors[to_sq] = moving_piece
        self.colors[from_sq] = 0
        for i, s in enumerate(self.pieces[piece_idx]):
            if s == from_sq: self.pieces[piece_idx][i] = to_sq; break
        # Handle promotion
        if move.type == TYPE_PROMOTION:
            for i, s in enumerate(self.pieces[0]):
                if s == to_sq: saved_pp = i; self.pieces[0][i] = -1; break
            promo_idx = move.promotion - 2
            self.pieces[promo_idx].append(to_sq)
            self.material[color % 2] += PIECE_VALUES[promo_idx] - 100
            if color == 1: self.pawns[0] &= ~(1 << to_sq)
            else: self.pawns[1] &= ~(1 << to_sq)
        # Handle castling
        if move.type == TYPE_CASTLE:
            if to_sq == 62:
                self.colors[61] = 1; self.colors[63] = 0
                for i, s in enumerate(self.pieces[3]):
                    if s == 63: self.pieces[3][i] = 61; break
            elif to_sq == 58:
                self.colors[59] = 1; self.colors[56] = 0
                for i, s in enumerate(self.pieces[3]):
                    if s == 56: self.pieces[3][i] = 59; break
            elif to_sq == 6:
                self.colors[5] = 2; self.colors[7] = 0
                for i, s in enumerate(self.pieces[3]):
                    if s == 7: self.pieces[3][i] = 5; break
            elif to_sq == 2:
                self.colors[3] = 2; self.colors[0] = 0
                for i, s in enumerate(self.pieces[3]):
                    if s == 0: self.pieces[3][i] = 3; break
        # Update pawn position
        if piece_idx == 0:
            if color == 1: self.pawns[0] = (self.pawns[0] & ~(1 << from_sq)) | (1 << to_sq)
            else: self.pawns[1] = (self.pawns[1] & ~(1 << from_sq)) | (1 << to_sq)
        # Update king
        if piece_idx == 5: self.king_sq[color - 1] = to_sq
        # En passant square
        self.ep_sq = -1
        if piece_idx == 0:
            if color == 1 and from_sq // 8 == 6 and to_sq // 8 == 4: self.ep_sq = from_sq + 8
            elif color == 2 and from_sq // 8 == 1 and to_sq // 8 == 3: self.ep_sq = from_sq - 8
        # Castling rights
        if from_sq in [0, 7]: self.castle &= ~1 if color == 1 else ~4
        if from_sq in [56, 63]: self.castle &= ~2 if color == 1 else ~8
        self.side = enemy
        self.compute_hash()

    def unmake_move(self, move):
        from_sq, to_sq = move.from_sq, move.to_sq
        color = 3 - self.side
        enemy = self.side
        moving_piece = self.colors[to_sq]
        piece_idx = (moving_piece - 1) % 6
        # Restore position
        self.colors[from_sq] = moving_piece
        self.colors[to_sq] = 0
        for i, s in enumerate(self.pieces[piece_idx]):
            if s == to_sq: self.pieces[piece_idx][i] = from_sq; break
        # Restore captured
        if move.type == TYPE_EN_PASSANT:
            ep_sq = to_sq - (8 if color == 1 else -8)
            for i, s in enumerate(self.pieces[0]):
                if s == -1: self.pieces[0][i] = ep_sq; break
            self.material[enemy % 2] += 100
            if color == 1: self.pawns[0] |= 1 << ep_sq
            else: self.pawns[1] |= 1 << ep_sq
        elif move.captured:
            cap_idx = (move.captured - 1) % 6
            self.pieces[cap_idx].append(to_sq)
            self.colors[to_sq] = move.captured
            self.material[enemy % 2] += PIECE_VALUES[cap_idx]
        # Undo promotion
        if move.type == TYPE_PROMOTION:
            promo_idx = move.promotion - 2
            for i, s in enumerate(self.pieces[promo_idx]):
                if s == to_sq: self.pieces[promo_idx].remove(to_sq); break
            for i, s in enumerate(self.pieces[0]):
                if s == -1: self.pieces[0][i] = to_sq; break
            self.material[color % 2] -= PIECE_VALUES[promo_idx] - 100
            if color == 1: self.pawns[0] |= 1 << to_sq
            else: self.pawns[1] |= 1 << to_sq
        # Undo castling
        if move.type == TYPE_CASTLE:
            if to_sq == 62:
                self.colors[60] = moving_piece; self.colors[61] = 0; self.colors[63] = color
                for i, s in enumerate(self.pieces[3]):
                    if s == 61: self.pieces[3][i] = 63; break
            elif to_sq == 58:
                self.colors[60] = moving_piece; self.colors[59] = 0; self.colors[56] = color
                for i, s in enumerate(self.pieces[3]):
                    if s == 59: self.pieces[3][i] = 56; break
            elif to_sq == 6:
                self.colors[4] = moving_piece; self.colors[5] = 0; self.colors[7] = color
                for i, s in enumerate(self.pieces[3]):
                    if s == 5: self.pieces[3][i] = 7; break
            elif to_sq == 2:
                self.colors[4] = moving_piece; self.colors[3] = 0; self.colors[0] = color
                for i, s in enumerate(self.pieces[3]):
                    if s == 3: self.pieces[3][i] = 0; break
        # Restore pawn position
        if piece_idx == 0:
            if color == 1: self.pawns[0] = (self.pawns[0] & ~(1 << to_sq)) | (1 << from_sq)
            else: self.pawns[1] = (self.pawns[1] & ~(1 << to_sq)) | (1 << from_sq)
        # Restore king
        if piece_idx == 5: self.king_sq[color - 1] = from_sq
        self.side = color
        self.compute_hash()

    def evaluate(self):
        mg = self.material[0] - self.material[1]
        eg = 0
        for sq in range(64):
            c = self.colors[sq]
            if c:
                idx = (c - 1) % 6
                pc = 'PNBRQK'[idx]
                if c == 1:
                    mg += PST[pc][0][sq]
                    eg += PST[pc][1][sq]
                else:
                    mg -= PST[pc][0][63 - sq]
                    eg -= PST[pc][1][63 - sq]
        # Bishop pair
        wb = len([s for s in self.pieces[2] if self.colors[s] == 1])
        bb = len([s for s in self.pieces[2] if self.colors[s] == 2])
        if wb >= 2: mg += 30; eg += 50
        if bb >= 2: mg -= 30; eg -= 50
        # Rook on open/semi-open files
        for sq in self.pieces[3]:
            c = self.colors[sq]
            if not c: continue
            file_mask = 0x0101010101010101 << (sq & 7)
            white_pawns_on_file = self.pawns[0] & file_mask
            black_pawns_on_file = self.pawns[1] & file_mask
            if c == 1:
                if not white_pawns_on_file and not black_pawns_on_file: mg += 25  # open
                elif not white_pawns_on_file: mg += 15  # semi-open
            else:
                if not white_pawns_on_file and not black_pawns_on_file: mg -= 25
                elif not black_pawns_on_file: mg -= 15
        # Passed pawns
        for sq in self.pieces[0]:
            if self.colors[sq] != 1: continue
            r, c = sq // 8, sq & 7
            # Check if passed (no enemy pawn ahead)
            passed = True
            pawn_dir = 8
            for dr in range(1, 8 - r):
                if self.pawns[1] & (1 << ((r + dr) * 8 + c)): passed = False; break
                if c > 0 and self.pawns[1] & (1 << ((r + dr) * 8 + c - 1)): passed = False; break
                if c < 7 and self.pawns[1] & (1 << ((r + dr) * 8 + c + 1)): passed = False; break
            if passed:
                mg += 15; eg += 30
                # Connected passed pawns
                for friend_sq in self.pieces[0]:
                    if friend_sq == sq or self.colors[friend_sq] != 1: continue
                    if abs((friend_sq & 7) - c) == 1 and friend_sq // 8 == r:
                        mg += 10; eg += 20
        for sq in self.pieces[0]:
            if self.colors[sq] != 2: continue
            r, c = sq // 8, sq & 7
            passed = True
            for dr in range(1, r + 1):
                if self.pawns[0] & (1 << ((r - dr) * 8 + c)): passed = False; break
                if c > 0 and self.pawns[0] & (1 << ((r - dr) * 8 + c - 1)): passed = False; break
                if c < 7 and self.pawns[0] & (1 << ((r - dr) * 8 + c + 1)): passed = False; break
            if passed:
                mg -= 15; eg -= 30
                for friend_sq in self.pieces[0]:
                    if self.colors[friend_sq] != 2: continue
                    if abs((friend_sq & 7) - c) == 1 and friend_sq // 8 == r:
                        mg -= 10; eg -= 20
        # King safety in middlegame
        if sum(self.material) > 3000:
            wk_sq = self.king_sq[0]
            bk_sq = self.king_sq[1]
            # White king pawn shield
            wk_file = wk_sq & 7
            shield_bonus = 0
            if wk_sq // 8 == 0:  # king on back rank
                if wk_file >= 1 and (self.pawns[0] & (1 << (1 * 8 + wk_file - 1))): shield_bonus += 10
                if wk_file <= 6 and (self.pawns[0] & (1 << (1 * 8 + wk_file + 1))): shield_bonus += 10
            if shield_bonus: mg += shield_bonus
            # Black king
            if bk_sq // 8 == 7:
                bk_file = bk_sq & 7
                if bk_file >= 1 and (self.pawns[1] & (1 << (6 * 8 + bk_file - 1))): mg -= 10
                if bk_file <= 6 and (self.pawns[1] & (1 << (6 * 8 + bk_file + 1))): mg -= 10
        # Knight outpost bonus
        for sq in self.pieces[1]:
            if self.colors[sq] != 1: continue
            r, c = sq // 8, sq & 7
            if r >= 3 and r <= 5:
                # Can be attacked by enemy pawn but not occupied by enemy pawn
                if not (self.pawns[1] & (1 << sq)):
                    # Check if supported by own pawn
                    if (c > 0 and self.pawns[0] & (1 << ((r - 1) * 8 + c - 1))) or \
                       (c < 7 and self.pawns[0] & (1 << ((r - 1) * 8 + c + 1))):
                        mg += 20
        for sq in self.pieces[1]:
            if self.colors[sq] != 2: continue
            r, c = sq // 8, sq & 7
            if r >= 2 and r <= 4:
                if not (self.pawns[0] & (1 << sq)):
                    if (c > 0 and self.pawns[1] & (1 << ((r + 1) * 8 + c - 1))) or \
                       (c < 7 and self.pawns[1] & (1 << ((r + 1) * 8 + c + 1))):
                        mg -= 20
        # Tapered eval
        phase = min(24, max(0, 24 - (self.material[0] - self.material[1] - 2000) // 70))
        score = (mg * (24 - phase) + eg * phase) // 24
        return score

    def is_check(self):
        return self.is_attacked(self.king_sq[self.side - 1], 3 - self.side)
    def is_checkmate(self):
        return self.is_check() and len(self.generate_moves()) == 0
    def is_stalemate(self):
        return not self.is_check() and len(self.generate_moves()) == 0

class Engine:
    __slots__ = ('board','tt','best_move','nodes','depth','history','killers','counter','start_time','sel_depth')

    def __init__(self, board):
        self.board = board
        board.init_zobrist()
        self.tt = TranspositionTable(HASH_SIZE)
        self.tt.clear()
        self.best_move = None
        self.nodes = 0
        self.depth = 0
        self.history = [[0] * 64 for _ in range(2)]
        self.killers = [[None, None] for _ in range(64)]
        self.counter = [[None] * 64 for _ in range(64)]  # counter-move table
        self.start_time = time.time()
        self.sel_depth = 0

    def search(self, max_time=4.5):
        start = time.time()
        self.start_time = start
        best_score = -INFINITY
        best_move = None
        for depth in range(1, MAX_DEPTH + 1):
            self.depth = depth
            self.nodes = 0
            alpha = best_score - 30
            beta = best_score + 30
            score = self.negamax(depth, alpha, beta, False, 0)
            if score > best_score:
                best_score = score
                best_move = self.best_move
            if time.time() - start > max_time * 0.9: break
            if abs(score) > 9000: break
            # Emergency time check
            if time.time() - start > max_time * 0.7 and depth > 3: break
        return best_move if best_move else self.best_move

    def order_moves(self, moves, tt_best=None, depth=0, ply=0):
        for m in moves:
            score = 0
            if tt_best and m == tt_best: score += 10000000
            if m.captured:
                # MVV-LVA with SEE
                see_score = self.board.see(m)
                score += m.captured * 1000 + see_score - ((m.piece - 1) % 6) * 200
            else:
                # Quiet move bonuses
                ki = self.killers[m.to_sq]
                if ki[0] and m == ki[0]: score += 900000
                elif ki[1] and m == ki[1]: score += 800000
                # Counter-move
                cm = self.counter[m.from_sq][m.to_sq]
                if cm: score += 700000
                # History
                score += self.history[(self.board.side - 1) % 2][m.to_sq]
                # Late move relative ordering
                score -= (len(moves) - moves.index(m)) * 10
            m.score = score
        moves.sort(key=lambda m: m.score, reverse=True)

    def negamax(self, depth, alpha, beta, cutnode, ply):
        if self.board.is_checkmate(): return -9999 + self.depth - depth
        if self.board.is_stalemate(): return 0
        # Quiescence at horizon
        if depth <= 0:
            self.sel_depth = max(self.sel_depth, ply)
            return self.quiescence(alpha, beta)
        self.nodes += 1
        if self.nodes > 5000000: return 0
        # Mate distance pruning
        mate_value = 9999 - ply
        if -mate_value < beta:
            beta = -mate_value
            if alpha < -mate_value: alpha = -mate_value
        if mate_value < alpha: return mate_value
        # TT lookup
        tt_entry = self.tt.entries[self.board.hash_key % self.tt.size]
        tt_best = tt_entry.best if tt_entry.key == self.board.hash_key else None
        if tt_entry.key == self.board.hash_key and tt_entry.depth >= depth:
            if tt_entry.flag == 0: return tt_entry.score
            if tt_entry.flag == 1: alpha = max(alpha, tt_entry.score)
            elif tt_entry.flag == 2: beta = min(beta, tt_entry.score)
            if alpha >= beta: return tt_entry.score
        # Null move (razoring) - NOT in check, not near leaf
        if not self.board.is_check() and depth >= 3 and sum(self.board.material) > 2000 and ply > 0:
            old_side = self.board.side
            old_ep = self.board.ep_sq
            old_hash = self.board.hash_key
            self.board.side = 3 - old_side
            self.board.ep_sq = -1
            self.board.hash_key ^= self.board.zobrist_side
            R = 3 if depth > 6 else 2
            null_score = -self.negamax(depth - 1 - R, -beta, -beta + 1, True, ply + 1)
            self.board.side = old_side
            self.board.ep_sq = old_ep
            self.board.hash_key = old_hash
            if null_score >= beta: return beta
        # Internal iterative deepening
        if depth >= 4 and (tt_entry.key != self.board.hash_key or tt_entry.depth < depth - 2):
            self.negamax(depth // 2, alpha, beta, cutnode, ply)
            tt_entry = self.tt.entries[self.board.hash_key % self.tt.size]
            tt_best = tt_entry.best if tt_entry.key == self.board.hash_key else None
        moves = self.board.generate_moves()
        self.order_moves(moves, tt_best, depth, ply)
        best_score = -INFINITY
        best_move_in_line = None
        legal = 0
        best_flag = 2
        for i, m in enumerate(moves):
            # SEE-based pruning for captures at low depths
            if depth <= 3 and m.captured and self.board.see(m) < -100 * depth:
                continue
            # LMR
            if depth >= 3 and legal >= 4 and not cutnode and m.type == TYPE_NORMAL and not m.captured:
                R = 2 + i // 4
                score = -self.negamax(depth - 1 - R, -alpha - 1, -alpha, True, ply + 1)
                if score > alpha:
                    score = -self.negamax(depth - 1, -beta, -alpha, False, ply + 1)
            else:
                # Singularity detection (extensions)
                extension = 0
                if depth >= 8 and m == tt_best and tt_entry.key == self.board.hash_key and tt_entry.depth >= depth - 3 and tt_entry.flag == 1 and abs(tt_entry.score) < 9000:
                    extension = 1
                score = -self.negamax(depth - 1 + extension, -beta, -alpha, cutnode, ply + 1)
            self.board.unmake_move(m)
            if score > best_score:
                best_score = score
                best_move_in_line = m
            if score > alpha:
                alpha = score
                best_flag = 1 if score < beta else 0
                if score >= beta:
                    if m.type == TYPE_NORMAL:
                        self.killers[m.to_sq][1] = self.killers[m.to_sq][0]
                        self.killers[m.to_sq][0] = m
                        self.history[(self.board.side - 1) % 2][m.to_sq] += depth * depth
                        if m.from_sq < 64 and m.to_sq < 64:
                            self.counter[m.from_sq][m.to_sq] = m
                    break
            legal += 1
        if len(moves) == 0:
            if self.board.is_check(): return -9999 + self.depth - depth
            return 0
        if best_move_in_line:
            self.tt.store(self.board.hash_key, depth, best_score, best_flag, best_move_in_line)
            if depth == self.depth: self.best_move = best_move_in_line
        return alpha if best_score == -INFINITY else best_score

    def quiescence(self, alpha, beta):
        self.nodes += 1
        stand_pat = self.board.evaluate()
        if stand_pat >= beta: return beta
        if stand_pat > alpha: alpha = stand_pat
        moves = []
        color = self.board.side
        for piece_idx, sq_list in enumerate(self.board.pieces):
            for sq in sq_list[:]:
                if self.board.colors[sq] != color: continue
                if piece_idx == 0:
                    dir = -8 if color == 1 else 8
                    for df in [-1, 1]:
                        ns = sq + dir + df
                        if 0 <= ns < 64 and self.board.colors[ns]:
                            moves.append(Move(sq, ns, 0, self.board.colors[ns]))
                elif piece_idx in [3, 4]:
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        r, c = sq // 8 + dr, sq % 8 + dc
                        while 0 <= r < 8 and 0 <= c < 8:
                            ns = r * 8 + c
                            if self.board.colors[ns]:
                                if self.board.colors[ns] != color: moves.append(Move(sq, ns, 0, self.board.colors[ns]))
                                break
                            r += dr; c += dc
                elif piece_idx in [2, 4]:
                    for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
                        r, c = sq // 8 + dr, sq % 8 + dc
                        while 0 <= r < 8 and 0 <= c < 8:
                            ns = r * 8 + c
                            if self.board.colors[ns]:
                                if self.board.colors[ns] != color: moves.append(Move(sq, ns, 0, self.board.colors[ns]))
                                break
                            r += dr; c += dc
                elif piece_idx == 1:
                    for dr, dc in N_OFFSETS:
                        ns = sq + dr * 8 + dc
                        if 0 <= ns < 64 and self.board.colors[ns] and self.board.colors[ns] != color:
                            moves.append(Move(sq, ns, 0, self.board.colors[ns]))
                elif piece_idx == 5:
                    for dr, dc in K_OFFSETS:
                        ns = sq + dr * 8 + dc
                        if 0 <= ns < 64 and self.board.colors[ns] and self.board.colors[ns] != color:
                            moves.append(Move(sq, ns, 0, self.board.colors[ns]))
        # Sort captures by MVV-LVA + SEE
        for m in moves:
            if m.captured: m.score = m.captured * 1000 + self.board.see(m)
            else: m.score = 0
        moves.sort(key=lambda m: m.score, reverse=True)
        for m in moves[:48]:
            self.board.make_move(m)
            score = -self.quiescence(-beta, -alpha)
            self.board.unmake_move(m)
            if score >= beta: return beta
            if score > alpha: alpha = score
        return alpha

def solve():
    board = Board()
    board.init_zobrist()
    engine = None
    for line in sys.stdin:
        fen = line.strip()
        if not fen: continue
        board.set_fen(fen)
        if engine is None:
            engine = Engine(board)
        else:
            engine.tt.clear()
            engine.best_move = None
            engine.history = [[0] * 64 for _ in range(2)]
            engine.killers = [[None, None] for _ in range(64)]
            engine.board = board
        move = engine.search(max_time=4.5)
        if move:
            sys.stdout.write(move.uci() + "\n")
        else:
            moves = board.generate_moves()
            if moves:
                sys.stdout.write(moves[0].uci() + "\n")
            else:
                sys.stdout.write("e1e2\n")

if __name__ == "__main__":
    solve()