本科三年级计算机科学与技术（AI方向）：博弈树搜索算法深度教学教案

本科三年级计算机科学与技术（AI方向）：博弈树搜索算法深度教学教案

一、课程定位与内容分析

本教案服务于本科三年级计算机科学与技术专业人工智能方向核心必修课程“人工智能原理”，置于教材第五章“搜索与求解”第二节。该内容前承无信息搜索与启发式搜索，后启强化学习与深度博弈网络，是学生从确定性单智能体规划过渡至多智能体对抗决策的核心枢纽。课程选取完备信息零和博弈为研究载体，以博弈树为结构模型，系统讲授Minimax算法、Alpha-Beta剪枝及其工程实现，并延伸至蒙特卡洛树搜索思想。依据ACM/IEEE计算课程体系规范CS2023，本内容属于“智能系统”知识领域中的核心算法模块，具有极高的理论密度与工程迁移价值。【基础基石】【非常重要】

二、教学目标层级矩阵

依据布鲁姆认知目标修订版与工程教育认证毕业要求指标点，构建三层九维目标体系。知识维度：学生能够准确复述博弈树、节点类型、深度、分枝因子等基本术语；能够默写Minimax递归伪代码；能够阐述Alpha-Beta剪枝的边界更新规则与剪枝条件；能够列举影响剪枝效率的关键因素。【基础】【高频考点】能力维度：学生能够手工推演深度三以内的博弈树估值过程；能够基于Python实现井字棋博弈搜索并集成剪枝优化；能够运用复杂度分析方法对比剪枝前后的节点扩展数量；能够针对新棋类任务设计简化的评估函数。【非常重要】素养维度：学生能够建立“对手理性假设”的建模意识；在调试递归程序过程中形成系统化排错思维；通过对抗性编程体验工程决策中的时间-质量权衡；初步形成从精确搜索向近似采样过渡的认知弹性。【核心素养】【热点】

三、教学阻塞点与应对策略

精准锁定三重阻塞点。阻塞点一：Minimax递归回溯时极大极小角色切换混乱。对策：采用“双色磁贴教具”，红色代表MAX层求最大，蓝色代表MIN层求最小，学生在物理层面移动磁贴模拟递归返回时的数值更新。阻塞点二：Alpha-Beta剪枝中α、β参数在递归调用链中的传递与更新规则。对策：设计递归栈可视化插件，每层栈帧上方悬浮显示当前α、β区间，学生拖动滑块调整子节点顺序实时观察剪枝触发位置。阻塞点三：评估函数设计与博弈态势量化之间的映射鸿沟。对策：引入线性加权模板，将棋子数量、控制区域、机动性等特征量化为可调参数，通过网格搜索观察不同权重对走子风格的影响。【难点】【高频考点】

四、教学环境与资源预制

构建高仿真工业级教学环境。硬件层面：配置双屏教师工位与六角形学生机位，便于小组代码会诊。软件层面：预制基于Python3.11的博弈树教学套件，内置TicTacToe、ConnectFour、Gomoku三类环境，均遵循Gymnasium接口规范。可视化层面：集成递归追踪器pytutor-web与剪枝过程热力图生成模块。数据层面：预生成不同深度、不同子节点顺序的博弈树测试集，支持批量回归测试。资源层面：学习通平台搭建“博弈算法攻防战”主题讨论区，上传DeepBlue技术史记原版论文节选、AlphaGoZeroNature论文插图集，供学有余力者研读。【教学保障】【拓展资源】

五、教学实施过程（核心环节）

本部分为教案主体，按两学时、每学时45分钟精细切割，每5分钟为一个教学微单元，全程标注知识权重与认知水平要求。

（一）课前悬置与认知预热

课前48小时通过学习通向学生推送博弈悖论案例：西洋跳棋程序Chinook在1994年击败人类冠军，其核心算法正是经过高度优化的Alpha-Beta剪枝。同时发布预学任务单，要求学生观看自制微课“从迷宫到棋局——搜索问题的形式化统一”，完成博弈树基本结构的思维导图。教师在课前汇总学生导图中出现的共性错误——约35%的学生将博弈树与决策树概念混淆，错误认为内部节点均代表智能体选择。此诊断数据直接植入课堂导入环节，实现精准纠偏。【预学分析】【基础夯实】

