简介：这份面向计算机博弈竞赛的辅导材料，适合备赛学生、指导教师及入门研究者梳理知识框架，尤其便于在赛前对照棋类规则、搜索算法与局面评估建立整体认识。压缩包内仅含1个PPT，约2.57MB，内容以东北大学机器博弈研究室的“计算机博弈原理与方法学概述”为主线，串联棋类介绍与分类、计算机博弈软件构成、棋局评估、博弈树展开与分析，以及基于搜索的方法学特点和学科关系。课件还举例中国象棋、国际象棋、围棋、五子棋、六子棋及部分民间棋类，帮助读者比较不同棋类的棋盘规模、行棋规则与胜负判定，并理解alpha-beta剪枝、启发式搜索等核心思路。目前已有330人学习，适合用作竞赛培训提纲、课堂讲义或自学索引，便于快速定位后续深入方向。

1. 计算机博弈：规则最简单的那门棋，反而最难写程序

国际象棋的规则一页纸能写完，围棋的规则更短——轮流落子，谁占的地盘多谁赢。可偏偏是后者，让计算机多花了几十年才摸到门槛。一份讲计算机博弈的竞赛辅导资料，最值得先划出来的恰恰是这个反直觉结论：棋的复杂度从来不写在规则里，而是藏在「从当前局面走到终局」的分支数量里。程序要做的不是背规则，是在一个组合爆炸的空间里用有限算力逼近最优的一步。理解了这套「展开—评估—回传」的底层机制，才会明白为什么着法排序能决定胜负，为什么评估函数差一个兵值就足以让整盘棋崩掉。

2. 完全信息动态博弈：这个前提决定了你的算法边界在哪

2.1 从棋到状态：三类着法规则如何倒推出棋盘数据结构

一份讲义肯花一大半篇幅去罗列中国象棋 9×10 的棋盘、国际象棋的车马象后、围棋的 19 路、五子棋的 15×15、六子棋的连珠规则、点格棋的死格双环长链、苏拉卡尔塔的弧线吃子、亚马逊的移动加设障，看上去像在讲常识，实际是在划定问题的边界。棋类属于完全信息动态博弈，牌类属于不完全信息动态博弈，这个分野不是学术洁癖——完全信息意味着盘面上没有隐藏变量，程序不需要维护对手私有信息的信念状态，于是可以老老实实建一棵确定的博弈树，用极大极小把叶子分数回传到根节点。牌类做不到这一点，只能在信息集上求期望，那是另一套数学。

确定了这个前提，接下来才是数据结构。按着法分类，棋大致落进三个格子：走子类（开局摆好、轮流走动，中国象棋、国际象棋、跳棋、苏拉卡尔塔、亚马逊都算），填子类（开局空盘、轮流落子，围棋、五子棋、点格棋），混合类（先填后走，五道棋的填子走子吃子、日本将棋的走子吃子填子）。这三种规则对局面表示的要求完全不同，走子类关心「哪颗子能挪到哪」，填子类关心「空点集合和连子计数」，混合类还多一个阶段状态，同一个棋盘在不同阶段的合法着法集合根本不一样。

from dataclasses import dataclass, field @dataclass class Position: board: list # 一维数组，0 表空点，正负号区分阵营，一维化是为了 Zobrist 哈希够快 side: int # 1 或 -1，轮到谁走 phase: str = "place" # 混合类棋必须显式建模阶段：place 填子 / move 走子 history: list = field(default_factory=list) # 局面哈希序列，用于重复局面检测 def legal_moves(self): """合法着法生成器，所有搜索的地基，这里错一步后面全废""" if self.phase == "place": return [(i, None) for i, v in enumerate(self.board) if v == 0] # 伪合法与合法性分离：先快速生成，再逐条做将军/禁手/自杀检查 return [(s, d) for s, d in self._pseudo_moves() if self._is_legal(s, d)]

这段代码里有两个容易被忽略的设计。board压成一维而不是二维，是为了让置换表的键计算走一条连续的整数循环，二维数组取哈希时多一层索引在每秒几十万节点的搜索里会被放大成可观的常数。_pseudo_moves和_is_legal拆开，是因为伪合法着法生成极快，而合法性判定要模拟落子、检查是否自曝其将、是否踩了禁手，慢一个数量级——拆开之后才能在排序阶段用便宜的信息做粗筛，把贵的检查留到最后。

