Minimax实际工程中常写作 Minmax是博弈决策里最基础的一类搜索算法也是很多下棋 AI 的起点。它要解决的问题很简单在两名玩家轮流行动、局面信息完全公开的棋类游戏中如何让程序在有限时间内选出不低于最坏预期的一步棋。这个算法在井字棋、五子棋、国际象棋和各类回合制游戏中都有应用。理解 Minmax 之后再去学习 alpha-beta 剪枝、蒙特卡洛树搜索或者基于神经网络的策略评估都会容易很多。本文用一个可本地运行的 Python 小项目来演示完整链路先设计棋盘和胜负判断逻辑再实现基础 Minmax接着加入 alpha-beta 剪枝最后用命令行对局、测试脚本和参数调整验证 AI 行为。整个学习过程不依赖远程服务环境收敛到本地即可完整复现。项目材料里的 Minmax 相关热词经常指向本地部署方向。实际做这类博弈搜索算法时把运行环境收敛到本地是最高效的方式因为不需要等待网络请求修改评估函数后可以直接观察对局变化。下面从算法原理开始讲起再逐步落到代码、验证和排错。1. 理解 Minmax 算法解决什么问题1.1 从最坏情况理解极大极小先讲通俗含义。下棋时AI 每走一步都要想象后续若干步自己选择对自己最有利的分支同时假设对手会选择对 AI 最不利的分支。Minmax 的价值就是在这两种力量之间取一个平衡。AI 遵守极大原则从所有候选走法中选择收益最高的进入对手回合后递归逻辑自动切换成极小原则假设对手会选择一个让 AI 收益最低的分支。技术定义是Minmax 是一种递归搜索算法它在博弈树中自底向上计算每个节点在双方都按理性决策时的收益。如果当前节点轮到 AI就取所有子节点收益的最大值如果轮到对手就取所有子节点收益的最小值。每层交替取大取小直到搜索到终局或达到深度上限。放到井字棋项目里棋盘就是游戏状态落子产生新状态递归展开直到一方获胜、平局或搜索深度耗尽。Minmax 的返回值不是某一手棋的绝对好坏而是双方后续都正常发挥时当前局面能带给 AI 的期望分数。这里容易产生一个误解Minmax 不是帮 AI 找一条必胜路径而是评估双方都不犯错时 AI 的保底收益。例如井字棋的最优结果通常就是平局所以空棋盘下 AI 先手的最佳分数是 0而不是 10这并不代表算法错了。1.2 为什么必须同时存在极大和极小如果只写一层找最大得分AI 会变成贪心策略只关注眼前收益忽略对手下一回合的反击。Minmax 的递归结构恰好避免了这个问题。用一个最小场景说明。假设 AI 可以在两步内获胜但它先落子在不相干的位置这一步本身可能不产生威胁评估函数会给出一个低分。真正的问题是如果 AI 在一步棋后就形成了一个双威胁结构那么下一步它已经提前锁定胜利。这套推理需要至少搜索到对手的回击层单层搜索做不到。更准确地说Minmax 的极大层负责模拟 AI 的理性选择极小层负责模拟对手的反制。只有把两个视角交替展开AI 才能理解这一步虽然现在有利但对手下一步会立刻反制这种局面。设计递归函数时is_maximizing这个布尔参数就是用来切换两个视角的入口。1.3 为什么博弈树会膨胀以及剪枝的作用井字棋最多 9 层理论搜索空间是 9!也就是 362880 个叶子节点。虽然看起来不多但如果棋盘扩大到五子棋或者国际象棋搜索空间会急速膨胀甚至无法在有限时间内遍历。alpha-beta 剪枝就是为这个问题设计的优化方法。它在递归过程中维护两个边界alphaAI 已经能拿到的最低保证分数。beta对手能接受给 AI 的最高分数上限。当某一个分支的分数已经不可能超过当前已有方案时递归可以直接中断不再展开后面的兄弟节点。剪枝不会改变结果只是把明显不值得探索的分支砍掉。很多新手担心剪枝会漏掉更好的走法实际上 alpha-beta 只处理已经确定不可能改善当前结果的分支所以最终选出的分数和完整搜索一致。2. 本地环境准备与项目结构2.1 运行环境与依赖这个项目只需要 Python 3.8 及以上版本不需要安装任何第三方依赖。为了不让系统中的包环境变得混乱推荐先创建虚拟环境。在项目根目录执行python -m venv .venv source .venv/bin/activateWindows 系统下激活命令是.venv\Scripts\activate如果只跑命令行对局不需要额外库。如果希望用测试框架管理验证用例可以额外安装 pytestpip install pytest也可以不安装 pytest直接使用 Python 内置的assert编写测试函数。下面给出环境要求速查表。软件建议版本用途Python3.8运行算法和测试pytest7.x可选统一执行测试用例操作系统Windows / macOS / Linux本地运行环境均可执行python --version确认 Python 版本。如果输出低于 3.8需要先升级运行环境否则代码中的一些语法可能不兼容。2.2 项目目录结构建议把棋盘逻辑、Minmax 算法、命令行对局和测试分开不要让所有代码都堆在一个文件里。这样后续替换评估函数、增加剪枝逻辑时会更容易定位问题。minmax/ ├── tic_tac_toe.py # 棋盘数据结构、胜负判断、打印棋盘 ├── minimax.py # Minmax 算法、alpha-beta 剪枝、选最优走法 ├── game.py # 命令行人机对局入口 └── tests/ └── test_minimax.py # 测试用例这种拆分不是强制要求但推荐。算法文件只负责计算不负责输入输出棋盘文件只负责状态描述对局入口负责把两者串起来这样测试时可以直接调用算法函数不需要进入交互式循环。2.3 棋盘数据结构设计井字棋棋盘用长度为 9 的一维列表表示索引 0 到 8 对应从左到右、从上到下的九个格子。# 0 表示空1 表示 AI2 表示玩家 board [0] * 9用一维列表的好处是索引计算简单。例如第 i 行的三个格子是i*3、i*31、i*32第 j 列的三个格子是j、j3、j6两条对角线分别是0,4,8和2,4,6。定义一个打印棋盘的函数方便命令行对局时查看当前局面def board_to_str(board): symbols {0: ., 1: X, 2: O} rows [] for i in range(0, 9, 3): rows.append( .join(symbols[v] for v in board[i:i 3])) return \n.join(rows)这个函数把 0、1、2 分别映射成点、X、O。学习阶段保留数字可以但真正对局时符号更直观。该函数只用于展示不影响内部计算。3. 用 Python 实现 Minmax 算法3.1 先写胜负判断Minmax 最依赖的基础函数是胜负判断。只有判断出终局递归才知道应该返回分数。定义所有能获胜的三连位置WIN_LINES ( (0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6), ) def winner(board): for a, b, c in WIN_LINES: if board[a] ! 0 and board[a] board[b] board[c]: return board[a] if all(v ! 0 for v in board): return 0 return None返回值的含义返回 1 或 2表示对应玩家获胜。返回 0表示棋盘已满且没有人获胜即平局。返回 None表示还未结束。注意返回顺序。先判断是否有三连再判断是否平局这个顺序不能颠倒。如果棋盘满了但最后一步形成了三连应该优先返回获胜方否则会被误判为平局。3.2 基础 Minmax 递归先写核心的递归函数。参数中的is_maximizing表示当前层轮到 AI 决策还是对手决策。def empty_cells(board): return [i for i, v in enumerate(board) if v 0] def minimax(board, depth, is_maximizing, ai_player1): result winner(board) if result ai_player: return 10 * (depth 1) if result 0: return 0 if result is not None: return -10 * (depth 1) if is_maximizing: best -float(inf) for move in empty_cells(board): board[move] ai_player score minimax(board, depth 1, False, ai_player) board[move] 0 best max(best, score) return best else: best float(inf) opponent 3 - ai_player for move in empty_cells(board): board[move] opponent score minimax(board, depth 1, True, ai_player) board[move] 0 best min(best, score) return best关键点有三个。第一终局分数的计算使用10 * (depth 1)而不是固定返回 10。AI 获胜且深度越小说明赢得越快分数越高。对手获胜返回负数也是越快输分越差。这样 AI 在做选择时不仅知道哪步能赢还能在多条获胜路线里优先选择最快的一条。第二每次试探性落子之后必须把棋盘恢复原状也就是执行board[move] 0。这一步经常被漏掉漏掉之后递归分支会相互污染导致 AI 看到一堆根本不存在的棋子。第三is_maximizing用于切换视角。AI 层求最大值对手层求最小值。如果整个函数都写成了求最大值AI 就无法预判对手的反击。得到每个候选走法的分数后再选出最优位置import random def best_move(board, ai_player1): best_score -float(inf) best_moves [] for move in empty_cells(board): board[move] ai_player score minimax(board, 0, False, ai_player) board[move] 0 if score best_score: best_score score best_moves [move] elif score best_score: best_moves.append(move) return random.choice(best_moves) if best_moves else None为什么累积best_moves然后随机选一个因为很多局面下多个位置都是最优解固定选第一个会让 AI 的走法千篇一律削弱对局的观赏性和练习价值。随机选择不会降低棋力因为分数相同的走法在理论上具有相同的最坏预期收益。3.3 加入 alpha-beta 剪枝基础 Minmax 在小棋盘上可以工作但为了让读者理解性能优化需要实现 alpha-beta 剪枝。这里维护两个参数alpha表示 AI 已经得到的最大保底值beta表示对手能接受的最小限制值。def minimax_ab(board, depth, alpha, beta, is_maximizing, ai_player1): result winner(board) if result ai_player: return 10 * (depth 1) if result 0: return 0 if result is not None: return -10 * (depth 1) if is_maximizing: best -float(inf) for move in empty_cells(board): board[move] ai_player best max(best, minimax_ab(board, depth 1, alpha, beta, False, ai_player)) board[move] 0 alpha max(alpha, best) if beta alpha: break return best else: best float(inf) opponent 3 - ai_player for move in empty_cells(board): board[move] opponent best min(best, minimax_ab(board, depth 1, alpha, beta, True, ai_player)) board[move] 0 beta min(beta, best) if beta alpha: break return best调用best_move_ab时初始alpha设为负无穷beta设为正无穷因为一开始 AI 还没有找到任何候选分数。def best_move_ab(board, ai_player1): best_score -float(inf) best_moves [] for move in empty_cells(board): board[move] ai_player score minimax_ab(board, 0, -float(inf), float(inf), False, ai_player) board[move] 0 if score best_score: best_score score best_moves [move] elif score best_score: best_moves.append(move) return random.choice(best_moves) if best_moves else None这里的剪枝条件beta alpha意味着在当前层已经可以肯定无论继续探索多少兄弟分支都无法改变祖先层的最优选择。于是安全地停止循环。剪枝不改变返回值只减少搜索时间。3.4 评估函数如何影响分数形态上面的实现等价于一个最简单的评估函数终局时返回正负固定分平局返回 0。当棋盘更大、搜索无法到达终局时就必须在深度截断处用一个评估函数给中间局面打分。评估函数通常返回一个连续值范围不一定是整数。例如可以给连成二子的棋型加分给占据中心或四角的位置加权也可以把已方威胁和对手威胁的差值作为评分。这些计算组合起来后输出就会出现类似9.93、-3.5这样带正负和小数的评估分数。项目材料里出现类似crazy9.93的评估符号可以理解为一种把某个局面的优势量化为带符号数值的表达。正数表示对 AI 有利负数表示不利数字绝对值越大代表优势或劣势越明显。Minmax 本身不关心评估值是整数还是小数它只负责在搜索树中传播这些分数并选择极值。4. 本地运行与对局验证4.1 命令行对局有了算法函数之后编写一个简单的命令行交互入口。文件game.py负责接收玩家的落子输入并调用 AI 选择落子位置。from tic_tac_toe import board_to_str, empty_cells, winner from minimax import best_move_ab as best_move def main(): board [0] * 9 ai_player 1 current_player 1 while True: print(board_to_str(board)) result winner(board) if result is not None: if result 0: print(平局) elif result ai_player: print(AI 获胜) else: print(玩家获胜) break if current_player ai_player: move best_move(board, ai_player) board[move] ai_player print(fAI 落子位置: {move}) else: try: move int(input(请输入落子位置 0-8: )) except ValueError: print(输入必须是数字) continue if move 0 or move 8 or board[move] ! 0: print(非法落子) continue board[move] 3 - ai_player current_player 3 - current_player if __name__ __main__: main()启动命令python game.py这个入口把输入校验、输赢判断和 AI 调用串起来。要注意3 - ai_player的写法因为玩家棋子和 AI 棋子分别是 1 和 2两边轮流落子时3 - 1 23 - 2 1正好互相切换。4.2 用测试用例验证算法行为命令行对局适合人工体验但验证算法正确性最好用自动化测试。下面的测试用例覆盖三种典型场景赢得胜利、及时阻挡、空棋盘最优分数。from minimax import best_move from tic_tac_toe import winner def test_take_winning_move(): board [1, 1, 0, 2, 2, 0, 0, 0, 0] assert best_move(board, ai_player1) 2 def test_block_opponent(): board [0, 0, 0, 0, 0, 0, 2, 2, 0] assert best_move(board, ai_player1) 8 def test_empty_board_best_score_is_zero(): board [0] * 9 assert best_move(board, ai_player1) is not None def test_already_won(): board [1, 1, 1, 0, 0, 0, 0, 0, 0] assert winner(board) 1执行测试pytest tests/test_minimax.py -v如果没安装 pytest也可以直接写一个脚本文件逐个执行并打印结果python -c from tests.test_minimax import *; test_take_winning_move(); test_block_opponent(); print(ok)这些测试覆盖的不只是算法能跑而是算法在关键局面上做出了正确的战术选择。能通过测试说明胜负判断、递归终止条件、极值选择逻辑没有明显问题。4.3 验证剪枝没有改变结果写一个统计节点数的版本或者用全局计数器。下面以全局计数的方式演示node_count 0 def minimax_count(board, depth, is_maximizing, ai_player1): global node_count node_count 1 result winner(board) if result is not None: return 0 if result 0 else (10 * (depth 1) if result ai_player else -10 * (depth 1)) if is_maximizing: best -float(inf) for move in empty_cells(board): board[move] ai_player best max(best, minimax_count(board, depth 1, False, ai_player)) board[move] 0 return best else: best float(inf) opponent 3 - ai_player for move in empty_cells(board): board[move] opponent best min(best, minimax_count(board, depth 1, True, ai_player)) board[move] 0 return best调用后统计节点数。由于剪枝效果与节点访问顺序密切相关不同实现得到的节点数可能不同。实际运行时会发现alpha-beta 剪枝后的节点数明显小于基础版本但返回的最优分数一致。如果出现分数不一致优先检查递归中的棋盘恢复、alpha/beta 更新位置和极大极小层是否匹配。实现方式节点计数方式结果基础 minimax每次进入递归函数加 1节点数较多alpha-beta 剪枝每次进入递归函数加 1节点数明显下降两者分数对同一局面调用应保持一致4.4 调整搜索深度和随机性井字棋可以穷尽搜索所以不需要设置深度限制。但扩展到更大的棋类游戏时必须增加一个max_depth参数在递归到达深度上限时调用评估函数截断搜索避免陷入指数级的时间开销。随机性来自best_move中random.choice(best_moves)。如果把随机选择去掉AI 每次都选第一个最优位置对局会显得机械。随机选一个最优位置不会降低 AI 强度还能让同一个程序产生不同的对局过程调试时更有价值。这里有一个典型参数选择问题搜索深度越大AI 越强耗时越长评估函数越精细AI 在截断位置越有方向性但实现复杂度越高。学习阶段建议先用完整搜索跑通井字棋再去尝试深度限制和复杂评估函数。5. 常见问题排查5.1 程序卡住或递归过深现象点击运行后长时间没有输出CPU 占用很高。可能原因递归缺少终止条件或者棋盘状态在递归中没有正确减少。尤其容易出错的是落子后没有判断终局导致递归在已经填满的棋盘上继续尝试空位。检查方式打印递归入口的board和depth观察棋盘是否越变越满。确认winner(board)是否在平局和胜负两种情况下都正确返回非 None。确认empty_cells(board)在满棋盘时返回空列表否则极大极小层会一直循环。处理建议在递归开头先判断终局再判断空位列表。如果空位列表为空但游戏还没结束说明胜负判断逻辑有误。问题现象常见原因检查方式处理建议递归不停止缺少终局判断打印 board 和 winner 返回值优先处理胜利和平局分支程序卡死落子后没恢复棋盘状态打印每次递归的 board检查board[move] 0是否执行5.2 AI 走法不聪明现象程序能运行但 AI 经常错过立即获胜或阻挡对手的走法。可能原因winner判断错误导致递归提前终止或者is_maximizing层写反AI 层选最小、对手层选最大或者评估函数分数正负没有统一。检查方式先用最简单的测试用例验证。构造一个 AI 一步能赢的局面检查best_move是否返回正确位置。再构造对手一步能赢的局面检查 AI 是否选择阻挡。处理建议按顺序检查胜负判断、终局分数、极大极小层逻辑。一个很实用的做法是从只有 1 个空位的棋盘开始测试确认递归结果正确后再逐步增加空位数量。5.3 修改棋盘后没有恢复状态现象AI 的走法看起来非常奇怪甚至把对手的棋子当成自己的棋子来规划。这是最隐蔽的坑之一。递归试探落子后如果忘记把board[move]恢复为 0那么同一个棋盘对象会在多条递归分支之间共享被污染的状态。调试时很难通过单步观察发现因为问题会呈指数级扩散。典型错误写法board[move] ai_player score minimax(board, depth 1, False, ai_player) # 缺少 board[move] 0推荐写法board[move] ai_player score minimax(board, depth 1, False, ai_player) board[move] 0如果出现这种问题可以用一个小的手动用例排查构造三步以内的局面递归时打印每次落子和恢复后的棋盘对比状态是否一致。5.4 剪枝结果与完整搜索不一致现象minimax_ab返回的分数或走法和minimax不一致。可能原因alpha和beta的初始值写成了固定数字而不是正负无穷。在极大层更新了beta或者在极小层更新了alpha。剪枝条件写成了alpha beta在相等时才剪枝导致少剪或误剪。递归调用时把alpha和beta传反了。处理建议先写单测对同一局面分别调用minimax和minimax_ab比较返回值。如果不一致在剪枝函数开头打印当前 alpha、beta、is_maximizing 和 board。比较完整搜索和剪枝搜索在第一个分歧节点上的差异。5.5 排查顺序清单遇到任何 Minmax 相关问题建议按这个顺序排查先确认输入棋盘是否正确棋子是否用 0、1、2 表示。再确认winner是否覆盖所有胜利线和平局。检查递归终止条件是否完整。检查递归落子后是否恢复棋盘状态。检查极大极小层的选值方向是否写反。若启用剪枝检查 alpha 和 beta 的更新位置。最后检查评估函数符号方向是否与 AI 视角一致。6. 最佳实践与扩展方向6.1 学习环境与生产环境的差异学习阶段用一段几百行的 Python 脚本验证算法完全够用。但到了生产环境哪怕是做一个游戏 AI 服务都要额外考虑几件事维度学习环境生产环境配置常数写死在代码里配置外置走配置文件或环境变量日志print 调试结构化日志记录搜索耗时、走法、异常监控无统计每局平均搜索耗时、节点数、AI 胜负率异常处理忽略递归超时、非法棋盘、输入越界都要兜底回滚无如果算法版本有问题可以快速切回旧版本性能追求跑通设置最大搜索深度或搜索时间上限比如生产环境不能容忍一个极端局面导致递归 30 层不结束所以必须设置max_depth。也不能在服务器上打印大量调试信息而应该把关键节点输出到日志系统。6.2 可复用检查清单在把 Minmax 相关代码提交或发布之前建议做一次清单检查胜负判断是否覆盖了所有胜利线、平局和未结束三种状态。递归中每次试探性落子后是否恢复了棋盘。minimax和minimax_ab对同一局面的分数是否一致。是否存在最大深度限制防止极端情况递归过深。评估函数是否返回了统一视角的分数例如都以 AI 为正方向。命令行或接口层是否处理非法输入。日志中是否包含搜索深度、访问节点数、选出的走法和耗时。是否预留了调参入口例如深度、评估函数权重、随机种子。6.3 从井字棋扩展到更复杂棋类井字棋是 Minmax 的最小载体但真正体现算法价值的是五子棋、黑白棋、国际象棋等更大棋类。扩展时通常要做四件事。第一把一维棋盘改成二维数组或者继续用一维索引但重新计算连成线的方向集合。五子棋需要检查横、竖、正斜、反斜四个方向的连续子数。第二重写评估函数。因为五子棋无法在规定时间内搜索到终局评估函数必须能在任意中间局面给出分数例如给双活三等棋型加权。第三加入缓存。使用 Zobrist 哈希把常见局面映射到已计算分数可以避免同一局面在搜索树的不同位置重复计算。第四考虑换成蒙特卡洛树搜索。当评估函数难以设计或者搜索空间过大时MCTS 通过随机模拟和统计选择来弥补 Minmax 的不足。Minmax 的极大极小思想仍然有价值只是换了一种更适应大规模搜索的表达方式。6.4 对新手最有价值的练习建议如果要把这篇文章的内容真正变成自己的能力可以尝试三个递进练习。第一个练习是把棋盘尺寸改成 4x4 的井字棋观察搜索树规模的变化。4 格连成一线获胜时Minmax 的搜索时间会明显上升这时就体会到 alpha-beta 剪枝和深度限制的必要性。第二个练习是设计一个连续取值的评估函数在 3x3 棋盘上打印每个空位对应的评估分数。观察中心位置分数是否高于角落角落是否高于边线理解评估函数对 AI 行棋风格的影响。第三个练习是给minimax_ab加入一个缓存字典统计缓存命中后节点数下降了多少。这个练习可以平滑过渡到更高级的棋类 AI 学习。把 Minmax 手写过一遍之后最重要的事情是理解它天然适合的目标有限状态、轮流出招、信息完整。遇到这类问题可以先写一个 Minmax 版本作为基线再根据性能瓶颈决定是否剪枝、限制深度或者换用蒙特卡洛树搜索。