用Python手搓一个“不败”的三子棋AI：从MinMax算法到完整代码实现

用Python手搓一个“不败”的三子棋AI从MinMax算法到完整代码实现三子棋看似简单的3×3棋盘背后隐藏着博弈论的经典算法思想。作为初学者接触AI博弈算法的绝佳切入点本文将带你从零实现一个基于MinMax算法的不败AI。不同于单纯的理论讲解我们会通过可运行的完整代码和交互式调试技巧让你真正理解算法如何做出最优决策。1. 理解MinMax算法的核心思想想象你和AI在下棋时双方都在思考如果我走这一步对方会如何应对对方的最佳应对下我的最优策略是什么这正是MinMax算法的精髓——通过递归模拟双方的最优决策。算法运作遵循三个关键原则最大化自身利益当前玩家MAX方选择使评估值最大的走法最小化对手优势对手MIN方会选择对MAX最不利的走法递归评估从终局倒推计算每个可能状态的价值def minimax(node, depth, is_maximizing): if is_terminal(node) or depth 0: return evaluate(node) if is_maximizing: value -float(inf) for child in generate_moves(node): value max(value, minimax(child, depth-1, False)) return value else: value float(inf) for child in generate_moves(node): value min(value, minimax(child, depth-1, True)) return value表MinMax算法中MAX与MIN的决策对比玩家类型目标评估策略典型应用场景MAX最大化收益选择最大值先手玩家/AIMIN最小化损失选择最小值后手玩家/对手2. 构建三子棋游戏框架在实现算法前需要建立游戏的基本结构。我们使用面向对象的方式设计三个核心组件2.1 棋盘表示与状态判断用3×3的二维列表表示棋盘其中每个元素可以是X、O或_空位。关键是要能快速判断游戏状态class TicTacToe: def __init__(self): self.board [[_ for _ in range(3)] for _ in range(3)] self.current_player X # X先手 def is_winner(self, player): # 检查行 for row in self.board: if all(cell player for cell in row): return True # 检查列 for col in range(3): if all(self.board[row][col] player for row in range(3)): return True # 检查对角线 if all(self.board[i][i] player for i in range(3)): return True if all(self.board[i][2-i] player for i in range(3)): return True return False2.2 游戏树节点设计博弈树中的每个节点需要保存当前棋盘状态、当前玩家、子节点等信息class GameNode: def __init__(self, board, player): self.board [row[:] for row in board] # 深拷贝 self.player player self.children [] self.value None def generate_children(self): for i in range(3): for j in range(3): if self.board[i][j] _: new_board [row[:] for row in self.board] new_board[i][j] self.player next_player O if self.player X else X child GameNode(new_board, next_player) self.children.append(child)注意棋盘状态的深拷贝至关重要否则在递归过程中会意外修改父节点的状态3. 实现MinMax算法核心3.1 评估函数设计对于三子棋评估函数相对简单def evaluate(node): if node.is_winner(X): return 1 elif node.is_winner(O): return -1 else: return 0 # 平局但在更复杂的游戏中如五子棋、象棋评估函数需要考虑更多因素棋子位置优势潜在连珠可能性控制中心区域的程度3.2 递归实现与优化完整的MinMax实现需要考虑递归终止条件和最优解选择def minimax(node, depth, is_maximizing): if node.is_terminal() or depth 0: return evaluate(node) if is_maximizing: max_eval -float(inf) for child in node.children: eval minimax(child, depth-1, False) max_eval max(max_eval, eval) node.value max_eval return max_eval else: min_eval float(inf) for child in node.children: eval minimax(child, depth-1, True) min_eval min(min_eval, eval) node.value min_eval return min_eval表MinMax算法在不同游戏中的复杂度对比游戏类型平均分支因子典型搜索深度优化策略三子棋4-55-7完整搜索五子棋30-503-5Alpha-Beta剪枝国际象棋358-12迭代加深、启发式评估4. 算法优化与交互实现4.1 Alpha-Beta剪枝优化原始MinMax会搜索所有可能路径而Alpha-Beta剪枝可以大幅减少搜索量def alphabeta(node, depth, alpha, beta, is_maximizing): if node.is_terminal() or depth 0: return evaluate(node) if is_maximizing: value -float(inf) for child in node.children: value max(value, alphabeta(child, depth-1, alpha, beta, False)) alpha max(alpha, value) if alpha beta: break # β剪枝 return value else: value float(inf) for child in node.children: value min(value, alphabeta(child, depth-1, alpha, beta, True)) beta min(beta, value) if beta alpha: break # α剪枝 return value4.2 交互式游戏实现最后我们将AI与用户界面结合def play_game(): game TicTacToe() while True: game.print_board() if game.current_player X: # AI回合 print(AI正在思考...) best_move find_best_move(game.board) game.make_move(*best_move) else: # 玩家回合 while True: try: row int(input(输入行(0-2): )) col int(input(输入列(0-2): )) if game.make_move(row, col): break except: print(无效输入!) if game.is_winner(X): print(AI获胜!) break elif game.is_winner(O): print(你获胜!) break elif game.is_draw(): print(平局!) break实际测试中发现当AI先手时如果玩家不犯错误游戏必然以平局收场。这印证了MinMax算法在三子棋中的不败特性——它总能至少保证不输。