简介这是一份面向计算机博弈竞赛学习者与研究者的辅导课件内容源自东北大学机器博弈研究室的专题讲义。课件系统梳理了棋类介绍与分类、计算机博弈基本原理、方法学概述、计算机博弈软件构成、棋局评估、博弈树展开与分析、机器博弈的方法学特点及学科关系等核心模块适合用于备赛入门、课程教学与自学复习。资源以PPT形式呈现共1个文件压缩包大小2.57MB结构紧凑、便于直接阅读和对照梳理。目前已有329人学习浏览。通过这份资料读者可快速建立计算机博弈的整体知识框架了解中国象棋、国际象棋、围棋、五子棋、六子棋以及一字棋、二虎棋、三通棋、点格棋等典型棋类的规则特点与博弈复杂度掌握搜索算法、评估函数、蒙特卡罗树搜索等关键方法的适用思路为竞赛备赛和后续深入研究打下扎实基础。1. 计算机博弈竞赛辅导资料先搞清楚它解决什么、值不值得投入计算机博弈竞赛辅导资料说白了就是一套围绕对抗搜索、评估函数、时间管理与赛场策略的备赛素材目标是把一个“能思考几步棋”的程序训练成“在时限内做出好决策”的选手。很多第一次接触这类竞赛的开发者以为拼的是搜索深度结果在赛场被一个只算到第6层但评估函数写得极准的对手按在地上摩擦这是最常见的第一课。这类竞赛的核心不是“写一个会下棋的程序”而是“在一个固定时限内用有限算力做出最大限度接近最优的决策”。适合的人主要有两类一类是想通过竞赛验证自己算法工程能力的在校生另一类是工作中接触决策系统、想系统补对抗搜索知识的一线开发者。它不要求你懂深度学习但要求你把搜索、剪枝、评估、缓存这些基础功打磨到位。接下来我们按一套完整备赛路线展开从骨架算法讲到评估函数再到 MCTS 与避坑实录最后落到自我对弈的迭代闭环。以下内容全部围绕个人竞赛实践总结不依赖任何特定赛事规则原则适用于绝大多数棋类与对抗型博弈场景。2. 对抗搜索骨架minimax与Alpha-Beta剪枝的搭建与四个关键参数2.1 为什么先搭 minimax 而不是直接上 MCTS无论你参加的是棋类、牌类还是实时策略博弈第一步永远是先实现 minimax 搜索。原因很直接minimax 是最容易验证正确性的对抗搜索框架它的逻辑只有一层——我走一步对手走一步循环折叠到叶子节点后用评估函数打分我取最大、对手取最小。你不需要任何随机模拟代码量能控制在两个小时以内且每一步的决策过程都可以用日志打印出来方便定位 Bug。MCTS 听上去更现代但它的调试难度高一个量级黑匣子成分更重不适合作为第一个版本。我一般会在笔记本上先画一个三层的决策树手算每个节点的 minimax 值再用代码跑同一局面去对拍。这个习惯在备赛前两周尤其重要它能帮你确认搜索骨架本身没写错否则后面优化的所有东西都是在错误地基上盖楼。2.2 minimax 与 Alpha-Beta 剪枝的最小实现下面这段代码是比赛中最常用的对抗搜索骨架我按自己的工程习惯做了一些简化但保留了关键结构。注意这里假设state已经封装好了game_over()、legal_moves()、make_move()、undo_move()这些都是博弈类程序的基本接口。def alphabeta(state, depth, alpha, beta, maximizing): # depth 为剩余搜索深度alpha 为当前已知最大下限beta 为已知最小上限 if depth 0 or state.game_over(): return evaluate(state) if maximizing: value -float(inf) # 按“可能性”从大到小排序着法能显著提升剪枝效率 for move in sorted_legal_moves(state): state.make_move(move) value max(value, alphabeta(state, depth - 1, alpha, beta, False)) state.undo_move() alpha max(alpha, value) if alpha beta: break # 剪枝对手不会允许走到这条线后续着法无需再算 return value else: value float(inf) for move in sorted_legal_moves(state): state.make_move(move) value min(value, alphabeta(state, depth - 1, alpha, beta, True)) state.undo_move() beta min(beta, value) if alpha beta: break return value这段代码的逻辑说明每一层递归都维护一个alpha-beta窗口最大化节点负责抬高下限最小化节点负责压低上限一旦下限超过上限就立即截断该分支。关键点在于sorted_legal_moves这一步——着法排序质量直接决定剪枝效率排序好的搜索树可能比不排序的快 3 到 5 倍这是比赛里拉开差距的第一个隐蔽点。depth的初始值不要拍脑袋先设 4 层跑一遍全盘记录平均单步耗时再决定是否加深。评估函数没写到位之前盲目加深只会让你在局部战斗里算得远却看不懂局面实战中经常出现“高深度送子”的翻车场面。2.3 四个必调的搜索参数深度、排序、时间预算、窗口收紧第一个参数是搜索深度。我建议从 4 层起步每加深一层先做“单局面耗时测试”不要直接全盘测试。第二个参数是着法排序常见做法是先用上一轮迭代加深的 PV 线Principal Variation优先搜索再用吃子着法和历史表排序最后才是原顺序。第三个参数是时间预算这是比赛的生命线我的习惯是单步时间锁定在总时限的 1/20 以内比如每方 10 分钟则单步不超过 30 秒保留容错给极端复杂局面。第四个参数是窗口收紧优先尝试小窗口搜索如果返回的值在窗口内就说明结果可信如果越界了再重新搜索这种“渴望搜索”能减少大量不必要的计算但需要搭配一个可靠的越界重搜机制。这四个参数之间的联动关系经常被忽视。深度加深一步会让单节点耗时成倍增长排序改进却能以几乎零成本换同类深度下的速度提升时间预算反过来限制深度选择而窗口收紧又直接影响排序不佳时的回溯次数。我见过不少参赛者把深度从 6 改到 8 就以为万事大吉结果赛程后半段时间耗尽直接判负这就是参数没有联动调校的典型翻车。调参的节奏应该是先保证时间预算不破再优化排序最后才考虑加深。3. 评估函数设计从棋子价值到位置权重让AI看懂盘面3.1 评估函数为什么比搜索深度更早决定胜负对抗搜索本身不产生任何“棋感”它只是把一个局面的得分递归回溯到根节点。这个得分从哪来只能来自评估函数。如果你的评估函数只数棋子数量程序会把“吃子”当成唯一目标遇到弃子攻杀的局面会做出极其短视的选择。反过来如果评估函数能识别出中心控制、棋子活跃度、王城安全等因素搜索深度不需要很深也能打出相当有章法的棋。我最早参与的一次模拟项目X就是只做了子力评估结果搜索深度 8 仍然被一个仅有 6 层搜索但评估细致的对手碾压。那场比赛后我彻底改变了备赛优先级评估函数质量为王搜索深度只是放大器。评估函数的终点不是“更复杂”而是“更能区分好局面与坏局面”。每加一个特征都应该用同一组棋谱做前后对比胜率提升了才算有效否则就是玄学调参。3.2 特征设计从子力到位置的组合套路最朴素的评估函数是一个四项线性组合子力差、位置分、机动性、威胁度。子力差最直接但也是新手最容易陷入的陷阱——只算静态子力完全忽略位置交互。位置分通常用一个与棋子类型相关的棋盘查表实现比如中心格权重更高、边角格权重更低。机动性可以简单表示为当前方合法着法数量减去对方合法着法数量这个特征在开局和中局阶段区分度极高。威胁度则包括“被攻击的棋子数量”和“正在攻击对方高价值棋子的数量”。def evaluate(state): # 四类特征加权求和权重需要反复自对弈标定 material state.material_score(colorstate.current_player) position state.position_score(colorstate.current_player) my_moves state.legal_move_count(state.current_player) opp_moves state.legal_move_count(state.opponent) mobility my_moves - opp_moves threat state.threat_score(state.current_player) return material * 1.0 position * 0.1 mobility * 0.02 threat * 0.15这段代码的结构说明四项特征各自乘以一个权重后相加权重比例决定程序偏向“稳吃子”还是“抢位置”。position_score的实现通常是一个写死的二维数组不同棋子在不同位置的估值不同这部分不需要训练数据靠棋理常识就能手工标定。threat_score需要一枚棋子对对方棋子的攻击关系扫描计算复杂度较高但对杀棋局面帮助明显。权重标定时我一般先固定material1.0然后单独调整position用同一组开局库跑 20 盘自对弈统计胜率随权重变化的方向逐步逼近。mobility权重不要给太大否则程序会变得过于冒进频繁进入复杂弃子变化。3.3 权重标定的三个坑过拟合、数值爆炸与镜像不对称第一个坑是过拟合到特定开局。你用一个开局库反复测试调出来的权重面对不同风格对手时可能完全失灵特别是针对某种布局特点专门设计的权重。我通常准备至少三套不同风格的开局库用于测试一套平稳、一套激进、一套弃子型权重必须在这三套下都能保持 55% 以上胜率才算可用。第二个坑是数值爆炸——某个特征值的量级远大于其他项导致小权重项被完全淹没。解决方法是每项特征先做归一化让取值范围落在相近量级。第三个坑是镜像不对称棋盘上下左右对称不代表两个方向的权重完全等价尤其在国际象棋和中国象棋中子力位置的价值往往与是否靠近底线或中心有关直接写镜像权重会让你在某种颜色下出现系统性偏差。4. 蒙特卡洛树搜索与UCT评估函数写不好时的备用路线与参数区间4.1 MCTS 在什么情况下比 Alpha-Beta 更合适如果你的游戏存在较大的随机性比如包含掷骰子、抽牌或者局面评估极其困难写不出可靠的静态特征Alpha-Beta 会陷入“评估不准导致搜索终点质量差”的困境。这时 MCTS 是更合适的路线。MCTS 不需要设计评估函数它靠大规模随机模拟来估计每个着法的胜率模拟次数越多估计越准天然适合随机因素强的博弈。但注意MCTS 在纯策略棋类上未必优于 Alpha-Beta尤其是在局面评估清晰且搜索深度优势明显的场景下。我的建议是两条线并行骨架先用 Alpha-Beta 跑通评估函数实在调不出效果时再切 MCTS 做对照。比赛中的最优解往往是两者结合的——用 MCTS 模拟结果作为 Alpha-Beta 的着法排序依据这也是很多强博弈程序在中期局面的常见工程选择。4.2 一个可直接运行的 UCT 核心实现下面是一个浓缩版的 UCT 选择逻辑重点在 Select 阶段的 UCB1 公式和 Expand 阶段的触发条件。完整实现还需要模拟Rollout和回传Backpropagation但核心决策循环就是这段代码。import math def uct_select(node, c1.2): # c 是探索常数值越大越偏向探索访问次数少的节点 best_child None best_value -float(inf) for child in node.children: if child.visits 0: # 未访问节点直接给一个较大值强制先探索一次 ucb_val float(inf) else: exploitation child.wins / child.visits exploration c * math.sqrt(math.log(node.visits) / child.visits) ucb_val exploitation exploration if ucb_val best_value: best_value ucb_val best_child child return best_child5. 备赛避坑指南超时判负、缓存穿透与评估爆炸的五个排查实录5.1 现象搜索到中局阶段单步耗时突然飙升最终超时判负这是比赛中最常见的翻车方式没有之一。很多选手在自己电脑上测试流畅到赛场上就不行了因为比赛机的 CPU 型号、可用内存、后台进程完全不同。搜索耗时飙升的直接原因是局部分支因子过高某种局面下可走着法数量远超平均值搜索树宽度爆炸。更深层的原因是着法排序在你加到第 6 层之后失效了——排序不精准导致剪枝率骤降搜到的节点数量比预期多出数倍。解决白盒监测每步的节点数与剪枝率剪枝率低于 70% 时必须检查排序逻辑时间预算再收紧一档必要时做“极端局面降深度”保护——检测到可用时间低于某个阈值时自动减一层搜索深度。5.2 现象开局阶段就送子棋谱显示前几步走出离谱着法开局送子通常不是搜索问题而是开局库覆盖不足或者开局库写错了。排查时要先确认这个局面是否进入了开局库查询逻辑很多程序只命中固定行棋序列对方一旦走变着就直接返回空、落到搜索层。更隐蔽的情况是开局库的胜率权重被叶子节点的评估值污染了——回传时混入了一个异常值导致开局库推荐了看似合理但实际有缺陷的着法。解决开局库查询必须带局面哈希键不匹配就不命中开局库的推荐逻辑只依赖统计胜率不依赖当前搜索评估值。5.3 现象置换表命中率极高但棋力没有相应提升置换表Transposition Table是竞速型博弈程序的标配用来缓存搜索结果。命中率高看起来是好事但如果你发现棋力不升反降大概率是缓存过期策略有问题——存储的节点评分来自不同的搜索深度较浅深度的结果直接覆盖了较深深度的结果导致根节点采纳了次优着法。解决置换表条目必须包含搜索深度信息读取时只接受“不小于当前需求深度”的条目写入时优先保留深度大的结果如果局面评估值有窗口信息也要一并校验。5.4 现象评估函数调整后自对弈胜率上升但对人胜率下降这是典型的过拟合测试集问题。自对弈的对手是自身历史版本评估函数朝着对抗旧版本的弱点进化但这个弱点可能只在旧版本身上存在换一个对手就变成漏洞。解决引入第三方对照组用一个固定版本的参考程序当作测试基准任何改动必须同时打赢自身旧版本与参考基准才算数避免只用单一开局库反复自对弈。5.5 现象程序从不超时但每步棋都非常慢几乎用到时间上限这种“卡满时间”的现象通常不是 Bug而是时间分配策略写得过于保守。很多选手把单步时间预算设成了硬上限——每一层搜索跑满预算才停完全没有用迭代加深的提前终止机制。常见做法是每层搜索完成后检查当前最佳着法是否已经稳定连续两层同着法且评估值变化小于阈值稳定就提前终止。我一般在检测到 PV 连续两次一致时直接返回能省下三分之一的总时间。这个节省出来的时间在残局阶段非常关键可以用在更复杂的残局搜索上。6. 自我对弈与回归基线把备赛变成每天十五分钟的可迭代闭环备赛进入中后期拼的不是写新代码的速度而是“每个改动都能被验证”的工程效率。我习惯的做法是维护一份命令行自对弈脚本固定时间控制、固定开局库、固定初始随机种子让两个版本的程序自己下一盘输出胜、负、和以及平均单步耗时。每次改动评估函数或搜索逻辑后先跑三盘基线局做回归对比输了就立刻回滚赢了再扩大测试量到十盘。这个习惯把我从“越改越玄学”的泥潭里拉了出来。验证指标固定三个胜率、平均单步耗时、搜索节点数变化率。胜率看棋力方向耗时看时间预算健康度节点数变化率则用来判断改动是否真的改变了搜索行为。如果胜率没变但节点数暴涨说明你的改动只是在碰运气如果节点数下降但胜率微升说明排序或剪枝的改动是有效的。我每天投入十五分钟跑回归、记录表格备赛周期内积累了整整一张权衡日志。我最深的教训是发生在某次备赛后期评估函数连续一周越改越差胜率从 60% 跌到 42%原因就是没建回归基线每次改动都以为自己进步了。从那以后我把回归测试当成铁的纪律没有跑基线不允许提交任何代码改动。备赛不是堆工作量而是让每一次改动都留下可验证的脚印。希望帮到你。本文还有配套的精品资源点击获取
