计算机博弈竞赛辅导：博弈树搜索、剪枝与评估函数实践-北京尧图网络

简介这份计算机博弈竞赛辅导资料面向准备参加计算机博弈竞赛的学生、指导教师及入门研究者围绕棋类博弈的基本原理、软件实现与竞赛分析展开可用于课程辅导、赛前自学和知识梳理。压缩包共1个文件为1份PPT体积约2.57MB以讲义课件形式组织便于课堂讲解或按章节查阅。内容从中国象棋、国际象棋、围棋、五子棋、六子棋及点格棋、亚马逊等典型棋类切入覆盖博弈树展开与搜索、alpha-beta剪枝、棋局评估、计算机博弈软件构成以及基于搜索的方法学特点和与数学、人工智能等学科的关系。已有330人学习下载读者可借助其中的分类框架、棋例说明和评估思路建立从规则理解到算法实现的整体认识并对照竞赛项目查漏补缺。1. 计算机博弈竞赛辅导资料一份把搜索主线讲透的课程讲义很多人第一次拿到计算机博弈竞赛辅导资料以为会是棋谱合集或者某个现成引擎的源码包翻开才发现它讲的是“带普遍性的规律”棋类怎么分类、状态怎么表示、博弈树怎么展开、棋局怎么评估、剪枝参数怎么调。这份资料来自某高校机器博弈研究室的一次课程讲义把竞赛里最容易卡住的几个环节按顺序铺开——先判断研究对象是完全信息还是不完全信息再决定用搜索还是用学习最后落到评估函数的分层结构和 alpha-beta 的窗口设定。它适合三类人准备参赛但不知道从哪下手的队伍、已经能走棋但赢不了棋的引擎作者、以及需要给学生讲清楚“为什么剪枝有效”的指导者。整份资料没有堆公式重点全在可实现的环节上这一点对赶比赛进度的人很友好。2. 棋类分类与状态空间把五个典型棋种的参数摊开算一遍2.1 完全信息动态博弈棋和牌的分界线资料开篇就把这条线划得很清楚棋类属于完全信息动态博弈牌类属于不完全信息动态博弈。这不是学术上的分类癖好它直接决定你该拿哪套算法上场。完全信息意味着任意时刻盘面状态对所有参与者都是可见的于是整局游戏可以展开成一棵树——节点是局面边是着法搜索就是在树上找一条对自己最有利的路径反过来说如果对手手里握着你看不见的牌你就得维护“信念状态”只能按概率分布去推方法就换成了采样、反事实遗憾最小化那一套。竞赛题九成以上落在棋类所以资料的重心压在搜索上。判断一道题该走哪条路我一般按三步过一遍信息是否完全——棋盘上所有子都看得见成立转移是否确定——走一步之后局面唯一没有骰子没有随机发牌成立是否零和——一方所得即另一方所失成立。三条都成立就是标准的极小极大场景博弈树、alpha-beta、置换表这套工具可以直接上。任何一条不成立都要换思路比如带随机性的棋盘游戏要算期望值而不是最大值非零和则不能用“对手的损失就是我的收益”这个前提去剪枝。这里有个常被忽略的细节先手优势本身不影响算法选型但影响规则实现。中国象棋的长将判负、围棋的贴目、五子棋的禁手和换手、六子棋的“先手一子、之后每手两子”本质上都是在给先手优势打补丁。这些补丁不写进代码引擎在自对弈时就会反复走出规则不允许的着法测试阶段看着胜率很高一上正式裁判环境直接判负。2.2 按着法分类走子、填子、混合三类的建模差异资料的分类维度里按着法分类最实用因为着法生成器是整个引擎的第一道工序它写错了后面全白搭。类别代表棋种开局状态着法生成要点走子类中国象棋、国际象棋、跳棋、苏拉卡尔塔、亚马逊双方预先布好子生成后必须做合法性过滤剔除送将、自杀、违反行棋范围的着法填子类围棋、五子棋、点格棋盘面为空分支等于当前空点集合规则判定打劫、禁入点、成五占大头混合类五道棋、日本将棋先填后走或边走边填需要分阶段切换生成器阶段判定必须写死走子类的坑集中在合法性与自杀判定。中国象棋里“送将”是不合法的生成着法之后要模拟走一步再判断自己是否处于被将军状态这一步模拟的成本不低很多实现为了省时间只在根节点做完整校验结果浅层搜索里冒出大量非法着法。亚马逊更极端每一步包含“移动棋子”和“设置障碍”两个动作等于把分支因子又乘了一次棋盘剩余空格数着法生成效率直接决定搜索能到几层。填子类的坑在分支数。围棋 19×19 有 361 个空点平均分支因子在 250 上下比国际象棋的 35 高出一个数量级同样搜到第 8 层节点数差着好几个量级这还没算打劫和提子的规则判定开销。五子棋好一些15×15 盘面、分支因子约 50但它的胜负判定必须做增量更新——每落一子只检查穿过该点的四条线而不是每次全盘扫描。混合类最容易被低估。日本将棋除了走子还有吃子后的“持驹打入”手里吃到的子可以随时放回棋盘分支因子随局面剧烈波动五道棋则是先填子再走子阶段切换点要写死在代码里否则会出现在该走子的阶段还在生成填子着法的荒唐情况。提示华容道这类单人滑块游戏也在资料的棋类介绍里但它不是双人零和博弈别拿极小极大硬套。它是单 agent 的最短路径搜索启发式用曼哈顿距离配合状态去重就够了。2.3 状态空间与分支因子五个棋种的参数对照把参数摊开看才知道为什么有的棋种适合深搜、有的只能靠学习。棋种棋盘每方子数平均分支因子量级规则里必须先实现的三件事中国象棋9×1016约 38长将判负、60 回合不吃子判和、将帅照面国际象棋8×816约 35王车易位、吃过路兵、兵升变围棋19×19无固定约 250打劫、禁入点、贴目5–7 目五子棋15×15无固定约 50禁手、换手、金球制改进六子棋19×19无固定每手两子组合数万级先手一子后每手两子、连六判定亚马逊10×104 个后千级以上移动加设障、无子可动判负六子棋的分支因子要单独拎出来说19×19 共 361 个点先手落一子之后每一手要落两子两子的组合数在开局阶段接近三万哪怕砍掉顺序等价的组合也还有一万多。分支因子大带来的直接后果是同样的时间预算下能搜的深度比中国象棋浅两三层所以这类棋种通常要走“着法生成做增量评估函数做精细”的路线而不是一味加深搜索。国际象棋的相对子力值资料里给了明确数字以兵为 1马约 3、象约 3、车约 5、后约 9。中国象棋没有这么统一的口径实战里车约 9–10、马 4–5、炮 4.5–5、过河兵和未过河兵差着一倍以上士象在残局里才显出价值。这些数字只是评估函数的起点不是标准答案后面第 4 章会展开。3. 博弈树从零展开极小极大、alpha-beta 与着法排序3.1 棋盘表示与着法结构先把数据结构定死数据结构定得早后面改起来最省事。中国象棋 9 列 10 行共 90 格用一维数组比二维数组快因为索引计算只有一次乘加缓存也更友好。着法用不可变结构体表示起点、终点、被吃子三个字段就够特殊着法再挂扩展字段。from dataclasses import dataclass BOARD_W, BOARD_H 9, 10 # 中国象棋9 列 10 行 BOARD_SIZE BOARD_W * BOARD_H dataclass(frozenTrue) class Move: frm: int # 起点索引 0..89 to: int # 终点索引 0..89 capture: int 0 # 被吃子的兵种编号0 表示空格非吃子着法 def sq(file: int, rank: int) - int: 列、行转一维索引rank0 是红方底线 return rank * BOARD_W file def mirror(idx: int) - int: 黑方位置表镜像位置表只写红方一份黑方用镜像索引取 return (BOARD_H - 1 - idx // BOARD_W) * BOARD_W (BOARD_W - 1 - idx % BOARD_W)capture字段看着多余它其实是着法排序和置换表的关键输入吃子着法优先展开能显著提高剪枝率而被吃子的兵种编号直接决定优先级高低。mirror是为评估函数服务的位置权重表只维护红方一份黑方走镜像查询省掉一半的表数据也避免了两份表写不一致。如果后续要冲更高性能可以换成位棋盘但 90 格超过了单个 64 位字的容量得拆成两个 64 位字或者用 128 位结构这一层抽象建议留到搜索框架跑通之后再动。3.2 极小极大负极大值写法与终止条件极小极大的教科书版本分 max 层和 min 层写起来两套逻辑容易在符号上翻车。实战里更常见的是负极大值写法统一成一层靠返回值取负来表达“轮到对手时局面对我意味着什么”。INF 10 ** 9 def negamax(board, depth, side, alpha, beta): 负极大值搜索始终站在 side 的视角返回分数 if depth 0 or board.is_terminal(): return board.evaluate(side) # 终止评估或终局分 best -INF for mv in board.legal_moves(side): board.make(mv) # 走完之后轮到对手返回值取负才是自己的分 score -negamax(board, depth - 1, -side, -beta, -alpha) board.unmake(mv) if score best: best score if best alpha: alpha best if alpha beta: break # beta 截断这棵子树已无价值 return bestdepth到 0 时调用评估函数这里有个必须守住的约定评估函数返回的分数永远是“站在当前side视角”的不能写成固定红方视角否则递归返回取负之后符号全乱。alpha是当前节点已知得分的下界beta是上界一旦alpha beta说明对手在上层绝不会允许走到这个分支直接返回。is_terminal要覆盖三种情况将死、困毙、以及规则判和60 回合不吃子、双方无进攻子力等漏掉任何一种都会让引擎在残局里反复走废棋。3.3 alpha-beta 剪枝窗口、顺序与效率上限alpha-beta 不改变搜索结果只砍掉不可能被选中的分支。它的效率完全取决于着法排序排序完美时有效分支因子约等于真实分支因子的平方根节点数从 b^d 降到 b^(d/2)。拿国际象棋 b35、d8 算一笔账35^8 约 2.2×10^1235^4 约 1.5×10^6差了六个数量级。这就是为什么有经验的实现会把大量精力花在排序上而不是花在剪枝算法本身。最省事也最有效的排序策略是 MVV-LVA即“被吃子价值高、发起攻击的子价值低”的吃子优先。PIECE_VALUE {pawn: 1, advisor: 2, bishop: 2, knight: 4, cannon: 5, rook: 9, king: 100} def order_moves(board, moves): 吃子优先吃大子优先用小子吃大子再优先 def key(mv): if mv.capture: attacker board.piece_at(mv.frm) return 10_000 PIECE_VALUE[mv.capture] * 10 - PIECE_VALUE[attacker] return 0 return sorted(moves, keykey, reverseTrue)权重设计里10_000是个哨兵值保证所有吃子着法排在安静着法前面乘 10 是为了让被吃子价值成为主序攻击子价值只做微调避免“用兵吃车”和“用车吃兵”排到同一档。安静着法暂时一律给 0后面可以再叠加杀手着法同一层造成剪枝的着法和历史启发那属于第二阶段优化。还有两个参数层面的细节值得先记住。一是搜索窗口根节点第一次搜索用全窗口[-INF, INF]后续兄弟节点可以用零窗口试探失败再重搜这是 PVS 的思路二是迭代加深必须保留上一层的最优着法作为兜底超时中断的那一层结果不能直接用否则同一局面每次跑出来的着法都不一样这种“玄学”现象十有八九就是这里出的问题。3.4 迭代加深与置换表让时间预算真正生效比赛环境通常给固定的每步思考时间深度写死要么超时要么浪费。迭代加深从第 1 层开始逐层加深每层把上一层的分数作为下一层的初始窗口好处是任何时刻中断都有一个完整的结果可用。import time def search_iterative(board, side, time_budget_ms): best_move None deadline time.perf_counter() time_budget_ms / 1000.0 for depth in range(1, 64): if time.perf_counter() deadline: break mv, score root_search(board, depth, side) # 内部每若干节点检查一次超时 if mv is not None: best_move mv # 只接受完整搜完的那一层 return best_move核心约束就一条只有完整搜完的层才允许更新best_move被中断的层结果丢弃。time_budget_ms建议留 10% 到 20% 的余量因为着法生成和评估的实际耗时在不同局面上波动很大卡着上限设置会在复杂中局直接超时。置换表用来缓存已经搜过的局面键用 Zobrist 哈希值里至少要存深度、分值、边界类型精确值 / 下界 / 上界和最优着法。只有表里记录的深度大于等于当前剩余深度时分值才能直接复用深度更浅的记录只能拿最优着法去做排序分值不能用。边界类型这一点经常被忽略把上界值当成精确值用会让引擎在某些局面上突然下出明显亏子的棋而且极难复现。4. 棋局评估函数子力、位置、机动性的分层加权4.1 子力值只是起点不是标准答案资料给出国际象棋的相对子力值兵 1、马 3、象 3、车 5、后 9。这组数字背后是长期实战统计出来的兑换关系但它只在开局到中局阶段比较准进入残局之后兵的价值会明显上升因为升变的可能性变大了。中国象棋没有这么统一的口径车在绝大多数局面里都是最强子力马炮各有适用场景士象的价值高度依赖对方剩余进攻子力——对方只剩单马双士的价值可能还不如一个过河兵。我一般会这样起步先给一套粗值把引擎跑起来然后用自对弈的胜率去微调而不是一上来就追求“正确”的子力值。PIECE_BASE { rook: 900, cannon: 450, knight: 400, pawn: 100, advisor: 200, bishop: 200, king: 100000, }用整数而不是浮点好处是置换表里的分值比较不会有精度问题也不受不同平台浮点实现差异影响。所有分值统一放大到百位量级位置项和机动性项才有插值的空间否则一个位置微调 0.3 分在整数里根本表达不出来。4.2 分层加权子力位置机动性特殊项评估函数的结构比单项数值重要。一个能用的版本大致分四层子力、位置、机动性、特殊规则项。POS_BONUS {} # 每个兵种一张 90 格位置表只写红方视角 def evaluate(board, side): score 0 for idx, piece in board.iter_pieces(): v PIECE_BASE[piece.type] table POS_BONUS.get(piece.type) if table: v table[idx] if piece.color side else table[mirror(idx)] score v if piece.color side else -v # 机动性双方合法着法数之差权重必须压小 mob len(board.legal_moves(side)) - len(board.legal_moves(-side)) score mob * 2 return score位置表是评估函数里性价比最高的部分。以兵为例未过河的兵给 0刚过河给 30逼近对方九宫再 50这种阶梯式的加分能明显改善引擎的进攻倾向。位置表只维护红方一份黑方查表时走mirror镜像这一条既省内存也避免了手写两份表时漏改一格的低级错误。机动性权重必须压得很小mob * 2已经算偏大。权重一高引擎会为了“多走几步”而放弃实利典型表现是宁可来回晃车也不肯吃一个白送的兵。评估函数里任何一项的权重超过子力项的量级都会带来这类行为偏差。特殊规则项按棋种单独加中国象棋要加“将帅照面”的惩罚、残局里士象齐全的加成五子棋要加成五、活四、冲四、活三的棋型分亚马逊要加活动空间和障碍分割的评估。这部分没有通用写法只能按规则一条条补补的时候记得每条都给一个回归局面改完立刻验证。4.3 从评估到着法排序静态搜索与吃子延伸深度到 0 就直接调评估函数会遇到一个经典问题局面正处在吃子交换的中途评估出来的分值严重失真。比如刚用一个车吃掉对方一个马还没来得及被对方回吃静态评估会以为自己白赚一个马。解决办法是在叶子节点做静态搜索只展开吃子着法直到局面“安静”下来。def quiesce(board, side, alpha, beta): stand board.evaluate(side) if stand beta: return beta # stand-pat 截断 if stand alpha: alpha stand for mv in board.capture_moves(side): board.make(mv) score -quiesce(board, -side, -beta, -alpha) board.unmake(mv) if score beta: return beta if score alpha: alpha score return alphastand是“不再吃子”的静态分它同时充当截断依据和初始下界如果站着不动的分已经超过 beta对手不会让你走到这个分支直接返回。只遍历吃子着法保证了递归一定会终止因为每吃一子棋盘上的子力总数就少一个。静态搜索的深度要设一个硬上限否则在长兑换链上会退化成近似全宽搜索把时间全耗在叶子附近。5. 踩坑与排查搜索对却下错棋的五个现场5.1 搜索与数据结构层面的三个坑现象一深度加到 7 之后耗时突然涨了十几倍深度 6 只要 0.3 秒深度 7 要 5 秒以上。原因基本可以锁定在着法排序失效或者剪枝根本没生效。剪枝生效时节点数随深度是平方根增长如果耗时呈指数级爆炸说明每一层都在展开全部着法。排查方法是在搜索里统计节点数和剪枝次数正常情况下剪枝次数应该和节点数处在同一量级。常见诱因是排序函数对所有着法返回同一个键值sorted保持原序而生成器恰好按棋盘扫描顺序输出等于没排序。解决是把排序键打印出来看前十个着法确认吃子着法确实排在了前面。现象二同一局面反复搜索结果每次不一样甚至同一进程里连着搜两次都不一样。这是置换表用得不对的典型症状。原因通常有两个一是置换表只存了分值和深度没存边界类型把上界值当精确值用了二是表项没做深度校验浅层搜索的结果覆盖了深层结果。解决是给每个表项加一个标志位精确值、下界、上界分开存命中时按当前窗口判断能不能直接用深度不足时只取最优着法做排序。改完之后同一局面连续搜索一百次着法应该完全一致。现象三引擎在优势局面下反复走重复着法明明能赢却判和。原因是没有做重复局面检测或者做了但哈希算错了。搜索树里同一局面通过不同着法顺序到达是常态如果没有检测引擎会以为这是一条新分支继续往下搜白白消耗深度更糟的是在规则层面长将、长捉在多数棋规里是要判负或判和的引擎不知道就会一直将下去。解决是维护一个局面哈希栈make时压入、unmake时弹出搜索前先查栈里是否出现过出现过两次就按和棋返回 0 分。这一条在残局阶段尤其关键。5.2 规则与状态恢复层面的两个坑现象四搜索跑了几十万节点之后棋盘状态错乱出现同一格两个子或者子凭空消失。几乎可以断定是make和unmake不对称。中国象棋的吃子、国际象棋的吃过路兵和王车易位、日本将棋的持驹打入这几类着法在撤销时需要恢复的信息不止一个格子的内容。吃过路兵要恢复被吃兵的原位置王车易位要同时恢复王和车任何一处漏写都会在深层递归返回后留下脏数据。解决是给每次make返回一个撤销记录把所有被改动的格子打包存下来unmake只按记录反向恢复不要靠“再算一遍”去推。写完之后用固定局面做一万次随机 make/unmake最后比对棋盘哈希必须完全一致。现象五换了个棋种之前调好的评估权重全部失效引擎开始乱走。原因往往是把某个棋种的规则细节硬编码进了通用评估里比如把“过河兵加分”写死在通用函数中换到没有河界的棋种就变成了无意义计算。解决是把评估拆成通用层和棋种层通用层只管子力和位置棋种层用插件方式挂特殊项。另一个常见诱因是规则没实现完整比如五子棋的禁手、六子棋的每手两子引擎按自己的理解走棋在自对弈里合法在裁判程序里直接判负。每换一个棋种先把规则的可执行清单列出来逐条对着裁判程序跑一遍这一步千万不能省。注意这五条里有四条的共同特征是“自对弈看不出来”。自对弈双方用的是同一套错误实现错误会互相抵消所以测试必须引入独立的裁判程序或者权威着法序列。6. 用 perft 与回归集把引擎的“玄学”变成可复现数据着法生成器写对是后面一切的前提但它的错误最难靠肉眼发现因为引擎照样能走棋只是走的着法集合比正确值少几个或者多几个。perft 就是干这个的从某个固定局面出发统计深度 n 时叶子节点的总数把结果和一个可信的参考值比对差一个数就说明生成器有问题。def perft(board, depth, side): 返回该局面在 depth 层内的合法着法序列总数 if depth 0: return 1 total 0 for mv in board.legal_moves(side): board.make(mv) total perft(board, depth - 1, -side) board.unmake(mv) return total这个函数不调评估、不做剪枝纯粹数叶子所以任何生成器或状态恢复的错误都会在结果上放大。跑的时候从深度 1 开始逐层加每层都记下来深度本层节点数与参考值差值排查方向1着法数差值为正生成了非法着法优先查送将过滤2—差值为负漏生成优先查边界格子和特殊着法3—差值突然放大状态恢复不对称make/unmake 有问题4—只在个别分支差定位到具体着法序列手工单步深度 1 就对不上说明合法性过滤有问题深度 1 对、深度 2 不对说明漏着法或者撤销不干净深层才出问题多半是特殊着法在特定局面下才触发。六子棋这类每手两子的棋种perft 还要额外处理“同一手内两子的顺序等价”否则结果会翻倍这属于规则层面必须先想清楚的事。perft 通过之后再建一个固定局面回归集。我习惯把二十到三十个局面存成文本每个局面标注“期望引擎在限定时间内选择的前三个着法”格式就三列FEN 串、深度或时间预算、期望着法列表。每次改评估函数或者调搜索参数跑一遍这个集合看有多少局面的首选着法变了。变少是好事变多就要逐个看是变好还是变坏——很多“优化”就是在这一步被证伪的权重调完之后自对弈胜率涨了两个点回归集里却有五个局面下出了明显亏子的棋。血泪经验是改评估函数之前先存一份回归结果改完对比别凭感觉。有一次我把一个位置项从 30 调到 50自对弈胜率确实涨了回归集一跑发现三个残局局面全部走错原因是这个位置项在残局里盖过了子力项。从那以后我每次动评估权重都强制走一遍 perft 加回归集两步都过才允许合进主分支。希望帮到你。本文还有配套的精品资源点击获取

计算机博弈竞赛辅导：博弈树搜索、剪枝与评估函数实践

相关推荐

基于Playwright的E2E测试体系搭建：用例设计、稳定性与CI集成实践

大模型优化核心技术：计算图重构与量化实践

工业路由器R40在隧道通风控制与环境监测中的边缘网关方案

更多资讯

降维与度量学习：高维数据处理的核心技术解析

Sublime Text 3 3211 完美配置指南：解决卡顿、乱码与插件失效

Docker Compose编排Spring Boot与Redis通信实战

营销人完整技能框架：洞察、策略、内容、渠道与数据实战指南

HDFS核心架构与大数据存储优化实践

IDA Pro逆向入门：PE装载、F5伪代码与异或校验解密

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？