Реализация минимаксного алгоритма для Tic Tac Toe в Python - PullRequest
Новая
       58

Реализация минимаксного алгоритма для Tic Tac Toe в Python

0 голосов
/ 29 ноября 2018

Я работаю над созданием простого минимаксного алгоритма для бота Tic Tac Toe.Я прочитал некоторые другие ответы здесь, но я все еще не совсем уверен, что я делаю неправильно, я довольно плохо знаком с рекурсивными функциями.Я думаю, что понимаю, как работает алгоритм, но я не совсем уверен. 

def minimax(board, player, originalPlayer):
    global ai, human
    if gameOver(board):
        if hasWon(board, originalPlayer):
            return 1, None
        if hasWon(board, opposite(originalPlayer)):
            return -1, None
        if len(getEmptyIndexes(board)) is 0:
            return 0, None

    possibleMoves = getEmptyIndexes(board)
    if player == originalPlayer:
        bestScore = float('-inf')
    else:
        bestScore = float('inf')

    for moveIndex in possibleMoves:
        clone = copy(board)
        clone = makeMove(clone, moveIndex, player)
        score, index = minimax(clone, opposite(player), originalPlayer)

        if player == originalPlayer:
            if score > bestScore:
                bestScore = score
                bestMove = index
        else:
            if score < bestScore:
                bestScore = score
                bestMove = index

    return bestScore, bestMove

Мой игровой цикл находится ниже, я просто использую его для отладки.Ошибка, которую я получаю, состоит в том, что функция minimax возвращает кортеж (0, None), когда я ожидаю получить индекс доски, где None. 

ai = 'X'
human = 'O'
board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']

while True:
    print('Board:')
    printBoard(board)
    choice = int(input('Your choice: '))
    board[choice] = human
    print('AI Moves')
    score, index = minimax(board, ai, ai)
    board[index] = ai

Спасибо за вашу помощь!

Редактировать: getEmptyIndexes возвращает индексы пробелов на доске;например: 

getEmptyIndexes([' ', 'X', ' ', 'X', ' ', 'O', ' ', 'O', ' ']) = [0, 2, 4, 6, 8]

Редактировать 2: Я думаю, что я на самом деле просто исправил это, я писал «bestMove = index» вместо «bestMove = moveIndex», в значительной степени я использовалстарый индекс перемещения из старых листовых узлов вместо нового.

...