Cele OK OK

import time
from datetime import datetime
from collections import deque, defaultdict
import copy

def print_board(board):
    print(str(board))

def print_ascii_board(board, title="Pozice"):
    """Print simple ASCII chess board with coordinates"""
    print(f"\n{title}:")

    for rank in range(7, -1, -1):
        row_str = f"{rank + 1} "
        for file in range(8):
            piece = board.board[rank][file]
            if piece is None:
                row_str += "."
            else:
                color, piece_type = piece
                if color == 'w':
                    row_str += piece_type.upper()
                else:
                    row_str += piece_type.lower()
        print(row_str)

    print("  abcdefgh")
    print()

def coords_to_algebraic(from_pos, to_pos):
    """Convert coordinates to algebraic notation"""
    from_file = chr(ord('a') + from_pos[1])
    from_rank = str(from_pos[0] + 1)
    to_file = chr(ord('a') + to_pos[1])
    to_rank = str(to_pos[0] + 1)

    return f"{from_file}{from_rank}", f"{to_file}{to_rank}"

def move_to_algebraic(board, from_pos, to_pos, check_status=""):
    """Convert move to proper algebraic notation"""
    piece = board.board[from_pos[0]][from_pos[1]]
    if not piece:
        return "invalid"

    color, piece_type = piece
    target = board.board[to_pos[0]][to_pos[1]]
    is_capture = target is not None

    from_square, to_square = coords_to_algebraic(from_pos, to_pos)

    # Pawn moves
    if piece_type == 'P':
        if is_capture:
            notation = f"{from_square[0]}x{to_square}"
        else:
            notation = to_square
    else:
        # Piece moves
        notation = piece_type

        # Check for ambiguity (multiple pieces of same type can reach target)
        ambiguous_pieces = []
        for rank in range(8):
            for file in range(8):
                other_piece = board.board[rank][file]
                if (other_piece and other_piece[0] == color and
                    other_piece[1] == piece_type and (rank, file) != from_pos):
                    # This piece could potentially move to the same square
                    ambiguous_pieces.append((rank, file))

        # Add disambiguation if needed
        if ambiguous_pieces:
            notation += from_square[0]  # Add file for disambiguation

        if is_capture:
            notation += "x"

        notation += to_square

    # Add check/mate indicators
    notation += check_status

    return notation

class ChessBoard:
    """Enhanced chess board implementation for fairy pieces"""

    def __init__(self, fen=None):
        self.board = [[None for _ in range(8)] for _ in range(8)]
        self.turn = True  # True = white, False = black
        self.castling_rights = {'K': True, 'Q': True, 'k': True, 'q': True}
        self.en_passant = None
        self.halfmove_clock = 0
        self.fullmove_number = 1
        self.position_history = []  # For repetition detection
        self.move_history = []  # Store moves in algebraic notation

        if fen:
            self.set_fen(fen)
        else:
            self.setup_initial_position()

    def __str__(self):
        """Simple text representation"""
        rows = []
        for i, row in enumerate(self.board[::-1], 1):
            safe_row = []
            for piece in row:
                if piece is None:
                    safe_row.append('.')
                elif isinstance(piece, tuple):
                    color, symbol = piece
                    safe_row.append(symbol.upper() if color == 'w' else symbol.lower())
                else:
                    safe_row.append(str(piece))
            rows.append(f"{8 - i + 1} " + " ".join(safe_row))
        rows.append("  a b c d e f g h")
        return "\n".join(rows)

    def setup_initial_position(self):
        """Set up starting position"""
        pieces = ['R', 'N', 'B', 'Q', 'K', 'B', 'N', 'R']
        for i, piece in enumerate(pieces):
            self.board[0][i] = ('w', piece)
        for i in range(8):
            self.board[1][i] = ('w', 'P')

        pieces = ['R', 'N', 'B', 'Q', 'K', 'B', 'N', 'R']
        for i, piece in enumerate(pieces):
            self.board[7][i] = ('b', piece)
        for i in range(8):
            self.board[6][i] = ('b', 'P')

    def set_fen(self, fen_string):
        """Set position from FEN string"""
        parts = fen_string.split()

        # Board position
        rows = parts[0].split('/')
        for rank, row in enumerate(rows):
            file_idx = 0
            for char in row:
                if char.isdigit():
                    for _ in range(int(char)):
                        self.board[7-rank][file_idx] = None
                        file_idx += 1
                else:
                    color = 'w' if char.isupper() else 'b'
                    self.board[7-rank][file_idx] = (color, char.upper())
                    file_idx += 1

        self.turn = parts[1] == 'w'

        castling = parts[2] if len(parts) > 2 else '-'
        self.castling_rights = {
            'K': 'K' in castling, 'Q': 'Q' in castling,
            'k': 'k' in castling, 'q': 'q' in castling
        }

        self.en_passant = parts[3] if len(parts) > 3 and parts[3] != '-' else None
        self.halfmove_clock = int(parts[4]) if len(parts) > 4 else 0
        self.fullmove_number = int(parts[5]) if len(parts) > 5 else 1

    def get_fen(self):
        """Return FEN string of position"""
        fen_parts = []
        for rank in range(7, -1, -1):
            row_fen = ""
            empty_count = 0

            for file in range(8):
                piece = self.board[rank][file]
                if piece is None:
                    empty_count += 1
                else:
                    if empty_count > 0:
                        row_fen += str(empty_count)
                        empty_count = 0
                    color, piece_type = piece
                    row_fen += piece_type if color == 'w' else piece_type.lower()

            if empty_count > 0:
                row_fen += str(empty_count)

            fen_parts.append(row_fen)

        position = '/'.join(fen_parts)
        turn = 'w' if self.turn else 'b'

        castling = ''
        for right in ['K', 'Q', 'k', 'q']:
            if self.castling_rights[right]:
                castling += right
        if not castling:
            castling = '-'

        en_passant = self.en_passant if self.en_passant else '-'

        return f"{position} {turn} {castling} {en_passant} {self.halfmove_clock} {self.fullmove_number}"

    def get_position_key(self):
        """Get position key for repetition detection (without clocks)"""
        parts = self.get_fen().split()
        return f"{parts[0]} {parts[1]} {parts[2]} {parts[3]}"

    def copy(self):
        """Create a copy of the board"""
        new_board = ChessBoard()
        new_board.board = [row[:] for row in self.board]
        new_board.turn = self.turn
        new_board.castling_rights = self.castling_rights.copy()
        new_board.en_passant = self.en_passant
        new_board.halfmove_clock = self.halfmove_clock
        new_board.fullmove_number = self.fullmove_number
        new_board.position_history = self.position_history[:]
        new_board.move_history = self.move_history[:]
        return new_board

    def make_move(self, from_pos, to_pos):
        """Make a move and update board state"""
        from_rank, from_file = from_pos
        to_rank, to_file = to_pos

        # Store position for repetition detection
        self.position_history.append(self.get_position_key())

        piece = self.board[from_rank][from_file]
        captured = self.board[to_rank][to_file]

        # Generate algebraic notation before making the move
        algebraic = move_to_algebraic(self, from_pos, to_pos)

        # Update halfmove clock
        if piece[1] == 'P' or captured is not None:
            self.halfmove_clock = 0
        else:
            self.halfmove_clock += 1

        # Make the move
        self.board[to_rank][to_file] = piece
        self.board[from_rank][from_file] = None

        # Check if this move puts opponent in check
        opponent_color = 'b' if piece[0] == 'w' else 'w'
        if self.is_check(opponent_color):
            # Check if it's mate
            temp_board = self.copy()
            temp_board.turn = not temp_board.turn
            if not temp_board.has_legal_moves():
                algebraic += "#"  # Checkmate
            else:
                algebraic += "+"  # Check

        self.move_history.append(algebraic)

        # Update castling rights if king or rook moves
        if piece[1] == 'K':
            if piece[0] == 'w':
                self.castling_rights['K'] = False
                self.castling_rights['Q'] = False
            else:
                self.castling_rights['k'] = False
                self.castling_rights['q'] = False
        elif piece[1] == 'R':
            if from_pos == (0, 0):
                self.castling_rights['Q'] = False
            elif from_pos == (0, 7):
                self.castling_rights['K'] = False
            elif from_pos == (7, 0):
                self.castling_rights['q'] = False
            elif from_pos == (7, 7):
                self.castling_rights['k'] = False

        # Change turn
        self.turn = not self.turn
        if self.turn:  # If white to move, increment fullmove
            self.fullmove_number += 1

    def has_legal_moves(self):
        """Check if current player has any legal moves"""
        for rank in range(8):
            for file in range(8):
                piece = self.board[rank][file]
                if piece and piece[0] == ('w' if self.turn else 'b'):
                    # This is simplified - would need full move generation
                    return True
        return False

    def find_king(self, color):
        """Find king of given color"""
        for rank in range(8):
            for file in range(8):
                piece = self.board[rank][file]
                if piece and piece[0] == color and piece[1] == 'K':
                    return (rank, file)
        return None

    def is_check(self, color):
        """Check if king is in check"""
        king_pos = self.find_king(color)
        if not king_pos:
            return False

        enemy_color = 'b' if color == 'w' else 'w'

        for rank in range(8):
            for file in range(8):
                piece = self.board[rank][file]
                if piece and piece[0] == enemy_color:
                    if self.attacks_square((rank, file), king_pos):
                        return True
        return False

    def is_threefold_repetition(self):
        """Check for threefold repetition"""
        current_pos = self.get_position_key()
        count = self.position_history.count(current_pos)
        return count >= 2

    def is_fifty_move_rule(self):
        """Check for fifty move rule"""
        return self.halfmove_clock >= 100

    def attacks_square(self, from_pos, to_pos):
        """Check if piece attacks given square"""
        rank, file = from_pos
        piece = self.board[rank][file]

        if not piece:
            return False

        color, piece_type = piece

        if piece_type == 'P':
            return self.pawn_attacks(from_pos, to_pos, color)
        elif piece_type == 'R':
            return self.rook_attacks(from_pos, to_pos)
        elif piece_type == 'N':
            return self.knight_attacks(from_pos, to_pos)
        elif piece_type == 'B':
            return self.bishop_attacks(from_pos, to_pos)
        elif piece_type == 'Q':
            return self.queen_attacks(from_pos, to_pos)
        elif piece_type == 'K':
            return self.king_attacks(from_pos, to_pos)
        elif piece_type == 'A':  # Amazon (Q+N)
            return self.queen_attacks(from_pos, to_pos) or self.knight_attacks(from_pos, to_pos)
        elif piece_type == 'C':  # Cyril (R+N)
            return self.rook_attacks(from_pos, to_pos) or self.knight_attacks(from_pos, to_pos)
        elif piece_type == 'E':  # Eve (B+N)
            return self.bishop_attacks(from_pos, to_pos) or self.knight_attacks(from_pos, to_pos)

        return False

    def pawn_attacks(self, from_pos, to_pos, color):
        """Check pawn attack"""
        from_rank, from_file = from_pos
        to_rank, to_file = to_pos

        direction = 1 if color == 'w' else -1
        return (abs(from_file - to_file) == 1 and
                to_rank - from_rank == direction)

    def knight_attacks(self, from_pos, to_pos):
        """Check knight attack"""
        from_rank, from_file = from_pos
        to_rank, to_file = to_pos

        dr = abs(from_rank - to_rank)
        df = abs(from_file - to_file)

        return (dr == 2 and df == 1) or (dr == 1 and df == 2)

    def rook_attacks(self, from_pos, to_pos):
        """Check rook attack"""
        from_rank, from_file = from_pos
        to_rank, to_file = to_pos

        if from_rank != to_rank and from_file != to_file:
            return False

        if from_rank == to_rank:  # Horizontal
            start = min(from_file, to_file) + 1
            end = max(from_file, to_file)
            for f in range(start, end):
                if self.board[from_rank][f] is not None:
                    return False
        else:  # Vertical
            start = min(from_rank, to_rank) + 1
            end = max(from_rank, to_rank)
            for r in range(start, end):
                if self.board[r][from_file] is not None:
                    return False

        return True

    def bishop_attacks(self, from_pos, to_pos):
        """Check bishop attack"""
        from_rank, from_file = from_pos
        to_rank, to_file = to_pos

        dr = to_rank - from_rank
        df = to_file - from_file

        if abs(dr) != abs(df) or dr == 0:
            return False

        step_r = 1 if dr > 0 else -1
        step_f = 1 if df > 0 else -1

        steps = abs(dr)
        for i in range(1, steps):
            check_rank = from_rank + i * step_r
            check_file = from_file + i * step_f
            if self.board[check_rank][check_file] is not None:
                return False

        return True

    def queen_attacks(self, from_pos, to_pos):
        """Check queen attack"""
        return self.rook_attacks(from_pos, to_pos) or self.bishop_attacks(from_pos, to_pos)

    def king_attacks(self, from_pos, to_pos):
        """Check king attack"""
        from_rank, from_file = from_pos
        to_rank, to_file = to_pos

        return (abs(from_rank - to_rank) <= 1 and
                abs(from_file - to_file) <= 1 and
                from_pos != to_pos)


