大学本科计算机科学与技术专业《随机化对抗搜索算法》教案

大学本科计算机科学与技术专业《随机化对抗搜索算法》教案

一、课程基本信息

（一）学科与学段：计算机科学与技术专业，大学本科三年级第二学期，人工智能方向核心选修课程。

（二）课程性质：专业高阶选修课，定位于算法设计与博弈决策的交汇前沿，兼具理论深度与工程实践属性。

（三）课时安排：总计4学时，每学时50分钟，建议连续两周双学时段实施。

（四）先修课程要求：概率论与数理统计、数据结构与算法、人工智能导论。学生必须熟练掌握博弈树搜索基本范式，熟悉期望值计算、伯努利试验、置信区间基础概念，并具备Python面向对象编程能力。

（五）教材与核心参考文献：自编数字化讲义及经典教材《人工智能：一种现代方法》第5章“对抗搜索”；指定必读综述《蒙特卡洛树搜索：算法、理论与实践》，并提供AlphaGoZero原始论文节选作为拓展材料。

二、教学目标

（一）知识与技能目标

第一，准确复述随机化对抗搜索的本质特征，并将其与传统确定性对抗搜索进行结构化对比。【基础】

第二，独立绘制蒙特卡洛树搜索（MCTS）四阶段流程图，并能口头解释每一阶段的计算目标与实现约束。【核心概念】【非常重要】

第三，手动执行小型博弈树（深度≤4，分支因子≤3）的UCT选择与反向传播推演，计算节点访问次数及胜率估计值。【关键技能】【高频考点】

第四，使用Python语言在给定框架内补全MCTS核心模块，实现一个能在井字棋环境中以超过90%胜率击败随机走子对手的博弈智能体。【高频考点】【热点】

（二）过程与方法目标

通过算法伪代码的渐进重构、可视化模拟程序的观察分析、完整代码实现与调试，培养学生将不完全信息或随机性博弈问题转化为蒙特卡洛采样模型的能力，强化“以随机模拟逼近复杂期望值”的计算思维。

（三）情感态度与价值观目标

深刻理解随机化方法在破解围棋等此前被认为不可逾越的博弈难题中所扮演的革命性角色，体会从AlphaGoFan到AlphaGoZero的算法迭代中蕴含的工程简约主义美学，激发对人工智能前沿研究的学术志趣与跨学科迁移意识。

三、教学重难点

（一）教学重点

第一，蒙特卡洛树搜索标准流程中四个阶段（选择、扩展、模拟、反向传播）的严格定义与衔接逻辑。【非常重要】

第二，置信上限（UCB1）公式的结构解读及其在树搜索中平衡探索与利用的核心机制。【难点】【高频考点】

第三，模拟策略（默认走子策略）的设计对收敛速度与最终决策质量的影响，以及速度-精度的典型权衡。【热点】

（二）教学难点

第一，UCB1公式中均值项与置信区间项的动态耦合关系，以及探索常数C的物理意义与调参经验法则。【难点】【非常重要】

第二，多玩家或非零和博弈环境下回报符号反向传播的正确翻转逻辑，尤其避免玩家视角混淆导致的更新方向错误。

第三，MCTS算法在有限模拟次数下无法保证收敛的理论边界，以及冷启动阶段节点价值估计偏差极大的缓释策略。

四、教学准备

（一）教师准备

开发基于PyQt的蒙特卡洛树搜索可视化演示程序，支持实时显示树结构、节点访问次数、UCB值及模拟路径高亮；编写井字棋、四子棋两套完整MCTS代码模板，保留核心方法空缺作为课上练习素材；整理AlphaGoZero、OpenAIFive、DeepNash等系统中MCTS应用的视频切片与架构图；课前于学习平台发布预习任务：复习极大极小算法并完成UCB公式基本符号映射练习。

（二）学生准备

回顾概率论中伯努利试验均值的方差计算公式；阅读讲义中关于多臂老虎机问题与UCB算法的类比段落；安装Python3.8及以上版本，配置NumPy、Matplotlib库，并确保能够运行教师提供的棋盘环境测试脚本。

五、教学实施过程

第一课时随机化对抗搜索的思想奠基与朴素方法

（一）认知冲突导入︱8分钟

教师直接投影围棋棋枰，提问：“假设当前局面分支因子超过200，搜索深度达到150，传统α-β剪枝即便配合迭代加深也无法在合理时间内给出应手。更棘手的是，对手可能并非最优玩家，甚至包含故意随机落子的干扰策略。此刻，我们应依赖何种计算哲学？”学生短暂分组交流，黑板记录下各组直觉关键词：抽样、统计、随机对局、概率。教师顺势总结：当精确解遥不可及时，用随机样本的统计量逼近期望值——这是随机化对抗搜索的底层信仰。【非常重要】

