python - 井字游戏和 Minimax AI

Question

这是我的基本 Tic Tac Toe 程序代码(减去实际的游戏类和我的测试)。我在编写实际的 minimax 算法时遇到了问题。我很难验证实际发生了什么，但这段代码似乎只是从当前状态返回随机移动。

我的想法是，我无法在 minimax() 中初始化“最佳”变量，因为每次调用该函数时它都会被覆盖...此时我真的迷路了。

任何人都可以指出我在这个算法上的正确方向吗？我觉得我已经很接近了，但是缺少一些关于递归的关键点或概念，它们将把所有这些放在一起。

def makeMove(board, player, location):
    gridlist = list(board)
    gridlist[location] = player
    return ''.join(gridlist)

def printBoard(board):
    return board

def winner(board):
    for row in winning_combos:
        if (board[row[0]] is not ' ') and (equal([board[i] for i in row])):
            return board[row[0]]

def equal(row):
    return row == [row[0]] * 3

winning_combos = [
        [0, 1, 2], [3, 4, 5], [6, 7, 8],
        [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6]]

def availableMoves(board):
    return [k for k, v in enumerate(board) if v == ' ']

def isComplete(board):
    if availableMoves(board) == []:
        return True
    elif winner(board):
        return True
    else:
        return False

def x_won(board):
    return winner(board) == 'x'

def o_won(board):
    return winner(board) == 'o'

def tied(board):
    return isComplete(board) and winner(board) is None

def get_enemy(player):
    if player == 'x':
        return 'o'
    else:
        return 'x'

def score(board):
    if x_won(board):
        return 10
    elif o_won(board):
        return -10
    elif tied(board):
        return 0


def determine(board, player):
    if isComplete(board):
        return score(board)
    best = 0
    for move in availableMoves(board):
        board = makeMove(board, player, move)
        val = determine(board, get_enemy(player))
        print val
        if val > best:
            best = val
    return best

Answer 1

您的代码示例缺少极小极大算法的 1 个关键部分。你正在做最大的部分，而不是最小的部分。您假设两位玩家总是会以更高的值(value)下棋。那不是真的。对手将取较低的值。所以修改你的确定函数来检查轮到谁了。如果轮到计算机了，像你一直在做的那样取更高的值。但是如果轮到对方了，就这样取较低的值:

if(value<best)
   best = val;

这应该可以解决您的问题。