（二）第一学时：Minimax算法建构与递归思维驯化

1.认知冲突创设与问题域界定（5分钟）

教师展示人类棋手与GNUChess对弈录像，暂停于中局时刻，提问：若程序仅能向前看一步，如何决定当前走子？学生自然回应“选择评估最高的位置”。教师随即展示下一步对手反杀的局面，学生意识到单步贪婪极易陷入陷阱。此时板书核心命题：在对手同样追求最优的前提下，我的最优决策是什么？由此引出vonNeumann博弈论基本定理，在黑板左侧永久板书“零和博弈·极大极小等价”【核心信念】【非常重要】

2.博弈树数学建模（8分钟）

教师以井字棋初始空盘为例，在黑板逐步构建深度为2的部分博弈树。严格定义三个集合：节点集S，每个节点s包含完整盘面编码；边集E，每条边e标记走子坐标；根节点s0为当前实际盘面。首次区分终局节点与非终局节点，终局节点评估值为｛1，0，-1｝对应胜、平、负。特别强调：在博弈树中，奇数层通常为MAX方行动，偶数层为MIN方行动，此约定后续直接影响递归函数中极值运算符的选择。此时插入Nearpod即时选择题，呈现四棵局部树结构，要求学生识别哪一棵符合“MAX-MIN交替且叶子已赋值”的规范。正确率82%，教师针对错误选项剖析角色分配颠倒的典型案例。【高频考点】【基础】

3.Minimax递归形式化推演（12分钟）【非常重要】

教师摒弃直接展示伪代码的传统教法，改为现场“活代码”编程。打开JupyterLab，新建空白单元格，以函数minimax(board,depth,isMaxTurn)为骨架，通过对话式提问逐行填充。第一问：递归出口是什么？学生答：游戏结束或depth为零。第二问：返回值类型？学生答：数值，表示当前局面对MAX方的最终优势。第三问：如何生成子节点？学生调用预定义的get_valid_moves与make_move函数。第四问：在递归调用时isMaxTurn参数如何变化？学生明确应取反。第五问：子节点返回值如何聚合成当前节点值？此时分歧出现，部分学生习惯性写max(scores)或min(scores)。教师不直接纠正，而是在两个分支分别写max和min，并故意写反，运行代码评估初始局面，得到明显反直觉的走子建议。学生哄笑中深刻铭记：MAX层聚合一众子节点评估值时必须取最大，MIN层必须取最小。此环节将语法错误转化为概念冲突，记忆留存率极高。

随后教师演示pyTutor可视化，设置初始盘面“X下左上角，O下正中”，递归深度设为3。学生清晰看到递归函数反复入栈出栈，每次入栈生成新局，每次出栈返回评估值，栈顶不断更替，最终根节点获得回传值-1（即初始局面必败）。有学生惊呼：“原来不是程序笨，是开局就输了！”课堂爆发掌声。【深度理解】【高频考点】

4.纸牌推演与角色扮演（10分钟）

全班分为12组，每组领取一幅大型博弈树挂图，树深度3，叶子节点已标注浮点型评估值（-5至+5）。组内角色轮换：扮演MAX者负责在偶数层求极大，扮演MIN者负责在奇数层求极小，扮演递归控制器者负责指引当前应该展开哪个子节点并记录返回值。教师巡视发现经典错误——部分组在MIN层忘记将子节点值先取反（若评估函数始终以MAX方视角），立即组织30秒微教学：强调评估函数视角一致性原则，要么始终从当前走子方视角给出估值，要么始终从MAX方视角估值，两者在递归回溯时需进行符号转换。各组修正后均得出正确的根节点估值-2。每组提交推演挂图，作为过程性评价依据。【合作学习】【重要】

5.代码半成品填空与差异化指导（8分钟）