class EnhancedFairyChessAnalyzer:
    """Enhanced analyzer focused on recursive search for fairy chess - FIXED VERSION"""

    def __init__(self, start_fen):
        self.start_fen = start_fen
        self.transposition_table = {}
        self.nodes_evaluated = 0
        self.depth_stats = {}
        self.move_count = 0
        self.total_moves = 0
        self.current_search_depth = 0  # FIXED: Initialize search depth tracking

        # Time tracking
        self.start_time = None
        self.total_analysis_time = 0
        self.mate_sequence_time = 0
        self.depth_times = {}  # Time per depth level

    def print_time(self, message=""):
        """Print time with message and elapsed time"""
        now = datetime.now()
        time_str = now.strftime("%H:%M:%S")

        # Calculate elapsed time if analysis started
        if self.start_time:
            elapsed = time.time() - self.start_time
            elapsed_str = f" | Celkem: {elapsed:.1f}s"
        else:
            elapsed_str = ""

        print(f"[{time_str}]{elapsed_str} {message}")

    def start_timing(self, operation_name="Analýza"):
        """Start timing an operation"""
        self.start_time = time.time()
        self.print_time(f"🚀 Začátek: {operation_name}")

    def stop_timing(self, operation_name="Analýza"):
        """Stop timing and return elapsed time"""
        if self.start_time:
            elapsed = time.time() - self.start_time
            self.print_time(f"⏹️  Konec: {operation_name} ({elapsed:.1f}s)")
            return elapsed
        return 0

    def print_intermediate_time(self, message=""):
        """Print intermediate timing"""
        if self.start_time:
            elapsed = time.time() - self.start_time
            self.print_time(f"⏱️  {message} (mezičas: {elapsed:.1f}s)")
        else:
            self.print_time(f"⏱️  {message}")

    def print_position_info(self, board, title="Pozice"):
        """Print basic position information"""
        print_ascii_board(board, title)
        print(f"FEN: {board.get_fen()}")
        print(f"Na tahu: {'Bílý' if board.turn else 'Černý'}")

    def print_depth_progress(self, depth, move_num, total_moves):
        """Print minimal progress for current depth"""
        if move_num % 3 == 0 or move_num == total_moves:
            percentage = (move_num / total_moves * 100) if total_moves > 0 else 0
            print(f"Hloubka {depth}: {move_num}/{total_moves} ({percentage:.0f}%)")

    def evaluate_material(self, board):
        """Evaluate material balance - enhanced for fairy pieces"""
        piece_values = {
            'P': 1, 'N': 3, 'B': 3, 'R': 5, 'Q': 9, 'K': 0,
            'A': 13,  # Amazon is very powerful (Q+N)
            'C': 8,   # Cyril (R+N)
            'E': 6    # Eve (B+N)
        }

        white_material = 0
        black_material = 0

        for rank in range(8):
            for file in range(8):
                piece = board.board[rank][file]
                if piece:
                    color, piece_type = piece
                    value = piece_values.get(piece_type, 0)
                    if color == 'w':
                        white_material += value
                    else:
                        black_material += value

        return white_material - black_material

    def determine_stronger_side(self, board):
        """Determine which side is stronger based on material"""
        material_diff = self.evaluate_material(board)
        if abs(material_diff) < 1:
            return None
        return 'w' if material_diff > 0 else 'b'

    def evaluate_position(self, board):
        """Enhanced position evaluation for fairy pieces"""
        score = 0

        # 1. Material evaluation
        material = self.evaluate_material(board)
        score += material

        # 2. Piece activity and centralization
        activity_bonus = 0
        for rank in range(8):
            for file in range(8):
                piece = board.board[rank][file]
                if piece:
                    color, piece_type = piece

                    # Center control bonus
                    center_distance = abs(3.5 - rank) + abs(3.5 - file)
                    center_bonus = (7 - center_distance) * 0.05

                    # Enhanced bonus for fairy pieces in center
                    if piece_type in ['A', 'C', 'E']:
                        center_bonus *= 2

                    if color == 'w':
                        activity_bonus += center_bonus
                    else:
                        activity_bonus -= center_bonus

        score += activity_bonus

        # 3. Mobility (very important for fairy pieces)
        current_side = 'w' if board.turn else 'b'
        mobility = len(self.generate_legal_moves(board))

        # Switch sides to count opponent mobility
        temp_board = board.copy()
        temp_board.turn = not temp_board.turn
        opponent_mobility = len(self.generate_legal_moves(temp_board))

        mobility_diff = mobility - opponent_mobility
        if current_side == 'w':
            score += mobility_diff * 0.1
        else:
            score -= mobility_diff * 0.1

        # 4. King safety
        for color in ['w', 'b']:
            king_pos = board.find_king(color)
            if king_pos:
                king_rank, king_file = king_pos
                # Penalty for king in center (dangerous with fairy pieces)
                if 2 <= king_rank <= 5 and 2 <= king_file <= 5:
                    danger_penalty = -1.0
                    if color == 'w':
                        score += danger_penalty
                    else:
                        score -= danger_penalty

        # 5. Check bonus/penalty
        if board.is_check('w'):
            score -= 0.5
        if board.is_check('b'):
            score += 0.5

        return score

    def generate_legal_moves(self, board):
        """Generate all legal moves for current position"""
        moves = []

        for rank in range(8):
            for file in range(8):
                piece = board.board[rank][file]
                if piece and piece[0] == ('w' if board.turn else 'b'):
                    piece_moves = self.generate_piece_moves(board, (rank, file))
                    for to_pos in piece_moves:
                        if self.is_move_legal(board, (rank, file), to_pos):
                            moves.append(((rank, file), to_pos))

        return moves

    def generate_piece_moves(self, board, from_pos):
        """Generate moves for a specific piece"""
        rank, file = from_pos
        piece = board.board[rank][file]

        if not piece:
            return []

        color, piece_type = piece

        if piece_type == 'P':
            return self.generate_pawn_moves(board, from_pos)
        elif piece_type == 'R':
            return self.generate_sliding_moves(board, from_pos, [(0,1), (0,-1), (1,0), (-1,0)])
        elif piece_type == 'N':
            return self.generate_knight_moves(board, from_pos)
        elif piece_type == 'B':
            return self.generate_sliding_moves(board, from_pos, [(1,1), (1,-1), (-1,1), (-1,-1)])
        elif piece_type == 'Q':
            return self.generate_sliding_moves(board, from_pos,
                [(0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)])
        elif piece_type == 'K':
            return self.generate_king_moves(board, from_pos)
        elif piece_type == 'A':  # Amazon
            queen_moves = self.generate_sliding_moves(board, from_pos,
                [(0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)])
            knight_moves = self.generate_knight_moves(board, from_pos)
            return queen_moves + knight_moves
        elif piece_type == 'C':  # Cyril
            rook_moves = self.generate_sliding_moves(board, from_pos, [(0,1), (0,-1), (1,0), (-1,0)])
            knight_moves = self.generate_knight_moves(board, from_pos)
            return rook_moves + knight_moves
        elif piece_type == 'E':  # Eve
            bishop_moves = self.generate_sliding_moves(board, from_pos, [(1,1), (1,-1), (-1,1), (-1,-1)])
            knight_moves = self.generate_knight_moves(board, from_pos)
            return bishop_moves + knight_moves

        return []

    def generate_pawn_moves(self, board, from_pos):
        """Generate pawn moves"""
        rank, file = from_pos
        piece = board.board[rank][file]
        color = piece[0]
        moves = []

        direction = 1 if color == 'w' else -1
        start_rank = 1 if color == 'w' else 6

        # Forward move
        new_rank = rank + direction
        if 0 <= new_rank <= 7 and board.board[new_rank][file] is None:
            moves.append((new_rank, file))

            # Double move from starting position
            if rank == start_rank and board.board[new_rank + direction][file] is None:
                moves.append((new_rank + direction, file))

        # Captures
        for df in [-1, 1]:
            new_file = file + df
            if 0 <= new_file <= 7 and 0 <= new_rank <= 7:
                target = board.board[new_rank][new_file]
                if target and target[0] != color:
                    moves.append((new_rank, new_file))

        return moves

    def generate_knight_moves(self, board, from_pos):
        """Generate knight moves"""
        rank, file = from_pos
        piece = board.board[rank][file]
        color = piece[0]
        moves = []

        knight_moves = [(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2)]

        for dr, df in knight_moves:
            new_rank = rank + dr
            new_file = file + df

            if 0 <= new_rank <= 7 and 0 <= new_file <= 7:
                target = board.board[new_rank][new_file]
                if not target or target[0] != color:
                    moves.append((new_rank, new_file))

        return moves

    def generate_sliding_moves(self, board, from_pos, directions):
        """Generate sliding piece moves"""
        rank, file = from_pos
        piece = board.board[rank][file]
        color = piece[0]
        moves = []

        for dr, df in directions:
            for distance in range(1, 8):
                new_rank = rank + dr * distance
                new_file = file + df * distance

                if not (0 <= new_rank <= 7 and 0 <= new_file <= 7):
                    break

                target = board.board[new_rank][new_file]

                if not target:
                    moves.append((new_rank, new_file))
                elif target[0] != color:
                    moves.append((new_rank, new_file))
                    break
                else:
                    break

        return moves

    def generate_king_moves(self, board, from_pos):
        """Generate king moves"""
        rank, file = from_pos
        piece = board.board[rank][file]
        color = piece[0]
        moves = []

        for dr in [-1, 0, 1]:
            for df in [-1, 0, 1]:
                if dr == 0 and df == 0:
                    continue

                new_rank = rank + dr
                new_file = file + df

                if 0 <= new_rank <= 7 and 0 <= new_file <= 7:
                    target = board.board[new_rank][new_file]
                    if not target or target[0] != color:
                        moves.append((new_rank, new_file))

        return moves

    def is_move_legal(self, board, from_pos, to_pos):
        """Check if move is legal (doesn't leave king in check)"""
        temp_board = board.copy()
        temp_board.make_move(from_pos, to_pos)

        color = 'w' if board.turn else 'b'
        return not temp_board.is_check(color)

    def is_terminal_position(self, board):
        """Check if position is terminal and return evaluation"""
        legal_moves = self.generate_legal_moves(board)
        current_color = 'w' if board.turn else 'b'

        # Check for checkmate or stalemate
        if not legal_moves:
            if board.is_check(current_color):
                # Checkmate - losing side
                return ('mate', 0)
            else:
                # Stalemate - draw
                return ('draw', 0)

        # Check for draw conditions
        if board.is_fifty_move_rule() or board.is_threefold_repetition():
            return ('draw', 0)

        # Check for insufficient material (basic check)
        if self.is_insufficient_material(board):
            return ('draw', 0)

        return None

    def is_insufficient_material(self, board):
        """Basic insufficient material detection"""
        pieces = []
        for rank in range(8):
            for file in range(8):
                piece = board.board[rank][file]
                if piece:
                    pieces.append(piece[1])

        # King vs King
        if len(pieces) == 2:
            return True

        # King + Bishop/Knight vs King
        if len(pieces) == 3 and any(p in pieces for p in ['B', 'N']):
            return True

        return False

    def minimax_with_fairy_optimization(self, board, depth, alpha, beta, maximizing_player):
        """FIXED minimax with correct mate detection for fairy chess pieces"""
        self.nodes_evaluated += 1

        # Check transposition table first
        position_key = board.get_position_key()
        if position_key in self.transposition_table:
            stored_depth, stored_value = self.transposition_table[position_key]
            if stored_depth >= depth:
                return stored_value

        # FIXED: Terminal position check with correct mate distance calculation
        terminal_result = self.is_terminal_position(board)
        if terminal_result or depth == 0:
            if terminal_result:
                result_type, moves_to_end = terminal_result
                if result_type == 'mate':
                    # FIXED: Mate distance calculation
                    # Current player is in checkmate, so opponent wins
                    # Distance to mate = remaining depth (how many moves until mate)
                    if maximizing_player:
                        # Current maximizing player loses (gets mated)
                        return -10000 + (self.current_search_depth - depth)
                    else:
                        # Current minimizing player loses (gets mated)
                        return 10000 - (self.current_search_depth - depth)
                else:  # draw
                    return 0
            else:
                # Leaf node - evaluate position
                return self.evaluate_position(board)

        legal_moves = self.generate_legal_moves(board)

        # FIXED: If no legal moves but not detected as terminal, it's mate/stalemate
        if not legal_moves:
            current_color = 'w' if board.turn else 'b'
            if board.is_check(current_color):
                # Checkmate
                if maximizing_player:
                    return -10000 + (self.current_search_depth - depth)
                else:
                    return 10000 - (self.current_search_depth - depth)
            else:
                # Stalemate
                return 0

        # Move ordering for better alpha-beta pruning
        legal_moves = self.order_moves_for_fairy_pieces(board, legal_moves)

        # Progress tracking for root level
        if depth == self.current_search_depth:
            self.total_moves = len(legal_moves)
            self.move_count = 0

        if maximizing_player:
            max_eval = float('-inf')
            for move in legal_moves:
                if depth == self.current_search_depth:
                    self.move_count += 1
                    self.print_depth_progress(depth, self.move_count, self.total_moves)

                temp_board = board.copy()
                temp_board.make_move(move[0], move[1])

                eval_score = self.minimax_with_fairy_optimization(
                    temp_board, depth - 1, alpha, beta, False)

                if eval_score > max_eval:
                    max_eval = eval_score
                    if depth == self.current_search_depth:
                        algebraic = move_to_algebraic(board, move[0], move[1])
                        print(f"Nový nejlepší: {algebraic} ({max_eval:.1f})")

                alpha = max(alpha, eval_score)
                if beta <= alpha:
                    break  # Alpha-beta cutoff

            # Store result in transposition table
            self.transposition_table[position_key] = (depth, max_eval)
            return max_eval
        else:
            min_eval = float('inf')
            for move in legal_moves:
                temp_board = board.copy()
                temp_board.make_move(move[0], move[1])

                eval_score = self.minimax_with_fairy_optimization(
                    temp_board, depth - 1, alpha, beta, True)

                min_eval = min(min_eval, eval_score)
                beta = min(beta, eval_score)
                if beta <= alpha:
                    break  # Alpha-beta cutoff

            # Store result in transposition table
            self.transposition_table[position_key] = (depth, min_eval)
            return min_eval

    def order_moves_for_fairy_pieces(self, board, moves):
        """Order moves to improve alpha-beta pruning efficiency"""
        def move_priority(move):
            from_pos, to_pos = move
            piece = board.board[from_pos[0]][from_pos[1]]
            target = board.board[to_pos[0]][to_pos[1]]

            priority = 0

            # 1. Captures get highest priority
            if target:
                piece_values = {'P': 1, 'N': 3, 'B': 3, 'R': 5, 'Q': 9, 'A': 13, 'C': 8, 'E': 6}
                priority += piece_values.get(target[1], 0) * 10

            # 2. Fairy piece moves get bonus
            if piece and piece[1] in ['A', 'C', 'E']:
                priority += 5

            # 3. Center moves get small bonus
            to_rank, to_file = to_pos
            center_distance = abs(3.5 - to_rank) + abs(3.5 - to_file)
            priority += (7 - center_distance) * 0.1

            # 4. Check-giving moves get bonus
            temp_board = board.copy()
            temp_board.make_move(from_pos, to_pos)
            opponent_color = 'b' if board.turn else 'w'
            if temp_board.is_check(opponent_color):
                priority += 3

            return priority

        # Sort moves by priority (highest first)
        return sorted(moves, key=move_priority, reverse=True)

    def evaluate_position_static(self, board):
        """Statické ohodnocení pozice bez rekurze"""
        score = 0

        # 1. Materiálové ohodnocení
        material_score = self.evaluate_material(board)
        score += material_score

        # 2. Pozice figur (centralizace)
        positional_score = 0
        for rank in range(8):
            for file in range(8):
                piece = board.board[rank][file]
                if piece:
                    color, piece_type = piece

                    # Bonus za centrální pozice
                    center_distance = abs(3.5 - rank) + abs(3.5 - file)
                    center_bonus = (7 - center_distance) * 0.1

                    if color == 'w':
                        positional_score += center_bonus
                    else:
                        positional_score -= center_bonus

                    # Speciální bonusy pro pohádkové figury
                    if piece_type in ['A', 'C', 'E']:  # Fairy pieces
                        if color == 'w':
                            positional_score += center_bonus * 2  # Double bonus
                        else:
                            positional_score -= center_bonus * 2

        score += positional_score

        # 3. Mobilita (počet legálních tahů)
        legal_moves = len(self.generate_legal_moves(board))
        mobility_bonus = legal_moves * 0.05

        if board.turn:  # White to move
            score += mobility_bonus
        else:  # Black to move
            score -= mobility_bonus

        # 4. Bezpečnost krále
        king_safety_score = 0
        for color in ['w', 'b']:
            king_pos = board.find_king(color)
            if king_pos:
                # Penalizace za krále v centru
                king_rank, king_file = king_pos
                if 2 <= king_rank <= 5 and 2 <= king_file <= 5:
                    king_danger = -0.5
                else:
                    king_danger = 0

                if color == 'w':
                    king_safety_score += king_danger
                else:
                    king_safety_score -= king_danger

        score += king_safety_score

        # 5. Kontrola šachu (důležité pro taktiku)
        if board.is_check('w'):
            score -= 0.3  # Penalty for white in check
        if board.is_check('b'):
            score += 0.3  # Bonus if black in check

        return score

    def analyze_position_static_only(self, max_evaluations=1000):
        """Analýza pouze se statickým ohodnocením"""
        board = ChessBoard(self.start_fen)

        print("=== STATICKÁ ANALÝZA (bez rekurze) ===")
        self.print_position_info(board, "Výchozí pozice")

        # Ohodnotit výchozí pozici
        base_score = self.evaluate_position_static(board)
        print(f"Ohodnocení výchozí pozice: {base_score:.2f}")

        # Získat všechny legální tahy
        legal_moves = self.generate_legal_moves(board)
        print(f"Legálních tahů: {len(legal_moves)}")

        if not legal_moves:
            print("Žádné legální tahy")
            return None

        # Ohodnotit každý tah
        print(f"\nOhodnocování tahů:")
        move_evaluations = []

        for i, move in enumerate(legal_moves, 1):
            temp_board = board.copy()
            temp_board.make_move(move[0], move[1])

            # Statické ohodnocení
            move_score = self.evaluate_position_static(temp_board)
            algebraic = move_to_algebraic(board, move[0], move[1])

            move_evaluations.append((move, move_score, algebraic))
            print(f"  {i:2d}. {algebraic}: {move_score:+.2f}")

        # Najít nejlepší tah
        stronger_side = self.determine_stronger_side(board)
        current_color = 'w' if board.turn else 'b'

        if stronger_side == current_color:
            # Silnější strana - maximalizuj
            best_move_data = max(move_evaluations, key=lambda x: x[1])
            strategy = "AGRESIVNÍ (maximalizace)"
        elif stronger_side is not None:
            # Slabší strana - minimalizuj (hledej nejmenší ztrátu)
            best_move_data = min(move_evaluations, key=lambda x: x[1])
            strategy = "DEFENZIVNÍ (minimalizace)"
        else:
            # Vyrovnaná pozice
            if board.turn:  # White maximizes
                best_move_data = max(move_evaluations, key=lambda x: x[1])
            else:  # Black minimizes
                best_move_data = min(move_evaluations, key=lambda x: x[1])
            strategy = "VYVÁŽENÁ"

        best_move, best_score, best_algebraic = best_move_data

        print(f"\nStrategie: {strategy}")
        print(f"Nejlepší tah: {best_algebraic}")
        print(f"Ohodnocení: {best_score:+.2f}")

        # Ukázat pozici po nejlepším tahu
        final_board = board.copy()
        final_board.make_move(best_move[0], best_move[1])
        self.print_position_info(final_board, f"Po tahu {best_algebraic}")

        return best_move, best_score

    def find_best_move_recursive(self, board, depth=6):
        """Find best move using recursive minimax - FIXED logic for fairy pieces"""
        depth_start_time = time.time()

        print(f"\nREKURZIVNÍ ANALÝZA (hloubka {depth})")
        print("Optimalizováno pro pohádkové figury")

        nodes_before = self.nodes_evaluated
        self.current_search_depth = depth

        legal_moves = self.generate_legal_moves(board)

        if not legal_moves:
            print("Žádné legální tahy")
            return None

        print(f"Analyzuji {len(legal_moves)} tahů...")

        # FIXED: Determine strategy based on material advantage
        stronger_side = self.determine_stronger_side(board)
        current_color = 'w' if board.turn else 'b'

        # CRITICAL FIX: Stronger side should ALWAYS maximize their advantage
        if stronger_side == current_color:
            strategy = "AGRESIVNÍ (hledáme mat)"
            # Stronger side wants to MAXIMIZE evaluation (find highest value)
            best_value = float('-inf')
            is_maximizing_search = True
        elif stronger_side is not None:
            strategy = "DEFENZIVNÍ (zdržujeme)"
            # Weaker side wants to MINIMIZE opponent's advantage (find lowest value)
            best_value = float('inf')
            is_maximizing_search = False
        else:
            strategy = "VYVÁŽENÁ"
            # Standard minimax: white maximizes, black minimizes
            if board.turn:  # White
                best_value = float('-inf')
                is_maximizing_search = True
            else:  # Black
                best_value = float('inf')
                is_maximizing_search = False

        print(f"Strategie: {strategy}")

        best_move = None

        # FIXED: Consistent move evaluation logic
        for move in legal_moves:
            temp_board = board.copy()
            temp_board.make_move(move[0], move[1])

            # Always call minimax from opponent's perspective
            move_value = self.minimax_with_fairy_optimization(
                temp_board, depth - 1, float('-inf'), float('inf'), not board.turn)

            # FIXED: Select best move based on consistent strategy
            move_is_better = False

            if is_maximizing_search:
                # Want higher values (better for current player)
                if move_value > best_value:
                    move_is_better = True
            else:
                # Want lower values (less bad for current player)
                if move_value < best_value:
                    move_is_better = True

            if move_is_better:
                best_value = move_value
                best_move = move
                algebraic = move_to_algebraic(board, move[0], move[1])
                print(f"Nový nejlepší: {algebraic} ({move_value:.1f})")

        # Calculate timing for this depth
        depth_duration = time.time() - depth_start_time
        nodes_for_depth = self.nodes_evaluated - nodes_before
        self.depth_times[depth] = depth_duration

        print(f"Dokončeno za {depth_duration:.1f}s")

        # FIXED: Avoid division by zero
        if depth_duration > 0:
            nodes_per_sec = nodes_for_depth / depth_duration
            print(f"Evaluováno {nodes_for_depth} uzlů ({nodes_per_sec:.0f}/s)")
        else:
            print(f"Evaluováno {nodes_for_depth} uzlů (příliš rychlé pro měření)")

        print(f"Cache obsahuje {len(self.transposition_table)} pozic")

        # Print intermediate total time
        self.print_intermediate_time(f"Hloubka {depth} dokončena")

        if best_move:
            best_algebraic = move_to_algebraic(board, best_move[0], best_move[1])
            print(f"Nejlepší tah: {best_algebraic}")
            print(f"Ohodnocení: {best_value:.1f}")

            # FIXED: Correct mate interpretation with proper move counting
            if abs(best_value) > 9000:
                mate_in = int(10000 - abs(best_value))
                # Add 1 because we count the move we're about to make
                actual_mate_in = mate_in + 1
                if best_value > 0:
                    print(f"🎯 MAT za {actual_mate_in} tah{'ů' if actual_mate_in > 1 else ''}!")
                else:
                    print(f"🛡️  Obrana {actual_mate_in} tah{'ů' if actual_mate_in > 1 else ''}")
            elif abs(best_value) < 0.5:
                print("⚖️  Vyrovnaná pozice")
            elif best_value > 2:
                print("💪 Velká výhoda")
            elif best_value > 0:
                print(f"👍 Mírná výhoda (+{best_value:.1f})")
            elif best_value < -2:
                print("😰 Velká nevýhoda")
            else:
                print(f"👎 Mírná nevýhoda ({best_value:.1f})")

        return best_move, best_value

    def analyze_position_recursive(self, max_depth=6):
        """Complete recursive analysis with FIXED evaluation logic"""
        recursive_start_time = time.time()

        board = ChessBoard(self.start_fen)

        print("=== REKURZIVNÍ ANALÝZA POHÁDKOVÉ POZICE ===")
        self.print_position_info(board, "Analyzovaná pozice")

        # Material analysis
        material_diff = self.evaluate_material(board)
        stronger_side = self.determine_stronger_side(board)
        print(f"Materiál: {material_diff:+.1f} (silnější: {stronger_side or 'vyrovnané'})")

        # Check if already terminal
        terminal_result = self.is_terminal_position(board)
        if terminal_result:
            result_type, moves_to_end = terminal_result
            print(f"🏁 Terminální pozice: {result_type}")
            return None

        # Count fairy pieces for complexity estimate
        fairy_count = 0
        for rank in range(8):
            for file in range(8):
                piece = board.board[rank][file]
                if piece and piece[1] in ['A', 'C', 'E']:
                    fairy_count += 1

        if fairy_count > 0:
            print(f"🧚 Pohádkových figur: {fairy_count} (složitost: vysoká)")

        # FIXED: Store current search depth for mate distance calculation
        self.current_search_depth = 0

        # Reset timing for this analysis
        total_nodes_start = self.nodes_evaluated

        # Iterative deepening search
        best_result = None

        for depth in range(1, max_depth + 1):
            depth_start_time = time.time()

            print(f"\n📊 HLOUBKA {depth}")
            print("-" * 20)

            try:
                # FIXED: Set current search depth before each iteration
                self.current_search_depth = depth

                result = self.find_best_move_recursive(board, depth)
                if result:
                    best_move, best_value = result
                    best_result = result

                    # Track depth completion time
                    depth_duration = time.time() - depth_start_time
                    self.print_intermediate_time(f"Kompletní hloubka {depth} ({depth_duration:.1f}s)")

                    # FIXED: Early termination for forced mates with correct calculation
                    if abs(best_value) > 9000:
                        mate_in = int(10000 - abs(best_value)) + 1  # +1 for the move we make
                        print(f"\n🚀 NUCENÝ MAT za {mate_in} tah{'ů' if mate_in > 1 else ''}! (hloubka {depth})")

                        # Show the matting move position
                        temp_board = board.copy()
                        temp_board.make_move(best_move[0], best_move[1])
                        algebraic = move_to_algebraic(board, best_move[0], best_move[1])
                        self.print_position_info(temp_board, f"Po maticím tahu {algebraic}")

                        # FIXED: Don't stop too early, let's see if there are quicker mates
                        if depth >= 3 and mate_in <= 2:  # Found mate in 1-2, can stop
                            break

                    # Show position after best move for deeper searches
                    elif depth >= 3:
                        temp_board = board.copy()
                        temp_board.make_move(best_move[0], best_move[1])
                        algebraic = move_to_algebraic(board, best_move[0], best_move[1])
                        self.print_position_info(temp_board, f"Po tahu {algebraic}")

            except KeyboardInterrupt:
                print("⏹️  Analýza přerušena uživatelem")
                break
            except Exception as e:
                print(f"❌ Chyba na hloubce {depth}: {e}")
                import traceback
                traceback.print_exc()
                break

        # Calculate total recursive analysis time
        recursive_duration = time.time() - recursive_start_time
        total_nodes_analyzed = self.nodes_evaluated - total_nodes_start

        print(f"\n🎯 FINÁLNÍ VÝSLEDEK")
        print("=" * 40)

        # Print timing summary for recursive analysis
        print(f"⏱️  ČASOVÝ PŘEHLED REKURZIVNÍ ANALÝZY:")
        print(f"   Celkový čas: {recursive_duration:.1f}s")
        print(f"   Uzlů celkem: {total_nodes_analyzed:,}")

        # FIXED: Avoid division by zero
        if recursive_duration > 0:
            print(f"   Rychlost: {total_nodes_analyzed/recursive_duration:.0f} uzlů/s")
        else:
            print(f"   Rychlost: >1000000 uzlů/s (příliš rychlé pro měření)")

        if self.depth_times:
            print(f"   Časy podle hloubky:")
            for depth, duration in self.depth_times.items():
                print(f"     Hloubka {depth}: {duration:.1f}s")

        if best_result:
            best_move, best_value = best_result
            algebraic = move_to_algebraic(board, best_move[0], best_move[1])

            print(f"Doporučený tah: {algebraic}")
            print(f"Konečné ohodnocení: {best_value:.1f}")

            # Show final position
            final_board = board.copy()
            final_board.make_move(best_move[0], best_move[1])
            self.print_position_info(final_board, f"Výsledná pozice")

            return best_result
        else:
            print("❌ Analýza nebyla úspěšná")
            return None

    def analyze_position_with_mate_sequence(self, max_depth=6):
        """Analyze position and if mate is found, show complete sequence - FIXED VERSION"""
        # Start total timing
        self.start_timing("Kompletní analýza pozice")

        print("🔍 Spouštím základní analýzu pozice...")

        # First do regular analysis
        result = self.analyze_position_recursive(max_depth)

        sequence = None
        if result:
            best_move, best_value = result

            print(f"\n📊 VÝSLEDEK ZÁKLADNÍ ANALÝZY:")
            print(f"   Nejlepší tah: {move_to_algebraic(ChessBoard(self.start_fen), best_move[0], best_move[1])}")
            print(f"   Ohodnocení: {best_value:.1f}")
            print(f"   Je to mat?: {abs(best_value) > 9000}")

            # FIXED: Always analyze mate sequence if evaluation suggests mate OR if we want to verify
            if abs(best_value) > 9000:
                mate_in = int(10000 - abs(best_value)) + 1
                print(f"\n🔍 NALEZEN MAT ZA {mate_in} TAH{'ů' if mate_in > 1 else ''}!")
                print("🎯 ANALYZUJI KOMPLETNÍ MATOVOU SEKVENCI...")
                self.print_intermediate_time("Začátek analýzy matové sekvence")

                # FIXED: Use larger depth to ensure we see the complete sequence
                sequence_depth = max(10, mate_in * 3)
                print(f"🔧 Použije hloubku {sequence_depth} pro matovou sekvenci")

                # Analyze complete mate sequence
                sequence = self.analyze_mate_sequence(max_depth=sequence_depth)

                if sequence:
                    print(f"✅ Matová sekvence nalezena s {len(sequence)} kroky")
                else:
                    print("❌ Matová sekvence se nepodařila analyzovat")
            else:
                print(f"\n📊 Ohodnocení {best_value:.1f} nenaznačuje nucený mat")
                print("🤔 Zkusím analyzovat sekvenci alespoň 5 kroků pro ověření...")

                # Even if not mate, try to analyze a few moves to see what happens
                sequence = self.analyze_mate_sequence(max_depth=5)
        else:
            print("❌ Základní analýza nevrátila žádný výsledek")

        # Stop total timing
        self.total_analysis_time = self.stop_timing("Kompletní analýza pozice")

        return result, sequence

    def analyze_mate_sequence(self, max_depth=10):
        """ZCELA NOVÁ VERZE - zaručeně vypisuje všechny pozice až do skutečného matu"""
        mate_sequence_start = time.time()

        print(f"\n🎯 ZAČÍNÁM ANALÝZU MATOVÉ SEKVENCE (max {max_depth} kroků)")
        print("="*60)
        print("🔥 BUDU POKRAČOVAT AŽ DO SKUTEČNÉHO CHECKMATE!")

        board = ChessBoard(self.start_fen)

        # KROK 0: Zobraz výchozí pozici
        print(f"\n📍 KROK 0 - VÝCHOZÍ POZICE")
        print_ascii_board(board, "Výchozí pozice")
        print(f"FEN: {board.get_fen()}")
        print(f"Na tahu: {'Bílý' if board.turn else 'Černý'}")

        sequence = []
        current_board = board.copy()
        step = 0

        # Hlavní smyčka - pokračuj až do matu
        while step < max_depth:
            step += 1

            print(f"\n{'='*60}")
            print(f"📊 KROK {step}")
            print(f"Na tahu: {'🔵 BÍLÝ' if current_board.turn else '🔴 ČERNÝ'}")
            print("="*60)

            # 1. ZKONTROLUJ AKTUÁLNÍ STAV
            current_color = 'w' if current_board.turn else 'b'
            legal_moves = self.generate_legal_moves(current_board)
            is_in_check = current_board.is_check(current_color)

            print(f"🔍 STAV POZICE:")
            print(f"   Hráč na tahu: {current_color.upper()}")
            print(f"   Počet legálních tahů: {len(legal_moves)}")
            print(f"   Je v šachu: {is_in_check}")

            # 2. KONTROLA KONCE HRY
            if len(legal_moves) == 0:
                if is_in_check:
                    print(f"\n🎉 CHECKMATE! {current_color.upper()} nemá legální tahy a je v šachu!")
                    print(f"🏁 MATOVÁ SEKVENCE DOKONČENA po {step-1} krocích")
                    break
                else:
                    print(f"\n🤝 PAT! {current_color.upper()} nemá legální tahy ale není v šachu")
                    print(f"🏁 Sekvence končí patem po {step-1} krocích")
                    break

            # 3. ZOBRAZ DOSTUPNÉ TAHY
            print(f"\n📋 DOSTUPNÉ TAHY PRO {current_color.upper()}:")
            for i, move in enumerate(legal_moves[:8], 1):  # Show first 8 moves
                move_alg = move_to_algebraic(current_board, move[0], move[1])
                print(f"   {i}. {move_alg}", end="")
                if i % 4 == 0:
                    print()
                else:
                    print("", end="  ")
            if len(legal_moves) > 8:
                print(f"   ... a dalších {len(legal_moves) - 8} tahů")
            elif len(legal_moves) % 4 != 0:
                print()

            # 4. NAJDI NEJLEPŠÍ TAH
            print(f"\n🎯 HLEDÁM NEJLEPŠÍ TAH...")

            # Use simple search for mate sequence
            self.current_search_depth = 3  # Keep it simple for sequence

            # Reset nodes for this step
            nodes_before = self.nodes_evaluated
            step_start = time.time()

            result = self.find_best_move_recursive(current_board, depth=3)

            step_time = time.time() - step_start
            nodes_this_step = self.nodes_evaluated - nodes_before

            if not result:
                print("❌ NEPODAŘILO SE NAJÍT TAH - končím analýzu")
                break

            best_move, best_value = result
            algebraic = move_to_algebraic(current_board, best_move[0], best_move[1])

            print(f"✅ NEJLEPŠÍ TAH: {algebraic}")
            print(f"📊 Ohodnocení: {best_value:.1f}")

            # FIXED: Avoid division by zero in step timing
            if step_time > 0:
                print(f"⏱️  Čas: {step_time:.1f}s, Uzlů: {nodes_this_step} ({nodes_this_step/step_time:.0f}/s)")
            else:
                print(f"⏱️  Čas: {step_time:.1f}s, Uzlů: {nodes_this_step} (příliš rychlé)")


            # 5. PROVEĎ TAH A ULOŽ INFORMACE
            move_info = {
                'step': step,
                'move': algebraic,
                'from_pos': best_move[0],
                'to_pos': best_move[1],
                'evaluation': best_value,
                'color': 'Bílý' if current_board.turn else 'Černý',
                'fen_before': current_board.get_fen(),
                'legal_moves_before': len(legal_moves)
            }

            print(f"\n🎯 PROVÁDÍM TAH: {algebraic}")
            current_board.make_move(best_move[0], best_move[1])
            move_info['fen_after'] = current_board.get_fen()
            sequence.append(move_info)

            # 6. ZOBRAZ POZICI PO TAHU
            print(f"\n📍 POZICE PO TAHU {algebraic}:")
            print_ascii_board(current_board, f"Po tahu {step}. {algebraic}")
            print(f"FEN: {current_board.get_fen()}")

            # 7. ZKONTROLUJ STAV PO TAHU
            next_color = 'w' if current_board.turn else 'b'
            next_legal_moves = self.generate_legal_moves(current_board)
            next_in_check = current_board.is_check(next_color)

            print(f"\n🔍 STAV PO TAHU:")
            print(f"   Nyní na tahu: {next_color.upper()}")
            print(f"   Legální tahy: {len(next_legal_moves)}")
            print(f"   Je v šachu: {next_in_check}")

            if len(next_legal_moves) == 0:
                if next_in_check:
                    print(f"\n🎉 TO JE MAT! {next_color.upper()} nemá kam táhnout a je v šachu!")
                    print(f"🏁 CHECKMATE po tahu {algebraic}!")
                    break
                else:
                    print(f"\n🤝 TO JE PAT! {next_color.upper()} nemá kam táhnout ale není v šachu")
                    break
            else:
                print(f"✅ Hra pokračuje - {next_color.upper()} má {len(next_legal_moves)} možností")

            self.print_intermediate_time(f"Krok {step} hotov")

            # Safety break
            if step >= 15:
                print("⚠️ Dosažen bezpečnostní limit - ukončuji analýzu")
                break

        # VÝSLEDKY
        self.mate_sequence_time = time.time() - mate_sequence_start

        print(f"\n{'='*60}")
        print("📋 SHRNUTÍ MATOVÉ SEKVENCE")
        print("="*60)

        if sequence:
            print(f"🎯 ANALYZOVÁNO {len(sequence)} KROKŮ:")
            for i, move_data in enumerate(sequence, 1):
                print(f"   {i}. {move_data['color']}: {move_data['move']} ({move_data['evaluation']:+.1f})")

            print(f"\n📊 DETAILY:")
            for move_data in sequence:
                print(f"\nKrok {move_data['step']}: {move_data['move']}")
                print(f"   FEN před: {move_data['fen_before']}")
                print(f"   FEN po:   {move_data['fen_after']}")
        else:
            print("❌ Žádná sekvence nebyla zaznamenána")

        print(f"\n🏆 STATISTIKY:")
        print(f"📊 Kroků celkem: {len(sequence)}")
        print(f"⏱️  Celkový čas: {self.mate_sequence_time:.1f}s")

        return sequence

    def analyze_position(self, max_depth=6):
        """Main analysis method - uses recursive search"""
        return self.analyze_position_recursive(max_depth)

    def analyze_position(self, max_depth=6):
        """Analyze the starting position with minimal output"""
        board = ChessBoard(self.start_fen)

        print("=== ANALÝZA POZICE ===")
        self.print_position_info(board, "Výchozí pozice")

        # Check if position is already terminal
        terminal_result = self.is_terminal_position(board)
        if terminal_result:
            result_type, moves_to_end = terminal_result
            print(f"Terminální pozice: {result_type}")
            return None

        # Progressive depth search
        best_result = None
        for depth in range(1, max_depth + 1):
            print(f"\n--- HLOUBKA {depth} ---")

            try:
                result = self.find_best_move(board, depth)
                if result:
                    best_move, best_value = result
                    best_result = result

                    # If we found a forced mate, we can stop
                    if abs(best_value) > 9000:
                        mate_in = int((10000 - abs(best_value)))
                        print(f"NUCENÝ MAT za {mate_in} tahů!")
                        if depth >= 4:
                            break
                else:
                    print(f"Žádný výsledek pro hloubku {depth}")

            except Exception as e:
                print(f"Chyba na hloubce {depth}: {e}")
                break

        print(f"\n=== FINÁLNÍ VÝSLEDEK ===")

        if best_result:
            best_move, best_value = best_result
            algebraic = move_to_algebraic(board, best_move[0], best_move[1])

            print(f"Doporučený tah: {algebraic}")
            print(f"Ohodnocení: {best_value}")

            # Show final position
            final_board = board.copy()
            final_board.make_move(best_move[0], best_move[1])
            self.print_position_info(final_board, f"Po tahu {algebraic}")

            # Interpret the evaluation
            if abs(best_value) > 9000:
                mate_in = int((10000 - abs(best_value)))
                if best_value > 0:
                    print(f"Mat za {mate_in} tahů")
                else:
                    print(f"Obrana {mate_in} tahů")
            elif abs(best_value) < 0.1:
                print("Vyrovnaná pozice")
            elif best_value > 0:
                print(f"Výhoda (+{best_value:.1f})")
            else:
                print(f"Nevýhoda ({best_value:.1f})")

            return best_result
        else:
            print("Analýza selhala")
            return None


