excellent 4 OK very good final

import time
import copy
from typing import List, Tuple, Optional, Dict, Set

class ChessEngine:
    def __init__(self):
        # Základní nastavení
        self.board = [['' for _ in range(8)] for _ in range(8)]
        self.white_to_move = True
        self.castling_rights = {'K': True, 'Q': True, 'k': True, 'q': True}
        self.en_passant = None
        self.halfmove_clock = 0
        self.fullmove_number = 1

        # Hodnoty figur pro evaluaci
        self.piece_values = {
            'P': 100, 'N': 320, 'B': 330, 'R': 500, 'Q': 900, 'K': 20000,
            'p': -100, 'n': -320, 'b': -330, 'r': -500, 'q': -900, 'k': -20000,
            'A': 1200, 'a': -1200,  # Amazonka (kůň + dáma)
            'C': 800, 'c': -800,    # Cyril (kůň + věž)
            'E': 650, 'e': -650     # Eve (kůň + střelec)
        }

        # Historie tahů pro výpis cesty
        self.move_history = []
        self.position_history = []

    def load_fen(self, fen: str):
        """Načte pozici z FEN stringu"""
        # Nejdříve vymaž šachovnici
        self.board = [['' for _ in range(8)] for _ in range(8)]

        parts = fen.split()

        # Parsování pozice
        rows = parts[0].split('/')
        for row_idx, row in enumerate(rows):
            if row_idx >= 8:  # Ochrana proti příliš mnoha řádkům
                break
            col_idx = 0
            for char in row:
                if col_idx >= 8:  # Ochrana proti překročení sloupců
                    break
                if char.isdigit():
                    # Prázdná pole
                    empty_squares = int(char)
                    for _ in range(empty_squares):
                        if col_idx < 8:
                            self.board[row_idx][col_idx] = ''
                            col_idx += 1
                else:
                    self.board[row_idx][col_idx] = char
                    col_idx += 1

        # Na tahu
        self.white_to_move = parts[1] == 'w'

        # Rošáda
        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
        }

        # En passant
        self.en_passant = parts[3] if len(parts) > 3 and parts[3] != '-' else None

        # Počet tahů
        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 to_fen(self) -> str:
        """Převede aktuální pozici na FEN string"""
        # Pozice
        fen_rows = []
        for row in self.board:
            fen_row = ''
            empty_count = 0
            for cell in row:
                if cell == '':
                    empty_count += 1
                else:
                    if empty_count > 0:
                        fen_row += str(empty_count)
                        empty_count = 0
                    fen_row += cell
            if empty_count > 0:
                fen_row += str(empty_count)
            fen_rows.append(fen_row)

        board_fen = '/'.join(fen_rows)

        # Na tahu
        active_color = 'w' if self.white_to_move else 'b'

        # Rošáda
        castling = ''
        if self.castling_rights['K']: castling += 'K'
        if self.castling_rights['Q']: castling += 'Q'
        if self.castling_rights['k']: castling += 'k'
        if self.castling_rights['q']: castling += 'q'
        if not castling: castling = '-'

        # En passant
        en_passant = self.en_passant if self.en_passant else '-'

        return f"{board_fen} {active_color} {castling} {en_passant} {self.halfmove_clock} {self.fullmove_number}"

    def print_board(self):
        """Vypíše šachovnici v ASCII formátu"""
        print("  a b c d e f g h")
        for i in range(8):
            print(f"{8-i} ", end="")
            for j in range(8):
                piece = self.board[i][j]
                if piece == '':
                    piece = '.'
                print(f"{piece} ", end="")
            print(f"{8-i}")
        print("  a b c d e f g h")
        print()

    def is_white_piece(self, piece: str) -> bool:
        """Zjistí, zda je figura bílá"""
        return piece.isupper()

    def get_piece_moves(self, row: int, col: int, check_castling: bool = True) -> List[Tuple[int, int]]:
        """Získá všechny možné tahy pro figuru na dané pozici"""
        piece = self.board[row][col]
        if piece == '':
            return []

        piece_type = piece.lower()
        is_white = self.is_white_piece(piece)
        moves = []

        if piece_type == 'p':
            # Pěšec
            direction = -1 if is_white else 1
            start_row = 6 if is_white else 1

            # Tah dopředu
            if 0 <= row + direction < 8 and self.board[row + direction][col] == '':
                moves.append((row + direction, col))
                # Dvojitý tah z počáteční pozice
                if row == start_row and self.board[row + 2 * direction][col] == '':
                    moves.append((row + 2 * direction, col))

            # Braní úhlopříčně
            for dc in [-1, 1]:
                new_row, new_col = row + direction, col + dc
                if 0 <= new_row < 8 and 0 <= new_col < 8:
                    target = self.board[new_row][new_col]
                    if target != '' and self.is_white_piece(target) != is_white:
                        moves.append((new_row, new_col))
                    # En passant
                    elif self.en_passant and self.en_passant == f"{chr(ord('a') + new_col)}{8 - new_row}":
                        moves.append((new_row, new_col))

        elif piece_type == 'r':
            # Věž
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            for dr, dc in directions:
                for i in range(1, 8):
                    new_row, new_col = row + i * dr, col + i * dc
                    if not (0 <= new_row < 8 and 0 <= new_col < 8):
                        break
                    target = self.board[new_row][new_col]
                    if target == '':
                        moves.append((new_row, new_col))
                    else:
                        if self.is_white_piece(target) != is_white:
                            moves.append((new_row, new_col))
                        break

        elif piece_type == 'n':
            # Kůň
            knight_moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
            for dr, dc in knight_moves:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < 8 and 0 <= new_col < 8:
                    target = self.board[new_row][new_col]
                    if target == '' or self.is_white_piece(target) != is_white:
                        moves.append((new_row, new_col))

        elif piece_type == 'b':
            # Střelec
            directions = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
            for dr, dc in directions:
                for i in range(1, 8):
                    new_row, new_col = row + i * dr, col + i * dc
                    if not (0 <= new_row < 8 and 0 <= new_col < 8):
                        break
                    target = self.board[new_row][new_col]
                    if target == '':
                        moves.append((new_row, new_col))
                    else:
                        if self.is_white_piece(target) != is_white:
                            moves.append((new_row, new_col))
                        break

        elif piece_type == 'q':
            # Dáma
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
            for dr, dc in directions:
                for i in range(1, 8):
                    new_row, new_col = row + i * dr, col + i * dc
                    if not (0 <= new_row < 8 and 0 <= new_col < 8):
                        break
                    target = self.board[new_row][new_col]
                    if target == '':
                        moves.append((new_row, new_col))
                    else:
                        if self.is_white_piece(target) != is_white:
                            moves.append((new_row, new_col))
                        break

        elif piece_type == 'k':
            # Král
            king_moves = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
            for dr, dc in king_moves:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < 8 and 0 <= new_col < 8:
                    target = self.board[new_row][new_col]
                    if target == '' or self.is_white_piece(target) != is_white:
                        moves.append((new_row, new_col))

            # Rošáda - pouze pokud je povoleno kontrolovat (vyhneme se rekurzi)
            if check_castling and not self.is_in_check(is_white):
                # Krátká rošáda
                castling_key = 'K' if is_white else 'k'
                if self.castling_rights[castling_key]:
                    if (self.board[row][col + 1] == '' and self.board[row][col + 2] == '' and
                        not self.is_square_attacked(row, col + 1, not is_white) and
                        not self.is_square_attacked(row, col + 2, not is_white)):
                        moves.append((row, col + 2))

                # Dlouhá rošáda
                castling_key = 'Q' if is_white else 'q'
                if self.castling_rights[castling_key]:
                    if (self.board[row][col - 1] == '' and self.board[row][col - 2] == '' and
                        self.board[row][col - 3] == '' and
                        not self.is_square_attacked(row, col - 1, not is_white) and
                        not self.is_square_attacked(row, col - 2, not is_white)):
                        moves.append((row, col - 2))

        elif piece_type == 'a':  # Amazonka (kůň + dáma)
            # Tahy dámy
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
            for dr, dc in directions:
                for i in range(1, 8):
                    new_row, new_col = row + i * dr, col + i * dc
                    if not (0 <= new_row < 8 and 0 <= new_col < 8):
                        break
                    target = self.board[new_row][new_col]
                    if target == '':
                        moves.append((new_row, new_col))
                    else:
                        if self.is_white_piece(target) != is_white:
                            moves.append((new_row, new_col))
                        break
            # Tahy koně
            knight_moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
            for dr, dc in knight_moves:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < 8 and 0 <= new_col < 8:
                    target = self.board[new_row][new_col]
                    if target == '' or self.is_white_piece(target) != is_white:
                        moves.append((new_row, new_col))

        elif piece_type == 'c':  # Cyril (kůň + věž)
            # Tahy věže
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            for dr, dc in directions:
                for i in range(1, 8):
                    new_row, new_col = row + i * dr, col + i * dc
                    if not (0 <= new_row < 8 and 0 <= new_col < 8):
                        break
                    target = self.board[new_row][new_col]
                    if target == '':
                        moves.append((new_row, new_col))
                    else:
                        if self.is_white_piece(target) != is_white:
                            moves.append((new_row, new_col))
                        break
            # Tahy koně
            knight_moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
            for dr, dc in knight_moves:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < 8 and 0 <= new_col < 8:
                    target = self.board[new_row][new_col]
                    if target == '' or self.is_white_piece(target) != is_white:
                        moves.append((new_row, new_col))

        elif piece_type == 'e':  # Eve (kůň + střelec)
            # Tahy střelce
            directions = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
            for dr, dc in directions:
                for i in range(1, 8):
                    new_row, new_col = row + i * dr, col + i * dc
                    if not (0 <= new_row < 8 and 0 <= new_col < 8):
                        break
                    target = self.board[new_row][new_col]
                    if target == '':
                        moves.append((new_row, new_col))
                    else:
                        if self.is_white_piece(target) != is_white:
                            moves.append((new_row, new_col))
                        break
            # Tahy koně
            knight_moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
            for dr, dc in knight_moves:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < 8 and 0 <= new_col < 8:
                    target = self.board[new_row][new_col]
                    if target == '' or self.is_white_piece(target) != is_white:
                        moves.append((new_row, new_col))

        return moves

    def is_square_attacked(self, row: int, col: int, by_white: bool) -> bool:
        """Zjistí, zda je pole napadené danou barvou"""
        for r in range(8):
            for c in range(8):
                piece = self.board[r][c]
                if piece != '' and self.is_white_piece(piece) == by_white:
                    # Nekontroluji rošádu při detekci napadení (vyhneme se rekurzi)
                    moves = self.get_piece_moves(r, c, check_castling=False)
                    if (row, col) in moves:
                        return True
        return False

    def find_king(self, is_white: bool) -> Tuple[int, int]:
        """Najde krále dané barvy"""
        king = 'K' if is_white else 'k'
        for r in range(8):
            for c in range(8):
                if self.board[r][c] == king:
                    return (r, c)
        return (-1, -1)  # Král nenalezen

    def is_in_check(self, is_white: bool) -> bool:
        """Zjistí, zda je král v šachu"""
        king_pos = self.find_king(is_white)
        if king_pos == (-1, -1):
            return False
        return self.is_square_attacked(king_pos[0], king_pos[1], not is_white)

    def make_move(self, from_pos: Tuple[int, int], to_pos: Tuple[int, int]) -> bool:
        """Provede tah a vrátí True, pokud je legální"""
        from_row, from_col = from_pos
        to_row, to_col = to_pos

        piece = self.board[from_row][from_col]
        if piece == '':
            return False

        is_white = self.is_white_piece(piece)
        if is_white != self.white_to_move:
            return False

        # Zkontroluj, zda je tah v seznamu možných tahů
        possible_moves = self.get_piece_moves(from_row, from_col)
        if (to_row, to_col) not in possible_moves:
            return False

        # Ulož původní stav
        original_board = copy.deepcopy(self.board)
        original_castling = copy.deepcopy(self.castling_rights)
        original_en_passant = self.en_passant

        # Proveď tah
        captured_piece = self.board[to_row][to_col]
        self.board[to_row][to_col] = piece
        self.board[from_row][from_col] = ''

        # Speciální tahy
        piece_type = piece.lower()

        # En passant
        if piece_type == 'p' and self.en_passant and f"{chr(ord('a') + to_col)}{8 - to_row}" == self.en_passant:
            if is_white:
                self.board[to_row + 1][to_col] = ''
            else:
                self.board[to_row - 1][to_col] = ''

        # Rošáda
        if piece_type == 'k' and abs(to_col - from_col) == 2:
            if to_col > from_col:  # Krátká rošáda
                self.board[from_row][7] = ''
                self.board[from_row][5] = 'R' if is_white else 'r'
            else:  # Dlouhá rošáda
                self.board[from_row][0] = ''
                self.board[from_row][3] = 'R' if is_white else 'r'

        # Aktualizace en passant
        if piece_type == 'p' and abs(to_row - from_row) == 2:
            self.en_passant = f"{chr(ord('a') + from_col)}{8 - (from_row + to_row) // 2}"
        else:
            self.en_passant = None

        # Aktualizace rošádových práv
        if piece_type == 'k':
            if is_white:
                self.castling_rights['K'] = False
                self.castling_rights['Q'] = False
            else:
                self.castling_rights['k'] = False
                self.castling_rights['q'] = False
        elif piece_type == 'r':
            if from_row == 0 or from_row == 7:
                if from_col == 0:
                    key = 'Q' if from_row == 7 else 'q'
                    self.castling_rights[key] = False
                elif from_col == 7:
                    key = 'K' if from_row == 7 else 'k'
                    self.castling_rights[key] = False

        # Zkontroluj, zda vlastní král není v šachu
        if self.is_in_check(is_white):
            # Vrať původní stav
            self.board = original_board
            self.castling_rights = original_castling
            self.en_passant = original_en_passant
            return False

        # Tah je legální
        self.white_to_move = not self.white_to_move
        if not self.white_to_move:
            self.fullmove_number += 1

        if captured_piece or piece_type == 'p':
            self.halfmove_clock = 0
        else:
            self.halfmove_clock += 1

        return True

    def undo_move(self, from_pos: Tuple[int, int], to_pos: Tuple[int, int],
                  captured_piece: str, old_castling: dict, old_en_passant: str,
                  old_halfmove: int, old_fullmove: int, was_white_to_move: bool):
        """Vrátí tah zpět"""
        from_row, from_col = from_pos
        to_row, to_col = to_pos

        piece = self.board[to_row][to_col]
        self.board[from_row][from_col] = piece
        self.board[to_row][to_col] = captured_piece

        # Vrácení speciálních tahů
        piece_type = piece.lower()

        # Rošáda
        if piece_type == 'k' and abs(to_col - from_col) == 2:
            if to_col > from_col:  # Krátká rošáda
                self.board[from_row][7] = 'R' if self.is_white_piece(piece) else 'r'
                self.board[from_row][5] = ''
            else:  # Dlouhá rošáda
                self.board[from_row][0] = 'R' if self.is_white_piece(piece) else 'r'
                self.board[from_row][3] = ''

        # En passant
        if piece_type == 'p' and old_en_passant and f"{chr(ord('a') + to_col)}{8 - to_row}" == old_en_passant:
            if self.is_white_piece(piece):
                self.board[to_row + 1][to_col] = 'p'
            else:
                self.board[to_row - 1][to_col] = 'P'

        self.castling_rights = old_castling
        self.en_passant = old_en_passant
        self.halfmove_clock = old_halfmove
        self.fullmove_number = old_fullmove
        self.white_to_move = was_white_to_move

    def get_all_legal_moves(self) -> List[Tuple[Tuple[int, int], Tuple[int, int]]]:
        """Získá všechny legální tahy pro aktuálního hráče"""
        legal_moves = []

        for row in range(8):
            for col in range(8):
                piece = self.board[row][col]
                if piece != '' and self.is_white_piece(piece) == self.white_to_move:
                    moves = self.get_piece_moves(row, col)
                    for to_row, to_col in moves:
                        # Zkopíruj stav
                        original_state = self.save_state()

                        # Zkus tah
                        if self.make_move((row, col), (to_row, to_col)):
                            legal_moves.append(((row, col), (to_row, to_col)))

                        # Vrať stav
                        self.restore_state(original_state)

        return legal_moves

    def save_state(self):
        """Uloží aktuální stav hry"""
        return {
            'board': copy.deepcopy(self.board),
            'white_to_move': self.white_to_move,
            'castling_rights': copy.deepcopy(self.castling_rights),
            'en_passant': self.en_passant,
            'halfmove_clock': self.halfmove_clock,
            'fullmove_number': self.fullmove_number
        }

    def restore_state(self, state):
        """Obnoví uložený stav hry"""
        self.board = state['board']
        self.white_to_move = state['white_to_move']
        self.castling_rights = state['castling_rights']
        self.en_passant = state['en_passant']
        self.halfmove_clock = state['halfmove_clock']
        self.fullmove_number = state['fullmove_number']

    def get_material_balance(self) -> int:
        """Spočítá materiální vyváženost (pozitivní = výhoda bílého)"""
        balance = 0
        for row in range(8):
            for col in range(8):
                piece = self.board[row][col]
                if piece != '' and piece.lower() != 'k':  # Ignoruj krále
                    balance += self.piece_values.get(piece, 0)
        return balance

    def evaluate_position(self) -> int:
        """Ohodnotí pozici s lepším rozlišením koncových pozic"""
        # Rychlá kontrola matu/patu před materiálním hodnocením
        if self.is_checkmate():
            if self.white_to_move:  # Bílý v matu -> černý vyhrál
                return -999999
            else:  # Černý v matu -> bílý vyhrál
                return 999999

        elif self.is_stalemate():
            # Pat: ve vítězné pozici je to neúspěch
            material_balance = self.get_material_balance()
            if material_balance > 300:  # Bílý má výhodu -> pat je velmi špatný
                return -10000
            elif material_balance < -300:  # Černý má výhodu -> pat je velmi dobrý pro bílého
                return 10000
            else:
                return 0  # Vyrovnaná pozice

        # Materiální hodnocení
        score = self.get_material_balance()

        # Bonus pro pokročilé koncovky - motivace k matu
        if abs(score) > 500:  # Významná materiální výhoda
            # Penalty za vzdálenost králů (v koncovce chceme krále blízko)
            white_king = self.find_king(True)
            black_king = self.find_king(False)

            if white_king != (-1, -1) and black_king != (-1, -1):
                king_distance = abs(white_king[0] - black_king[0]) + abs(white_king[1] - black_king[1])
                if score > 0:  # Bílý vede
                    score -= king_distance * 10  # Penalty za vzdálené krále
                else:  # Černý vede
                    score += king_distance * 10

        return score

    def is_checkmate(self) -> bool:
        """Zjistí, zda je mat"""
        if not self.is_in_check(self.white_to_move):
            return False

        legal_moves = self.get_all_legal_moves()
        return len(legal_moves) == 0

    def is_stalemate(self) -> bool:
        """Zjistí, zda je pat"""
        if self.is_in_check(self.white_to_move):
            return False

        legal_moves = self.get_all_legal_moves()
        return len(legal_moves) == 0

    def is_game_over(self) -> Tuple[bool, str]:
        """Zjistí, zda je hra u konce"""
        if self.is_checkmate():
            winner = "Černý" if self.white_to_move else "Bílý"
            return True, f"Mat! Vyhrál {winner}."
        elif self.is_stalemate():
            return True, "Pat! Remíza."
        elif self.halfmove_clock >= 100:
            return True, "Remíza podle pravidla 50 tahů."

        return False, ""

    def minimax(self, depth: int, alpha: int, beta: int, maximizing: bool,
                path: List[str]) -> Tuple[int, List[str]]:
        """Minimax algoritmus s alfa-beta pruningem - OPRAVENO PRO MAT"""

        # Kontrola konce hry
        if self.is_checkmate():
            # Mat: kdo vyhrál?
            if self.white_to_move:  # Bílý je na tahu ale je v matu -> černý vyhrál
                return (-999999 + len(path), path)
            else:  # Černý je na tahu ale je v matu -> bílý vyhrál
                return (999999 - len(path), path)

        elif self.is_stalemate():
            # NOVÁ LOGIKA: Pat je vždy remíza, ale ve vítězné pozici je to selhání
            material_balance = self.get_material_balance()

            if material_balance > 300:  # Bílý má výraznou výhodu
                return (-10000, path)  # Pat ve vítězné pozici je velmi špatný pro bílého
            elif material_balance < -300:  # Černý má výraznou výhodu
                return (10000, path)   # Pat ve vítězné pozici je velmi špatný pro černého
            else:
                return (0, path)  # Vyrovnaná pozice -> pat je OK

        elif self.halfmove_clock >= 100:
            return (0, path)

        if depth == 0:
            return (self.evaluate_position(), path)

        legal_moves = self.get_all_legal_moves()

        if maximizing:
            max_eval = float('-inf')
            best_path = path

            for move in legal_moves:
                # Ulož stav
                original_state = self.save_state()

                # Proveď tah
                self.make_move(move[0], move[1])
                move_notation = f"{chr(ord('a') + move[0][1])}{8 - move[0][0]}-{chr(ord('a') + move[1][1])}{8 - move[1][0]}"
                new_path = path + [move_notation]

                eval_score, eval_path = self.minimax(depth - 1, alpha, beta, False, new_path)

                if eval_score > max_eval:
                    max_eval = eval_score
                    best_path = eval_path

                # Vrať stav
                self.restore_state(original_state)

                alpha = max(alpha, eval_score)
                if beta <= alpha:
                    break

            return (max_eval, best_path)

        else:
            min_eval = float('inf')
            best_path = path

            for move in legal_moves:
                # Ulož stav
                original_state = self.save_state()

                # Proveď tah
                self.make_move(move[0], move[1])
                move_notation = f"{chr(ord('a') + move[0][1])}{8 - move[0][0]}-{chr(ord('a') + move[1][1])}{8 - move[1][0]}"
                new_path = path + [move_notation]

                eval_score, eval_path = self.minimax(depth - 1, alpha, beta, True, new_path)

                if eval_score < min_eval:
                    min_eval = eval_score
                    best_path = eval_path

                # Vrať stav
                self.restore_state(original_state)

                beta = min(beta, eval_score)
                if beta <= alpha:
                    break

            return (min_eval, best_path)

    def find_best_move(self, max_depth: int = 10) -> Tuple[Optional[List[str]], int]:
        """Najde nejlepší tah pomocí iterativního prohloubení"""
        print(f"Hledání nejlepšího tahu (maximální hloubka: {max_depth})...")
        print(f"Na tahu: {'Bílý' if self.white_to_move else 'Černý'}")

        # Zkontroluj materiální situaci
        material_balance = self.get_material_balance()
        if material_balance > 300:
            print(f"Bílý má materiální výhodu ({material_balance} bodů) - hledám mat!")
        elif material_balance < -300:
            print(f"Černý má materiální výhodu ({-material_balance} bodů) - bráním se!")
        print()

        best_path = None
        best_score = 0

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

            # OPRAVA: maximizing musí odpovídat tomu, kdo je na tahu!
            # Bílý maximalizuje (+), černý minimalizuje (-)
            score, path = self.minimax(depth, float('-inf'), float('inf'), self.white_to_move, [])

            end_time = time.time()
            elapsed = end_time - start_time

            print(f"Hloubka {depth}: skóre {score}, čas {elapsed:.3f}s")

            best_path = path
            best_score = score

            # Pokud byl nalezen mat, skonči
            if abs(score) > 900000:
                print(f"Nalezen mat v {len(path)} tazích!")
                break

            # Pokud je skóre příliš nízké ve vítězné pozici, pokračuj v hledání
            if material_balance > 300 and score < -500:
                print(f"Skóre {score} je příliš nízké pro vítěznou pozici, pokračujem...")

        return best_path, best_score

    def play_game(self, initial_fen: str = None, max_depth: int = 6):
        """Spustí hru s automatickým hraním"""
        if initial_fen:
            self.load_fen(initial_fen)
        else:
            # Standardní počáteční pozice
            self.load_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1")

        print("=== ŠACHOVÝ ENGINE S NESTANDARDNÍMI FIGURAMI ===")
        print("Legenda figur:")
        print("A/a = Amazonka (Kůň + Dáma)")
        print("C/c = Cyril (Kůň + Věž)")
        print("E/e = Eve (Kůň + Střelec)")
        print()

        print("Počáteční pozice:")
        print(f"FEN: {self.to_fen()}")
        self.print_board()

        move_count = 0

        while True:
            game_over, result = self.is_game_over()
            if game_over:
                print(result)
                break

            move_count += 1
            print(f"\n=== TAH {move_count} ===")

            best_path, score = self.find_best_move(max_depth)

            if not best_path:
                print("Žádný tah nenalezen!")
                break

            # Simuluj celou cestu
            if abs(score) > 900000:
                print(f"\nNalezená cesta k matu ({len(best_path)} tahů):")
            elif abs(score) > 5000:
                print(f"\nNalezená silná cesta ({len(best_path)} tahů):")
            elif abs(score) < -5000:
                print(f"\nVarování: Možný pat v {len(best_path)} tazích!")
            else:
                print(f"\nNalezená cesta ({len(best_path)} tahů):")

            current_engine = ChessEngine()
            current_engine.restore_state(self.save_state())

            # Vypíš počáteční pozici
            print(f"\nPočáteční pozice:")
            print(f"FEN: {current_engine.to_fen()}")
            current_engine.print_board()

            for i, move_notation in enumerate(best_path):
                # Parsuj a proveď tah
                from_pos = (8 - int(move_notation[1]), ord(move_notation[0]) - ord('a'))
                to_pos = (8 - int(move_notation[4]), ord(move_notation[3]) - ord('a'))

                if not current_engine.make_move(from_pos, to_pos):
                    print("Chyba při provádění tahu!")
                    break

                # Teď vypíš pozici PO provedení tahu
                print(f"\nTah {i + 1}: {move_notation}")
                print(f"FEN: {current_engine.to_fen()}")
                current_engine.print_board()

                game_over, result = current_engine.is_game_over()
                if game_over:
                    print(f"{result}")
                    return

            # Proveď první tah z nalezené cesty
            if best_path:
                first_move = best_path[0]
                from_pos = (8 - int(first_move[1]), ord(first_move[0]) - ord('a'))
                to_pos = (8 - int(first_move[4]), ord(first_move[3]) - ord('a'))

                if self.make_move(from_pos, to_pos):
                    print(f"\nProveden tah: {first_move}")
                else:
                    print("Chyba při provádění prvního tahu!")
                    break
            else:
                break

# Spuštění enginu
if __name__ == "__main__":
    engine = ChessEngine()

    # Testovací pozice - zajímavější matový problém
    # Černý král v rohu, bílá Amazonka a král pro demonstraci síly Amazonky
    test_fen = "k7/8/2A5/8/8/8/8/K7 w - - 0 1"
    test_fen = "7A/8/8/8/8/8/6k1/1K6 w - - 0 1"

    test_fen = "8/8/8/8/8/5BN1/5K1k/8 b - - 0 1"

    test_fen = "8/8/8/5N2/8/5B1k/5K2/8 b - - 0 1"

    print(f"Používám testovací pozici: {test_fen}")
    print("Pozice: Střelec na f3, Kůň na g3, Bílý král na f2, Černý král na h2")
    engine.play_game(test_fen, max_depth=8)