---

import copy
from typing import List, Tuple, Optional

BOARD_SIZE = 8
WIN_SCORE = 100000

def convert_site_board_to_engine(raw_board: List[List[int]]) -> List[List[Optional[dict]]]:
    """Преобразует матрицу цифр с сайта в формат для движка."""
    engine_board = []
    for r in range(BOARD_SIZE):
        row = []
        for c in range(BOARD_SIZE):
            cell = raw_board[r][c]
            if cell == 1:
                row.append({'player': 'black', 'type': 'man'})
            elif cell == 2:
                row.append({'player': 'black', 'type': 'king'})
            elif cell == 3:
                row.append({'player': 'white', 'type': 'man'})
            elif cell == 4:
                row.append({'player': 'white', 'type': 'king'})
            else:
                row.append(None)
        engine_board.append(row)
    return engine_board

def move_to_text(move: dict) -> str:
    """Переводит путь хода в формат 'A3 -> C5 -> E7'."""
    cols = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
    path_strs = [f"{cols[c]}{r + 1}" for r, c in move['path']]
    
    separator = " бьет " if move['is_capture'] else " -> "
    return separator.join(path_strs)

def evaluate_board(board: List[List[Optional[dict]]]) -> int:
    score = 0
    for r in range(BOARD_SIZE):
        for c in range(BOARD_SIZE):
            piece = board[r][c]
            if not piece:
                continue

            val = 300 if piece['type'] == 'king' else 100

            if piece['type'] == 'man':
                advancement = (7 - r) if piece['player'] == 'white' else r
                val += advancement * 5

            if 2 <= r <= 5 and 2 <= c <= 5:
                val += 10

            if piece['player'] == 'white':
                score += val
            else:
                score -= val

    return score

def get_valid_moves(board: List[List[Optional[dict]]], player: str) -> List[dict]:
    captures = []
    quiet_moves = []

    for r in range(BOARD_SIZE):
        for c in range(BOARD_SIZE):
            piece = board[r][c]
            if not piece or piece['player'] != player:
                continue

            piece_captures = _find_captures_for_piece(board, r, c, piece)
            captures.extend(piece_captures)

            if not captures:
                piece_quiets = _find_quiet_moves_for_piece(board, r, c, piece)
                quiet_moves.extend(piece_quiets)

    # Правило обязательного максимального взятия (Русские шашки)
    if captures:
        max_captured_count = max(len(m['captured']) for m in captures)
        return [m for m in captures if len(m['captured']) == max_captured_count]

    return quiet_moves

def _find_quiet_moves_for_piece(board, r: int, c: int, piece: dict) -> List[dict]:
    moves = []
    # Диагонали для шашек
    dirs = [(-1, -1), (-1, 1), (1, -1), (1, 1)] if piece['type'] == 'king' else (
        [(-1, -1), (-1, 1)] if piece['player'] == 'white' else [(1, -1), (1, 1)]
    )

    for dr, dc in dirs:
        if piece['type'] == 'king':
            nr, nc = r + dr, c + dc
            while 0 <= nr < BOARD_SIZE and 0 <= nc < BOARD_SIZE and board[nr][nc] is None:
                moves.append({
                    'from': (r, c),
                    'to': (nr, nc),
                    'path': [(r, c), (nr, nc)],
                    'captured': [],
                    'is_capture': False
                })
                nr += dr
                nc += dc
        else:
            nr, nc = r + dr, c + dc
            if 0 <= nr < BOARD_SIZE and 0 <= nc < BOARD_SIZE and board[nr][nc] is None:
                moves.append({
                    'from': (r, c),
                    'to': (nr, nc),
                    'path': [(r, c), (nr, nc)],
                    'captured': [],
                    'is_capture': False
                })

    return moves

