QUITE GOOD!

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

# Reprezentace stran: 'w' = bílý, 'b' = černý.
# Šachovnice se reprezentuje jako 8x8 pole znaků (řádek 0 odpovídá 8. řadě).

###############################################################################
# Třída Board – reprezentuje šachovnici a umí ji inicializovat z FEN řetězce.
###############################################################################

class Board:
    def __init__(self, fen=None):
        """Inicializace šachovnice; pokud je zadán FEN, nastaví pozici podle něj."""
        self.grid = [[' ' for _ in range(8)] for _ in range(8)]
        self.to_move = 'w'
        self.castling_rights = set()  # např. {'K','Q','k','q'}
        self.en_passant = None       # (row, col) nebo 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('/')
        # FEN řady začínají od horní (8.) a jdou dolů
        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)

###############################################################################
# Funkce pro detekci šachu, generování tahů a jejich provádění
###############################################################################

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_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'
    # Útoky pěšcem
    if side=='w':
        if kr+1 < 8 and kc-1 >= 0 and board.grid[kr+1][kc-1] == 'p': return True
        if kr+1 < 8 and kc+1 < 8 and board.grid[kr+1][kc+1] == 'p': return True
    else:
        if kr-1 >= 0 and kc-1 >= 0 and board.grid[kr-1][kc-1] == 'P': return True
        if kr-1 >= 0 and kc+1 < 8 and board.grid[kr-1][kc+1] == 'P': return True
    # Útoky jezdcem a dalšími s jezdcovým pohybem (N, A, C, E)
    knight_moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
    enemy_knights = ['n','a','c','e'] if enemy_side=='b' else ['N','A','C','E']
    for dr, dc in knight_moves:
        r, c = kr+dr, kc+dc
        if 0<=r<8 and 0<=c<8 and board.grid[r][c] in enemy_knights:
            return True
    # Útoky po řadách a sloupcích (R, Q, E, A)
    enemy_rook_like = ['r','q','e','a'] if enemy_side=='b' else ['R','Q','E','A']
    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
        r, c = kr+dr, kc+dc
        while 0<=r<8 and 0<=c<8:
            if board.grid[r][c] != '.':
                if board.grid[r][c] in enemy_rook_like:
                    return True
                break
            r += dr; c += dc
    # Útoky diagonálně (B, Q, C, A)
    enemy_bishop_like = ['b','q','c','a'] if enemy_side=='b' else ['B','Q','C','A']
    for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
        r, c = kr+dr, kc+dc
        while 0<=r<8 and 0<=c<8:
            if board.grid[r][c] != '.':
                if board.grid[r][c] in enemy_bishop_like:
                    return True
                break
            r += dr; c += dc
    # Sousední král
    enemy_king = 'k' if enemy_side=='b' else 'K'
    for dr in [-1,0,1]:
        for dc in [-1,0,1]:
            if dr==0 and dc==0: continue
            r, c = kr+dr, kc+dc
            if 0<=r<8 and 0<=c<8 and board.grid[r][c] == enemy_king:
                return True
    return False

def generate_pseudo_moves(board, side):
    """Generuje všechny pseudolegální tahy pro stranu side ('w' nebo 'b')."""
    moves = []
    enemy = 'b' if side=='w' else 'w'
    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 (základní verze – detailní bezpečnostní kontroly se provádí při provádění tahu)
                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
                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

# Zásobník pro tahy (pro možnost undo)
move_stack = []

