excellent 3

import time

# Chess board representation and FEN parsing
def parse_fen(fen_str):
    """Parse a FEN string into a board representation and additional info."""
    parts = fen_str.split()
    rows = parts[0].split('/')
    side_to_move = parts[1]

    # Initialize 8x8 board with empty squares
    board = []
    for rank in rows:
        row = []
        for ch in rank:
            if ch.isdigit():
                # Add empty squares
                row.extend(['.'] * int(ch))
            else:
                # Add piece
                row.append(ch)
        board.append(row)

    # Ensure 8x8 dimensions
    for i in range(len(board)):
        if len(board[i]) < 8:
            board[i].extend(['.'] * (8 - len(board[i])))
    while len(board) < 8:
        board.append(['.'] * 8)

    return board, side_to_move

def print_board(board):
    """Print the chess board in a readable format."""
    print("  a b c d e f g h")
    for r in range(8):
        print(f"{8-r} {' '.join(board[r])} {8-r}")
    print("  a b c d e f g h")

# Move generation for different piece types
def generate_moves(board, side):
    """Generate all possible moves for the given side."""
    moves = []

    # Define movement patterns for pieces
    king_dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    rook_dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    bishop_dirs = [(-1,-1), (-1,1), (1,-1), (1,1)]
    knight_moves = [(-2,-1), (-2,1), (-1,-2), (-1,2), (1,-2), (1,2), (2,-1), (2,1)]

    # Piece movement definitions
    piece_moves = {
        'p': {'dirs': [], 'sliding': False},  # Pawn (special handling)
        'r': {'dirs': rook_dirs, 'sliding': True},  # Rook
        'n': {'dirs': knight_moves, 'sliding': False},  # Knight
        'b': {'dirs': bishop_dirs, 'sliding': True},  # Bishop
        'q': {'dirs': rook_dirs + bishop_dirs, 'sliding': True},  # Queen
        'k': {'dirs': king_dirs, 'sliding': False},  # King
        'a': {'dirs': rook_dirs + bishop_dirs, 'sliding': True, 'knight_moves': knight_moves},  # Amazonka (queen + knight)
        'c': {'dirs': rook_dirs, 'sliding': True, 'knight_moves': knight_moves},  # Cardinal (rook + knight)
        'e': {'dirs': bishop_dirs, 'sliding': True, 'knight_moves': knight_moves}  # Eve (bishop + knight)
    }

    for r in range(8):
        for c in range(8):
            piece = board[r][c]
            if piece == '.':
                continue

            # Skip pieces of the opposite side
            if side == 'w' and piece.islower():
                continue
            if side == 'b' and piece.isupper():
                continue

            piece_type = piece.lower()

            # Handle pawns specially
            if piece_type == 'p':
                if side == 'w':
                    # Move forward
                    if r > 0 and board[r-1][c] == '.':
                        moves.append((r, c, r-1, c))
                        # Double move from starting position
                        if r == 6 and board[r-2][c] == '.':
                            moves.append((r, c, r-2, c))
                    # Captures
                    for dc in [-1, 1]:
                        if 0 <= c+dc < 8 and r > 0:
                            target = board[r-1][c+dc]
                            if target != '.' and target.islower():
                                moves.append((r, c, r-1, c+dc))
                else:  # Black pawn
                    # Move forward
                    if r < 7 and board[r+1][c] == '.':
                        moves.append((r, c, r+1, c))
                        # Double move from starting position
                        if r == 1 and board[r+2][c] == '.':
                            moves.append((r, c, r+2, c))
                    # Captures
                    for dc in [-1, 1]:
                        if 0 <= c+dc < 8 and r < 7:
                            target = board[r+1][c+dc]
                            if target != '.' and target.isupper():
                                moves.append((r, c, r+1, c+dc))

            # Handle other pieces
            elif piece_type in piece_moves:
                movement = piece_moves[piece_type]

                # Handle standard sliding or non-sliding moves
                for dr, dc in movement['dirs']:
                    nr, nc = r + dr, c + dc
                    # For non-sliding pieces, check one step
                    if not movement['sliding']:
                        if 0 <= nr < 8 and 0 <= nc < 8:
                            target = board[nr][nc]
                            if target == '.' or (side == 'w' and target.islower()) or (side == 'b' and target.isupper()):
                                moves.append((r, c, nr, nc))

                    # For sliding pieces, check the ray
                    else:
                        while 0 <= nr < 8 and 0 <= nc < 8:
                            target = board[nr][nc]
                            if target == '.':
                                moves.append((r, c, nr, nc))
                            elif (side == 'w' and target.islower()) or (side == 'b' and target.isupper()):
                                moves.append((r, c, nr, nc))
                                break
                            else:
                                break
                            nr += dr
                            nc += dc

                # Handle knight moves for special pieces
                if 'knight_moves' in movement:
                    for dr, dc in movement['knight_moves']:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < 8 and 0 <= nc < 8:
                            target = board[nr][nc]
                            if target == '.' or (side == 'w' and target.islower()) or (side == 'b' and target.isupper()):
                                moves.append((r, c, nr, nc))

    return moves

# Board state evaluation functions
def make_move(board, move):
    """Apply a move to a board and return the new board."""
    fr, fc, tr, tc = move
    new_board = [row[:] for row in board]
    new_board[tr][tc] = new_board[fr][fc]
    new_board[fr][fc] = '.'
    return new_board

def is_in_check(board, side):
    """Check if the king of the given side is in check."""
    # Find the king
    king_char = 'K' if side == 'w' else 'k'
    king_pos = None

    for r in range(8):
        for c in range(8):
            if board[r][c] == king_char:
                king_pos = (r, c)
                break
        if king_pos:
            break

    if not king_pos:
        return False  # No king found (shouldn't happen in normal chess)

    # Check if king is attacked by any opponent piece
    opponent_side = 'b' if side == 'w' else 'w'
    opponent_moves = generate_moves(board, opponent_side)

    for move in opponent_moves:
        _, _, tr, tc = move
        if (tr, tc) == king_pos:
            return True

    return False

def get_legal_moves(board, side):
    """Get all legal moves (not leaving king in check)."""
    moves = generate_moves(board, side)
    legal_moves = []

    for move in moves:
        new_board = make_move(board, move)
        if not is_in_check(new_board, side):
            legal_moves.append(move)

    return legal_moves

def is_checkmate(board, side):
    """Check if the given side is in checkmate."""
    if not is_in_check(board, side):
        return False
    return len(get_legal_moves(board, side)) == 0

def find_checkmate_in_one(board, side_to_move):
    """Find all moves that result in checkmate in one move."""
    checkmate_moves = []

    # Generate all moves for the side to move
    moves = generate_moves(board, side_to_move)

    for move in moves:
        # Apply the move
        new_board = make_move(board, move)

        # Check if opponent is in checkmate
        opponent = 'b' if side_to_move == 'w' else 'w'
        if is_checkmate(new_board, opponent):
            checkmate_moves.append(move)

    return checkmate_moves

def move_to_algebraic(board, move):
    """Convert a move from coordinates to algebraic notation."""
    fr, fc, tr, tc = move
    piece = board[fr][fc]

    from_square = chr(ord('a') + fc) + str(8 - fr)
    to_square = chr(ord('a') + tc) + str(8 - tr)

    return f"{piece}{from_square}-{to_square}"

# Main function to analyze and find mates
# Minimax search with focus on finding checkmate
def minimax(board, depth, maximizing_player, side, alpha=-float('inf'), beta=float('inf')):
    """
    Minimax search with alpha-beta pruning to find checkmate sequences.
    Returns (score, best_move, mate_found)
    """
    # Constants for scoring
    MATE_SCORE = 10000

    # Terminal state check
    legal_moves = get_legal_moves(board, side)

    # Check for checkmate or stalemate
    if not legal_moves:
        if is_in_check(board, side):
            return -MATE_SCORE + (100 - depth) if maximizing_player else MATE_SCORE - (100 - depth), None, True
        else:
            return 0, None, False  # Stalemate

    # Reached maximum depth without finding checkmate
    if depth == 0:
        return 0, None, False

    mate_found = False
    best_move = None

    if maximizing_player:
        max_eval = -float('inf')

        for move in legal_moves:
            new_board = make_move(board, move)
            next_side = 'b' if side == 'w' else 'w'

            eval_score, _, child_mate_found = minimax(new_board, depth - 1, False, next_side, alpha, beta)

            # Update best score and move
            if eval_score > max_eval:
                max_eval = eval_score
                best_move = move
                mate_found = child_mate_found

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

        return max_eval, best_move, mate_found
    else:
        min_eval = float('inf')

        for move in legal_moves:
            new_board = make_move(board, move)
            next_side = 'b' if side == 'w' else 'w'

            eval_score, _, child_mate_found = minimax(new_board, depth - 1, True, next_side, alpha, beta)

            # Update best score and move
            if eval_score < min_eval:
                min_eval = eval_score
                best_move = move
                mate_found = child_mate_found

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

        return min_eval, best_move, mate_found

