Как выполнить поиск дерева на доске connect-4 и определить лучший ход?

Question

Мне нужно создать рекурсивную функцию, которая перебирает все возможные ходы игры «4 в ряд» на заданной глубине и находит лучший ход.

Доступны следующие функции:

eval_pos(board, pid) # Returns eval score of a given board and pid(player id, either -1 or 1) 
get_legal_moves(board) # Returns all legals moves in a tuple

Цель состоит в том, чтобы создать рекурсивную функцию, которая находит, какой ход дает лучший результат, учитывая лучшую игру с обеих сторон.

def get_score(board, depth, pid):
    moves = get_legal_moves(board)
    evals = []
    for move in moves:
        board[move] = pid
        evals.append(eval_pos(board, pid))
        board[move] = 0 #0 signifies an empty board space, doing this to prevent filling the board

    if depth == 0:
        return max(evals)

    idx = evals.index(max(evals))
    board[moves[idx]] = pid
    # Notice we are passing -pid on each new iteration
    return get_score(board, depth-1, -pid, start_pid)

Что я придумал так далеко, не работает вообще. Он делает то, что я хочу, в реверс и пропускает много позиций, где он проверяет лучший ход для игрока1 на первой позиции, затем лучший ход для игрока2 на следующей позиции и так далее. Тем не менее, он должен искать ВСЕ ходы, а затем определять, что лучше всего, учитывая лучшую контригру. Есть ли эффективный способ сделать это sh? 1011 *

Answer 1

Похоже, что это решение работает, но оно чрезвычайно медленное и может достичь глубины 5, прежде чем оно станет непригодным для использования.

def minimax(board, depth, max_turn):
    # Base case
    if depth == 0:
        return eval_pos(board)

    eval = eval_pos(board)

    if eval is None:
        return 0

    if abs(eval) == 100:
        return eval

    moves = get_legal_moves(board)

    if max_turn:
        return max([minimax(update_board(board, move, 1), depth-1, False) for move in moves])
    else:
        return min([minimax(update_board(board, move, -1), depth-1, True) for move in moves])