好的，我为一个机器人编写了以下代理来玩井字游戏。我使用了传统的极小化极大算法，没有进行剪枝。这个算法在3×3的棋盘上运行得非常完美。

但是，当我在4×4的棋盘上运行这个算法时，它会卡在计算过程中。我无法理解为什么会这样。我向代理传递了一个numpy数组perspectiveState，其中0表示空位，1表示代理的移动，-1表示对手的移动。它返回下一步移动的位置（1）。

控制流程从turn()函数开始，该函数调用minimax()函数。

我在这里做错了什么？

class MiniMaxAgent:
    def isMovesLeft(self, perspectiveState):
        size = perspectiveState.shape[0]
        #print('!!', np.abs(perspectiveState).sum())
        if np.abs(perspectiveState).sum() == size*size:
            return False
        return True

    def evaluate(self, perspectiveState):
        size = perspectiveState.shape[0]
        rsum = perspectiveState.sum(axis=0)
        csum = perspectiveState.sum(axis=1)
        diagSum = perspectiveState.trace()
        antiDiagSum = np.fliplr(perspectiveState).trace()
        if size in rsum or size in csum or size == diagSum or size == antiDiagSum:
            return 10
        if -1*size in rsum or -1*size in csum or -1*size == diagSum or -1*size == antiDiagSum:
            return -10
        return 0

    def minimax(self, perspectiveState, isMax):
        score = self.evaluate(perspectiveState)
        if score == 10:
            return score
        if score == -10:
            return score
        if not self.isMovesLeft(perspectiveState):
            return 0
        if isMax:
            best = -1000
            for i in range(perspectiveState.shape[0]):
                for j in range(perspectiveState.shape[0]):
                    if perspectiveState[i,j]==0:
                        perspectiveState[i,j] = 1
                        #print('@', isMax)
                        best = max(best, self.minimax(perspectiveState, not isMax))
                        perspectiveState[i,j] = 0
            #print('#', best)
            return best
        else:
            best = 1000;
            for i in range(perspectiveState.shape[0]):
                for j in range(perspectiveState.shape[0]):
                    if perspectiveState[i,j]==0:
                        perspectiveState[i,j] = -1
                        #print('@', isMax)
                        best = min(best, self.minimax(perspectiveState, not isMax))
                        perspectiveState[i,j] = 0
            #print('#', best)
            return best

    def turn(self, perspectiveState):
        r,c = perspectiveState.shape
        bestVal = -1000
        bestR, bestC = -1, -1
        for i in range(r):
            for j in range(c):
                if perspectiveState[i,j] == 0:
                    perspectiveState[i,j] = 1
                    moveVal = self.minimax(perspectiveState, False)
                    #undo
                    perspectiveState[i,j] = 0
                    if moveVal > bestVal:
                        bestVal = moveVal
                        bestR = i
                        bestC = j
        return bestR, bestC

回答：

我使用了传统的极小化极大算法 没有进行剪枝 。

这就是你问题的答案。这就是为什么剪枝和记住过去状态在算法设计中如此重要的原因。

如果你将棋盘大小增加到4×4，你将面临计算时间的指数增长。如果你估计3×3棋盘上的可能移动数，你会得到(3×3)! = 9!，即362,880种移动。

如果你现在对4×4棋盘上的可能移动做同样的计算，你将得到16!种可能的状态，这是一个极其庞大的数字，约20,922,790,000,000种可能的移动。虽然这些只是近似值，但你可以估计你的计算时间必须增加超过一百万倍。

有关进一步的解释，请参见：井字游戏的极小化极大算法在4×4棋盘上无法正常工作