Minimax 算法不适用于 4x4 TicTacToe

Question

好的，所以我为机器人编写了以下代理来玩井字游戏。我使用了没有 p运行ing 的传统 minimax 算法。问题是它非常适合 3x3 板。

但是当我在 4x4 板上运行时，它会卡住计算。我不明白为什么。我正在向代理传递一个 numpy 数组 perspectiveState，其中 0 表示空，1 表示代理移动，-1 表示对手移动。它 returns 下一步 (1) 的位置。

控制流从调用minimax()函数的turn()函数开始。

我做错了什么？

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

Answer 1

I have used the traditional minimax algorithm without pruning .

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

如果您将棋盘大小增加到 4x4，您将呈指数级增长并经历计算时间的爆炸式增长。如果您估计 3x3 棋盘上可能的步数，您将有 (3x3)！ = 9!，等于 362 880 步。

如果您现在对 4x4 棋盘上可能的走法执行此操作，您将得到 16 步！可能的状态，这是数量惊人的 20 922 790 000 000 种可能的移动。虽然这些只是近似值，但您可以估计您的计算时间必须高出一百万倍以上。

更多解释见：

Minimax 算法不适用于 4x4 TicTacToe

Minimax algorithm not working for 4x4 TicTacToe

python

numpy

artificial-intelligence

minimax