brief OK

import time
from copy import deepcopy

directions = {
    'K': [(1,0), (0,1), (-1,0), (0,-1), (1,1), (-1,-1), (1,-1), (-1,1)],
    'Q': [(1,0), (0,1), (-1,0), (0,-1), (1,1), (-1,-1), (1,-1), (-1,1)],
    'R': [(1,0), (0,1), (-1,0), (0,-1)],
    'B': [(1,1), (-1,-1), (1,-1), (-1,1)],
    'N': [(2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)],
    'P': [(1,1), (-1,1)],
    'p': [(1,-1), (-1,-1)],
    'A': [],
    'C': [],
    'E': [],
}

def in_bounds(x,y):
    return 0 <= x < 8 and 0 <= y < 8

class Board:
    def __init__(self, grid, turn):
        self.grid = grid
        self.turn = turn

    def copy(self):
        return Board(deepcopy(self.grid), self.turn)

    def is_white(self, p):
        return p.isupper()

    def is_black(self, p):
        return p.islower()

    def enemy_color(self):
        return 'b' if self.turn == 'w' else 'w'

    def get_king_pos(self, color):
        king_char = 'K' if color == 'w' else 'k'
        for y in range(8):
            for x in range(8):
                if self.grid[y][x] == king_char:
                    return (x,y)
        return None

    def under_attack(self, x, y, color):
        enemy = 'b' if color == 'w' else 'w'
        enemy_pieces = []
        for yy in range(8):
            for xx in range(8):
                p = self.grid[yy][xx]
                if p and ((enemy == 'w' and p.isupper()) or (enemy == 'b' and p.islower())):
                    enemy_pieces.append( (p, xx, yy) )
        for (p, ex, ey) in enemy_pieces:
            if self.attacks_square(ex, ey, x, y, p):
                return True
        return False

    def attacks_square(self, sx, sy, tx, ty, piece):
        c = piece.upper()
        dx = tx - sx
        dy = ty - sy

        def sign(n): return (n > 0) - (n < 0)

        if c == 'P':
            if piece.isupper():
                return (dx, dy) in [(1, -1), (-1, -1)]
            else:
                return (dx, dy) in [(1, 1), (-1, 1)]

        elif c == 'N':
            return (abs(dx), abs(dy)) in [(2,1), (1,2)]

        elif c == 'K':
            return max(abs(dx), abs(dy)) == 1

        elif c in ['B', 'Q', 'A', 'E']:
            if abs(dx) == abs(dy) and dx != 0:
                stepx = sign(dx)
                stepy = sign(dy)
                x = sx + stepx
                y = sy + stepy
                while (x, y) != (tx, ty):
                    if self.grid[y][x] is not None:
                        return False
                    x += stepx
                    y += stepy
                return True

        if c in ['R', 'Q', 'C', 'E']:
            if (dx == 0 and dy != 0) or (dy == 0 and dx != 0):
                stepx = sign(dx)
                stepy = sign(dy)
                x = sx + stepx
                y = sy + stepy
                while (x, y) != (tx, ty):
                    if self.grid[y][x] is not None:
                        return False
                    x += stepx
                    y += stepy
                return True

        if c in ['A','C','E']:
            knight_jumps = [(2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)]
            if (dx, dy) in knight_jumps:
                return True

        return False

    def generate_moves(self):
        moves = []
        for y in range(8):
            for x in range(8):
                p = self.grid[y][x]
                if p is None:
                    continue
                if (self.turn == 'w' and p.isupper()) or (self.turn == 'b' and p.islower()):
                    moves.extend(self.piece_moves(x, y, p))
        return moves

    def piece_moves(self, x, y, p):
        moves = []
        c = p.upper()

        def add_move_if_valid(nx, ny):
            if not in_bounds(nx, ny):
                return False
            target = self.grid[ny][nx]
            if target is None or (self.turn == 'w' and target.islower()) or (self.turn == 'b' and target.isupper()):
                moves.append((x, y, nx, ny))
                return target is None
            return False

        if c == 'P':
            forward = -1 if p.isupper() else 1
            start_row = 6 if p.isupper() else 1

            if in_bounds(x, y + forward) and self.grid[y + forward][x] is None:
                moves.append((x, y, x, y + forward))
                if y == start_row and self.grid[y + 2 * forward][x] is None:
                    moves.append((x, y, x, y + 2 * forward))
            for dx in [-1, 1]:
                nx, ny = x + dx, y + forward
                if in_bounds(nx, ny):
                    target = self.grid[ny][nx]
                    if target and ((p.isupper() and target.islower()) or (p.islower() and target.isupper())):
                        moves.append((x, y, nx, ny))

        else:
            knight_moves = [(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)]
            if c in ['N','A','C','E']:
                for dx, dy in knight_moves:
                    nx, ny = x + dx, y + dy
                    if in_bounds(nx, ny):
                        target = self.grid[ny][nx]
                        if target is None or (self.turn == 'w' and target.islower()) or (self.turn == 'b' and target.isupper()):
                            moves.append((x, y, nx, ny))

            if c in ['R','Q','C','E']:
                for dx, dy in [(1,0),(0,1),(-1,0),(0,-1)]:
                    nx, ny = x + dx, y + dy
                    while in_bounds(nx, ny):
                        target = self.grid[ny][nx]
                        if target is None:
                            moves.append((x, y, nx, ny))
                        else:
                            if (self.turn == 'w' and target.islower()) or (self.turn == 'b' and target.isupper()):
                                moves.append((x, y, nx, ny))
                            break
                        nx += dx
                        ny += dy

            if c in ['B','Q','A','E']:
                for dx, dy in [(1,1),(1,-1),(-1,1),(-1,-1)]:
                    nx, ny = x + dx, y + dy
                    while in_bounds(nx, ny):
                        target = self.grid[ny][nx]
                        if target is None:
                            moves.append((x, y, nx, ny))
                        else:
                            if (self.turn == 'w' and target.islower()) or (self.turn == 'b' and target.isupper()):
                                moves.append((x, y, nx, ny))
                            break
                        nx += dx
                        ny += dy

            if c == 'K':
                for dx, dy in directions['K']:
                    nx, ny = x + dx, y + dy
                    if in_bounds(nx, ny):
                        target = self.grid[ny][nx]
                        if target is None or (self.turn == 'w' and target.islower()) or (self.turn == 'b' and target.isupper()):
                            moves.append((x, y, nx, ny))

        return moves

    def move(self, x1, y1, x2, y2):
        b = self.copy()
        b.grid[y2][x2] = b.grid[y1][x1]
        b.grid[y1][x1] = None
        b.turn = 'b' if self.turn == 'w' else 'w'
        return b

    def is_in_check(self, color):
        king_pos = self.get_king_pos(color)
        if king_pos is None:
            return True
        xk, yk = king_pos
        return self.under_attack(xk, yk, color)

    def is_checkmate(self):
        if not self.is_in_check(self.turn):
            return False
        for move in self.generate_moves():
            new_board = self.move(*move)
            if not new_board.is_in_check(self.turn):
                return False
        return True

    def is_stalemate(self):
        if self.is_in_check(self.turn):
            return False
        for move in self.generate_moves():
            new_board = self.move(*move)
            if not new_board.is_in_check(self.turn):
                return False
        return True

    def fen(self):
        rows = []
        for y in range(8):
            row = ''
            empty = 0
            for x in range(8):
                p = self.grid[y][x]
                if p is None:
                    empty += 1
                else:
                    if empty > 0:
                        row += str(empty)
                        empty = 0
                    row += p
            if empty > 0:
                row += str(empty)
            rows.append(row)
        fen_str = '/'.join(rows)
        fen_str += ' ' + self.turn + ' - - 0 1'
        return fen_str

    def ascii(self):
        lines = []
        for y in range(8):
            line = ''
            for x in range(8):
                p = self.grid[y][x]
                if p is None:
                    line += '.'
                else:
                    if p.upper() == 'K':
                        line += 'K' if p.isupper() else 'k'
                    else:
                        line += p
            lines.append(line)
        return '\n'.join(lines)