def make_move(move, board):
    """Provede tah na šachovnici a uloží potřebné informace pro undo.
       move: (r1, c1, r2, c2, promo, special)"""
    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)
    move_stack.append((r1, c1, r2, c2, promo, special, piece, captured, prev_state))
    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
    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')
    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."""
    r1, c1, r2, c2, promo, special, piece, captured, prev_state = move_stack.pop()
    board.grid[r1][c1] = piece
    board.grid[r2][c2] = captured
    board.castling_rights, board.en_passant = prev_state
    board.to_move = 'b' if board.to_move=='w' else 'w'

###############################################################################
# Negamax s alfa-beta ořezáváním
###############################################################################

def negamax(board, depth, alpha, beta, side):
    """Negamax s alfa-beta ořezáváním. side: 1 pokud hledáme z pohledu bílé, -1 pro černé.
       Vrací (hodnota, tahová sekvence)."""
    moves = generate_pseudo_moves(board, 'w' if side==1 else 'b')
    if not moves:
        return ((-inf if is_in_check(board, 'w' if side==1 else 'b') else 0), [])
    if depth == 0:
        return (0, [])
    best_val = -inf
    best_line = []
    for move in moves:
        make_move(move, board)
        if is_in_check(board, 'w' if side==1 else 'b'):
            undo_move(board)
            continue
        val, line = negamax(board, depth-1, -beta, -alpha, -side)
        val = -val
        undo_move(board)
        if val > best_val:
            best_val = val
            best_line = [move] + line
        alpha = max(alpha, best_val)
        if alpha >= beta:
            break
    return best_val, best_line

###############################################################################
# Iterativní prohlubování – hledáme do maximální hloubky a vypisujeme uplynulý čas
###############################################################################

def iterative_deepening(board, max_depth=50):
    best_line = []
    best_val = 0
    start_time = time.time()
    for depth in range(1, max_depth+1):
        t0 = time.time()
        val, line = negamax(board, depth, -inf, inf, 1 if board.to_move=='w' else -1)
        t1 = time.time()
        elapsed = time.time() - start_time
        hrs = int(elapsed // 3600)
        mins = int((elapsed % 3600) // 60)
        secs = int(elapsed % 60)
        print(f"Hloubka {depth:2d} – uplynulý čas: {hrs:02d}h {mins:02d}m {secs:02d}s")
        best_val = val
        best_line = line
        if val == inf or val == -inf:
            break
    total_elapsed = time.time() - start_time
    return best_val, best_line, total_elapsed

###############################################################################
# Převod tahu do šachové notace
###############################################################################

def move_to_notation(move):
    cols = "abcdefgh"
    r1, c1, r2, c2, promo, special = move
    if special == 'castle':
        return "O-O" if c2 > c1 else "O-O-O"
    s = cols[c1] + str(8 - r1) + cols[c2] + str(8 - r2)
    if promo:
        s += "=" + promo.upper()
    if special == 'enpassant':
        s += " e.p."
    return s

###############################################################################
# Hlavní program – inicializace z FEN a výpis optimální tahové sekvence
###############################################################################

def main():
    # Nastavíme pozici ze zadaného FEN (např.: "8/6A1/8/8/8/k1K5/8/8 w - - 0 1")
    fen = "8/6A1/8/8/8/k1K5/8/8 w - - 0 1"
    board_obj = Board(fen)
    board = board_obj.copy()

    print("Počáteční pozice:")
    print(board.display())
    print("\nVyhledávání optimální tahové sekvence – iterativní prohlubování...\n")

    best_val, best_line, total_elapsed = iterative_deepening(board, max_depth=50)
    hrs = int(total_elapsed // 3600)
    mins = int((total_elapsed % 3600) // 60)
    secs = int(total_elapsed % 60)

    # Postupné provádění tahů a výpis pozic
    variant_board = board.copy()
    moves_notation = []
    print("Postup tahů:")
    print("-"*40)
    print("Start:")
    print(variant_board.display())
    print("-"*40)
    for move in best_line:
        s = move_to_notation(move)
        moves_notation.append(s)
        make_move(move, variant_board)
        print("Tah:", s)
        print(variant_board.display())
        print("-"*40)

    if best_val == inf:
        result_text = "Mat – bílý vyhrává"
    elif best_val == -inf:
        result_text = "Mat – černý vyhrává"
    else:
        # Zkontrolujeme, zda tahy vedou k patu
        side_to_move = 'b' if board.to_move=='w' else 'w'
        if not generate_pseudo_moves(variant_board, side_to_move) and not is_in_check(variant_board, side_to_move):
            result_text = "Pat (remíza)"
        else:
            result_text = "Remíza"
    print("Optimální tahová sekvence:", " ".join(moves_notation) if moves_notation else "(žádný tah)")
    print("Výsledek:", result_text)
    print(f"Celkový uplynulý čas: {hrs:02d}h {mins:02d}m {secs:02d}s")

if __name__ == '__main__':
    main()