我最近实现了一个4×4 井字游戏的代码，该游戏使用了极小化极大算法。然而，我的极小化极大函数却无限递归调用自己。
初始棋盘（4×4）井字游戏 ->
board = np.array([['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_']])电脑回合的代码 ->
import mathfrom utility import *def minimax(board, spotsLeft, maximizing): bestIdx = (0,0) p1 = 'X' p2 = 'O' res, stat = checkGameOver(board, spotsLeft) if res==True: if stat == 'X': return 17-spotsLeft, bestIdx elif stat == 'O': return -17+spotsLeft, bestIdx else: return 0, bestIdx if maximizing: # 返回最高分 bestMove = -math.inf for i in range(4): for j in range(4): if board[i][j] == '_': board[i][j] = p1 score, idx = minimax(board, spotsLeft-1, False) print(score, idx) board[i][j] = '_' if bestMove<score: bestMove = score bestIdx = (i,j) return bestMove, bestIdx else: # 返回最低分 bestMove = math.inf for i in range(4): for j in range(4): if board[i][j] == '_': board[i][j] = p2 score, idx = minimax(board, spotsLeft-1, True) print(score, idx) board[i][j] = '_' if bestMove>score: bestMove = score bestIdx = (i,j) return bestMove, bestIdx def ai(board): spotsLeft = 16 p1 = 'X' # 电脑 p2 = 'O' # 玩家 turn = p1 while True: res, stat = checkGameOver(board, spotsLeft) if res==False: if turn == p1: # AI boardCopy = board[:] score, idx = minimax(boardCopy, spotsLeft, True) board[idx[0]][idx[1]] = turn turn = p2 spotsLeft-=1 else: # 人类 inp = int(input(f"Your turn: ")) i, j = spotToIdx(inp) if board[i][j]=='_': board[i][j] = turn turn = p1 spotsLeft-=1 else: return stat printBoard(board)在上述代码中，spotsLeft表示棋盘上的空位数，checkGameOver函数返回”X”（如果玩家X获胜），返回”O”（如果玩家O获胜）以及返回”T”（如果游戏平局）
checkGameOver函数 ->
def checkWin(board): # 检查行 for i in board: if len(set(i)) == 1 and i[0]!='_': return i[0] # 检查列 for i in range(4): if (board[0][i] == board[1][i] == board[2][i] == board[3][i]) and board[0][i]!='_': return board[0][i] # 检查对角线 if (board[0][0]==board[1][1]==board[2][2]==board[3][3]) and board[0][0]!='_': return board[0][0] if (board[0][3]==board[1][2]==board[2][1]==board[3][0]) and board[0][3]!='_': return board[0][3] # 尚未有人获胜 return -1 def checkGameOver(board, spotsLeft): # t -> 游戏平局 # x -> 玩家X获胜 # o -> 玩家O获胜 # 如果平局 - 所有位置已填满 if spotsLeft == 0: return True, 'T' # 如果任何玩家赢得了游戏 result = checkWin(board) if result!=-1: return True, result return False, -1回答：
正如Jenny很好地解释的那样，搜索树太大了。即使你对数据结构和移动机制进行改进，使它们更高效并减少内存占用，仍然难以在可接受的时间内完成搜索。
一般来说，你可以采取以下措施来减少搜索树：
-
在某个搜索深度（如4）停止，并对棋盘进行静态评估。这种评估将是一种启发式方法。例如，它会对三连线上有一个空格可完成胜利的局面给予高分。它还会对未被对手阻挡的线上的两个棋子给予显著的分值，…等等。
-
使用alpha-beta剪枝来避免搜索那些在搜索树早期阶段永远不会导致更好选择的分支。
-
使用杀手移动：在某个对手移动后发现好的移动，也可能在回应另一个对手移动时表现良好。首先尝试这种移动可能与alpha-beta剪枝结合得很好。
-
记忆化已经评估过的位置（通过移动的交换），并将镜像位置映射到等效位置，以减少该字典的大小。
但说实话，4×4井字游戏相当无聊：很容易打成平局，而且需要非常糟糕的移动才会让游戏输给对方。例如，任何玩家都不能做出糟糕的第一步移动。无论他们在第一步做什么，正确的玩法仍然会导致平局。
所以…我建议只使用启发式评估函数，而不进行任何搜索。或者，执行浅层极小化极大，并在该固定深度使用这种启发式评估。但即使用评估函数替换极小化极大算法，也能很好地工作。
需要更改的内容
为了实现这个想法，请按以下步骤进行：
-
用以下代码替换AI部分：
if turn == p1: # AI -- 基于启发式的策略 bestScore = -math.inf bestMove = None for i in range(4): for j in range(4): if board[i][j] == '_': board[i][j] = turn score = evaluate(board, turn) if score > bestScore: bestScore = score bestMove = (i, j) board[i][j] = '_' i, j = bestMove board[i][j] = turn turn = p2 spotsLeft-=1这将调用
evaluate函数，该函数将为给定玩家（参数）提供一个数值分数，分数越高对该玩家越有利。 -
添加
evaluate函数的定义：# 获胜线lines = [ [(i, j) for i in range(4)] for j in range(4)] + [ [(j, i) for i in range(4)] for j in range(4)] + [ [(i, i) for i in range(4)], [(3-i, i) for i in range(4)]]def evaluate(board, player): score = 0 for line in lines: discs = [board[i][j] for i, j in line] # 同一线上的棋子越多越好 value = [1000, 10, 6, 1, 0][sum(ch == "_" for ch in discs)] if "X" in discs: if not "O" in discs: # X仍然有可能在这条线上获胜 score += value elif "O" in discs: # O仍然有可能在这条线上获胜 score -= value # 根据哪个玩家刚刚移动来改变符号 return score if player == "X" else -score
就这样！您可以选择使用evaluate函数来简化checkWin函数：
def checkWin(board): score = evaluate(board, "X") if abs(score) > 500: # 考虑到可能有一些减少 return "X" if score > 0 else "O" # 尚未有人获胜 return -1有了这个实现，您不再需要minimax函数，但您可能想保留它，并限制搜索深度。当达到该深度时，调用evaluate函数，…等等。尽管如此，我发现上述实现玩得还不错。您无法赢得对它的游戏。
