Минимакс Mancala не может найти решение в разумные сроки

Question

Я написал игру Mancala на python, которая реализует базовый алгоритм Minimax. Он настроен на случайную игру противника, но всякий раз, когда я даю ему полную доску (12 ям с одним камнем каждая), она никогда не заканчивается. Тем не менее, если я дам ему доску для окончания игры (только 4 или 5 камней в случайном порядке), она найдет правильное решение и закроет программу.

Я ожидаю, что потребуется некоторое время, чтобы найти решение, но я дал ему поработать всю ночь (10 часов +), и он никогда не вернул результат.

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

Я установил ограничения глубины, что помогает, но если я установилглубина примерно до 5, она никогда не останавливается.

INFINITY = 1.0e06

def game_over(board):
    if sum(board[0:6]) == 0 or sum(board[7:13]) == 0:
        return True
    else:
        return False

def valid_move(board, action, start, end):
    if start <= action < end and board[action] > 0:
        return True
    else:
        return False

def make_move(board, action, turn):
    start = 0 if turn else 7
    end = 6 if turn else 13

    num_stones = board[action]
    cur_pit = action + 1
    # Set initial pit to zero
    board[action] = 0

    for x in range(num_stones):
        # If current pit is opponents store, place next stone in cur_pit +1
        # then skip two to catch up
        if (cur_pit % 14) == (end + 7) % 14:
            board[(cur_pit + 1) % 14] += 1
            cur_pit += 2
        else:
            board[cur_pit % 14] += 1
            cur_pit += 1
    # Changes turn unless landing on own store
    new_turn = not turn if (cur_pit - 1) % 14 != end else turn

    return board, new_turn

def result(board, action, turn):
    new_board = copy.deepcopy(board)
    return make_move(new_board, action, turn)

def move_list(board, turn):
    start = 0 if turn else 7
    end = 6 if turn else 13
    moves = []
    for pit in range(start, end):
        if board[pit] > 0:
            moves.append(pit)
    return moves

def utility(state):
    return state[6] - state[13]

def minimax(board, maximizing_player, turn):
    if game_over(board):
        # if depth == 0:
        #     print("Depth limit reached.")
        # else:
        #     print('Game over reached')
        return utility(board)

    if maximizing_player:
        value = -INFINITY
        actions = move_list(board, turn)
        for a in actions:
            new_board, new_turn = result(board, a, turn)
            # If not repeat turn, changes max player
            maximizing_player = False if new_turn != turn else True
            value = max(value, minimax(new_board, maximizing_player, new_turn))
        return value

    else:
        value = INFINITY
        actions = move_list(board, turn)
        for a in actions:
            new_board, new_turn = result(board, a, turn)
            # If not repeat turn, changes max player
            maximizing_player = True if new_turn != turn else False
            value = min(value, minimax(new_board, maximizing_player, new_turn))
        return value

def run_turn(board, player, turn):
    if player == 'minimax':
        moves = []
        actions = move_list(board, turn)
        for a in actions:
            moves.append((a, minimax(board, False, turn)))
        p_move = max(moves, key=itemgetter(1))[0]

    else:   # Random
        pit_start = 0 if turn else 7
        pit_end = 6 if turn else 13
        p_move = random.choice(range(pit_start, pit_end))
        while not valid_move(board, p_move, pit_start, pit_end):
            p_move = random.choice(range(pit_start, pit_end))

    return make_move(board, p_move, turn)


def driver(one, two):
    board = [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0]
    # board = [1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]
    turn = True
    while True:
        if turn:
            board, turn = run_turn(board, one, turn)
            if game_over(board):
                return who_won(board)
        else:
            board, turn = run_turn(board, two, turn)
            if game_over(board):
                return who_won(board)

Код написан так, чтобы принимать двух игроков в качестве аргументов командной строки, но я пропустил основной метод, чтобы уменьшить код в посте.

Мне сказали, что время пробега составляет менее часа, когда доска начинается с 12 ям из 2 камней.