2.2 先手优势的修补工程：贴目、禁手、换手、每手两子改的其实是搜索判据

围棋先手占便宜，于是有了 5 到 7 目的贴目；五子棋的先手必胜已经被证明，于是有了禁手、换手、金球制这一串改良；六子棋干脆让先手只下一子、此后每手落两子，用规则本身把先手优势摊平；亚马逊棋用「移动之后必须设障」压缩活动空间，本质也是在给先手加负重。这些规则在棋迷眼里是平衡性调整，在写程序的人眼里是三个具体的改动点，每一个都会直接改到代码里。

第一是终局判据。围棋的胜负是「地盘差减去贴目」，评估函数的输出必须和这个换算严格一致，否则会出现程序明明领先却认输的荒唐局面。第二是着法生成器多一层过滤器，禁手判定本身是个小规模搜索——活三、冲四、长连要分别识别，判定逻辑写错，程序会自己走进禁手点被判负。第三是分支因子被规则改写，六子棋每手两子意味着单层分支从 b 变成大约 b²/2，同等时间内能搜的深度直接腰斩，这也是为什么填子类棋在中后盘更依赖候选点裁剪而不是蛮力加深。

表格里最扎眼的是围棋那一行。分支因子大不是最要命的，要命的是「评估」这一列——象棋里你可以说「我多一个车，值五分」，围棋里没有一个局部子能换算成分数，厚势和实地的兑换关系连职业棋手都说不清。这个差异后来逼出了完全不同的技术路线，第 4 章会展开。

2.3 单人与多人：华容道为什么不能用对抗搜索

华容道被归进这份讲义的棋类谱系里，乍看有点奇怪——滑块游戏，没有对手。但从状态空间的角度看，它恰恰提供了一个对照组：单人游戏没有「对手」这个变量，所以搜索目标不是极大极小，而是状态图上的最短路。一次移动一个人物到空格，直到把最大的方块挪到出口，这是标准的图搜索问题，广度优先、双向广度优先、IDA* 都能上，启发式用错位数或曼哈顿距离。它没有剪枝窗口那套东西，因为有对抗才有上下界。

多人博弈又是另一种退化。跳棋这类三人以上的局面，回传不再是非此即彼的 min 和 max，而是每个玩家对自己的名次排序，工程上通常用 Max^n 把每个玩家的收益向量整体回传，或者用 paranoid 模型把其他人合并成一个联盟。这两种做法都不完美，前者组合爆炸，后者会低估对手之间的互相牵制。理解这一点很关键：分类不是给棋贴标签，而是决定你打开哪个算法工具箱——选错工具箱，后面再优化都是徒劳。

3. 博弈树的展开与剪枝：为什么砍掉一半分支还能保证结果不变

3.1 值回传的语义约定：负极大值把两套代码合并成一套

博弈树的根节点是自己走，第二层是对手走，第三层又是自己走，于是最直观的写法是最大值层和最小值层交替。这套写法能跑，但代码里到处是if depth % 2 == 0的分支，一个符号写反就会出现「程序帮对手选棋」的经典 bug，而且这种 bug 在浅层测试里往往看不出来。工程上的标准解法是负极大值：每一层都取最大值，但在递归返回时把子节点的分数取负，等价于把「对手的好」翻译成「我的坏」。

这里的语义必须钉死：返回值永远是从当前行棋方视角看的分值，正数表示当前行棋方占优。一旦这个约定在某个函数里被破坏——比如评估函数返回的是红方视角而搜索里当成行棋方视角——程序不会报错，棋力会莫名其妙地掉，这属于血泪经验里最难查的一类问题。

INF = 10 ** 9 def negamax(pos, depth, alpha, beta): if depth == 0 or pos.is_terminal(): return pos.evaluate() # 统一返回「当前行棋方视角」的分值 best = -INF for move in order_moves(pos.legal_moves(), pos): # 排序质量直接决定剪枝率 child = pos.make_move(move) # 窗口取负并交换，这是 negamax 的核心语义：对手的上界就是我的下界 score = -negamax(child, depth - 1, -beta, -alpha) best = max(best, score) alpha = max(alpha, score) if alpha >= beta: # 对手不会让我走到这个分支，剪掉 break return best

