Что не так с моим минимаксным алгоритмом? - PullRequest
Новая
       93

Что не так с моим минимаксным алгоритмом?

0 голосов
/ 05 мая 2020

Я попытался создать MiniMax AI, используя учебник ,

AI не работает и просто переходит в нижнюю строку и каждый раз накапливается, сообщая индекс столбца 0, 1, 2, 3, 4, 5, 6, а затем для следующей строки и так далее. Единственное, что мне удалось найти в выводе кода, сильно отличающемся от моего и рабочей версии учебников, - это глубина алгоритма минимакса в процессе его выполнения. Где , это было глубиной рабочего, когда оно повторялось, а this было глубиной моего (оно было длиннее этого, но моя консоль не сохранила все это) . Я пробовал много вещей, чтобы заставить его работать, включая переработку системы досок для нескольких списков внутри списка и многие другие вещи, такие как удаление некоторых частей кода и переработка оценок, но, похоже, это не изменилось.

Моя минимаксная функция: 

def minimax(board, depth, alpha, beta, maximizingPlayer):
    print (depth)
    validLocations = getValidLocations(board)
    isTerminal = isTerminalNode(board)
    if depth == 0 or isTerminal:
        if isTerminal:
            if checkWin(board, computerDisc):
                return (None, math.inf)
            elif checkWin(board, playerDisc):
                return (None, -math.inf)
            else: # Game is over, no more spaces
                return (None, 0)
        else: # Depth is zero
            # print ("THIS IS DEPTH 0")
            return (None, scorePos(board, computerDisc))

    if maximizingPlayer:
        value = -math.inf
        column = random.choice(validLocations)
        for c in validLocations:
            boardCopy = copy.deepcopy(board)
            dropPiece(boardCopy, c, computerDisc)
            newScore = minimax(boardCopy, depth-1, alpha, beta, False)[1]
            if newScore > value:
                value = newScore
                column = c
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return (column, value)

    else: # Minimizing player
        value = math.inf
        column = random.choice(validLocations)
        for c in validLocations:
            boardCopy = copy.deepcopy(board)
            dropPiece(boardCopy, c, playerDisc)
            newScore = minimax(boardCopy, depth-1, alpha, beta, True)[1]
            if newScore < value:
                value = newScore
                column = c
            beta = min(beta, value)
            if alpha >= beta:
                break

        return (column, value)

И функция обучающих программ: 

def minimax(board, depth, alpha, beta, maximizingPlayer):
valid_locations = get_valid_locations(board)
is_terminal = is_terminal_node(board)
if depth == 0 or is_terminal:
    if is_terminal:
        if winning_move(board, AI_PIECE):
            return (None, 100000000000000)
        elif winning_move(board, PLAYER_PIECE):
            return (None, -10000000000000)
        else: # Game is over, no more valid moves
            return (None, 0)
    else: # Depth is zero
        return (None, score_position(board, AI_PIECE))
if maximizingPlayer:
    value = -math.inf
    column = random.choice(valid_locations)
    for col in valid_locations:
        row = get_next_open_row(board, col)
        b_copy = board.copy()
        drop_piece(b_copy, row, col, AI_PIECE)
        new_score = minimax(b_copy, depth-1, alpha, beta, False)[1]
        if new_score > value:
            value = new_score
            column = col
        alpha = max(alpha, value)
        if alpha >= beta:
            break
    return column, value

else: # Minimizing player
    value = math.inf
    column = random.choice(valid_locations)
    for col in valid_locations:
        row = get_next_open_row(board, col)
        b_copy = board.copy()
        drop_piece(b_copy, row, col, PLAYER_PIECE)
        new_score = minimax(b_copy, depth-1, alpha, beta, True)[1]
        if new_score < value:
            value = new_score
            column = col
        beta = min(beta, value)
        if alpha >= beta:
            break
    return column, value

Когда моя не работала, я пытался сделать ее как можно ближе к обучающей функции но это все еще не работает. Что мне нужно, чтобы он работал?

Полные программы: Mine: https://repl.it/@MyloBishop / Connect-4 Учебники: https://github.com/KeithGalli/Connect4-Python/blob/master/connect4_with_ai.py

1 Ответ

1 голос
/ 05 мая 2020

Плата передается в вашу минимаксную функцию как параметр node , но внутри функции вы используете board .

Эталонная программа: def minimax (board, depth, alpha, beta, maximizingPlayer):

Ваша программа: def minimax ( node , depth, alpha, beta, maximizingPlayer ):

Ваша рекурсивная функция минимакса, следовательно, не работает должным образом.

Изменить: Чтобы исправить это, замените плату внутри минимакса с node (не меняйте node в определении функции на board )

Edit 2: Также проверьте функцию scorePos - у вас жестко запрограммирован computerDis c вместо использования аргумента функции.

Редактировать 3: Кроме того, другие вспомогательные функции, такие как isBoardFull () и isSpaceFree (), должны работать с копией платы, а не с глобальной переменной.

...