def find_mate_sequence(board, side, max_depth=10):
    """Find a checkmate sequence up to max_depth."""
    # Iterative deepening to find mate
    for depth in range(1, max_depth + 1):
        print(f"Searching for mate in {depth} moves...")
        start_time = time.time()

        # Maximizing for the side to move
        score, best_move, mate_found = minimax(board, depth, True, side)

        end_time = time.time()
        elapsed = end_time - start_time
        print(f"Depth {depth} completed in {elapsed:.4f} seconds")

        if mate_found:
            print(f"Mate in {depth} found!")

            # Generate the mate sequence
            mate_sequence = []
            current_board = [row[:] for row in board]
            current_side = side
            current_depth = depth

            while current_depth > 0 and best_move:
                # Add the move to sequence
                mate_sequence.append((current_side, best_move))

                # Make the move
                current_board = make_move(current_board, best_move)

                # Switch sides
                current_side = 'b' if current_side == 'w' else 'w'
                current_depth -= 1

                # If this is checkmate, we're done
                if is_checkmate(current_board, current_side):
                    break

                # Find next best move in the sequence
                if current_depth > 0:
                    _, best_move, _ = minimax(current_board, current_depth, True, current_side)

            return mate_sequence

    print(f"No mate found within {max_depth} moves")
    return []

def analyze_position(fen, max_depth=10):
    """Analyze a position for checkmate possibilities."""
    print(f"Analyzing position: {fen}")
    board, side_to_move = parse_fen(fen)

    print("\nInitial position:")
    print_board(board)
    print(f"Side to move: {'White' if side_to_move == 'w' else 'Black'}")

    start_time = time.time()

    # First, find checkmate in one move
    checkmate_moves = find_checkmate_in_one(board, side_to_move)

    if checkmate_moves:
        end_time = time.time()
        elapsed = end_time - start_time

        print(f"\nFound {len(checkmate_moves)} immediate checkmate moves in {elapsed:.4f} seconds:")
        for i, move in enumerate(checkmate_moves, 1):
            algebraic = move_to_algebraic(board, move)
            print(f"{i}. {algebraic}")

            # Show the position after the checkmate move
            print(f"\nPosition after {algebraic}:")
            new_board = make_move(board, move)
            print_board(new_board)

            # Verify it's checkmate
            opponent = 'b' if side_to_move == 'w' else 'w'
            is_check = is_in_check(new_board, opponent)
            legal_moves = get_legal_moves(new_board, opponent)
            print(f"Opponent is in check: {is_check}")
            print(f"Opponent has {len(legal_moves)} legal moves")
            print(f"Checkmate: {is_check and len(legal_moves) == 0}")
    else:
        print("\nNo checkmate in one move found.")
        print("Proceeding with deeper search...")

        # If no immediate checkmate, search for longer mate sequences
        mate_sequence = find_mate_sequence(board, side_to_move, max_depth)

        if mate_sequence:
            print("\nCheckmate sequence found:")

            current_board = [row[:] for row in board]

            for i, (move_side, move) in enumerate(mate_sequence, 1):
                algebraic = move_to_algebraic(current_board, move)
                side_name = "White" if move_side == 'w' else "Black"
                print(f"Move {i}: {side_name} plays {algebraic}")

                # Apply the move
                current_board = make_move(current_board, move)
                print_board(current_board)

                # Check if this move results in checkmate
                opponent = 'b' if move_side == 'w' else 'w'
                if is_checkmate(current_board, opponent):
                    print(f"Checkmate! {side_name} wins.")
                    break
        else:
            print("No checkmate sequence found within the specified depth.")

    end_time = time.time()
    total_time = end_time - start_time
    print(f"\nTotal analysis time: {total_time:.4f} seconds")

# Execute the analysis
if __name__ == "__main__":
    # The position with Amazonka where we want to find the one-move checkmate
    fen = "8/8/8/q7/2k1R3/8/8/3K4 b - - 0 1"

    # You can test different positions by uncommenting these:
    # fen = "8/1K2k3/r7/8/8/8/8/8 b - - 0 1"  # Rook checkmate
    # fen = "8/1K6/3k1r2/8/8/8/8/8 b - - 0 1"  # Another rook position
    # fen = "8/2k2q2/8/3K1Q2/8/8/8/8 w - - 0 1"  # Queens position
    # fen = "8/k4q2/8/1K3Q2/8/8/8/8 w - - 0 1"  # Another queens position
    # fen = "8/1k6/1q6/8/1Q6/1K6/8/8 b - - 9 5"  # Position with queens

    # Set max_depth to control how far the search goes when no immediate mate is found
    analyze_position(fen, max_depth=50)