参数含义需要逐个说明。depth是剩余搜索深度，减到 0 就用评估函数截断；alpha是当前行棋方已经能确保拿到的分数下界，来自祖先层更优的选择；beta是对手允许我拿到的上界。-negamax(child, depth - 1, -beta, -alpha)这一行的窗口翻转是最容易写错的地方，写反了程序照样能跑、棋力也还凑合，但剪枝结果和暴力搜索对不上，只有拿浅层暴力解逐节点比对才能发现。

3.2 alpha-beta 的不变量：什么样的分支可以被安全丢弃

剪枝能成立，靠的是一条不变量：如果一个节点已经找到一个分数不小于 beta 的走法，那么在它的父节点（对手层）看来，这个分支再往下搜出多好的结果都会被对手用别的走法否决，所以整个分支的剩余部分可以安全丢弃。反过来，如果某个子节点的分数始终不超过 alpha，说明当前行棋方还有更好的选择，这个子节点也不必精确求解。整个过程不改变根节点的返回值，只是把「不可能被选中」的部分跳过——这是 alpha-beta 能和暴力搜索给出完全相同结果的数学保证，也是它能被信任的前提。

收益有多大？在着法顺序理想的情况下，复杂度从 O(b^d) 降到 O(b^(d/2))，换句话说同样的时间可以多搜一倍的深度。这个结论有个残酷的附加条件：理想顺序。顺序随机时，剪枝率会跌到几乎为零，程序的表现和纯暴力搜索相差无几。所以「alpha-beta 能砍掉一半分支」这句话只在配了好排序的前提下成立，脱离排序谈剪枝率是耍流氓。

3.3 让剪枝率变成必然：着法排序、置换表、迭代加深

排序的常用手段有三层。最便宜的是 MVV-LVA（先试吃大子、用小子吃的着法），因为吃子往往能立刻引发剪枝；其次是杀手着法，记录同一层里曾经触发剪枝的走法优先重试；最贵的但最准的是历史启发，用一张按「走法—深度」累计的分数表给安静着法排序。三层叠加之后，实际剪枝率能逼近理论值的大半。

置换表解决的是另一个问题：不同的着法顺序会走到同一个局面，重复搜索纯属浪费。表里存的不能只是分值，还必须存深度和边界类型，否则会得出错误结论。

# 置换表条目必须携带深度与边界类型 # flag: 0=EXACT 精确值, 1=LOWER 下界（曾发生 beta 剪枝）, 2=UPPER 上界（曾未超过 alpha） TT = {} def probe(key, depth, alpha, beta): entry = TT.get(key) if entry is None or entry["depth"] < depth: return None # 深度不够的条目直接弃用，混用会导致估值失真 if entry["flag"] == 0: return entry["value"] if entry["flag"] == 1 and entry["value"] >= beta: return entry["value"] if entry["flag"] == 2 and entry["value"] <= alpha: return entry["value"] return None # 边界不匹配，只能当作没查到，继续正常搜索

depth这个字段是置换表的命门。同一个局面在深度 4 搜出来的分数，绝不能拿去替代深度 8 的结果，因为深度不同意味着看的路数不同，分值的含义也不同。这就是为什么条目里要同时记录边界类型：发生 beta 剪枝时得到的只是一个下界，它可能被高估也可能被低估，只有边界条件匹配时才能安全复用。

迭代加深是第三块拼图。先搜 1 层、2 层、3 层，逐层加码，看起来做了大量重复功，实际上是给排序提供初值——上一层的首选着法往往在下一层仍然是最好的，把它排到最前面，剪枝率立刻上一个台阶。它顺带解决了时间控制：每一层完整搜完就把当前最优解存下来，时间耗尽时直接交上一层的答案，这是竞赛里唯一的后悔药。没有迭代加深的程序，一旦超时就是裸奔。

3.4 评估函数：相对子力值只是最粗的一层