学生打开本地实验环境，教师提供TicTacToe类，已实现棋盘表示、合法动作生成、输赢判断、简易评估函数（仅计算双方棋子数量差）。学生任务仅需补全minimax函数中递归调用与极值聚合部分，约15行代码。现场通过GitHubClassroom自动分发模板，教师使用LiveShare插件同时观察多位学生的编辑光标。发现共性问题：部分学生递归调用时传入depth-1但忘记切换isMaxTurn标志；个别学生使用Python内置max()函数但试图传入空列表。教师针对前者推送弹窗提示，针对后者引导学生思考递归深度到达0但局面未结束时的处理策略——应返回静态评估值而非抛出异常。8分钟内，87%的学生代码通过预置的3个单元测试用例。【实践达标】【高频考点】

6.第一学时总结与概念锚定（2分钟）

教师以板书收束：Minimax=深度优先遍历+递归回溯+交替极值。明确告知学生本节课内容是整个对抗搜索的“道”，后续所有剪枝、启发、采样均为此框架的优化，不具备可替代性。要求学生当晚闭卷默写递归核心四行代码，次日随机抽查。【知识固化】

（三）第二学时：Alpha-Beta剪枝与效率思维跃迁

1.计算复杂性危机渲染（5分钟）

教师投影展示井字棋完整博弈树统计量：5478个不同局面，26830条边，若每节点评估耗时1微秒，全树遍历需27毫秒。随即切换至国际象棋：平均分枝因子35，平均对局深度80，节点总数35^80，人类已知宇宙原子数量级。学生发出惊叹。教师追问：假如给你2秒钟完成一步棋，如何只搜索万分之一甚至亿分之一的节点依然保证决策质量？学生提出“只看看起来好的分支”。教师高度肯定，并点明Alpha-Beta剪枝正是将这种直觉算法化的典范。【认知危机】【热点切入】

2.剪枝区间数学建模（10分钟）【非常重要】【难点】

教师摒弃照本宣科定义αβ，采用“谈判区间”隐喻。设MAX为购房者，心理价位底线α，低于α绝不成交；MIN为售房者，心理价位底线β，高于β绝不售出。双方在交易过程中动态调整底线：MAX遇到优质盘会提升α，MIN遇到劣质盘会降低β。一旦α≥β，意味着买家底线超越卖家底线，交易必然达成，后续看盘毫无意义。此隐喻高度贴合αβ剪枝本质，学生顿悟表情明显。

继而形式化：α初始为-∞，β初始为+∞。在MAX层，遍历子节点过程中α=max(α,child_value)，若α≥β则剪枝剩余子节点；在MIN层，β=min(β,child_value)，若β≤α则剪枝。教师同步使用自制HTML5动画，左侧显示博弈树，右侧悬浮显示当前节点路径上的αβ区间。动画逐帧推进至第一个剪枝点，全班自发鼓掌。【可视化突破】【高频考点】

3.剪枝条件推导与边界测试（8分钟）

教师分发纸面练习题，博弈树深度3，给定子节点访问顺序为[3,17,2,5,12]（叶子值）。学生需标出哪些子节点被剪枝。大部分学生能正确剪掉第4、5个子节点。教师追问：若将子节点顺序调整为[17,12,5,3,2]，剪枝数量如何变化？学生计算发现只有第一个子节点被完全展开，其余全部剪枝，剪枝率从40%提升至80%。教师顺势引出启发式排序的核心价值：子节点按估值降序排列可最大化剪枝效率。这一结论成为后续评估函数设计的隐性驱动力。【重要】【高频考点】

4.代码迭代与剪枝植入（12分钟）【实践核心】

学生基于第一学时完成的Minimax代码，添加α、β参数并嵌入剪枝判定。教师巡回观察，发现三大典型错误。错误A：在MAX层剪枝条件写成ifvalue>betabreak，混淆了α与β的角色。错误B：递归调用时传入alpha,beta但忘记在MIN层交换参数位置。错误C：根节点调用时alpha,beta初始化为0,0而非负无穷正无穷。教师选择一份包含错误B的代码，投影至大屏，全班共同执行逻辑走查。当追踪至第三层递归时，有学生发现MIN层传入的beta值居然是-∞，迅速定位到调用语句写反了alpha与beta。修正后剪枝功能生效，扩展节点数从127骤降至59，学生真切感受到几十行代码带来的指数级收益。【工程难点】【成就感培养】

