Минимаксный алгоритм Tic Tac Toe не работает - PullRequest
Новая
       57

Минимаксный алгоритм Tic Tac Toe не работает

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

Мой код для минимаксного алгоритма Tic Tac Toe AI, кажется, не работает, и я не могу понять, почему. Кажется, что-то не так с аспектом recusrion и возвращением отрицательного значения, если движение приводит к потере; оно не делает различий между защитным ходом и наступательным.

Вместо того, чтобы поставить X на позицию 6, чтобы противник не достиг 3 подряд, он вместо этого помещает его на другую клетку 

board = [
        "X", "X", "O",
        "O", "O", "X",
        "-", "-", "-",
        ]

opp = "O"
plyr = "X"

def getOpenPos(board):
    openPos = []
    for index, state in enumerate(board):
        if state == "-":
            openPos.append(index)
    return openPos

def winning(board, plyr):
    if ((board[0] == plyr and board[1] == plyr and board[2] == plyr) or 
        (board[3] == plyr and board[4] == plyr and board[5] == plyr) or 
        (board[6] == plyr and board[7] == plyr and board[8] == plyr) or
        (board[0] == plyr and board[4] == plyr and board[8] == plyr) or
        (board[1] == plyr and board[4] == plyr and board[7] == plyr) or
        (board[2] == plyr and board[4] == plyr and board[6] == plyr) or
        (board[0] == plyr and board[3] == plyr and board[6] == plyr) or
        (board[2] == plyr and board[5] == plyr and board[8] == plyr)):
        return True
    else:
        return False 

def minimax(board, turn, FIRST):
    possibleMoves = getOpenPos(board)
    #check if won
    if (winning(board, opp)):
        return -10
    elif (winning(board, plyr)):
        return 10

    scores = []

    #new board created for recursion, and whoevers turn it is
    for move in possibleMoves:
        newBoard = board
        newBoard[move] = turn


        if (turn == plyr):
            scores.append( [move,minimax(newBoard, opp, False)] )
        elif (turn == opp):
            scores.append( [move, minimax(newBoard, plyr, False)] )

    #collapse recursion by merging all scores to find optimal position
    #see if there is a negative value (loss) and if there is its a -10
    if not FIRST:
        bestScore = 0
        for possibleScore in scores:
            move = possibleScore[0]
            score = possibleScore[1]
            if score == -10:
                return -10
            else:
                if score > bestScore:
                    bestScore = score
        return bestScore

    else:
        bestMove, bestScore = 0, 0
        for possibleScore in scores:
            move = possibleScore[0]
            score = possibleScore[1]
            if score > bestScore:
                bestMove = move
                bestScore = score

        #returns best position
        return bestMove



print(minimax(board, plyr, True))

1 Ответ

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

Я вижу две проблемы с вашим кодом. Если вы исправите их, в этом случае вы по крайней мере получите 6.

Первая проблема заключается в том, что строка newBoard = board на самом деле не создает копию списка, а просто создает копию ссылки. Это можно исправить, изменив его на newBoard = board[:].

Вторая проблема заключается в том, что ваше начальное значение для bestScore на самом деле не выходит за ожидаемый диапазон, поэтому вы не получаете значение для bestIndex каждый раз. Я изменил bestMove, bestScore = 0, 0 на bestMove, bestScore = 0, -11, и мне показалось, что это работает.

...