国际象棋里给兵赋 1，马和象约 3，车 5，后 9，这套相对子力值是所有评估函数的起点。中国象棋的车马炮兵权重完全不同，围棋干脆没有子力值这个概念，只有地盘、厚势和先手。评估函数的层次通常是：材料分打底，位置分（棋子位置表，比如马在中心比在边角值钱）修正，结构分（兵型、连通性、眼位、棋形的厚薄）再修正，最后加上动态项（机动性、直接威胁）。越往后越贵，也越容易引入噪声。

三条工程约束值得记住。第一，评估函数必须比搜索快一个数量级，因为它会被调用几十万次，一次多余的循环都会被放大；第二，评估误差会被搜索部分抵消，但系统性偏差不会——如果你的评估函数天生低估马的价值，搜得再深也只是把错误结论执行得更彻底；第三，评估函数必须是纯函数，不能有随机数、不能读全局状态，否则置换表里存进去的分值就失去了可复现性，调试时你会怀疑人生。

4. 蒙特卡罗树搜索：当评估函数写不出来时，用胜率代替估值

4.1 四个阶段与 UCT 公式：把置信上界塞进选择步骤

象棋类的程序靠「深搜 + 精评」取胜，这条路在围棋上撞墙了。19 路棋盘的分支因子在数百量级，评估函数又找不到可靠的局部量化方式，深搜和精评两头都堵死。蒙特卡罗树搜索换了个思路：不猜局面值多少钱，直接从这个局面开始随机下完若干盘，用胜率当作它的价值。随机对局当然很弱，但胜率是统计量，采样足够多就会收敛，而且它不需要任何领域知识。

一次完整的迭代分四步。选择：从根节点出发，每层按 UCT 公式挑一个子节点往下走，直到遇到还没完全展开的节点。扩展：给这个节点加一个没试过的着法。模拟：从新节点开始随机落子直到终局，得到胜负。回传：把结果沿着刚才的路径一路加回到每个节点的统计量上。四步循环，节点访问次数越多，树就越往有希望的方向长。

import math def uct_select(node, c=1.414): """c 是探索常数：越大越偏向少被访问的分支，越小越偏向当前胜率高的分支""" def score(ch): if ch.visits == 0: return float("inf") # 未访问的子节点优先，保证每个分支至少被试一次 exploit = ch.wins / ch.visits # 利用项：当前胜率 explore = c * math.sqrt(math.log(node.visits) / ch.visits) # 探索项 return exploit + explore return max(node.children, key=score)

公式里两个项在拔河。wins / visits是「利用」，告诉程序这个分支目前看起来不错；c * sqrt(log(N) / n)是「探索」，访问次数 n 越小这个值越大，逼程序去照顾被冷落的分支。c取 1.414 对应 UCB1 的理论值，实战里围棋程序会把它调小甚至随搜索进程动态衰减——前期多探索，后期多利用。这个参数没有普适最优，只能靠自对弈调，属于典型的玄学调参区。

4.2 围棋为什么逼出这条路，以及 MCTS 的代价

MCTS 的杀手锏是「不需要评估函数」，代价是「需要极多的模拟次数」。一盘随机对局可能几百手，每次迭代的成本远高于一次静态评估，所以它必须靠海量采样把方差压下去。纯随机模拟在围棋上还有个致命缺陷：随机落子几乎必然是愚蠢的，胜率信号极其嘈杂。后来的改进是把领域知识塞回模拟策略里（偏向提子、避免自填眼），再后来干脆用神经网络替代随机模拟和树内选择，但骨架上仍然是这四步——选择、扩展、模拟或估值、回传。

有意思的是，这条路后来反向渗透回了象棋类。当搜索深度足够深时，静态评估的误差会被稀释；当局面复杂到评估写不准时，胜率统计反而更稳。两类方法的分界线不在于棋种，而在于「你能不能写出一个便宜又准的评估函数」。写得出，深搜加剪枝更划算；写不出，就用采样去逼近。这份讲义把「基于搜索」列为机器博弈的方法学特点，正是抓住了这条主线：无论哪种棋，本质都是在巨大的状态空间里做有偏采样，区别只在于偏见的来源是人工设计的评估还是统计出来的胜率。

5. 竞赛场上的常见问题排查：五条踩坑记录

5.1 搜索层：结果对不上、越剪越慢

