我的极小极大算法输给了我，但看起来完美无缺

Question

我正在尝试使用 python 中的极小极大算法编写井字棋机器人。我的代码似乎应该对我有用，但错误地评估了位置，搜索太多或太少的节点，并且每场比赛都输给了我。

mainboard = ["-", "-", "-", "-", "-", "-", "-", "-", "-"]
nodes = 0

def detectwin(b):
    signs = ["O", "X"]
    for s in signs:
        for i in range(3):
            j = 3 * i
            if ((b[0 + j]==s and b[1 + j]==s and b[2 + j]==s) or
                (b[0 + i]==s and b[1 + i]==s and b[2 + i]==s)):
                if s == "O": return 1
                if s == "X": return -1
        if ((b[0]==s and b[4]==s and b[8]==s) or
            (b[2]==s and b[4]==s and b[6]==s)):
                if s == "O": return 1
                if s == "X": return -1
    return 0

def evaluate(board):
    return detectwin(board)

def fullboard(board):
    return all(cell != "-" for cell in board)

def makemove(board, move, maximizingPlayer):
    if maximizingPlayer:
        board[move] = "O"
        return board
    else:
        board[move] = "X"
        return board

def undomove(board, move):
    board[move] = "-"
    return board

def minimax(board, depth, maximizingPlayer):

    global nodes

    if depth == 0 or fullboard(board) or detectwin(board) != 0:
        nodes += 1
        return evaluate(board)

    if maximizingPlayer:
        maxEval = -1000
        for i in range(9):
            if board[i] == "-":
                board = makemove(board, i , True)
                newEval = minimax(board, depth-1, False)
                maxEval = max(maxEval, newEval)
                board = undomove(board, i)
        return maxEval
    
    else:
        minEval = 1000
        for i in range(9):
            if board[i] == "-":
                board = makemove(board, i , False)
                newEval = minimax(board, depth-1, True)
                minEval = min(minEval, newEval)
                board = undomove(board, i)
        return minEval

def findbestmove(board, maximizingPlayer):

    global nodes
    
    if maximizingPlayer:
        bestmove = -1
        maxEval = -1000
        for i in range(9):
            if board[i] == "-":
                board = makemove(board, i , True)
                nodes = 0
                newEval = minimax(board, 9, False)
                print(f"Eval move {i}: {newEval} ({nodes} nodes)")
                if newEval > maxEval:
                    maxEval = newEval
                    bestmove = i
                board = undomove(board, i)
        return bestmove

def printboard(b):
    signs = ["No", "O", "X"]
    win = signs[detectwin(b)] + " wins"
    print(f'{b[0]} {b[1]} {b[2]}\n{b[3]} {b[4]} {b[5]}\n{b[6]} {b[7]} {b[8]}\n{win}\n')

print("Ready!")
while True:
    move = findbestmove(mainboard, True)
    mainboard = makemove(mainboard, move, True)
    printboard(mainboard)
    yourmove = int(input())
    mainboard = makemove(mainboard, yourmove, False)
    printboard(mainboard)

我尝试过评估不同的职位，期望它通过搜索每一种可能性来给出正确的客观评估。相反，它会搜索错误数量的节点并错误地评估位置。为什么要这样做？

Answer 1

在函数for的循环中detectwin，(b[0 + j]==s and b[1 + j]==s and b[2 + j]==s)实际上是检查行，因为每次迭代将 j 加 3 时，您将移动到棋盘中的下一行。然而，(b[0 + i]==s and b[1 + i]==s and b[2 + i]==s)也是检查行而不是列，只是以不同的方式。这是因为，当您每次迭代将 i 增加 1 而不将其乘以 3 时，您将停留在 1D 棋盘表示的同一行内。

所以问题是你检查了行两次而根本没有检查列。

当前列检查循环：

for i in range(3):
    j = 3 * i
    if ((b[0 + j]==s and b[1 + j]==s and b[2 + j]==s) or
        (b[0 + i]==s and b[1 + i]==s and b[2 + i]==s)):
        if s == "O": return 1
        if s == "X": return -1

它根本不检查第二列和第三列。固定的：

for i in range(3):
    j = 3 * i
    if ((b[0 + j]==s and b[1 + j]==s and b[2 + j]==s) or
        (b[i]==s and b[i + 3]==s and b[i + 6]==s)):
        if s == "O": return 1
        if s == "X": return -1

通过替换(b[0 + i]==s and b[1 + i]==s and b[2 + i]==s)检查(b[i]==s and b[i + 3]==s and b[i + 6]==s)将遍历游戏板的列。希望这可以帮助。