def _find_captures_for_piece(board, r: int, c: int, piece: dict, visited_captured=None, current_path=None) -> List[dict]:
    if visited_captured is None:
        visited_captured = []
    if current_path is None:
        current_path = [(r, c)]

    captures = []
    opponent = 'black' if piece['player'] == 'white' else 'white'
    dirs = [(-1, -1), (-1, 1), (1, -1), (1, 1)]  # Бьют во все 4 стороны

    if piece['type'] == 'king':
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            found_enemy = None
            while 0 <= nr < BOARD_SIZE and 0 <= nc < BOARD_SIZE:
                cell = board[nr][nc]
                if cell:
                    if cell['player'] == opponent and (nr, nc) not in visited_captured:
                        if found_enemy is None:
                            found_enemy = (nr, nc)
                        else:
                            break
                    else:
                        break
                else:
                    if found_enemy:
                        new_captured = visited_captured + [found_enemy]
                        new_path = current_path + [(nr, nc)]
                        temp_board = copy.deepcopy(board)
                        temp_board[nr][nc] = temp_board[r][c]
                        temp_board[r][c] = None

                        further = _find_captures_for_piece(temp_board, nr, nc, piece, new_captured, new_path)
                        if further:
                            captures.extend(further)
                        else:
                            captures.append({
                                'from': current_path[0],
                                'to': (nr, nc),
                                'path': new_path,
                                'captured': new_captured,
                                'is_capture': True
                            })
                nr += dr
                nc += dc
    else:
        for dr, dc in dirs:
            mid_r, mid_c = r + dr, c + dc
            land_r, land_c = r + 2 * dr, c + 2 * dc

            if (0 <= land_r < BOARD_SIZE and 0 <= land_c < BOARD_SIZE and
                board[land_r][land_c] is None and
                board[mid_r][mid_c] and board[mid_r][mid_c]['player'] == opponent and
                (mid_r, mid_c) not in visited_captured):

                new_captured = visited_captured + [(mid_r, mid_c)]
                new_path = current_path + [(land_r, land_c)]
                temp_board = copy.deepcopy(board)
                promoted = (land_r == 0 if piece['player'] == 'white' else land_r == 7)
                p_copy = copy.deepcopy(piece)
                if promoted:
                    p_copy['type'] = 'king'

                temp_board[land_r][land_c] = p_copy
                temp_board[r][c] = None

                further = _find_captures_for_piece(temp_board, land_r, land_c, p_copy, new_captured, new_path)
                if further:
                    captures.extend(further)
                else:
                    captures.append({
                        'from': current_path[0],
                        'to': (land_r, land_c),
                        'path': new_path,
                        'captured': new_captured,
                        'is_capture': True
                    })

    return captures

def make_move(board: List[List[Optional[dict]]], move: dict) -> List[List[Optional[dict]]]:
    new_board = copy.deepcopy(board)
    fr, fc = move['from']
    tr, tc = move['to']

    piece = new_board[fr][fc]
    new_board[fr][fc] = None
    new_board[tr][tc] = piece

    if piece['type'] == 'man':
        if (piece['player'] == 'white' and tr == 0) or (piece['player'] == 'black' and tr == 7):
            piece['type'] = 'king'

    for cr, cc in move['captured']:
        new_board[cr][cc] = None

    return new_board

def quiescence(board, player: str, alpha: int, beta: int) -> int:
    static_eval = evaluate_board(board)
    current_eval = static_eval if player == 'white' else -static_eval

    if current_eval >= beta:
        return beta
    if current_eval > alpha:
        alpha = current_eval

    moves = get_valid_moves(board, player)
    captures = [m for m in moves if m['is_capture']]

    if not captures:
        return current_eval

    for move in captures:
        next_board = make_move(board, move)
        next_player = 'black' if player == 'white' else 'white'
        val = -quiescence(next_board, next_player, -beta, -alpha)

        if val >= beta:
            return beta
        if val > alpha:
            alpha = val

    return alpha

def negamax(board, depth: int, alpha: int, beta: int, player: str) -> Tuple[int, Optional[dict]]:
    moves = get_valid_moves(board, player)

    if not moves:
        return -WIN_SCORE + (10 - depth), None

    if depth <= 0:
        return quiescence(board, player, alpha, beta), None

    best_move = moves[0]
    best_val = -float('inf')

    moves.sort(key=lambda m: len(m['captured']), reverse=True)

    for move in moves:
        next_board = make_move(board, move)
        next_player = 'black' if player == 'white' else 'white'

        val, _ = negamax(next_board, depth - 1, -beta, -alpha, next_player)
        val = -val

        if val > best_val:
            best_val = val
            best_move = move

        if val > alpha:
            alpha = val

        if alpha >= beta:
            break

    return best_val, best_move

def get_best_move(board: List[List[Optional[dict]]], player: str, depth: int = 5) -> Optional[dict]:
    _, move = negamax(board, depth, -float('inf'), float('inf'), player)
    return move