Python TicTacToe minimax 选择了错误的选项

Question

我目前正在尝试为我的 Python TicTacToe 游戏实现 AI。除了一种情况外，一切都表现出色。我当前的代码：

def testLine(line):
    '''
    ' :param line: Liste containing 3 ints
    ' :return:   1, if all elements of the list == 1
    '           -1, if all elements of the list == -1
    '            0, otherwise
    '''

    if line[0] == 1 and line[1] == 1 and line[2] == 1:
        return 1
    elif line[0] == -1 and line[1] == -1 and line[2] == -1:
        return -1
    return 0


def getWinner(board):
    # test columns
    for idx in range(3):
        line = [board[0][idx], board[1][idx], board[2][idx]]
        if not testLine(line) == 0:
            return line[0]

    # test rows
    for idx in range(3):
        line = board[idx]
        if not testLine(line) == 0:
            return line[0]

    # test diagonals
    line = [board[0][0], board[1][1], board[2][2]]
    if not testLine(line) == 0:
        return line[0]
    line = [board[0][2], board[1][1], board[2][0]]
    if not testLine(line) == 0:
        return line[0]

    # no winner
    return 0

def count(board, obj):
    c = 0
    for r in range(len(board)):
        for col in range(len(board[r])): # FIXED IT
            if board[r][col] == obj:
                c += 1
    return c

def nextMove(board, player):

    if len(board[0]) + len(board[1]) + len(board[2]) == 1: return 0, 4
    nextPlayer = player * (-1)

    if not getWinner(board) == 0:
        if player is 1: return -1, (-1, -1)
        else: return 1, (-1, -1)
    listOfResults = [] # empty array

    if count(board, 0) == 0: # there is no empty field
        return 0, (-1, -1)

    _list = []
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] == 0:
                _list.append((i, j))

    for (i, j) in _list:
        board[i][j] = player
        ret, move = nextMove(board, nextPlayer)
        listOfResults.append(ret)
        board[i][j] = 0
    if player is 1:
        maxPossibleValue = max(listOfResults)
        return maxPossibleValue, _list[listOfResults.index(maxPossibleValue)]
    else:
        minPossibleValue = min(listOfResults)
        return minPossibleValue, _list[listOfResults.index(minPossibleValue)]



if __name__ == '__main__':
    print(str(nextMove([[ 1,  -1,  0],
                        [ -1, -1,  1],
                        [ 1,  1,  0]],
                       -1)))

输出：(0, (0, 2))

我可以肯定地说 count、getWinner 和 testLine 工作得很好。但是代码最底部的场景输出是完全错误的，因为 它应该是 (0, 2, 2) 因为计算机必须 "block" 我有机会获胜在底线。您对如何修复我的极小极大算法有什么建议吗？

编辑：我已经修复了它。 错误在 count 方法中。你不应该说

for col in board[r]

但是

for col in range(len(board[r]))

因为否则它不会保持元素的正确顺序并且整个方法返回一个错误值。

Answer 1

首先要知道return a, b和return (a,b)类似，因为定义元组不需要括号（空元组除外）。

所以你可以轻松地 return (0, 0, 2) 而不是 (0, (0, 2)) :

return (maxPossibleValue,) + _list[listOfResults.index(maxPossibleValue)]
# use (a,) for a tuple of len 1

但我知道这只能解决你一半的问题。

Answer 2

我已经修好了。错误出在计数方法中。你不应该说

for col in board[r]

但是

for col in range( len(board[r]) )

因为否则它不会保持元素的正确顺序并且整个方法返回一个错误值。

Python TicTacToe minimax 选择了错误的选项

Python TicTacToe minimax choses wrong option

python

algorithm

artificial-intelligence

minimax