生成井字棋可能的移动列表 Python

Question

我现在在做一个课堂项目，需要实现一个人工智能对手来玩井字棋。我打算用minmax和Alpha-Beta minmax算法来决定每一步该怎么走。

不过，我遇到的问题是如何生成一个棋盘上可能的走法列表。

以下是我遇到问题的代码：

def genMoves(genBoard, turnNumber):
    moveList = []

    print "inMovesList"
    #Figure out if X or O go now

    if turnNumber % 2 == 0:
        moveChar = "O"
    else:
        moveChar = "X"

    i = 0;

    while i < 9:
        tempBoard = genBoard
        if tempBoard[i] == "*":
            #set tempBoard[i] to X or O
            tempBoard[i] = moveChar
            #append move, new board
            moveList.append((i, tempBoard))

        i+=1

    print "MovesList: "
    print moveList
    return moveList

我的棋盘用一个包含9个字符串的列表来表示，初始化为["*", "*", "*", "*", "*", "*", "*", "*", "*"]。

我的目标是让走法列表返回一个元组的列表，元组的第一个元素是i（表示X或O放置的位置），第二个元素是更新后的棋盘状态。

我遇到的问题是，虽然我能得到正确数量的可能走法（比如：如果我手动进行前4步的走法，双方的走法会给我5个可能的走法），但它会把同样的走法放在每个包含*的位置上。（所以最终生成的可能第二步走法会变成X,O,O,O,O,O,O,O,O）

这不是我第一次使用minmax算法，但这是我第一次在Python中实现它。

如果有任何建议来解决这个问题，我会很感激！

谢谢！

Answer 1

我认为Python并不是在复制你的棋盘，而是直接指向原来的棋盘。所以你打印出来的内容是：

"MovesList: " [[0,(X,O,O,O,O,O,O,O,O)],[1,(X,O,O,O,O,O,O,O,O)],[2,(X,O,O,O,O,O,O,O,O)],等等。

而你的genBoard变量其实是被改变了。

为了测试这一点，可以在你的方法结束前加上：

print genBoard

如果这确实是问题所在，可以去网上搜索一下如何创建棋盘的副本，而不是直接引用它。

Answer 2

这一行代码有问题：

tempBoard = genBoard

在这行代码之后，你可能以为你有了两个列表——一个是原来的，由genBoard引用，另一个是新的，现在由tempBoard引用。但其实并不是这样的。

这一行代码并没有创建一个列表的副本。相反，它只是让tempBoard这个名字指向了和genBoard相同的对象。

因此，后面如果你用tempBoard[i]去修改内容，也会影响到genBoard[i]。

你可以试试下面这些代码：

tempBoard = list(genBoard)
tempBoard = genBoard[:]
tempBoard = copy.copy(genBoard)

这些代码每一行都会创建一个新的列表，初始内容和genBoard是一样的。此时，tempBoard指向这个新列表，而genBoard仍然指向旧的列表。

如果你处理的对象比字符串列表复杂，你可能需要这样做：

tempBoard = copy.deepcopy(genBoard)