# Test the enhanced analyzer with minimal output
if __name__ == "__main__":
    # Test positions
    test_positions = {
        1: ("Jednoduchý mat - Věž + Dáma", "5K1k/8/5R2/8/2Q5/8/8/8 w - - 0 1"),
        2: ("Amazonka vs malé figury", "8/8/8/8/A7/4c1k1/8/6K1 w - - 0 1"),
        3: ("Složitý endgame", "8/6K1/3b4/4n1k1/8/8/8/8 w - - 0 1"),
        4: ("Slabá Amazonka", "8/6k1/1A6/8/3K4/8/8/8 w - - 0 1"),
        5: ("Cyril vs Král", "8/8/8/3k4/8/3C4/8/3K4 w - - 0 1"),
        6: ("Eve + Pěšec", "8/1P6/8/3k4/8/3E4/8/3K4 w - - 0 1")
    }

    print("POHÁDKOVÝ ŠACHOVÝ ENGINE")
    print("Pohádkové figury: A=Amazonka(Q+N), C=Cyril(R+N), E=Eve(B+N)")
    print("="*50)

    print("\nTestovací pozice:")
    for num, (name, fen) in test_positions.items():
        print(f"{num}. {name}")

        # Simple board display with coordinates
        rows = fen.split()[0].split("/")
        for i, row in enumerate(rows):
            line = ""
            for char in row:
                if char.isdigit():
                    line += "." * int(char)
                else:
                    line += char
            print(f"   {8-i} {line}")
        print(f"     abcdefgh")
        print()

    # Select test position
    selected = 2  # Amazon vs small pieces
    name, fen = test_positions[selected]

    print(f"Analyzuji pozici {selected}: {name}")
    print(f"FEN: {fen}")
    print("="*50)