def parse_fen(fen):
    parts = fen.split()
    board_part = parts[0]
    turn = parts[1]
    rows = board_part.split('/')
    grid = []
    for r in rows:
        row = []
        for ch in r:
            if ch.isdigit():
                for _ in range(int(ch)):
                    row.append(None)
            else:
                row.append(ch)
        grid.append(row)
    return grid, turn

def minimax(board, depth, max_depth, printed_depths, path=[]):
    if depth == 0 or board.is_checkmate() or board.is_stalemate():
        # Konec větve, mat nebo pat nebo dosažení hloubky
        if board.is_checkmate():
            if board.turn == 'w':
                return -1, path
            else:
                return 1, path
        if board.is_stalemate():
            return 0, path
        return 0, path

    best_score = -float('inf') if board.turn == 'w' else float('inf')
    best_path = None

    moves = board.generate_moves()
    legal_moves = []
    for m in moves:
        new_board = board.move(*m)
        if not new_board.is_in_check(board.turn):
            legal_moves.append(m)

    if not legal_moves:
        # Žádné legální tahy
        if board.is_in_check(board.turn):
            # Mat
            return (-1 if board.turn == 'w' else 1), path
        else:
            # Pat
            return 0, path

    for m in legal_moves:
        new_board = board.move(*m)
        score, p = minimax(new_board, depth-1, max_depth, printed_depths, path + [new_board])
        if board.turn == 'w':
            if score > best_score:
                best_score = score
                best_path = p
        else:
            if score < best_score:
                best_score = score
                best_path = p

    current_depth = max_depth - depth + 1
    if current_depth not in printed_depths:
        print(f"[{time.strftime('%H:%M:%S')}] Dokončena hloubka: {current_depth}")
        printed_depths.add(current_depth)

    return best_score, best_path

# --- Hlavní program ---

fen = "8/8/4A3/8/6k1/8/8/6K1 b - - 0 1"
grid, turn = parse_fen(fen)
board = Board(grid, turn)

depth = 7
max_depth = depth
printed_depths = set()

score, path = minimax(board, depth, max_depth, printed_depths, [board])

if score == 1:
    print("Bílý vyhrává (mat):\n")
elif score == -1:
    print("Černý vyhrává (mat):\n")
else:
    print("Remíza (pat nebo nedosažený mat):\n")

for b in path:
    print(b.ascii())
    print(b.fen())
    print("-" * 20)