最小最大值算法不适用于 4x4 TicTacToe

Question

好的，所以我为机器人编写了以下代理来玩井字游戏。我使用了传统的最小最大值算法，没有修剪。问题是它非常适合 3x3 板。

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

我使用了传统的最小最大值算法，没有修剪。

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

如果将电路板尺寸增加到 4x4，您将呈指数级增长，并经历计算时间的爆炸式增长。如果您估计 3x3 棋盘中可能的移动次数，您将有 (3x3(！= 9！，等于 362 880 次移动。

如果你现在对 4x4 板上可能的移动这样做，你将得到 16！可能的状态，这是一个令人难以置信的 20 922 790 000 000 个可能的移动量。虽然这些只是近似值，但您可以估计您的计算时间必须高出一百万倍以上。

有关进一步说明，请参阅：井字游戏最小值算法不适用于 4x4 板