（二）从确定性到随机化的范式跨越︱12分钟

1.确定型搜索的局限性审视：教师以国际象棋为例，回顾极小化极大算法的完备性前提——博弈树完全展开且对手绝对理性。引导学生意识到现实博弈往往同时违反这两个前提。继而引出拉斯维加斯方法与蒙特卡洛方法的本质差异：前者始终输出正确结果但运行时间随机，后者在固定时间内输出近似解。【基础】

2.核心术语体系构建：教师于主屏幕动态构建概念地图——状态s、合法动作集A(s)、模拟策略π、终局回报R、访问计数N(s)、累积价值Q(s)。每出现一个新符号，均要求学生立即在笔记中标记并与概率统计教材中的样本量、样本均值符号建立映射。【重要】

（三）朴素蒙特卡洛方法全解析︱18分钟

1.动作价值估计的采样逻辑：教师现场运行井字棋Python脚本，从特定盘面出发，对每一个合法落子位置分别执行10次、50次、200次完整随机对局，动态柱状图显示胜率估计值随模拟次数增加而波动收窄。强调“随机对局”在此处指对弈双方后续均从合法动作集中均匀随机选择，直至终局。【基础】

2.手工估算对抗演练：教师投影一具深度为3的小型博弈树，根节点为当前局面的候选动作分支。学生三人一组，为每个动作分配20次虚拟随机对局，模拟并记录胜场，计算胜率点估计。教师巡视并针对性纠正常见偏差——部分学生误将随机对局理解为仅对手随机，己方仍贪心走子。随机抽取两组数据投屏，与精确期望值（课前穷举获得）并置，学生自发讨论误差与模拟次数、随机种子、终局回报赋值的关系。【热点】

3.缺陷的系统诊断：教师板书朴素蒙特卡洛三大瓶颈。第一，孤立采样：每个动作的评估从零开始，无法利用历史搜索信息。第二，无记忆性：同一状态在不同决策节点被反复从头模拟，计算冗余度极高。第三，平等对待所有分支：没有机制将计算资源向潜力更高的子节点倾斜。此三大缺陷直接构成蒙特卡洛树搜索的改进靶向。【非常重要】

（四）收束与前瞻︱7分钟

教师以极简语言复述随机化对抗搜索的操作性定义：重复随机模拟、统计胜率、选择最大期望动作。随即展示一张蒙特卡洛树搜索增量生长过程的示意动画——树并非一次性展开，而是每轮模拟仅在一条路径上添加一个叶子节点。设问：“如何让模拟结果不仅仅用于当前决策，还能被永久储存并在后续搜索中复用？”此问题作为第二课时的认知锚点。

（五）非正式延伸交流

鼓励课间围绕蒙特卡洛方法在其他领域的渗透展开自由对话，例如金融衍生品定价中的蒙特卡洛模拟、复杂物理系统的伊辛模型模拟等，教师择机插入短评，凸显跨学科思维迁移价值。

第二课时蒙特卡洛树搜索标准协议：UCT框架

（一）先行知识激活︱5分钟

教师通过定向提问快速回顾：朴素蒙特卡洛方法每做一次决策需要多少次模拟？这些模拟能否跨步骤共享？随机抽取一名学生简述模拟次数增加对估计方差的影响曲线。随后投影一段存在三处逻辑错误的MCTS伪代码片段，要求学生以旁观者视角尝试指认可能的异常断点，本环节旨在暴露对树搜索结构的迷思概念，并为精准讲授铺设认知缺口。【基础】

（二）MCTS四阶段精密解构︱30分钟

1.选择阶段——UCB1驱动的树内寻径【非常重要】【高频考点】

教师从多臂老虎机问题引入：假设面前有K台老虎机，每台的奖励分布未知，如何在有限拉动次数下最大化累积收益？UCB1策略在每一次选择时选取使得样本均值加置信区间上界最大的那台机器。将这一逻辑类比至博弈树节点：每个子节点即一台老虎机，当前节点的任务是选择UCB1值最高的子节点向下递归。教师板书UCB1公式严谨形式：UCB1=\bar{X}_j+C×sqrt(lnN/n_j)。逐项释义：第一项为节点当前平均胜率（利用项），第二项度量该节点未被充分尝试的程度（探索项），N为父节点总访问次数，n_j为子节点访问次数，C为探索常数。强调若n_j=0，则UCB1值视为无穷大，保证每个合法动作至少尝试一次。【难点】动画展示从根节点递归选择至叶子节点的完整路径，路径上每一层均应用UCB1准则。