def verify_mate_in_one(fen, expected_move):
    """Verify that expected move is indeed mate in one"""
    board = ChessBoard(fen)

    # Parse expected move (e.g., "Aa1")
    if len(expected_move) >= 3:
        piece_type = expected_move[0].upper()
        to_square = expected_move[1:]

        # Convert to coordinates
        to_file = ord(to_square[0]) - ord('a')
        to_rank = int(to_square[1]) - 1
        to_pos = (to_rank, to_file)

        # Find piece that can make this move
        for rank in range(8):
            for file in range(8):
                piece = board.board[rank][file]
                if piece and piece[1] == piece_type and piece[0] == ('w' if board.turn else 'b'):
                    from_pos = (rank, file)

                    # Check if this move is legal
                    analyzer = EnhancedFairyChessAnalyzer(fen)
                    if analyzer.is_move_legal(board, from_pos, to_pos):
                        # Make the move
                        temp_board = board.copy()
                        temp_board.make_move(from_pos, to_pos)

                        # Check if opponent is in checkmate
                        opponent_color = 'b' if board.turn else 'w'
                        if temp_board.is_check(opponent_color):
                            # Check if opponent has any legal moves
                            opponent_moves = analyzer.generate_legal_moves(temp_board)
                            if not opponent_moves:
                                print(f"✅ OVĚŘENO: {expected_move} je skutečně mat v 1 tahu")
                                return True
                            else:
                                print(f"❌ {expected_move} dává šach, ale není to mat")
                                return False
                        else:
                            print(f"❌ {expected_move} nedává ani šach")
                            return False

    print(f"❌ Tah {expected_move} není možný v této pozici")
    return False