5.剪枝效率对照实验（5分钟）

学生运行教师预置的批量测试脚本，随机生成100个初始盘面，分别使用Minimax与Alpha-Beta搜索深度6，统计平均扩展节点数。全班数据汇总至共享表单，生成箱线图。数据显示Minimax中位数扩展节点约3200，Alpha-Beta中位数约800，剪枝率75%。但极少数测试用例剪枝率不足20%，学生分组讨论发现这些用例均为开局阶段，合法动作多且评估值相近，启发式排序失效。教师总结：剪枝不是银弹，需配合走子顺序启发式，引入杀手启发与历史启发表可进一步优化。【实证素养】【热点】

6.对抗锦标赛与经验萃取（5分钟）

各小组将最终代码提交至擂台服务器，服务器随机配对进行井字棋百轮大战。排行榜实时滚动，学生发现并非代码完全正确就能登顶——搜索深度设置、评估函数细微差异、平局处理策略均影响胜率。冠军组分享其评估函数在基础棋子差之外额外奖励中心控制与边角优势，亚军组反思其剪枝虽快但深度浅导致战术短视。教师总结时强调：算法理论正确性与工程性能优化是两座山峰，本节课跨越了第一座，第二座需在后续课程与项目中持续攀登。【综合应用】【激励评价】

（四）课后分层拓展与学科融合

学习通发布三层贯通任务群。基础层：阅读教材“迭代加深搜索”节段，回答为何在实时对弈系统中不能固定深度而必须采用逐步加深策略，并以井字棋为例估算时间曲线。【基础巩固】进阶层：将Alpha-Beta剪枝算法移植至四子棋环境ConnectFour，自行设计评估函数，要求至少包含连续棋子计数与潜在连四可能性特征，提交代码至GitHub私有仓库并邀请教师评审。【能力跃迁】【高频应用】挑战层：精读AlphaGoZeroNature论文中关于MCTS的描述，撰写技术述评，对比蒙特卡洛树搜索与Alpha-Beta剪枝在搜索空间利用策略上的根本分野——前者是可变模拟次数的不对称搜索，后者是固定深度的对称剪枝，并论述为何围棋无法直接套用Alpha-Beta。【前沿视野】【学术潜质】

六、教学评价量规与反馈闭环

构建三维九级评价量规。维度一：算法理解力，从博弈树结构识别、Minimax递归追踪、剪枝条件判定三个水平层级评定。维度二：工程实现力，从代码语法正确性、边界条件覆盖度、效率优化意识三个水平层级评定。维度三：迁移设计力，从新棋类环境适配、评估函数原创性、实验对比规范性三个水平层级评定。评价主体包括教师、结对伙伴、自评三方权重4：3：3。每份代码作业均通过GitHubActions自动运行测试用例并生成测试报告，报告直接关联量规指标，实现评价即反馈、反馈即改进。单元结束时进行十分钟限时纸笔测验，典型题目为“给定一棵部分展开的博弈树及αβ初始值，请写出深度遍历过程中每个节点返回时的αβ值并圈出被剪枝的分支”。该题精准命中剪枝参数传递难点，历年区分度高达0.7以上。【科学评价】【高频考点】

七、教学预案与弹性调节

针对可能出现的技术意外与认知断裂准备三级预案。一级预案：若机房网络故障导致代码无法远程同步，立即切换至单机版Docker镜像环境，所有预制环境已打包至镜像，学生启动容器即得完整实验栈。二级预案：若Alpha-Beta剪枝动画演示出现卡顿，教师启用磁性黑板贴片教具，通过手动移动红蓝磁条模拟αβ区间收缩，保证教学流程不中断。三级预案：若前序递归概念薄弱学生占比超过40%，临时压缩剪枝证明时长，增设5分钟递归函数专项辨析环节，利用parson