excellent 44

import time
from datetime import datetime
from collections import deque
import copy

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

class ChessBoard:
    """Vlastní implementace šachovnice pro pohádkové figury"""

    def __init__(self, fen=None):
        self.board = [[None for _ in range(8)] for _ in range(8)]
        self.turn = True  # True = bílý, False = černý
        self.castling_rights = {'K': True, 'Q': True, 'k': True, 'q': True}
        self.en_passant = None
        self.halfmove_clock = 0
        self.fullmove_number = 1

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

    def __str__(self):
        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):
                    # Opraveno: tuple je (color, piece_type)
                    color, symbol = piece
                    safe_row.append(symbol.upper() if color == 'w' else symbol.lower())
                else:
                    # už je string, rovnou přidej
                    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):
        """Nastaví základní pozici"""
        # Bílé figury
        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')

        # Černé figury - opraveno
        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):
        """Nastaví pozici z FEN stringu"""
        parts = fen_string.split()

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

        # Na tahu
        self.turn = 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čítadla 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 get_fen(self):
        """Vrátí FEN string pozice"""
        # Pozice figur
        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)

        # Na tahu
        turn = 'w' if self.turn else 'b'

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

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

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

    def copy(self):
        """Vytvoří kopii šachovnice"""
        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
        return new_board

    def make_move(self, from_pos, to_pos):
        """Provede tah"""
        from_rank, from_file = from_pos
        to_rank, to_file = to_pos

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

        # Změnit hráče na tahu
        self.turn = not self.turn

        # Inkrementovat počítadla
        if self.turn:  # Pokud je nyní na tahu bílý, znamená to že černý právě táhl
            self.fullmove_number += 1
        self.halfmove_clock += 1

    def find_king(self, color):
        """Najde krále dané barvy"""
        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):
        """Kontroluje zda je král v šachu"""
        king_pos = self.find_king(color)
        if not king_pos:
            return False

        # Kontrola útoku od protivníka
        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 attacks_square(self, from_pos, to_pos):
        """Kontroluje zda figura útočí na dané pole"""
        rank, file = from_pos
        piece = self.board[rank][file]

        if not piece:
            return False

        color, piece_type = piece

        # Získat možné útoky podle typu figury
        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':  # Amazonka (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):
        """Kontroluje útok pěšce"""
        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):
        """Kontroluje útok jezdce"""
        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):
        """Kontroluje útok věže"""
        from_rank, from_file = from_pos
        to_rank, to_file = to_pos

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

        # Kontrola zda není blokováno
        if from_rank == to_rank:  # Horizontální
            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:  # Vertikální
            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):
        """Kontroluje útok střelce"""
        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

        # Kontrola zda není blokováno
        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):
        """Kontroluje útok dámy"""
        return self.rook_attacks(from_pos, to_pos) or self.bishop_attacks(from_pos, to_pos)

    def king_attacks(self, from_pos, to_pos):
        """Kontroluje útok krále"""
        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 FairyChessAnalyzer:
    def __init__(self, start_fen):
        self.start_fen = start_fen
        self.L = []
        self.fen_to_index = {}
        self.iteration_count = 0

    def print_time(self, message=""):
        """Vypíše čas ve formátu %hh%mm%ss"""
        now = datetime.now()
        time_str = now.strftime("%H:%M:%S")
        print(f"[{time_str}] Průchod {self.iteration_count}: {message}")

    def is_fairy_piece(self, piece_type):
        """Kontroluje zda je figura pohádková"""
        return piece_type in ['A', 'C', 'E']

    def generate_moves(self, board, from_pos):
        """Generuje všechny možné tahy z dané pozice"""
        rank, file = from_pos
        piece = board.board[rank][file]

        if not piece:
            return []

        color, piece_type = piece
        moves = []

        # Kontrola zda je figura na tahu
        if (color == 'w') != board.turn:
            return []

        if piece_type == 'P':
            moves = self.generate_pawn_moves(board, from_pos)
        elif piece_type == 'R':
            moves = self.generate_rook_moves(board, from_pos)
        elif piece_type == 'N':
            moves = self.generate_knight_moves(board, from_pos)
        elif piece_type == 'B':
            moves = self.generate_bishop_moves(board, from_pos)
        elif piece_type == 'Q':
            moves = self.generate_queen_moves(board, from_pos)
        elif piece_type == 'K':
            moves = self.generate_king_moves(board, from_pos)
        elif piece_type == 'A':  # Amazonka (Q+N)
            moves = self.generate_queen_moves(board, from_pos) + self.generate_knight_moves(board, from_pos)
        elif piece_type == 'C':  # Cyril (R+N)
            moves = self.generate_rook_moves(board, from_pos) + self.generate_knight_moves(board, from_pos)
        elif piece_type == 'E':  # Eve (B+N)
            moves = self.generate_bishop_moves(board, from_pos) + self.generate_knight_moves(board, from_pos)

        # Filtrovat legální tahy (král nesmí být v šachu)
        legal_moves = []
        for move in moves:
            if self.is_move_legal(board, from_pos, move):
                legal_moves.append(move)

        return legal_moves

    def generate_pawn_moves(self, board, from_pos):
        """Generuje tahy pěšce"""
        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

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

            # Dvojitý tah z výchozí pozice
            if rank == start_rank and board.board[new_rank + direction][file] is None:
                moves.append((new_rank + direction, file))

        # Braní
        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):
        """Generuje tahy jezdce"""
        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):
        """Generuje tahy pro posuvné figury"""
        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_rook_moves(self, board, from_pos):
        """Generuje tahy věže"""
        directions = [(0,1), (0,-1), (1,0), (-1,0)]
        return self.generate_sliding_moves(board, from_pos, directions)

    def generate_bishop_moves(self, board, from_pos):
        """Generuje tahy střelce"""
        directions = [(1,1), (1,-1), (-1,1), (-1,-1)]
        return self.generate_sliding_moves(board, from_pos, directions)

    def generate_queen_moves(self, board, from_pos):
        """Generuje tahy dámy"""
        directions = [(0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)]
        return self.generate_sliding_moves(board, from_pos, directions)

    def generate_king_moves(self, board, from_pos):
        """Generuje tahy krále"""
        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 generate_pawn_attacks(self, board, from_pos):
        """Generuje útoky pěšce (bez pohybu dopředu)"""
        rank, file = from_pos
        piece = board.board[rank][file]
        color = piece[0]
        moves = []

        direction = 1 if color == 'w' else -1
        new_rank = rank + direction

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

        return moves

    def is_move_legal(self, board, from_pos, to_pos):
        """Kontroluje zda je tah legální"""
        # Simulace tahu
        temp_board = board.copy()
        temp_board.make_move(from_pos, to_pos)

        # Kontrola zda vlastní král není v šachu
        color = 'w' if board.turn else 'b'
        return not temp_board.is_check(color)

    def get_all_legal_moves(self, board):
        """Získá všechny legální tahy"""
        moves = []

        for rank in range(8):
            for file in range(8):
                piece = board.board[rank][file]
                if piece:
                    color = piece[0]
                    if (color == 'w') == board.turn:
                        piece_moves = self.generate_moves(board, (rank, file))
                        for to_pos in piece_moves:
                            moves.append((rank, file, to_pos[0], to_pos[1]))

        return moves

    def create_position_dict(self, fen, radek):
        """Vytvoří slovník pro pozici"""
        board = ChessBoard(fen)

        to_mate = None
        to_end = None

        # Získat všechny legální tahy
        legal_moves = self.get_all_legal_moves(board)

        # Kontrola koncových pozic
        if len(legal_moves) == 0:
            color = 'w' if board.turn else 'b'
            if board.is_check(color):
                # Mat
                to_mate = 0
                to_end = 0
            else:
                # Pat
                to_mate = None
                to_end = 0

        return {
            'radek': radek,
            'N': [],
            'P': [],
            'FEN': board.get_fen(),
            'board': board,
            'to_mate': to_mate,
            'to_end': to_end
        }

    def build_position_tree(self, max_depth=5):
        """Postaví strom pozic pomocí BFS"""
        self.iteration_count += 1
        self.print_time("Začátek generování stromu pozic")

        # Inicializace
        start_dict = self.create_position_dict(self.start_fen, 0)
        self.L.append(start_dict)
        self.fen_to_index[start_dict['FEN']] = 0

        queue = deque([0])

        for depth in range(max_depth):
            self.iteration_count += 1

            if not queue:
                break

            level_size = len(queue)
            self.print_time(f"Hloubka {depth}, pozic: {level_size}")

            for _ in range(level_size):
                if not queue:
                    break

                current_index = queue.popleft()
                current_pos = self.L[current_index]

                # Přeskočit koncové pozice
                if current_pos['to_end'] is not None:
                    continue

                try:
                    # Získat všechny legální tahy
                    legal_moves = self.get_all_legal_moves(current_pos['board'])

                    for move in legal_moves:
                        from_rank, from_file, to_rank, to_file = move

                        # Vytvořit novou pozici
                        temp_board = current_pos['board'].copy()
                        temp_board.make_move((from_rank, from_file), (to_rank, to_file))
                        new_fen = temp_board.get_fen()

                        if new_fen not in self.fen_to_index:
                            # Nová pozice
                            new_dict = self.create_position_dict(new_fen, depth + 1)
                            new_index = len(self.L)
                            self.L.append(new_dict)
                            self.fen_to_index[new_fen] = new_index
                            queue.append(new_index)
                        else:
                            new_index = self.fen_to_index[new_fen]

                        # Přidat vazby
                        if new_index not in current_pos['N']:
                            current_pos['N'].append(new_index)
                        if current_index not in self.L[new_index]['P']:
                            self.L[new_index]['P'].append(current_index)

                except Exception as e:
                    self.print_time(f"Chyba při generování tahů: {e}")
                    continue

        self.print_time(f"Strom postaven, celkem pozic: {len(self.L)}")

    def evaluate_positions(self):
        """Ohodnotí všechny pozice pomocí minimax"""
        self.iteration_count += 1
        self.print_time("Začátek ohodnocování pozic")

        for iteration in range(50):
            self.iteration_count += 1

            if iteration % 10 == 0:
                self.print_time(f"Iterace ohodnocování {iteration}")

            changed = False

            # Procházet od nejhlubších pozic
            for i in reversed(range(len(self.L))):
                pos = self.L[i]

                # Přeskočit už ohodnocené
                if pos['to_mate'] is not None:
                    continue

                # Koncové pozice bez tahů
                if not pos['N']:
                    pos['to_mate'] = None
                    pos['to_end'] = 0
                    changed = True
                    continue

                # Kontrola zda jsou všichni následníci ohodnoceni
                successor_values = []
                all_evaluated = True

                for succ_idx in pos['N']:
                    if succ_idx < len(self.L):
                        succ = self.L[succ_idx]
                        if succ['to_mate'] is not None:
                            successor_values.append(succ['to_mate'])
                        elif succ['to_end'] == 0:
                            successor_values.append(None)
                        else:
                            all_evaluated = False
                            break

                if all_evaluated and successor_values:
                    # Minimax
                    numeric_values = [v for v in successor_values if v is not None]

                    if not numeric_values:
                        pos['to_mate'] = None
                    else:
                        if pos['board'].turn:  # Bílý minimalizuje
                            pos['to_mate'] = 1 + min(numeric_values)
                        else:  # Černý maximalizuje
                            pos['to_mate'] = 1 + max(numeric_values)

                    pos['to_end'] = pos['to_mate'] if pos['to_mate'] is not None else 0
                    changed = True

            if not changed:
                break

        self.print_time("Ohodnocování dokončeno")

    def find_optimal_path(self, start_index=0):
        """Najde optimální cestu z dané pozice"""
        path = []
        current_idx = start_index
        visited = set()

        while current_idx not in visited and current_idx < len(self.L):
            visited.add(current_idx)
            current_pos = self.L[current_idx]
            path.append(current_idx)

            if not current_pos['N'] or current_pos['to_end'] == 0:
                break

            # Najít nejlepší tah
            best_idx = None
            best_value = None

            for succ_idx in current_pos['N']:
                if succ_idx < len(self.L):
                    succ = self.L[succ_idx]
                    value = succ['to_mate']

                    if value is not None:
                        if best_value is None:
                            best_value = value
                            best_idx = succ_idx
                        else:
                            if current_pos['board'].turn:  # Bílý minimalizuje
                                if value < best_value:
                                    best_value = value
                                    best_idx = succ_idx
                            else:  # Černý maximalizuje
                                if value > best_value:
                                    best_value = value
                                    best_idx = succ_idx

            if best_idx is None:
                break

            current_idx = best_idx

        return path

    def analyze(self, max_depth=4):
        """Hlavní analýza"""
        start_time = time.time()
        self.iteration_count += 1
        self.print_time("Začátek analýzy")

        try:
            # Postavit strom
            self.build_position_tree(max_depth)

            # Ohodnotit pozice
            self.evaluate_positions()

            # Najít optimální cestu
            optimal_path = self.find_optimal_path()

            end_time = time.time()
            self.iteration_count += 1
            self.print_time(f"Analýza dokončena za {end_time - start_time:.2f} sekund")

            # Výsledky
            print(f"\nCelkem pozic: {len(self.L)}")
            print(f"Optimální cesta má {len(optimal_path)} tahů")

            if len(self.L) > 22:
                pos_22 = self.L[22]
                print(f"\nL[22]: {pos_22}")

            print(f"\nOptimální cesta (prvních 10 tahů):")
            for i, pos_idx in enumerate(optimal_path[:10]):
                if pos_idx < len(self.L):
                    pos = self.L[pos_idx]
                    turn = "Bílý" if pos['board'].turn else "Černý"
                    print(f"Tah {i} ({turn}): to_mate={pos['to_mate']}, FEN={pos['FEN'][:50]}...")
                    print_board(pos['board'])

            return optimal_path

        except Exception as e:
            self.iteration_count += 1
            self.print_time(f"Chyba při analýze: {e}")
            import traceback
            traceback.print_exc()
            return []