2.扩展阶段——树边界的可控生长【重要】

教师明确扩展触发条件：当被选择的叶子节点访问次数达到预设阈值（通常为1）时，为其添加一个之前未被扩展过的合法动作作为全新子节点。对比一次性扩展全部子节点与按需扩展的利弊：前者内存占用高但逻辑简洁，后者计算资源友好但需要维护待扩展动作列表。本教案强制统一采用按需扩展策略，以贴合大规模博弈场景的实际约束。

3.模拟阶段——默认策略的速度与精度博弈【基础】【热点】

模拟是指从刚扩展出的子节点状态开始，采用快速走子策略（defaultpolicy）快速完成对局直至终局。教师通过对比实验数据说明：均匀随机走子计算极快但单次模拟信息量低，基于少量手工特征的快速走子（如优先占角、成四）能显著提升单次模拟的回报信噪比，但会牺牲模拟速度。强调模拟策略属于算法可插拔组件，AlphaGoZero甚至使用价值网络完全取代模拟阶段，这是后话。

4.反向传播——统计量沿访问路径归因【核心操作】

模拟产生终局回报（通常己方胜=1，负=-1，平=0）。教师手绘已访问过的树路径，演示从叶节点逐层向根更新祖先节点的访问计数N和累计价值Q。更新规则必须严格对称：N←N+1，Q←Q+Δ。特别强调：回报Δ必须依据当前节点视角进行符号翻转——若模拟结果为当前玩家获胜，对于其父节点而言即为对手获胜，父节点的价值增量应取负。此翻转逻辑是反向传播唯一但最易出错的环节。【难点】【高频考点】教师通过多个实例对比翻转遗漏与正确翻转的收敛曲线差异，强化记忆。

（三）算法整合与任何时间特性︱10分钟

教师给出标准MCTS函数的输入（状态对象、迭代次数上限）与输出（最佳动作），逐行解读包含while循环、递归选择、扩展、模拟、反向传播的完整伪代码。复杂度分析：单次模拟的时间代价由平均对局深度d与分支因子b决定，即O(d·b)，但由于搜索树在迭代间持续复用，整体收敛速度远优于朴素蒙特卡洛方法。重点阐释任何时间算法的工程优势——搜索可在任意时刻中断，并立即返回当前根节点下访问次数最多（或平均价值最高）的子动作。【非常重要】

（四）即时诊断与反馈︱5分钟

投影一份残缺的反向传播递归函数，其中缺失了玩家角色翻转处理与累计值更新语句。学生独立补充代码，随后同桌交换比对，教师展示标准答案并列举三类高频错误：忘记递归基、更新路径上遗漏中间节点、价值累加时未乘以回报符号。本练习结果通过课堂应答系统实时统计，教师根据错误集中度调整后续习题课侧重点。

第三课时变体剖析、参数调节与理论边界

（一）主流变体与工程优化︱20分钟

1.UCT——UCBforTrees的标准具象化【高频考点】。教师明确指出，平时论及MCTS默认指代UCT，即将UCB1作为树内选择准则的范式。通过对比仿真实验，展示相同迭代次数下，采用UCB1引导的搜索树与非引导的均匀树扩展在根节点最优动作置信度上的显著差异。探索常数C的取值直接改变树形态：C过小导致搜索过早陷入局部最优，C过大则使选择近乎均匀，收敛缓慢。【重要】

2.渐进式加宽与RAVE【热点】。面对围棋这般分支因子动辄上百的问题，一次扩展全部子节点既无必要也不现实。教师阐释渐进式加宽机制：子节点仅当已有子节点被访问超过特定频次后才允许添加新子节点，使搜索聚焦于高潜力区域。继而介绍快速动作价值评估（RAVE）思想，利用历史对局中同一动作在不同状态下获得的全局统计量来平滑估计值，并简要提及RAVE与AMAF的同源性，此处仅要求概念理解，不考核公式推导。

3.专家迭代与神经MCTS。以AlphaGoZero为范例，展示策略网络提供先验概率P(s,a)以替代原始UCB中的均匀先验，同时价值网络直接输出位置胜率从而完全取代随机模拟阶段。此部分虽不要求代码实现，但要求学生认识到MCTS作为一个算法框架，可灵活嵌入各类学习模块，具备极强的可扩展性。【非常重要】

（二）参数敏感性实验分析︱12分钟

