#!/usr/bin/env python3
import time
import threading
import sys
from math import inf

# Konstanty pro pohyby jezdce
knight_moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]

# Globální proměnné pro čas a historii tahů
running = False
start_time = 0
move_stack = []

def time_reporter():
    """Funkce pro výpis času každou sekundu na stejném řádku."""
    global running, start_time
    while running:
        elapsed = time.time() - start_time
        hrs = int(elapsed // 3600)
        mins = int((elapsed % 3600) // 60)
        secs = int(elapsed % 60)
        sys.stdout.write(f"\r[INFO] Uplynulý čas: {hrs:02d}h {mins:02d}m {secs:02d}s")
        sys.stdout.flush()
        time.sleep(1)

class Board:
    def __init__(self, fen=None):
        """Inicializace šachovnice."""
        self.grid = [[' ' for _ in range(8)] for _ in range(8)]
        self.to_move = 'w'
        self.castling_rights = set()
        self.en_passant = None
        self.halfmove_clock = 0
        self.fullmove_number = 1
        if fen:
            self.set_fen(fen)
    
    def set_fen(self, fen):
        """Nastaví šachovnici podle FEN řetězce."""
        parts = fen.split()
        while len(parts) < 6:
            parts.append('0')
        board_part, turn_part = parts[0], parts[1]
        castling_part = parts[2] if len(parts) > 2 else '-'
        en_passant_part = parts[3] if len(parts) > 3 else '-'
        halfmove = parts[4] if len(parts) > 4 else '0'
        fullmove = parts[5] if len(parts) > 5 else '1'
        
        self.grid = [['.' for _ in range(8)] for _ in range(8)]
        ranks = board_part.split('/')
        
        for rank_idx, rank_str in enumerate(ranks):
            file_idx = 0
            for ch in rank_str:
                if ch.isdigit():
                    file_idx += int(ch)
                else:
                    self.grid[rank_idx][file_idx] = ch
                    file_idx += 1
        
        self.to_move = 'w' if turn_part == 'w' else 'b'
        self.castling_rights = set() if castling_part == '-' else set(castling_part)
        self.en_passant = None
        
        if en_passant_part != '-' and en_passant_part != '':
            file = ord(en_passant_part[0]) - ord('a')
            rank = int(en_passant_part[1])
            ri = 8 - rank
            fi = file
            if 0 <= ri < 8 and 0 <= fi < 8:
                self.en_passant = (ri, fi)
        
        try:
            self.halfmove_clock = int(halfmove)
        except:
            self.halfmove_clock = 0
        
        try:
            self.fullmove_number = int(fullmove)
        except:
            self.fullmove_number = 1
    
    def copy(self):
        """Vytvoří hlubokou kopii šachovnice."""
        new_board = Board()
        new_board.grid = [row.copy() for row in self.grid]
        new_board.to_move = self.to_move
        new_board.castling_rights = set(self.castling_rights)
        new_board.en_passant = None if self.en_passant is None else (self.en_passant[0], self.en_passant[1])
        new_board.halfmove_clock = self.halfmove_clock
        new_board.fullmove_number = self.fullmove_number
        return new_board

    def display(self):
        """Vrátí textovou reprezentaci šachovnice."""
        lines = []
        for ri in range(8):
            line = ""
            for fi in range(8):
                line += self.grid[ri][fi] + " "
            lines.append(line)
        return "\n".join(lines)

# Základní funkce pro šach
def find_king(board, side):
    """Najde pozici krále pro stranu 'w' nebo 'b'."""
    target = 'K' if side=='w' else 'k'
    for r in range(8):
        for c in range(8):
            if board.grid[r][c] == target:
                return (r, c)
    return None

def is_square_attacked(board, r, c, by_side):
    """Zjistí, zda je pole (r,c) napadeno stranou by_side."""
    # Útoky pěšcem
    if by_side == 'b':
        if r+1 < 8 and c-1 >= 0 and board.grid[r+1][c-1] == 'p': return True
        if r+1 < 8 and c+1 < 8 and board.grid[r+1][c+1] == 'p': return True
    else:
        if r-1 >= 0 and c-1 >= 0 and board.grid[r-1][c-1] == 'P': return True
        if r-1 >= 0 and c+1 < 8 and board.grid[r-1][c+1] == 'P': return True
    
    # Útoky jezdcem a dalšími s jezdcovým pohybem (N, A, C, E)
    enemy_knights = ['n','a','c','e'] if by_side=='b' else ['N','A','C','E']
    for dr, dc in knight_moves:
        nr, nc = r+dr, c+dc
        if 0<=nr<8 and 0<=nc<8 and board.grid[nr][nc] in enemy_knights:
            return True
    
    # Útoky po řadách/sloupcích (R, Q, E, A)
    enemy_rook_like = ['r','q','e','a'] if by_side=='b' else ['R','Q','E','A']
    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
        nr, nc = r+dr, c+dc
        while 0<=nr<8 and 0<=nc<8:
            if board.grid[nr][nc] != '.':
                if board.grid[nr][nc] in enemy_rook_like:
                    return True
                break
            nr += dr; nc += dc
    
    # Útoky diagonálně (B, Q, C, A)
    enemy_bishop_like = ['b','q','c','a'] if by_side=='b' else ['B','Q','C','A']
    for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
        nr, nc = r+dr, c+dc
        while 0<=nr<8 and 0<=nc<8:
            if board.grid[nr][nc] != '.':
                if board.grid[nr][nc] in enemy_bishop_like:
                    return True
                break
            nr += dr; nc += dc
    
    # Sousední král
    enemy_king = 'k' if by_side=='b' else 'K'
    for dr in [-1,0,1]:
        for dc in [-1,0,1]:
            if dr==0 and dc==0: continue
            nr, nc = r+dr, c+dc
            if 0<=nr<8 and 0<=nc<8 and board.grid[nr][nc] == enemy_king:
                return True
    
    return False

def is_in_check(board, side):
    """Zjistí, zda je král strany side ('w' nebo 'b') v šachu."""
    king_pos = find_king(board, side)
    if not king_pos:
        return False
    kr, kc = king_pos
    enemy_side = 'b' if side=='w' else 'w'
    return is_square_attacked(board, kr, kc, enemy_side)

def generate_pseudo_moves(board, side):
    """Generuje všechny pseudolegální tahy pro stranu side ('w' nebo 'b')."""
    moves = []
    is_white = (side=='w')
    pawn_dir = -1 if is_white else 1
    start_rank = 6 if is_white else 1
    promote_rank = 0 if is_white else 7
    
    for r in range(8):
        for c in range(8):
            piece = board.grid[r][c]
            if piece == '.': continue
            if is_white and not piece.isupper(): continue
            if not is_white and not piece.islower(): continue
            
            pt = piece.upper()
            if pt == 'P':
                nr = r + pawn_dir
                if 0<=nr<8 and board.grid[nr][c]=='.':
                    if nr==promote_rank:
                        for promo in ['Q','R','B','N','A','E','C']:
                            moves.append((r, c, nr, c, promo if is_white else promo.lower(), None))
                    else:
                        moves.append((r, c, nr, c, None, None))
                    if r==start_rank and board.grid[r+pawn_dir*2][c]=='.' and board.grid[r+pawn_dir][c]=='.':
                        moves.append((r, c, r+pawn_dir*2, c, None, 'double'))
                for dc in [-1,1]:
                    nc = c + dc
                    if 0<=nc<8 and 0<=nr<8:
                        if board.grid[nr][nc] != '.' and ((is_white and board.grid[nr][nc].islower()) or (not is_white and board.grid[nr][nc].isupper())):
                            if nr==promote_rank:
                                for promo in ['Q','R','B','N','A','E','C']:
                                    moves.append((r, c, nr, nc, promo if is_white else promo.lower(), None))
                            else:
                                moves.append((r, c, nr, nc, None, None))
                        if board.en_passant == (nr, nc):
                            moves.append((r, c, nr, nc, None, 'enpassant'))
            elif pt == 'K':
                for dr in [-1,0,1]:
                    for dc in [-1,0,1]:
                        if dr==0 and dc==0: continue
                        nr, nc = r+dr, c+dc
                        if 0<=nr<8 and 0<=nc<8:
                            if board.grid[nr][nc]=='.' or ((is_white and board.grid[nr][nc].islower()) or (not is_white and board.grid[nr][nc].isupper())):
                                moves.append((r, c, nr, nc, None, None))
                # Rošády
                if is_white and r==7 and c==4:
                    if 'K' in board.castling_rights and board.grid[7][5]=='.' and board.grid[7][6]=='.':
                        moves.append((7,4,7,6,None,'castle'))
                    if 'Q' in board.castling_rights and board.grid[7][3]=='.' and board.grid[7][2]=='.' and board.grid[7][1]=='.':
                        moves.append((7,4,7,2,None,'castle'))
                if not is_white and r==0 and c==4:
                    if 'k' in board.castling_rights and board.grid[0][5]=='.' and board.grid[0][6]=='.':
                        moves.append((0,4,0,6,None,'castle'))
                    if 'q' in board.castling_rights and board.grid[0][3]=='.' and board.grid[0][2]=='.' and board.grid[0][1]=='.':
                        moves.append((0,4,0,2,None,'castle'))
            else:
                # Tahy pro figury s jezdcovým pohybem (N, A, C, E)
                if pt in ['N','A','C','E']:
                    for dr, dc in knight_moves:
                        nr, nc = r+dr, c+dc
                        if 0<=nr<8 and 0<=nc<8:
                            if board.grid[nr][nc]=='.' or ((is_white and board.grid[nr][nc].islower()) or (not is_white and board.grid[nr][nc].isupper())):
                                moves.append((r, c, nr, nc, None, None))
                
                # Klouzavé tahy – pro R, Q, E, A
                if pt in ['R','Q','E','A']:
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = r+dr, c+dc
                        while 0<=nr<8 and 0<=nc<8:
                            if board.grid[nr][nc]=='.':
                                moves.append((r, c, nr, nc, None, None))
                            else:
                                if ((is_white and board.grid[nr][nc].islower()) or (not is_white and board.grid[nr][nc].isupper())):
                                    moves.append((r, c, nr, nc, None, None))
                                break
                            nr += dr; nc += dc
                
                # Diagonální tahy – pro B, Q, C, A
                if pt in ['B','Q','C','A']:
                    for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
                        nr, nc = r+dr, c+dc
                        while 0<=nr<8 and 0<=nc<8:
                            if board.grid[nr][nc]=='.':
                                moves.append((r, c, nr, nc, None, None))
                            else:
                                if ((is_white and board.grid[nr][nc].islower()) or (not is_white and board.grid[nr][nc].isupper())):
                                    moves.append((r, c, nr, nc, None, None))
                                break
                            nr += dr; nc += dc
    
    return moves

def get_legal_moves(board, side):
    """Vrátí seznam legálních tahů pro danou stranu."""
    moves = generate_pseudo_moves(board, side)
    legal_moves = []
    for move in moves:
        make_move(move, board)
        if not is_in_check(board, side):
            legal_moves.append(move)
        undo_move(board)
    return legal_moves

def make_move(move, board):
    """Provede tah na šachovnici a uloží stav pro možnost undo."""
    r1, c1, r2, c2, promo, special = move
    piece = board.grid[r1][c1]
    captured = board.grid[r2][c2] if special != 'enpassant' else ('p' if piece=='P' else 'P')
    prev_state = (set(board.castling_rights), board.en_passant, board.halfmove_clock, board.fullmove_number)
    move_stack.append((r1, c1, r2, c2, promo, special, piece, captured, prev_state))
    
    # Aktualizace půltahových hodin a čísla tahu
    if piece.upper() == 'P' or captured != '.':
        board.halfmove_clock = 0
    else:
        board.halfmove_clock += 1
    
    if board.to_move == 'b':
        board.fullmove_number += 1
    
    board.grid[r1][c1] = '.'
    
    if special == 'castle':
        board.grid[r2][c2] = piece
        if piece == 'K':
            if c2 == 6:
                board.grid[7][5] = 'R'; board.grid[7][7] = '.'
            else:
                board.grid[7][3] = 'R'; board.grid[7][0] = '.'
        else:
            if c2 == 6:
                board.grid[0][5] = 'r'; board.grid[0][7] = '.'
            else:
                board.grid[0][3] = 'r'; board.grid[0][0] = '.'
    elif special == 'enpassant':
        board.grid[r2][c2] = piece
        if piece == 'P':
            board.grid[r2+1][c2] = '.'
        else:
            board.grid[r2-1][c2] = '.'
    else:
        board.grid[r2][c2] = promo if promo else piece
    
    # Aktualizace rošádových práv
    if piece == 'K':
        board.castling_rights.discard('K'); board.castling_rights.discard('Q')
    if piece == 'k':
        board.castling_rights.discard('k'); board.castling_rights.discard('q')
    if piece == 'R' and (r1, c1)==(7,7):
        board.castling_rights.discard('K')
    if piece == 'R' and (r1, c1)==(7,0):
        board.castling_rights.discard('Q')
    if piece == 'r' and (r1, c1)==(0,7):
        board.castling_rights.discard('k')
    if piece == 'r' and (r1, c1)==(0,0):
        board.castling_rights.discard('q')
    
    # En passant
    if special == 'double':
        board.en_passant = (r1 + (-1 if board.to_move=='w' else 1), c1)
    else:
        board.en_passant = None
    
    board.to_move = 'b' if board.to_move=='w' else 'w'

def undo_move(board):
    """Vrátí poslední provedený tah."""
    if not move_stack:
        print("Chyba: Žádný tah k vrácení!")
        return
    
    r1, c1, r2, c2, promo, special, piece, captured, prev_state = move_stack.pop()
    castling_rights, en_passant, halfmove_clock, fullmove_number = prev_state
    
    board.grid[r1][c1] = piece
    
    if special == 'castle':
        board.grid[r2][c2] = '.'
        if piece == 'K':
            if c2 == 6:
                board.grid[7][7] = 'R'; board.grid[7][5] = '.'
            else:
                board.grid[7][0] = 'R'; board.grid[7][3] = '.'
        else:
            if c2 == 6:
                board.grid[0][7] = 'r'; board.grid[0][5] = '.'
            else:
                board.grid[0][0] = 'r'; board.grid[0][3] = '.'
    elif special == 'enpassant':
        board.grid[r2][c2] = '.'
        if piece == 'P':
            board.grid[r2+1][c2] = 'p'
        else:
            board.grid[r2-1][c2] = 'P'
    else:
        board.grid[r2][c2] = captured
    
    board.castling_rights = castling_rights
    board.en_passant = en_passant
    board.halfmove_clock = halfmove_clock
    board.fullmove_number = fullmove_number
    board.to_move = 'b' if board.to_move=='w' else 'w'

def move_to_notation(move, board):
    """Převede tah na standardní šachovou notaci."""
    cols = "abcdefgh"
    r1, c1, r2, c2, promo, special = move
    
    if special == 'castle':
        return "O-O" if c2 > c1 else "O-O-O"
    
    piece = board.grid[r1][c1].upper()
    is_pawn = piece == 'P'
    
    # Pro pěšce nezačínáme označením figury
    prefix = '' if is_pawn else piece
    
    # Pole
    from_square = cols[c1] + str(8 - r1)
    to_square = cols[c2] + str(8 - r2)
    
    # Proměna
    promotion = '=' + promo.upper() if promo else ''
    
    # En passant
    ep = " e.p." if special == 'enpassant' else ''
    
    return prefix + from_square + '-' + to_square + promotion + ep

def is_mate_in_n_plies(board, depth):
    """Zjistí, zda je v pozici mat v přesně 'depth' půltazích."""
    if depth == 0:
        # Je teď mat?
        side_to_move = board.to_move
        return is_in_check(board, side_to_move) and not get_legal_moves(board, side_to_move), None
    
    side_to_move = board.to_move
    legal_moves = get_legal_moves(board, side_to_move)
    
    # Pokud nemá tahy
    if not legal_moves:
        # Pokud je to mat nyní, není to mat v hloubce depth (musí být přesně)
        if is_in_check(board, side_to_move):
            return False, None
        # Pat - nemůže dát mat
        return False, None
    
    # Určení, zda je strana, která mate, na tahu
    mating_color = 'w'  # Předpokládejme, že bílý dává mat
    if depth % 2 == 0:
        # Pokud je sudý počet půltahů, pak je na tahu matovaná strana
        mating_color = 'b' if board.to_move == 'w' else 'w'
    else:
        # Pokud je lichý počet půltahů, pak je na tahu matující strana
        mating_color = board.to_move
    
    # Je matující strana na tahu?
    is_mating_side_to_move = (board.to_move == mating_color)
    
    if is_mating_side_to_move:
        # Matující strana hledá tah, který vede k matu
        for move in legal_moves:
            make_move(move, board)
            is_mate, _ = is_mate_in_n_plies(board, depth - 1)
            undo_move(board)
            
            if is_mate:
                return True, move
        
        # Nenašli jsme žádnou matující sekvenci
        return False, None
    else:
        # Bránící se strana hledá nejlepší obranu
        all_lead_to_mate = True
        best_defensive_move = None
        
        # Zkusíme najít tah, který oddálí mat
        for move in legal_moves:
            make_move(move, board)
            is_mate, _ = is_mate_in_n_plies(board, depth - 1)
            undo_move(board)
            
            if not is_mate:
                # Našli jsme únikový tah, který vyvrací mat v daném počtu půltahů
                all_lead_to_mate = False
                best_defensive_move = move
                break
        
        # Pokud všechny tahy vedou k matu, alespoň vybereme ten, který dává nejlepší šanci na obranu
        if all_lead_to_mate and legal_moves:
            # Tady bychom ideálně měli vybrat tah, který maximalizuje počet tahů do matu
            # Pro jednoduchost vybereme první tah, ale v reálném enginu bychom zde 
            # implementovali důkladnější analýzu
            best_defensive_move = legal_moves[0]
            
            # Pokusíme se najít tah, který oddálí mat (pokud všechny vedou k matu)
            max_depth_to_mate = -1
            for move in legal_moves:
                make_move(move, board)
                
                # Zkusíme najít mat ve všech možných hloubkách menších než aktuální
                for d in range(1, depth):
                    mate_found, _ = is_mate_in_n_plies(board, d)
                    if mate_found:
                        if d > max_depth_to_mate:
                            max_depth_to_mate = d
                            best_defensive_move = move
                        break
                
                undo_move(board)
            
        return all_lead_to_mate, best_defensive_move

def find_best_defensive_move(board, legal_moves):
    """Najde nejlepší obranný tah pro stranu na tahu."""
    if not legal_moves:
        return None
    
    # Pro krále se snažíme maximalizovat vzdálenost k soupeřovu králi
    side = board.to_move
    king_pos = find_king(board, side)
    enemy_king_pos = find_king(board, 'b' if side == 'w' else 'w')
    
    if king_pos and enemy_king_pos:
        kr, kc = king_pos
        ekr, ekc = enemy_king_pos
        
        # Pro krále hledáme tah, který maximalizuje vzdálenost mezi králi
        best_move = legal_moves[0]
        max_distance = -1
        
        for move in legal_moves:
            r1, c1, r2, c2, _, _ = move
            
            # Pokud pohybujeme králem
            if board.grid[r1][c1].upper() == 'K' and (r1, c1) == king_pos:
                # Spočítejme vzdálenost po tahu
                distance = max(abs(r2 - ekr), abs(c2 - ekc))
                
                if distance > max_distance:
                    max_distance = distance
                    best_move = move
        
        return best_move
    
    # Pokud nemáme krále nebo jiný případ, vrátíme první legální tah
    return legal_moves[0]

def find_mate_sequence(board, max_plies=20):
    """Najde a vypíše posloupnost tahů vedoucí k matu."""
    global running, start_time, move_stack
    
    # Vyčistit zásobník
    move_stack = []
    
    # Spustit časovač
    running = True
    start_time = time.time()
    timer_thread = threading.Thread(target=time_reporter)
    timer_thread.daemon = True
    timer_thread.start()
    
    try:
        # Nejprve kontrola, zda je již mat
        side_to_move = board.to_move
        legal_moves = get_legal_moves(board, side_to_move)
        
        if not legal_moves:
            if is_in_check(board, side_to_move):
                print("\nPoziční analýza: Mat - " + 
                      ("černý vyhrává" if side_to_move == 'w' else "bílý vyhrává"))
                return
            else:
                print("\nPoziční analýza: Pat - remíza")
                return
        
        # Zkusíme najít mat v několika tazích
        print("\nHledám posloupnost tahů k matu...")
        print("\nProhledávám jednotlivé hloubky:")
        
        for plies in range(1, max_plies + 1):
            print(f"\n--- Hloubka {plies} půltahů ---")
            
            # Zkusíme najít mat v této hloubce
            is_mate, best_move = is_mate_in_n_plies(board, plies)
            
            if is_mate:
                print(f"\nNalezen mat v {plies} půltazích!")
                
                # Rekonstruujeme a vypisujeme sekvenci tahů k matu
                print("\nPosloupnost tahů k matu (s optimální obranou):")
                variant_board = board.copy()
                
                # Vypíšeme počáteční pozici
                print("\nVýchozí pozice:")
                print(variant_board.display())
                print(f"Na tahu je {'bílý' if variant_board.to_move == 'w' else 'černý'}")
                print("-" * 30)
                
                # Proveďme první tah
                move_notation = move_to_notation(best_move, variant_board)
                make_move(best_move, variant_board)
                print(f"1. {move_notation}")
                print(variant_board.display())
                print(f"Na tahu je {'bílý' if variant_board.to_move == 'w' else 'černý'}")
                print("-" * 30)
                
                # Pokud je již mat, končíme
                if not get_legal_moves(variant_board, variant_board.to_move) and is_in_check(variant_board, variant_board.to_move):
                    print("Mat!")
                    return
                
                # Nyní pokračujeme v rekonstrukci sekvence tahů
                curr_depth = plies - 1
                move_num = 2
                
                while curr_depth > 0:
                    # Najdeme nejlepší odpověď pro aktuální stranu na tahu
                    is_mat, next_move = is_mate_in_n_plies(variant_board, curr_depth)
                    
                    if next_move:
                        move_notation = move_to_notation(next_move, variant_board)
                        make_move(next_move, variant_board)
                        print(f"{move_num}. {move_notation}")
                        print(variant_board.display())
                        print(f"Na tahu je {'bílý' if variant_board.to_move == 'w' else 'černý'}")
                        print("-" * 30)
                        
                        # Kontrola, zda je již mat
                        if not get_legal_moves(variant_board, variant_board.to_move) and is_in_check(variant_board, variant_board.to_move):
                            print("Mat!")
                            return
                        
                        move_num += 1
                        curr_depth -= 1
                    else:
                        # Pokud nemáme další tah v sekvenci, najdeme nejlepší tah pro aktuální stranu
                        legal_moves = get_legal_moves(variant_board, variant_board.to_move)
                        if legal_moves:
                            # Vybereme nejlepší obranný tah
                            next_move = find_best_defensive_move(variant_board, legal_moves)
                            move_notation = move_to_notation(next_move, variant_board)
                            make_move(next_move, variant_board)
                            print(f"{move_num}. {move_notation}")
                            print(variant_board.display())
                            print(f"Na tahu je {'bílý' if variant_board.to_move == 'w' else 'černý'}")
                            print("-" * 30)
                            
                            move_num += 1
                            curr_depth -= 1
                        else:
                            break
                
                return
            else:
                # Pokud jsme nenašli mat v této hloubce, ukážeme posun hloubky simulací tahů
                # Vytvoříme kopii šachovnice pro simulaci
                sim_board = board.copy()
                # Pro sudé hloubky simulujeme tahy, abychom ukázali jinou pozici
                if plies > 1 and plies <= len(get_legal_moves(board, board.to_move)):
                    # Provedeme jeden tah pro ilustraci
                    sim_move = get_legal_moves(sim_board, sim_board.to_move)[0]
                    make_move(sim_move, sim_board)
                    print("Ukázka pozice po jednom tahu:")
                    print(sim_board.display())
                    print(f"Na tahu je {'bílý' if sim_board.to_move == 'w' else 'černý'}")
                else:
                    # Pokud nemůžeme simulovat, aspoň zobrazíme aktuální pozici
                    print("Aktuální pozice pro tuto hloubku:")
                    print(board.display())
                    print(f"Na tahu je {'bílý' if board.to_move == 'w' else 'černý'}")
        
        # Pokud nenajdeme mat, vypíšeme posloupnost tahů s nejlepšími tahy pro obě strany
        print("\nMat nebyl nalezen v hloubce do", max_plies, "půltahů.")
        print("\nPosloupnost nejlepších tahů (bez zaručeného matu):")
        
        legal_moves = get_legal_moves(board, board.to_move)
        
        if legal_moves:
            variant_board = board.copy()
            
            # Vypíšeme počáteční pozici
            print("\nVýchozí pozice:")
            print(variant_board.display())
            print(f"Na tahu je {'bílý' if variant_board.to_move == 'w' else 'černý'}")
            print("-" * 30)
            
            # Jednoduché vyhledávání: pokusit se najít tahy vedoucí k matu nebo materiálnímu zisku
            for i in range(10):  # Max 10 tahů
                legal_moves = get_legal_moves(variant_board, variant_board.to_move)
                if not legal_moves:
                    if is_in_check(variant_board, variant_board.to_move):
                        print("Mat!")
                    else:
                        print("Pat - remíza!")
                    break
                
                # Zkusíme najít mat v 1
                best_move = None
                for move in legal_moves:
                    make_move(move, variant_board)
                    if not get_legal_moves(variant_board, variant_board.to_move) and is_in_check(variant_board, variant_board.to_move):
                        best_move = move
                        break
                    undo_move(variant_board)
                
                if best_move:
                    print(f"{i+1}. {move_to_notation(best_move, board)} (mat)")
                    print(variant_board.display())
                    print(f"Na tahu je {'bílý' if variant_board.to_move == 'w' else 'černý'}")
                    print("-" * 30)
                    print("Mat!")
                    break
                
                # Nemáme mat, zkusíme najít braní figury
                best_move = None
                for move in legal_moves:
                    r1, c1, r2, c2, _, _ = move
                    if variant_board.grid[r2][c2] != '.':
                        best_move = move
                        make_move(move, variant_board)
                        print(f"{i+1}. {move_to_notation(move, board)} (braní)")
                        print(variant_board.display())
                        print(f"Na tahu je {'bílý' if variant_board.to_move == 'w' else 'černý'}")
                        print("-" * 30)
                        break
                
                if best_move:
                    continue
                
                # Žádné braní, vybereme tah, který maximalizuje vzdálenost králů
                best_move = find_best_defensive_move(variant_board, legal_moves)
                make_move(best_move, variant_board)
                print(f"{i+1}. {move_to_notation(best_move, board)}")
                print(variant_board.display())
                print(f"Na tahu je {'bílý' if variant_board.to_move == 'w' else 'černý'}")
                print("-" * 30)
    
    finally:
        # Ukončit časovač
        running = False
        if timer_thread.is_alive():
            timer_thread.join(timeout=1.0)
        print("")  # Nový řádek po časovém výpisu

def main():
    """Hlavní funkce programu."""
    # Několik zajímavých pozic pro testování
    standard_fen = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"  # Základní pozice
    
    # Pozice s Amazonkou (A/a) - kombinuje tahy dámy a jezdce
    amazon_fen = "8/6A1/8/8/8/k7/8/K7 w - - 0 1"  # Bílá Amazonka
    
    # Pozice s Cyrilo (C/c) - kombinuje tahy jezdce a střelce
    cyrilo_fen = "8/8/8/8/8/kq2K3/6C1/8 w - - 0 1"
    
    # Pozice s Eve (E/e) - kombinuje tahy jezdce a věže
    eve_fen = "8/8/8/8/8/k2E4/8/K7 w - - 0 1"
    
    # Mat Amazonkou v jednom tahu
    amazon_mate_fen = "k7/8/1K6/8/8/8/8/A7 w - - 0 1"
    
    # Bílý dá mat v 2
    mate_in_2_fen = "3k4/8/3K4/8/8/8/8/R7 w - - 0 1"
    
    # Pozice pro testování (můžete změnit na jinou z výše uvedených)
    test_fen = amazon_mate_fen
    
    test_fen = "6k1/8/5a2/3K4/8/8/8/3B4 w - - 0 1"
    
    print("Šachový engine pro hledání matových sekvencí")
    print("============================================")
    
    # Načtení pozice
    board = Board(test_fen)
    print("\nPočáteční pozice:")
    print(board.display())
    print(f"Na tahu je {'bílý' if board.to_move == 'w' else 'černý'}")
    
    # Najít sekvenci tahů k matu
    find_mate_sequence(board, max_plies=10)

if __name__ == "__main__":
    main()