# Testování
if __name__ == "__main__":
    # Testovací pozice

    # 1. Jednoduchá matová pozice (mat v 1 tahu)
    simple_mate = "7k/4A3/8/7K/8/8/8/8 w - - 0 1"

    # 2. Pozice s delším matem
    longer_mate = "8/6K1/3b4/4n1k1/8/8/8/8 w - - 0 1"

    # 3. Weak Amazon
    weak_amaz = "8/6k1/1A6/8/3K4/8/8/8 w - - 0 1"

    # Výběr pozice pro testování
    test_positions = {
        1: ("Jednoduchý mat", simple_mate),
        2: ("Delší mat", longer_mate),
        3: ("Weak Amazon", weak_amaz)
    }

    print("Dostupné testovací pozice:")
    for num, (name, fen) in test_positions.items():
        print(f"{num}. {name}: {fen}")

    # Použijeme pozici 1 (jednoduchý mat) pro analýzu
    selected_pos = 1
    name, start_fen = test_positions[selected_pos]

    print(f"\nTestování šachové analýzy s pohádkovými figurami...")
    print(f"Vybraná pozice: {name}")
    print(f"FEN: {start_fen}")
    print("Pohádkové figury: A=Amazonka(Q+N), C=Cyril(R+N), E=Eve(B+N)")
    print("="*60)

    analyzer = FairyChessAnalyzer(start_fen)
    optimal_path = analyzer.analyze(max_depth=12)

    print(f"\nFINÁLNÍ VÝSLEDEK:")
    print(f"Pozic: {len(analyzer.L)}")
    print(f"Optimální cesta: {len(optimal_path)} tahů")

    if len(optimal_path) > 1:
        start_pos = analyzer.L[0]
        if start_pos['to_mate'] is not None:
            print(f"Mat v {start_pos['to_mate']} tazích")
        else:
            print("Pozice vede k remíze")
    else:
        print("Koncová pozice nebo chyba v analýze")