Python Deep copy in minimax function

I am creating a chess engine in Python by using a minimax algortihm with alpha-beta pruning. It is however very slow at the moment, and I found that doing deepcopy each iteration in minimax is as slow as all my other functions combined.

Is there any way to get around the deepcopy, or to make it faster? Below is my minimax function as of today. It can only think 3-4 moves ahead or so, which doesn't make a very good engine... Any suggestions on speeding the algorithm up is very appreciated.

def minimax(board, depth, alpha, beta, maximizing_player):

    board.is_human_turn = not maximizing_player 

    children = board.get_all_possible_moves()

    if depth == 0 or board.is_draw or board.is_check_mate:
        return None, evaluate(board)

    best_move = random.choice(children)

    if maximizing_player:
        max_eval = -math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child[0][0], child[0][1], child[1][0], child[1][1])
            current_eval = minimax(board_copy, depth - 1, alpha, beta, False)[1]
            if current_eval > max_eval:
                max_eval = current_eval
                best_move = child
            alpha = max(alpha, current_eval)
            if beta <= alpha:
                break
        return best_move, max_eval

    else:
        min_eval = math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child[0][0], child[0][1], child[1][0], child[1][1])
            current_eval = minimax(board_copy, depth - 1, alpha, beta, True)[1]
            if current_eval < min_eval:
                min_eval = current_eval
                best_move = child
            beta = min(beta, current_eval)
            if beta <= alpha:
                break
        return best_move, min_eval

Some ideas on how to optimize your program (in no particular order):

1. Make the check if depth == 0 or board.is_draw or board.is_check_mate first thing you do in the minimax function. Right now you call board.get_all_possible_moves() which might be redundant (e.g. in the case depth == 0).

2. I don't see how the get_all_possible_moves() method is implemented and assume that it doesn't do any kind of sorting. It's a good practice to order moves for minimax algorithm so that you loop over them starting from the best one to the worst (in this case you are likely to prune more nodes and speed up the program).

3. The child variable in the for child in children loop is a two-dimensional matrix. I also guess that board is a multi-dimensional array as well. Multi-dimensional arrays can be slower than one-dimensional because of their memory layout (e.g. if you iterate over them column-wise). Use one-dimensional arrays if possible (e.g. you can represent a two-dim array as "concatenation" of one-dim arrays).

4. Use generators for lazy evaluation. For instance, you can turn your get_all_possible_moves() into a generator and iterate over it without creating lists and consuming extra memory. If the alpha/beta pruning condition triggers early, you won't need to expand the whole list of children in the position.

5. Avoid deepcopying of the board by making and unmaking the current move. In this case you don't create copies of the board but reuse the original board which might be faster:

current_move_info = ... # collect and store info necessary to make/unmake the current move

board.move(current_move_info)

current_eval = minimax(board, ...)[1]

board.unmake_move(current_move_info) # restore the board position by undoing the last move

6. Add more classical optimizing chess-engine features like iterative deepening, principal variation search, transposition tables, bitboards etc.