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

简介：这份计算机博弈竞赛辅导资料面向准备参加计算机博弈竞赛的学生、指导教师及入门研究者，围绕棋类博弈的基本原理、软件实现与竞赛分析展开，可用于课程辅导、赛前自学和知识梳理。压缩包共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 状态空间与分支因子：五个棋种的参数对照

把参数摊开看，才知道为什么有的棋种适合深搜、有的只能靠学习。

六子棋的分支因子要单独拎出来说：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(frozen=True) class Move: frm: int # 起点索引 0..89 to: int # 终点索引 0..89 capture: int = 0 # 被吃子的兵种编号，0 表示空格（非吃子着法） def sq(file: int, rank: int) -> int: """列、行转一维索引；rank=0 是红方底线""" 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 best

depth到 0 时调用评估函数，这里有个必须守住的约定：评估函数返回的分数永远是“站在当前side视角”的，不能写成固定红方视角，否则递归返回取负之后符号全乱。alpha是当前节点已知得分的下界，beta是上界，一旦alpha >= beta说明对手在上层绝不会允许走到这个分支，直接返回。is_terminal要覆盖三种情况：将死、困毙、以及规则判和（60 回合不吃子、双方无进攻子力等），漏掉任何一种都会让引擎在残局里反复走废棋。

3.3 alpha-beta 剪枝：窗口、顺序与效率上限

alpha-beta 不改变搜索结果，只砍掉不可能被选中的分支。它的效率完全取决于着法排序：排序完美时有效分支因子约等于真实分支因子的平方根，节点数从 b^d 降到 b^(d/2)。拿国际象棋 b=35、d=8 算一笔账，35^8 约 2.2×10^12，35^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, key=key, reverse=True)

权重设计里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 alpha

stand是“不再吃子”的静态分，它同时充当截断依据和初始下界：如果站着不动的分已经超过 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 就对不上，说明合法性过滤有问题；深度 1 对、深度 2 不对，说明漏着法或者撤销不干净；深层才出问题，多半是特殊着法在特定局面下才触发。六子棋这类每手两子的棋种，perft 还要额外处理“同一手内两子的顺序等价”，否则结果会翻倍，这属于规则层面必须先想清楚的事。

perft 通过之后，再建一个固定局面回归集。我习惯把二十到三十个局面存成文本，每个局面标注“期望引擎在限定时间内选择的前三个着法”，格式就三列：FEN 串、深度或时间预算、期望着法列表。每次改评估函数或者调搜索参数，跑一遍这个集合，看有多少局面的首选着法变了。变少是好事，变多就要逐个看是变好还是变坏——很多“优化”就是在这一步被证伪的，权重调完之后自对弈胜率涨了两个点，回归集里却有五个局面下出了明显亏子的棋。

血泪经验是：改评估函数之前先存一份回归结果，改完对比，别凭感觉。有一次我把一个位置项从 +30 调到 +50，自对弈胜率确实涨了，回归集一跑发现三个残局局面全部走错，原因是这个位置项在残局里盖过了子力项。从那以后我每次动评估权重都强制走一遍 perft 加回归集，两步都过才允许合进主分支。希望帮到你。

本文还有配套的精品资源，点击获取