---

import copy
from typing import List, Tuple, Optional, Dict, Any

BOARD_SIZE = 8
WIN_SCORE = 100000

# ==============================================================================
# 1. ОЦЕНОЧНАЯ ФУНКЦИЯ ПОЗИЦИИ (STATIC EVALUATION)
# ==============================================================================
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 = 350 if piece['type'] == 'king' else 100

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

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

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

    return score


# ==============================================================================
# 2. ГЕНЕРАЦИЯ ХОДОВ И ПРАВИЛО МАКСИМАЛЬНОГО ВЗЯТИЯ
# ==============================================================================
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, 0), (1, 0), (0, -1), (0, 1)] if piece['type'] == 'king' else (
        [(-1, 0), (0, -1), (0, 1)] if piece['player'] == 'white' else [(1, 0), (0, -1), (0, 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),
                    '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),
                    'captured': [],
                    'is_capture': False
                })

    return moves


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

    captures = []
    opponent = 'black' if piece['player'] == 'white' else 'white'
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    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]
                        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)
                        if further:
                            captures.extend(further)
                        else:
                            captures.append({
                                'from': (r, c),
                                'to': (nr, nc),
                                '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)]
                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)
                if further:
                    captures.extend(further)
                else:
                    captures.append({
                        'from': (r, c),
                        'to': (land_r, land_c),
                        '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


# ==============================================================================
# 3. АЛГОРИТМ НЕГАМАКС И QUIESCENCE SEARCH
# ==============================================================================
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


# ==============================================================================
# 4. АДАПТЕР С ОТЛАДКОЙ
# ==============================================================================
def matrix_to_internal_board(matrix: List[List[Any]]) -> List[List[Optional[dict]]]:
    internal_board = [[None for _ in range(8)] for _ in range(8)]
    
    if not matrix or len(matrix) != 8:
        return internal_board

    for r in range(8):
        for c in range(8):
            val = matrix[r][c]
            if val is None or val == 0:
                continue
            
            s_val = str(val).strip().rstrip('.0')
            
            if s_val in ('1', '2', 'black'):
                internal_board[r][c] = {'type': 'man', 'player': 'black'}
            elif s_val in ('3', '4', 'white'):
                internal_board[r][c] = {'type': 'man', 'player': 'white'}
            elif s_val in ('5', '6', 'b_king', 'black_king'):
                internal_board[r][c] = {'type': 'king', 'player': 'black'}
            elif s_val in ('7', '8', 'w_king', 'white_king'):
                internal_board[r][c] = {'type': 'king', 'player': 'white'}
                
    return internal_board


def get_best_move_from_matrix(matrix: List[List[Any]], side_to_move: int = 3, depth: int = 5):
    print("--- DEBUG ENGINE ---")
    print("Side to move:", side_to_move)
    
    board = matrix_to_internal_board(matrix)
    
    pieces_count = sum(1 for r in range(8) for c in range(8) if board[r][c] is not None)
    print("Recognized pieces on board:", pieces_count)

    player = 'white' if side_to_move == 3 else 'black'
    score, move = negamax(board, depth, -float('inf'), float('inf'), player)

    print("Calculated move:", move)
    print("--------------------")

    if not move:
        return None

    return {
        "score": score,
        "from": move['from'],
        "to": move['to'],
        "captured": move['captured'],
        "raw_move": move
    }