Minimax 算法不适用于 4x4 井字游戏

Question

好的，所以我为机器人编写了以下代理来玩井字游戏。我使用了传统的极小极大算法而没有修剪。问题是它非常适合 3x3 板。但是当我在 4x4 板上运行它时，它会卡住计算。我不明白为什么。我正在向代理传递一个 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 Truedef 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 0def 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

Answer 1

我使用了传统的 minimax 算法而没有 pruning。

这已经是你问题的答案。这就是为什么修剪和记住过去的状态是算法设计中如此重要的主题。

如果您将电路板大小增加到 4x4，您将获得指数增长并体验计算时间的爆炸式增长。如果您估计 3x3 棋盘中可能的移动次数，您将有 (3x3)！= 9!，等于 362 880 次移动。

如果您现在为 4x4 棋盘上的可能动作执行此操作，您将获得 16 个！可能的状态，这是令人难以置信的大量 20 922 790 000 000 个可能的移动。尽管这些只是近似值，但您可以估计您的计算时间必须高出一百万倍以上。