Как использовать алгоритм Minimax для TicTacToe AI? - PullRequest
Новая
       68

Как использовать алгоритм Minimax для TicTacToe AI?

0 голосов
/ 12 июля 2020

Я новичок в рекурсивных алгоритмах, я работал над этим часами и понятия не имею, что с этим не так. Я создаю ИИ на основе уже работающей программы TicTacToe для двух игроков. 

def minimax(board, isMaximizing):    
    maxScore = -2
    minScore = 2
    px = None
    py = None
    qx = None
    qy = None
    
    result = is_Winner()

    if result == 'X':
        return (-1, 0, 0)
    elif result == 'O':
        return (1, 0, 0)
    if result == 'T':
        return (0, 0, 0) 

    if isMaximizing:
        for pos_moves in validmoves:
            i, j = dicBoard.get(int(pos_moves))
            if board[i][j] == ' ':
                board[i][j] = 'O'
                (score, min_i, min_j) = minimax(board, False)
                board[i][j] = ' '
                if (score > maxScore):
                    maxScore = score
                    px = i
                    py = j
        return (maxScore, px, py)
    else:
        for pos_moves in validmoves:
            i, j = dicBoard.get(int(pos_moves))
            if board[i][j] == ' ':
                board[i][j] = 'X'
                (score, max_i, max_j) = minimax(board, True)
                board[i][j] = ' '
                if (score < minScore):
                    minScore = score
                    qx = i
                    qy = j
        return (minScore, qx, qy)

def bestMove(board):
    global turn

    score, x, y = minimax(board, True)
    print(score, x, y)
    board[x][y] = 'O'
    turn += 1

Функция bestMove() - это то, что я называю в моей игре l oop, когда наступает очередь ИИ. Как бы то ни было, программа возвращает игру, но она не выбирает лучшую игру в соответствии с ее значением, а вместо этого просто идет в порядке доступных ходов в списке validmoves, который содержит строки 1-9. Код dicBoard.get() преобразует строку 1–9 в набор координат на игровом поле. Все это, похоже, работает, и вставка функции, которая печатает плату в середину al oop, действительно показывает все итерации в дереве.

Что не работает, так это фактический min-max часть этого. Алгоритм не выбирает максимальное значение. Я подозреваю, что проблема заключается в следующем коде: 

if (score < minScore):
   minScore = score
   qx = i
   qy = j

Я, по праву, не могу этого понять. Спасибо за любую помощь!

EDIT

Я понимаю, что мне нужно больше кода для моей второй функции bestMove(). Я изменил его на следующий, эффективно используя тот же код из функции minimax: 

def bestMove(board):
global turn
maxScore = -1

for pos_moves in validmoves:
    i, j = dicBoard.get(int(pos_moves))
    if board[i][j] == ' ':
        board[i][j] = 'O'
        score, x, y = minimax(board, False)
        print(score, x, y)
        board[i][j] = ' '
        if score > maxScore:
            px = x
            py = y
board[px][py] = 'O'
turn += 1

Тем не менее, алгоритм не находит подходящего хода. Строка print(score, x, y) выдаёт следующее: 

-1 1 0
-1 0 0
-1 0 0
-1 0 0
-1 0 0
-1 0 0
-1 0 0
-1 0 0

Для того, чтобы найти правильный ход, score должен быть равен 0 или 1 (что означает ie или выигрыш за ИИ), но, как вы можете видеть, он возвращает все -1 scores, как если бы это была победа для X, в данном случае игрока.

...