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 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

Answer 1

我使用了传统的 minimax 算法而没有 pruning。这已经是你问题的答案。这就是为什么修剪和记住过去的状态是算法设计中如此重要的主题。如果您将电路板大小增加到 4x4，您将获得指数增长并体验计算时间的爆炸式增长。如果您估计 3x3 棋盘中可能的移动次数，您将有 (3x3)！= 9!，等于 362 880 次移动。如果您现在为 4x4 棋盘上的可能动作执行此操作，您将获得 16 个！可能的状态，这是令人难以置信的大量 20 922 790 000 000 个可能的移动。尽管这些只是近似值，但您可以估计您的计算时间必须高出一百万倍以上。