计算机博弈竞赛辅导资料：棋类、搜索与评估函数入门

简介：这份PPT讲稿来自东北大学机器博弈研究室，面向备战计算机博弈竞赛的高校学生、指导教师和初学机器博弈的算法爱好者，梳理从棋类对象到软件实现的整体知识框架。压缩包内仅1个PPT文件，约2.57MB，以单份讲稿承载完整讲授脉络，便于课堂投影与自学翻阅。内容先按着法把棋类分为走子、填子与混合三类，逐一介绍中国象棋、国际象棋、围棋、五子棋、六子棋，并兼及一字棋、点格棋、苏拉卡尔塔、亚马逊、华容道等民间与滑块类游戏；随后讲解博弈树展开与搜索、alpha-beta剪枝、棋局评估函数，分析软件由界面、棋盘模拟、搜索与评估模块构成的架构，讨论基于搜索与基于学习两类方法学特点及与数学、人工智能的学科关系。已有331人学习，适合赛前搭建知识地图、对照不同棋种理解算法取舍。

1. 计算机博弈竞赛辅导资料到底是什么：先搞清它在解决谁的困惑

小时候第一次被塞一本棋谱，大人只说“照着摆”，没人解释为什么这么摆。后来听到“计算机博弈竞赛辅导资料”这个说法，也是一样的感觉——名字听着像一摞棋谱，翻开来才发现完全是另一回事。

它更像一张地图，把“让机器学会下棋”这件事拆成几块能讲清楚的东西：研究哪些棋、一个会下棋的程序由哪几部分组成、棋局怎么打分、博弈树怎么展开、方法学上凭什么站得住。它不讲怎么赢一盘棋，讲的是那台机器被人怎么想出来。

对刚接触这个方向的人来说，最大的拦路虎往往不是数学，而是这些词之间谁管着谁——搜索和评估是什么关系，剪枝剪掉的到底是什么，为什么围棋难而五子棋早被“判了死刑”。这份计算机博弈竞赛辅导资料值得花时间搞懂，原因也在这儿：它先把概念的位置摆正，后面的术语才不至于乱成一团。

2. 为什么偏偏是棋类：计算机博弈的研究对象是怎么挑出来的

要让机器学会“动脑子”，第一步不是写代码，而是找一块合适的试验田。棋类被选中，不是因为下棋高雅，而是因为它身上恰好长着几样机器喜欢的东西：规则写在纸上、胜负判定明确、过程没有运气成分。这一章就把这块试验田的边界划清楚。

2.1 棋类与牌类的分水岭：信息是不是全摆在桌面上

棋和牌看着都是“游戏”，但对程序来说，它们是两个物种。分界线只有一条：局面信息是不是全部公开。

棋类属于完全信息动态博弈。完全信息，意思是该知道的都摆在明面上——你的车在哪、我的马在哪、轮到谁走，双方看到的是同一张棋盘，没有暗牌。“动态”不是说棋子在动，而是说双方不是同时出手，而是一步接一步，后手能看到先手干了什么再回应。

牌类属于不完全信息动态博弈。你永远不知道对手手里剩什么牌，只能根据他前面出过什么去猜。这一猜，问题的性质就变了：程序要处理的不是“我走这步他会怎么应”，而是“他手里可能是哪几种牌，各自的概率有多大”。

打个比方：下棋像两个人当面对账，账本摊在桌上，谁都能翻；打牌像各自捂着自己的牌，你只能从对方要了几张、出过什么，反推他手里还剩什么。

这条分界线之所以重要，是因为搜索类方法的前提就是“未来可以被枚举”。棋盘看得见，程序才能把“我走这步、你走那步、我再走这步”一层层铺开去算。一旦有隐藏信息，铺开的树就不再是一棵树，而是一团带概率的雾，算法得换一整套思路。所以这份资料把棋和牌明确切开，不是分类癖，是在划方法论的适用边界。

2.2 人们为什么爱下棋，机器为什么也“爱”下棋

人喜欢下棋的理由，恰好一条条对上了机器的胃口。这不是巧合，棋类能被选成研究对象，正是因为它对人友好和对机器友好在这里重合了。

第一条，下棋是为了决出胜负、比出高低，并且和某种收获挂钩，物质的也好，精神的也好。对程序来说，这意味着“赢”可以被写成一个明确的数值目标，搜索才有方向。要是目标模糊，比如“下得好看”，程序就不知道往哪优化。

第二条，规则简单明确，成功与失败的判定标准简单。这一条对机器是硬门槛：规则必须能被写成代码。中国象棋的“马走日、象走田”、国际象棋的“王车易位”、围棋的“气尽提子”，都能翻译成判定函数。规则越干净，模拟层越好写。

第三条，博弈过程透明、公平，不包含任何机会或偶然性。没有掷骰子，没有洗牌，同样的局面下走同样的着法，结果必然一样。这一点让算法的强弱可以被公平比较——赢就是赢，不存在“这把运气好”。唯一的“不公平点”是先手优势，所以围棋有贴目、五子棋有禁手和换手，这些补丁后面还会细说。

第四条，智力和经验决定胜负，问题的解决在认识意义上不需要过多的知识。这一条最容易被忽略，但对机器极其关键：下棋不需要懂“下雨要带伞”“水往低处流”这类常识。它只在一个封闭的规则世界里推演，不需要调用现实世界的知识库。早期的程序能在这条路上跑通，靠的就是这一点。

第五条，变化无穷，很难走出同样的棋谱。同一开局，两个人下十次能下出十个样子。变化多，意味着搜索空间大，正好是算法证明自己的地方——如果一盘棋三步就下完，再聪明的搜索也没处施展。

把这五条放在一起看，棋类像是一个为算法量身定制的考场：目标清晰、规则可编码、过程可复现、不需要常识、空间足够大。这也解释了为什么计算机博弈的研究对象长期集中在棋上，而不是别的游戏上。

2.3 走子、填子、混合：着法类型决定了程序骨架

同样是棋，程序内部的结构差别很大，最直接的分法不是看棋盘大小，而是看着法怎么产生。

走子类，开局前双方把棋子摆好，开局后轮流移动已有棋子。中国象棋、国际象棋、跳棋、苏拉卡尔塔、亚马逊棋都是这一类。程序要处理的是“某个棋子从 A 到 B 是否合法”，着法生成器围绕“移动”来写。

填子类，开局前盘面是空的，开局后轮流往盘上放子。围棋、五子棋、点格棋属于这一类。程序要处理的是“这个空点能不能下”，着法生成器围绕“落点”来写，通常简单得多，但分支数量往往大得多。

混合类，开局先填子，到一定条件后转为走子。五道棋是填子、走子、吃子三样都有；将棋类则是走子、吃子、填子混在一起。这一类的模拟层最麻烦，因为规则要在不同阶段切换，代码里最容易写漏一个状态标志。

还有一条分法是按参与人数：单人游戏如华容道，双人游戏如象棋、围棋、五子棋，多人游戏如跳棋。双人弈棋占了绝大多数，原因是双人博弈的结构最干净——一方所得即另一方所失，评估函数只需要站在一方视角打分，不用处理“三方混战”这种麻烦事。

把常见棋种摊开看一遍，能直观感受到这块试验田有多宽：

这张表里有意思的一点是：民间棋类的规则往往比国际大赛的棋更“野”。一字棋允许一次移动多个棋子，三通棋给一方一次连下两着的机会，亚马逊棋每步还要堵一个格子。这些看似古怪的规则，恰恰是练手的好材料——规则越不规整，着法生成和合法性判定就越容易写出 bug，也越能暴露程序结构的薄弱处。

3. 一台会下棋的机器由什么拼成：软件构成与搜索原理

把棋种选好，接下来要回答的是“程序里到底装了什么”。很多人以为会下棋的程序核心是一段聪明的算法，实际上它是几个部件咬合起来的整体，缺一块都跑不动。这一章按部件拆开看。

3.1 四个部件：界面、棋盘模拟、搜索、评估

一台会下棋的程序，通常可以分成四层。

第一层是界面，负责显示棋盘、接收点击、把结果画出来。这一层最贴近用户，也最不影响棋力，但在竞赛里反而容易翻车——超时、非法着法输入、复盘显示错位，都出在这里。

第二层是棋盘模拟，是整台程序的地基。它包含三件事：局面怎么存、着法怎么生成、规则怎么裁决。局面存储决定了程序跑多快，用二维数组还是位棋盘，差别很大；着法生成决定了程序能想多远，漏掉一个合法着法，整棵搜索树就是错的；规则裁决决定了程序会不会被判负，长将怎么算、多少步不吃子判和、时间怎么控制，全在这一层。

第三层是搜索，负责在博弈树上往下算，回答“走哪一步”。

第四层是评估，负责在没有算到终局时给局面打分，回答“这个局面对我好不好”。

这四层里，界面和模拟层是“不出错就行”，搜索和评估才是拉开差距的地方。但顺序不能颠倒：模拟层写错，搜索再深也是错上加错。血泪经验通常都来自这里——着法生成里少判一条和棋规则，程序在关键时刻自己走进死局。

3.2 博弈树展开：把“我一步、你一步”画成一棵倒挂的树

搜索的直觉很简单：我走一步，对手会怎么应，我再怎么应，一路推下去，看哪条路最后对我有利。

把这件直觉画出来，就是博弈树。根节点是当前局面，每一条边是一种着法，子节点是走完这一步后的新局。一层是我走，下一层是对手走，再下一层又是我走，如此交替。叶子节点是搜索停下的地方——可能是终局，也可能是到达了深度上限。

树的规模涨得有多快？设分支因子为 b，也就是平均每步有多少种合法着法；搜索深度为 d，那么节点数量大约是 b 的 d 次方。国际象棋的分支因子通常在几十的量级，取 40 算，深度 6 就是 40 的 6 次方，四十多亿个节点。就算一秒算一百万个节点，也要跑一个多小时。

这就是为什么“多想几步”听起来朴素，做起来是硬仗。围棋更夸张，分支因子动辄两三百，同样深度下节点数直接失控。所以真实的程序从来不是老老实实铺满整棵树，而是想办法少算——这就轮到剪枝登场。

3.3 剪枝与评估函数：把省下来的时间换成深度

剪枝的核心思路，用一句话说：已经确定没戏的分支，就别再往下算了。

拿 alpha-beta 剪枝举例。假设你正在比较几个选择，已经找到一个“至少能保证 5 分”的走法。现在你去检查另一个分支，刚看了对手的一步应招，就发现这一招会让你最多只能拿 3 分。既然对手一定会选这招，那这个分支的上限就是 3 分，已经不如手上的 5 分，剩下没看的着法全部作废，直接剪掉。

下面这段是示意代码，把负极大值搜索和 alpha-beta 剪枝合在一起：

# 负极大值搜索 + alpha-beta 剪枝（示意，着法生成与评估细节略） INF = 10 ** 9 def negamax(board, depth, alpha, beta, side): # 到达深度上限或终局，交给评估函数打分 if depth == 0 or board.is_game_over(): return board.evaluate(side) best = -INF for move in board.legal_moves(): # 着法生成，最容易出错的一环 board.make_move(move) # 走一步，进入子局面 # 对手视角的分数取负，就变回自己视角 score = -negamax(board, depth - 1, -beta, -alpha, -side) board.undo_move(move) # 撤销，恢复到原局面 best = max(best, score) # 记录当前最好的结果 alpha = max(alpha, score) # 抬高自己的下界 if alpha >= beta: # 对手不会放任你拿到这个分数 break # 剪掉剩余着法 return best

几个参数的含义：depth是还剩几层可以往下算；alpha是当前一方已经能确保拿到的分数下界；beta是对方能接受的上界；side表示轮到谁走。函数返回的是站在side视角的分数。make_move和undo_move必须严格配对，少撤销一步，后面所有搜索都是脏数据。

剪枝能省多少？在着法排序理想的情况下，同样的时间可以把搜索深度大致翻一倍，等效分支因子从 b 降到接近根号 b。着法排序做得好不好，直接决定剪枝效率——先试吃子、先试上一轮算出来最好的那步，都是常见做法。

评估函数则是另一条腿。搜索算不到终局时，只能靠它给局面打分。国际象棋里最经典的做法是子力值加位置分：给兵定 1 分，马约 3 分、象约 3 分、车约 5 分、后约 9 分，再叠加机动性、王的安全、兵形结构这些项。这套相对子力值之所以好用，是因为棋子的价值在大量对局中被反复验证过。

但同样的思路搬到围棋上就失效了。围棋棋子本身没有固定价值，一颗子的强弱取决于周围棋形和全局配置，没法用“这颗子值几分”来近似。这也是为什么围棋的评估长期是难题，后来的突破靠的是把评估本身也交给网络去学，而不是人手写规则。

一句话收束这一章：模拟层保证不出错，搜索负责算得远，评估负责算得准，剪枝负责在有限时间里把前两者榨出最大效果。

4. 常见误区与易混概念：搜索、评估、学习到底谁管什么

概念一多，最容易出现的情况是把不相干的东西混成一锅。下面五条是初学者最常踩的坑，每一条都按“混在哪、为什么混、怎么分”拆开说。

4.1 误区一：搜索越深，棋力就一定越强

易混点：把“算得深”直接等同于“下得好”。

为什么混：深度确实直观，加一层深度看得更远，听起来就该更强。而且跑分时深度是可量化的数字，很容易被当成唯一指标。

怎么区分：深度只保证看得远，不保证看得对。如果叶子节点上的评估函数本身偏差很大，搜得越深，错误被放大的机会越多——你会更精确地走向一个错误结论。反过来，一个评估更准、深度稍浅的程序，往往赢过深度更大但评估粗糙的对手。判断该加深度还是改评估，看的是“输的棋是漏算还是看错”，漏算是深度问题，看错是评估问题，这两件事的修法完全不同。

4.2 误区二：评估函数算出来的分数就是胜率

易混点：把评估分数当成“我赢的概率”。

为什么混：分数高的局面确实更容易赢，因果方向没错，于是很容易顺口说成胜率。

怎么区分：评估分数是一个相对量，只有在自己和自己比较时才有意义。同一个评估函数下，+200 分比 +100 分好，但 +200 分不代表八成胜率，换一个评估函数，这个数字就完全变了。真正的胜率要靠大量对局统计或者专门的概率模型去估，它是另一个层面的东西。复习时看到“评估值 +5.0”这种表述，先问一句：这是谁定义的分数体系。

4.3 误区三：蒙特卡罗树搜索就是深度学习

易混点：把两种完全不同来源的方法当成一件事。

为什么混：它们在著名棋类程序里经常一起出现，名字又都很“高级”，很容易被合并成一个模糊的印象。

怎么区分：蒙特卡罗树搜索是一种搜索策略，核心是用大量随机模拟的结果来估计某个分支值不值得深入，它不学任何东西，每次都是现算。深度学习是从大量数据里拟合出一个函数，比如用网络替代人工评估。两者可以组合——网络给出初判，搜索负责验证和修正——但组合不等于等同。判断一句话对不对，看它说的是“怎么分配计算资源”还是“参数从哪来”，前者是搜索，后者是学习。

4.4 误区四：棋类那一套能直接搬去处理牌类

易混点：以为博弈就是博弈，棋和牌只差一副道具。

为什么混：两者都叫游戏，都有对手，都要做决策，表面上共用“博弈”两个字。

怎么区分：回到信息那条线。棋类是完全信息，程序可以放心展开博弈树；牌类是不完全信息，同一局面下还带着一堆未知，直接展开会得到一棵“自己骗自己”的树——你假设对手手里有你想象不到的牌，算出来的结论自然不可靠。这类问题通常要引入概率信念、采样或者对策论里的均衡概念。所以看到“把棋类算法改改就能打牌”的说法，基本可以直接判定为想当然。

4.5 误区五：规则越简单，机器越容易下好

易混点：把“规则简单”当成“问题简单”。

为什么混：围棋规则几句话就能讲完，比国际象棋的升变、易位、吃过路兵干净得多，直觉上应该更好写程序。

怎么区分：难度取决于搜索空间的形状，不取决于规则条文的长度。围棋规则简单，但对局面的判断极其困難，人眼一眼能看出的厚薄、模样、大势，很难写成打分规则；同时分支因子巨大，搜索也铺不开。反过来，国际象棋规则复杂，但每个兵种价值清晰、局面评估有成熟套路，反而更早被攻克。判断一个棋种难不难，看两件事：分支因子有多大，局面好不好评估。这两条都不看规则写了多少行。

5. 难度的账本：为什么围棋最难、五子棋却早已被判“死刑”

竞赛里选棋种，本质上是在选难度档位。同样是棋盘上摆子，有的棋种已经被算穿，有的棋种至今没有定论。这一章把“难度”这件事拆成可比较的两笔账。

5.1 分支因子与状态空间：难度不是看棋盘大小

很多人以为棋盘越大越难，这个直觉只在同一类棋里成立。真正决定难度的是两件事：每一步有多少种选择，以及每个局面好不好判断。

五子棋棋盘 15×15，看着不小，但它的胜负条件极其明确——连成五个就赢，局部形状可以枚举，所以先手已经被证明必胜。这个结论一出来，竞技层面就必须靠规则补丁来续命，否则比赛没有悬念。围棋棋盘 19×19，规则比五子棋还简单，却至今被认为是计算机博弈难度最大的棋种，原因就在分支因子和局面判断这两项上：每步可选点动辄两三百，而“这个局面谁占优”很难用几条规则说清。

打个比方，五子棋像一条有明确终点的窄路，走得快的人迟早能走到头；围棋像一片没有标尺的旷野，方向感本身就是最难的部分。

5.2 先手优势与规则补丁：贴目、禁手、换手、连下两子

棋类有一个天然的“不公平点”：先手占便宜。越是均衡的棋，这个便宜越是决定性的。所以成熟的棋种几乎都打了补丁。

围棋用贴目，先手要贴给后手 5 到 7 目左右，把先行的便宜折算成分数还回去。五子棋的办法更硬：先手必胜已被证明，于是引入禁手限制先手的某些走法，再引入换手让对手可以选择执黑还是执白，还有金球制一类的赛制改进，目的都是把胜率拉回五五开。六子棋的思路又不一样：先手先下一子，之后每手落两子，用“后手每轮多下一子”的方式削减先手优势，代价是复杂度显著提高。

这些补丁对写程序的人意味着什么？意味着规则实现的工作量成倍增加。禁手判定要精确到每一种形成方式，换手要在开局阶段切换角色，连下两子要让搜索层支持“同一方连续行动”的节点。这些地方写错一个分支，比赛里就是一次莫名其妙的判负。所以别小看补丁，它们往往比主规则更容易出 bug。

5.3 9×9 为什么常被单独拎出来

19×19 的围棋有 361 个交叉点，光是“哪里能下”这一层就够喝一壶。所以在教学和算法验证阶段，常见的做法是先啃小棋盘，9×9 只有 81 个点，状态空间小了一大截，搜索还能铺得开，评估的反馈也更清晰。很多方法都是先在缩小的棋盘上跑通，再考虑往全盘迁移。

这不是取巧，而是工程上的常规节奏：先把一个问题缩小到能观察、能复现、能对比的规模，再谈扩展。反过来，一上来就对着全盘调参，往往连“是搜索不够还是评估不准”都分不清，只能靠玄学改数字。

6. 什么时候该翻这份资料，什么时候别指望它

资料再好，也有它管不到的地方。判断要不要花时间，其实就看你现在卡在哪一步。

6.1 这些情况值得认真看

第一种，刚接触计算机博弈，术语一堆但拼不成图。这时候最需要的是把概念的位置摆正：什么是完全信息、博弈树为什么要展开、剪枝剪的到底是什么、评估和搜索各管哪一段。这份资料的价值就在这里，它按“对象—原理—软件构成—评估—搜索”的顺序铺开，读完能形成一条线，而不是一堆散点。

第二种，准备参加竞赛，要选棋种、搭框架。不同的棋种对着法生成、评估函数、规则裁决的要求差别很大，走子类和填子类的程序骨架甚至不一样。先看清楚自己要做的棋属于哪一类，能省下大量返工。

第三种，带队或者讲课，需要一份能讲清楚的知识地图。把棋类分类、软件构成、方法学特点、学科关系这几块讲明白，比直接甩代码有用得多。

6.2 这些情况别指望它

第一种，想要现成的强程序源码。这份资料讲的是原理与方法学，不是某个棋种的完整实现，指望复制粘贴就能打赢比赛，会失望。

第二种，想学最新的深度强化学习方法。资料的方法学立足点是“基于搜索”，这是经典路线，也是理解后续一切改进的地基，但它本身不覆盖神经网络训练那一套。

第三种，想靠它速成某个具体规则细节。不同棋种的规则补丁千差万别，禁手怎么判、贴目怎么算，最终还是要回到该棋种的正式规则文本去核对。

我自己踩过的一个坑是：拿到一个新棋种就想直接开写，规则看到一半就动手，结果着法生成写完才发现漏了和棋判定，搜索跑出来的结果全是错的，回头重写模拟层花了双倍时间。从那以后我每次碰新棋种，都强制先把规则补丁和胜负判定一条条列出来，再动第一行代码。希望帮到你。

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