教师展示预先生成的奥赛罗棋小规模MCTS实验数据箱线图。横轴为探索常数C，取值序列[0.2,0.5,1.0,2.0,5.0]；纵轴为与固定基准智能体对弈100局胜率。学生明显观察到C=1.0附近胜率最高，C过大或过小均劣。教师引导学生总结：第一，性能与模拟次数并非线性正比，存在边际收益递减；第二，C的最优区间与回报取值范围强烈相关，若回报压缩至[0,1]区间，C≈0.7是常用初始试探值。分组讨论：若将胜负平回报设为{1,-1,0}，C的初始试探值应如何调整？各小组运用方差稳定性原理推断C应同比放大至1.4附近。

（三）收敛性非形式化证明与开放问题︱10分钟

教师借助伯努利大数定律直观说明：当某节点被模拟的次数趋于无穷时，其平均回报依概率收敛于真实期望值；又因为UCB1策略在无限步数下能保证每个子节点被无限次访问，因此根节点所选择的动作必为真正最优动作。收敛速度是指数级还是多项式级至今仍是理论计算机科学未决问题，教师借此激发学生挑战前沿的学术勇气。【难点】

（四）AlphaGo案例深潜︱8分钟

播放经过剪辑的3分钟短视频，重点展示AlphaGoZero自对弈过程中MCTS生成训练数据的闭环：当前神经网络指导MCTS进行搜索，MCTS返回更强大的动作分布，该分布又被用作标签优化神经网络。教师拆解其PUCT公式与标准UCT的差异——先验概率P(s,a)取代了恒定先验，且探索项改为C×P(s,a)×sqrt(Σn_b)/(1+n_j)。简要说明这种改造能利用先验知识显著加速收敛，实现从零到职业水平的自我进化。

第四课时代码实现、调试与博弈迁移

（一）项目目标与脚手架代码说明︱5分钟

教师重申本课时核心产出：基于给定Python框架，补全MCTS类的四个核心方法，最终获得一个在井字棋环境下对随机走子对手胜率不低于90%的博弈智能体。分发代码压缩包，内含已高度封装的board.py、game.py以及待填充的mcts.py。快速过一遍Node类的数据结构：parent、children、visit_count、total_value、untried_actions，确保全班对类属性含义理解一致。【核心任务】

（二）关键函数逐项攻坚︱20分钟

1.select方法——递归下的UCB仲裁。教师现场编码，强调当子节点访问次数为0时必须返回一个极大UCB值（通常用float(‘inf’)）以保证未探索节点优先被选中。处理根节点直接调用及中途遇完全扩展节点的边界条件。展示Node类中is_fully_expanded辅助方法的实现逻辑。【非常重要】【高频考点】

2.expand方法——新节点的诞生。从未尝试动作列表中pop一个动作，创建子节点，将其添入children字典，务必同时设置子节点的parent指针。教师故意遗漏parent赋值，让学生观察反向传播因递归断裂而失败的现象，巩固记忆。

3.simulate方法——快速对局仲裁。接收当前状态对象，拷贝后交替随机落子直至终局，返回当前视角下的回报值。提醒学生注意state是否允许原地修改，必须使用深拷贝或提供克隆接口。同时对比纯随机走子与轻量启发式走子的代码长度与胜率差异。

4.backpropagate方法——符号翻转的工程实现。教师给出递归基：到达根节点或None则返回。递归向上时，累加访问计数，同时根据node.parent视角对回报取反。通过单元测试用例验证：模拟结果对根玩家为胜，反向传播到根的直接子节点时，该子节点的total_value增量应为-1（因为子节点视角下父节点玩家是对方）。【难点】【高频考点】

（三）集成调试与对战验证︱15分钟

学生独立或结伴完善代码，教师巡回观察，收集匿名化典型错误投屏集体修正。错误类型包括但不限于：UCB公式中使用log10而非自然对数；节点total_value误用增量赋值而非累加；反向传播时未正确翻转符号。待大部分小组通过单元测试后，启动批量对弈，学生记录MCTS_AI与随机AI对战100局的累积胜率，实时生成散点图，绝大多数案例胜率落在92%-98%区间。教师引导讨论：为何始终无法达到100%胜率？学生联系MCTS的随机模拟本质，归纳出有限模拟次数下必然存在估计误差这一核心结论。

（四）能力迁移与挑战任务︱10分钟

第一，拓展至四子棋环境。仅替换board模块，保留MCTS核心代码，观察搜索空间扩大后相同模拟次数下的胜率衰减现象，并尝试通过增加迭代次数补偿。第二，超参数网格搜索。编写简单脚本，令探索常数C在[0.5,1.5]区间内步进0.2，每点运行200对局，绘制C值与胜率曲线，提交最优参数值。第三，开放性思维问题：若博弈图包含环（例如允许重复状态），标准MCTS会陷入无限递归或重复统计同一状态，应如何改造？提示可使用状态哈希表记录已访问节点并实施状态回溯阻止策略。学有余力者课后尝