现象一：加了剪枝之后，浅层搜索结果和暴力搜索对不上。原因通常出在窗口传递，-negamax(child, depth-1, -beta, -alpha)里的负号和交换漏了一个，或者评估函数在不同分支返回了不同视角的分值。解决办法是写一个不带剪枝的纯 negamax 作为参照，在 3 到 4 层的穷举上逐节点比对分值，只要有一个叶子对不上就顺藤摸瓜。这个测试最好在写完搜索的第一天就做，越晚做代价越大。

现象二：置换表加了之后棋力反而下降。原因是把不同深度的条目混用了，或者边界类型标记错误——发生剪枝时得到的是下界，却被当成精确值存了进去，后续查询就会返回一个偏高的分数，程序开始自我欺骗。解决方式是给每个条目强校验深度，并对边界不匹配的查询一律返回未命中，宁可多搜一遍也不能用错值。

现象三：搜索时间忽长忽短，偶尔超时判负。没有迭代加深，或者迭代加深里没有在中途检查剩余时间。正确做法是每搜完一层检查一次预算，超时就交上一层的解；更深一层的部分结果即使看起来更好也不能用，因为它没搜完，分值的含义是残缺的。

5.2 规则层与工程层：能赢的棋被判负

现象四：程序把对手将死之后，自己反而被判违规。长将、长捉、重复局面这些规则没实现，搜索树里出现了环，程序在两个局面之间来回走，裁判按规则判负。解决方式是在局面里维护历史哈希序列，每次落子后检查是否构成三次重复，并按规则给出和棋或判负的终局分值。注意这个判定必须在搜索内部也生效，否则搜索会认为「循环下去对我有利」而主动求和。

现象五：明明能吃子却吃不掉，或者升变之后棋子消失。特殊规则漏实现。国际象棋的吃过路兵、王车易位、兵升变，中国象棋的 60 步不吃子判和，五子棋的禁手点，每一个都是独立的分支逻辑，靠人工看棋谱是测不完的。可靠的办法是 perft：从初始局面出发，统计深度 n 的叶子节点总数，和国际公认的基准值逐层对比。第 1 层差一个数，说明着法生成器有 bug；第 5 层差一大截，说明某个深层才触发的规则写错了。这是唯一能在几秒内验证规则引擎正确性的手段，没有之一。

6. 设计取舍：把棋抽象成搜索问题，你付出的和得到的

走到这里可以回头看一件事：这份讲义把中国象棋、国际象棋、围棋、五子棋、六子棋、点格棋、苏拉卡尔塔、亚马逊、华容道全塞进同一套框架里讲，代价是什么？代价是每种棋的独特性被压扁了。中国象棋的长将规则、围棋的贴目换算、五子棋的禁手判定，在通用框架里都只是「着法生成器的一个过滤器」或「终局判据的一个偏移量」，看起来很不体面。但收益同样明显：一旦你把棋抽象成「局面 + 合法着法 + 评估 + 搜索」这四个接口，negamax、alpha-beta、置换表、迭代加深、UCT 这些机制就全部可以复用，换一种棋只需要重写最底下那一层。

这个取舍在实践中有一个具体的分水岭：什么时候该做通用框架，什么时候该做专用优化。我的判断标准是分支因子和评估可靠性。分支因子小、评估写得准（象棋类），专用优化的收益极大——一个位置表、一个杀手着法表能顶几百 Elo，通用框架反而拖慢常数。分支因子大、评估写不准（围棋类），通用框架的搜索骨架就比任何手工调优都重要，因为决定胜负的是采样效率而不是某个局部知识。

验证这套取舍是否成立，靠的不是感觉。规则层用 perft 逐层对齐叶子数，这是硬指标，差一个就是错。搜索层用浅层暴力解做参照，负极大值的符号约定、剪枝的窗口传递、置换表的边界类型，都能在这个比对里现原形。棋力层用自对弈跑循环赛算相对胜率，比手工挑几盘棋看要可靠得多——人对局面的直觉在几百盘样本面前往往站不住脚。

从那以后我每次改动着法生成器，都会强制先跑一遍 perft 再谈别的优化，因为规则错一次的代价是整场比赛判负，而搜索慢一点最多是输一盘棋。顺序搞反，就是拿最贵的错误去换最便宜的收益。希望帮到你。

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