# Enhanced fairy chess engine with recursive search focus
if __name__ == "__main__":
    # Test positions optimized for fairy piece analysis
    test_positions = {
        1: ("Mat s Věží + Dámou", "5K1k/8/5R2/8/2Q5/8/8/8 w - - 0 1"),
        2: ("Amazonka vs Král+Střelec", "8/8/8/8/A7/4c1k1/8/6K1 w - - 0 1"),
        3: ("Složitý endgame", "8/6K1/3b4/4n1k1/8/8/8/8 w - - 0 1"),
        4: ("Amazonka vs Král", "8/6k1/1A6/8/3K4/8/8/8 w - - 0 1"),
        5: ("Cyril matuje", "8/8/8/3k4/8/3C4/8/3K4 w - - 0 1"),
        6: ("Eve + Pěšec endgame", "8/1P6/8/3k4/8/3E4/8/3K4 w - - 0 1"),
        7: ("Všechny pohádkové figury", "r1bqkb1r/pppp1ppp/2n2n2/1B2p3/1A2P3/5N2/PPPP1PcP/RNBQK2R w KQkq - 0 1"),
        8: ("Amazonka vs Cyril", "8/8/8/3A4/8/3c4/8/3K1k2 w - - 0 1")
    }

    print("🧚 REKURZIVNÍ POHÁDKOVÝ ŠACHOVÝ ENGINE")
    print("Optimalizováno pro hluboké prohledávání")
    print("Pohádkové figury: A=Amazonka(Q+N), C=Cyril(R+N), E=Eve(B+N)")
    print("="*60)

    print("\nTestovací pozice:")
    for num, (name, fen) in test_positions.items():
        print(f"{num}. {name}")

        # Show board with coordinates
        rows = fen.split()[0].split("/")
        for i, row in enumerate(rows):
            line = ""
            for char in row:
                if char.isdigit():
                    line += "." * int(char)
                else:
                    line += char
            print(f"   {8-i} {line}")
        print(f"     abcdefgh")
        print()

    # Select position for deep analysis
    selected = 2  # Amazonka vs small pieces - complex tactics
    name, fen = test_positions[selected]

    print(f"🎯 ANALÝZA POZICE {selected}: {name}")
    print(f"FEN: {fen}")
    print("="*60)

    # TESTING: Quick verification of expected result
    print("🧪 OVĚŘENÍ OČEKÁVANÉHO VÝSLEDKU:")
    print("Očekávaný nejlepší tah: Aa1 (mat v 1 tahu)")
    verify_mate_in_one(fen, "Aa1")
    print("="*60)

    # Create analyzer instance
    analyzer = EnhancedFairyChessAnalyzer(fen)

    # Run recursive analysis with mate sequence tracking
    print("Spouštím rekurzivní analýzu s matovou sekvencí...")
    print("Tip: Přerušte Ctrl+C pro rychlejší výsledek")

    # Start total timing from the very beginning
    total_start_time = time.time()
    analyzer.print_time("🚀 ZAČÁTEK KOMPLETNÍ ANALÝZY")

    # Use the enhanced analysis that shows complete mate sequence
    analysis_result = analyzer.analyze_position_with_mate_sequence(max_depth=5)

    if isinstance(analysis_result, tuple):
        result, mate_sequence = analysis_result
    else:
        result = analysis_result
        mate_sequence = None

    # Calculate total time including everything
    total_time = time.time() - total_start_time
    analyzer.print_time(f"⏹️  KONEC KOMPLETNÍ ANALÝZY (celkem {total_time:.1f}s)")

    print(f"\n🏆 ZÁVĚREČNÉ SHRNUTÍ")
    print("="*60)

    if result:
        move, evaluation = result
        from_pos, to_pos = move
        algebraic = move_to_algebraic(ChessBoard(fen), from_pos, to_pos)

        print(f"📍 Testovaná pozice: {name}")
        print(f"🎯 Doporučený tah: {algebraic}")
        print(f"📊 Finální ohodnocení: {evaluation:.1f}")
        print(f"🔍 Analyzovaných uzlů: {analyzer.nodes_evaluated:,}")
        print(f"💾 Pozic v cache: {len(analyzer.transposition_table):,}")

        # TESTING: Verification of expected result
        if algebraic == "Aa1":
            print("✅ SPRÁVNĚ! Engine našel očekávaný tah Aa1")
        else:
            print(f"❌ CHYBA! Očekával jsem Aa1, ale engine doporučuje {algebraic}")

        # Show mate sequence summary if available
        if mate_sequence:
            print(f"\n🎯 MATOVÁ SEKVENCE NALEZENA:")
            print(f"📊 Celkem kroků do matu: {len(mate_sequence)}")
            print(f"📊 Celkem tahů do matu: {len(mate_sequence)}")

            print(f"\n📝 SHRNUTÍ MATOVÉ SEKVENCE:")
            for move_data in mate_sequence:
                step = move_data['step']  # FIXED: Use 'step' instead of 'ply'
                move = move_data['move']
                color = move_data['color']
                print(f"  {step}. {color}: {move}")

        # ENHANCED: Detailed timing statistics
        print(f"\n⏱️  DETAILNÍ ČASOVÉ STATISTIKY:")
        print(f"   🕐 Celkový čas analýzy: {total_time:.1f}s")
        print(f"   🔧 Čas engine operací: {analyzer.total_analysis_time:.1f}s")

        if hasattr(analyzer, 'mate_sequence_time') and analyzer.mate_sequence_time > 0:
            print(f"   🎯 Čas matové sekvence: {analyzer.mate_sequence_time:.1f}s")
            recursive_time = analyzer.total_analysis_time - analyzer.mate_sequence_time
            print(f"   🔍 Čas rekurzivní analýzy: {recursive_time:.1f}s")

            # FIXED: Avoid division by zero
            if analyzer.mate_sequence_time > 0:
                ratio = recursive_time / analyzer.mate_sequence_time
                print(f"   📊 Poměr času (rekurze/sekvence): {ratio:.1f}:1")
            else:
                print(f"   📊 Matová sekvence byla příliš rychlá pro poměr")

        if analyzer.depth_times:
            print(f"   📈 Časy podle hloubky:")
            total_depth_time = 0
            for depth in sorted(analyzer.depth_times.keys()):
                duration = analyzer.depth_times[depth]
                total_depth_time += duration
                print(f"      Hloubka {depth}: {duration:.1f}s")
            print(f"   📊 Celkem všechny hloubky: {total_depth_time:.1f}s")

        if total_time > 0:
            print(f"   ⚡ Celková rychlost: {analyzer.nodes_evaluated/total_time:.0f} uzlů/s")
            efficiency = (analyzer.nodes_evaluated / total_time) / 1000
            print(f"   🏃 Efektivita: {efficiency:.1f}k uzlů/s")
        else:
            print(f"   ⚡ Analýza byla příliš rychlá pro přesné měření rychlosti")
            print(f"   🏃 Efektivita: >1000k uzlů/s")

        # Strategic interpretation
        if abs(evaluation) > 9000:
            mate_in = int(10000 - abs(evaluation)) + 1  # FIXED: Correct mate counting
            print(f"🎯 Výsledek: Nucený mat za {mate_in} tah{'ů' if mate_in > 1 else ''}")
        elif abs(evaluation) > 5:
            print(f"💪 Výsledek: Rozhodující výhoda")
        elif abs(evaluation) > 2:
            print(f"👍 Výsledek: Značná výhoda")
        elif abs(evaluation) > 0.5:
            print(f"🤏 Výsledek: Mírná výhoda")
        else:
            print(f"⚖️  Výsledek: Vyrovnaná pozice")

    else:
        print("❌ Rekurzivní analýza nebyla úspěšná")
        print("Možné příčiny:")
        print("- Terminální pozice (mat/pat)")
        print("- Příliš složitá pozice pro danou hloubku")
        print("- Chyba v implementaci")

        # Show timing even for failed analysis
        if total_time > 0:
            print(f"\n⏱️  Celkový čas neúspěšné analýzy: {total_time:.1f}s")
            if analyzer.total_analysis_time > 0:
                print(f"   🔧 Čas engine operací: {analyzer.total_analysis_time:.1f}s")

                # FIXED: Avoid division by zero for failed analysis
                if total_time > 0:
                    print(f"   ⚡ Rychlost: {analyzer.nodes_evaluated/total_time:.0f} uzlů/s")
        else:
            print(f"\n⏱️  Analýza byla příliš rychlá pro měření času")
            print(f"   🔧 Evaluováno uzlů: {analyzer.nodes_evaluated}")

    print("="*60)
    print("✅ OPRAVENÝ ENGINE - správná logika pro silnější/slabší stranu")
    print("✅ OPRAVENÉ POČÍTÁNÍ - správné tahy do matu")
    print("✅ MATOVÁ SEKVENCE - kompletní analýza až do matu")
    print("✅ ČASOVÉ STATISTIKY - detailní tracking všech operací")
    print("✅ OPTIMALIZACE - rekurzivní prohledávání pro pohádkové figury")