python - Minimax 算法只返回特定的一组值

Question

我在 Python 中为基本的井字棋 AI 实现了一个极小极大算法，如下所示:

def minimax(currentBoard, player):
    if isGameOver(currentBoard):
        score = evaluate(currentBoard)
        return score
    for cell in getEmptySpots(currentBoard):
        x = cell[0]
        y = cell[1]
        currentBoard[x][y] = player
        bestScore = -1000000
        score = minPlay(currentBoard, -player)
        currentBoard[x][y] = 0
        if score > bestScore:
            bestScore = score
            bestMove = cell
            print('Best move:')
            print(bestMove)
            print('\n')
        return bestMove

def minPlay(currentBoard, player):
    if isGameOver(currentBoard):
        score = evaluate(currentBoard)
        return score
    for cell in getEmptySpots(currentBoard):
        x = cell[0]
        y = cell[1]
        currentBoard[x][y] = player
        bestScore = 1000000
        score = maxPlay(currentBoard, -player)
        currentBoard[x][y] = 0
        if score < bestScore:
            bestScore = score
        return bestScore

def maxPlay(currentBoard, player):
    if isGameOver(currentBoard):
        score = evaluate(currentBoard)
        return score
    for cell in getEmptySpots(currentBoard):
        x = cell[0]
        y = cell[1]
        currentBoard[x][y] = player
        bestScore = -1000000
        score = minPlay(currentBoard, -player)
        currentBoard[x][y] = 0
        if score > bestScore:
            bestScore = score
        return bestScore

其他支持功能是不言自明的。但是，此脚本无法正常运行。例如，它似乎总是从选择 [0,0] 开始，然后进行一组相对恒定的移动，即使有更好的移动可用。此外，给定以下状态(以及一般情况下获胜 Action 可用的状态):

其中 1 代表人类，-1 代表计算机，计算机选择 [2][1] 作为最佳着法移动，而不是 [2][2] 或 [1][2] 两者都会导致胜利。

我已经用不同的语言回答了许多与极小极大实现相关的问题，据我所知，我的代码在逻辑上是有意义的。因此，我不确定问题出在哪里。 我的完整代码可以找到here .

Answer 1

有两个问题。首先是@Flopp 的回答中的逻辑问题。第二个是 isGameOver 在没有更多移动时不返回 true。 0 的分数作为初始最高或最低分数返回。

这里:

def minPlay(currentBoard, player):
    if isGameOver(currentBoard):
        score = evaluate(currentBoard)
        return score

相关的(固定的)行在这里(它并不漂亮，它只是证明它会起作用):

def isGameOver(currentBoard):
    return checkGameOver(currentBoard, HUMAN) or checkGameOver(currentBoard, COMPUTER) or getEmptySpots(currentBoard) == []

对于 minimax，确保也有一个初始的 bestMove 可能是个好主意。

def minimax(currentBoard, player):
    if isGameOver(currentBoard):
        score = evaluate(currentBoard)
        return score
    allMoves = getEmptySpots(currentBoard)
    bestMove = allMoves[0]
    for cell in allMoves: