简介这份PPT讲稿来自东北大学机器博弈研究室面向备战计算机博弈竞赛的高校学生、指导教师和初学机器博弈的算法爱好者梳理从棋类对象到软件实现的整体知识框架。压缩包内仅1个PPT文件约2.57MB以单份讲稿承载完整讲授脉络便于课堂投影与自学翻阅。内容先按着法把棋类分为走子、填子与混合三类逐一介绍中国象棋、国际象棋、围棋、五子棋、六子棋并兼及一字棋、点格棋、苏拉卡尔塔、亚马逊、华容道等民间与滑块类游戏随后讲解博弈树展开与搜索、alpha-beta剪枝、棋局评估函数分析软件由界面、棋盘模拟、搜索与评估模块构成的架构讨论基于搜索与基于学习两类方法学特点及与数学、人工智能的学科关系。已有331人学习适合赛前搭建知识地图、对照不同棋种理解算法取舍。1. 计算机博弈竞赛辅导资料到底是什么先搞清它在解决谁的困惑小时候第一次被塞一本棋谱大人只说“照着摆”没人解释为什么这么摆。后来听到“计算机博弈竞赛辅导资料”这个说法也是一样的感觉——名字听着像一摞棋谱翻开来才发现完全是另一回事。它更像一张地图把“让机器学会下棋”这件事拆成几块能讲清楚的东西研究哪些棋、一个会下棋的程序由哪几部分组成、棋局怎么打分、博弈树怎么展开、方法学上凭什么站得住。它不讲怎么赢一盘棋讲的是那台机器被人怎么想出来。对刚接触这个方向的人来说最大的拦路虎往往不是数学而是这些词之间谁管着谁——搜索和评估是什么关系剪枝剪掉的到底是什么为什么围棋难而五子棋早被“判了死刑”。这份计算机博弈竞赛辅导资料值得花时间搞懂原因也在这儿它先把概念的位置摆正后面的术语才不至于乱成一团。2. 为什么偏偏是棋类计算机博弈的研究对象是怎么挑出来的要让机器学会“动脑子”第一步不是写代码而是找一块合适的试验田。棋类被选中不是因为下棋高雅而是因为它身上恰好长着几样机器喜欢的东西规则写在纸上、胜负判定明确、过程没有运气成分。这一章就把这块试验田的边界划清楚。2.1 棋类与牌类的分水岭信息是不是全摆在桌面上棋和牌看着都是“游戏”但对程序来说它们是两个物种。分界线只有一条局面信息是不是全部公开。棋类属于完全信息动态博弈。完全信息意思是该知道的都摆在明面上——你的车在哪、我的马在哪、轮到谁走双方看到的是同一张棋盘没有暗牌。“动态”不是说棋子在动而是说双方不是同时出手而是一步接一步后手能看到先手干了什么再回应。牌类属于不完全信息动态博弈。你永远不知道对手手里剩什么牌只能根据他前面出过什么去猜。这一猜问题的性质就变了程序要处理的不是“我走这步他会怎么应”而是“他手里可能是哪几种牌各自的概率有多大”。打个比方下棋像两个人当面对账账本摊在桌上谁都能翻打牌像各自捂着自己的牌你只能从对方要了几张、出过什么反推他手里还剩什么。这条分界线之所以重要是因为搜索类方法的前提就是“未来可以被枚举”。棋盘看得见程序才能把“我走这步、你走那步、我再走这步”一层层铺开去算。一旦有隐藏信息铺开的树就不再是一棵树而是一团带概率的雾算法得换一整套思路。所以这份资料把棋和牌明确切开不是分类癖是在划方法论的适用边界。2.2 人们为什么爱下棋机器为什么也“爱”下棋人喜欢下棋的理由恰好一条条对上了机器的胃口。这不是巧合棋类能被选成研究对象正是因为它对人友好和对机器友好在这里重合了。第一条下棋是为了决出胜负、比出高低并且和某种收获挂钩物质的也好精神的也好。对程序来说这意味着“赢”可以被写成一个明确的数值目标搜索才有方向。要是目标模糊比如“下得好看”程序就不知道往哪优化。第二条规则简单明确成功与失败的判定标准简单。这一条对机器是硬门槛规则必须能被写成代码。中国象棋的“马走日、象走田”、国际象棋的“王车易位”、围棋的“气尽提子”都能翻译成判定函数。规则越干净模拟层越好写。第三条博弈过程透明、公平不包含任何机会或偶然性。没有掷骰子没有洗牌同样的局面下走同样的着法结果必然一样。这一点让算法的强弱可以被公平比较——赢就是赢不存在“这把运气好”。唯一的“不公平点”是先手优势所以围棋有贴目、五子棋有禁手和换手这些补丁后面还会细说。第四条智力和经验决定胜负问题的解决在认识意义上不需要过多的知识。这一条最容易被忽略但对机器极其关键下棋不需要懂“下雨要带伞”“水往低处流”这类常识。它只在一个封闭的规则世界里推演不需要调用现实世界的知识库。早期的程序能在这条路上跑通靠的就是这一点。第五条变化无穷很难走出同样的棋谱。同一开局两个人下十次能下出十个样子。变化多意味着搜索空间大正好是算法证明自己的地方——如果一盘棋三步就下完再聪明的搜索也没处施展。把这五条放在一起看棋类像是一个为算法量身定制的考场目标清晰、规则可编码、过程可复现、不需要常识、空间足够大。这也解释了为什么计算机博弈的研究对象长期集中在棋上而不是别的游戏上。2.3 走子、填子、混合着法类型决定了程序骨架同样是棋程序内部的结构差别很大最直接的分法不是看棋盘大小而是看着法怎么产生。走子类开局前双方把棋子摆好开局后轮流移动已有棋子。中国象棋、国际象棋、跳棋、苏拉卡尔塔、亚马逊棋都是这一类。程序要处理的是“某个棋子从 A 到 B 是否合法”着法生成器围绕“移动”来写。填子类开局前盘面是空的开局后轮流往盘上放子。围棋、五子棋、点格棋属于这一类。程序要处理的是“这个空点能不能下”着法生成器围绕“落点”来写通常简单得多但分支数量往往大得多。混合类开局先填子到一定条件后转为走子。五道棋是填子、走子、吃子三样都有将棋类则是走子、吃子、填子混在一起。这一类的模拟层最麻烦因为规则要在不同阶段切换代码里最容易写漏一个状态标志。还有一条分法是按参与人数单人游戏如华容道双人游戏如象棋、围棋、五子棋多人游戏如跳棋。双人弈棋占了绝大多数原因是双人博弈的结构最干净——一方所得即另一方所失评估函数只需要站在一方视角打分不用处理“三方混战”这种麻烦事。把常见棋种摊开看一遍能直观感受到这块试验田有多宽棋种棋盘与棋子值得注意的特点中国象棋9×10 交叉点红黑各 7 个兵种、16 枚子有长将、长捉等和棋规则还有 60 步不吃子判和、时间约束国际象棋8×8 格双方各 16 枚子王车易位、兵升变、吃过路兵马不蹩腿、象可过河、后威力最大围棋19×19 交叉点规则最简单博弈难度最大先手有优势用贴目平衡五子棋15×15先手已被证明必胜靠禁手、换手、金球制一类赛制补救六子棋19×19先手先下一子之后每手两子用来削减先手优势复杂度显著提高一字棋线性棋位走子距离不限但不准逆行可同时移动多个棋子须停在同一个目标棋位二虎棋虎犬两方虎方先行可跳吃虎吃够数量获胜犬方靠围困使虎无子可动获胜三通棋64 个小正三角形棋位双方各 32 枚轮流布子其中一方有一次连下两着的机会先成三通者胜点格棋点阵连线连成方格者占格并再连一边格多者胜要关注死格、双环、长链、短链、环苏拉卡尔塔带弧线的盘面除吃子外每步一格沿弧吃子且必须走完整条弧吃光对方获胜亚马逊棋每方 4 个“后”每步包含移动和设障争取更大活动范围无子可动判负华容道滑块盘面单人游戏一次移动一个人物到空格把最大方块移到指定出口这张表里有意思的一点是民间棋类的规则往往比国际大赛的棋更“野”。一字棋允许一次移动多个棋子三通棋给一方一次连下两着的机会亚马逊棋每步还要堵一个格子。这些看似古怪的规则恰恰是练手的好材料——规则越不规整着法生成和合法性判定就越容易写出 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 这些情况别指望它第一种想要现成的强程序源码。这份资料讲的是原理与方法学不是某个棋种的完整实现指望复制粘贴就能打赢比赛会失望。第二种想学最新的深度强化学习方法。资料的方法学立足点是“基于搜索”这是经典路线也是理解后续一切改进的地基但它本身不覆盖神经网络训练那一套。第三种想靠它速成某个具体规则细节。不同棋种的规则补丁千差万别禁手怎么判、贴目怎么算最终还是要回到该棋种的正式规则文本去核对。你的处境建议术语看不懂、概念串不起来从头读重点看原理与软件构成两部分要选棋种、搭程序框架重点看棋类分类与着法类型先定骨架再写代码程序能跑但总输回头查评估函数与搜索深度分清是漏算还是看错想要现成源码或最新算法不合适这份资料不承担这两件事我自己踩过的一个坑是拿到一个新棋种就想直接开写规则看到一半就动手结果着法生成写完才发现漏了和棋判定搜索跑出来的结果全是错的回头重写模拟层花了双倍时间。从那以后我每次碰新棋种都强制先把规则补丁和胜负判定一条条列出来再动第一行代码。希望帮到你。本文还有配套的精品资源点击获取