★ FEATURED ARTICLE 简介这份计算机博弈竞赛辅导PPT由东北大学机器博弈研究室整理面向准备参加计算机博弈类竞赛的学生、教练及入门研究者系统讲解从理论基础到实战评估的核心内容。课件围绕棋类介绍与分类、计算机博弈基本原理、博弈树展开与分析、棋局评估、机器博弈方法学特点及学科关系展开涵盖中国象棋、国际象棋、围棋、五子棋、六子棋及一字棋、二虎棋、三通棋、点格棋等典型棋种规则并介绍alpha-beta剪枝、搜索算法、启发式评估等关键技术可帮助读者快速建立计算机博弈知识框架明确竞赛准备方向。资源为单个PPT文件大小约2.57MB便于直接查看与演示适合用作赛前培训、课堂讲义或自学入门材料。目前已有329人学习下载。1. 计算机博弈竞赛辅导资料到底讲了什么不是棋谱是一套让机器会下棋的方法第一次看到“计算机博弈竞赛辅导资料”这个名头你可能以为它是一本棋谱合集教人怎么赢棋。其实方向完全相反——它要解决的是怎么让计算机自己学会下棋并在和人对弈、和程序对弈时做出合理决策。通俗地说教计算机下棋就像教一个完全没摸过球的新手打球先讲规则再讲战术最后在实战里学会取舍。这份资料讲的正是这样一套完整的“棋力工程”方法论从棋类分类到博弈树、搜索算法、评估函数再到博弈软件的模块构成。它不告诉你某一步怎么走而是告诉你怎样让机器“思考”下一步。参加计算机博弈竞赛不管选哪个棋种认知起点都是它。2. 计算机博弈的基本原理机器凭什么“想”到下一步下棋这件事对人类来说靠经验和棋感对计算机来说靠的其实只有一个字搜。把棋盘上所有可能的变化展开逐个比较再从中挑一个最有利的着法。这个思路听起来笨却是计算机博弈所有方法的地基。2.1 博弈树把棋盘局面变成一棵不断分叉的树要理解计算机怎么下棋先要理解一个关键模型博弈树。简单说把一盘棋的每一个局面都当作一个节点从当前局面出发每走一步合法着法就长出一个子节点如此层层展开就形成一棵树。根节点是当前棋盘叶节点是胜负已分或停止搜索的界面。计算机下棋本质上就是两件事建树然后在树里找最优解。举个例子。五子棋 15×15 的棋盘开局有 225 个空位第一步就有 225 种合法着法对手回应之后每个分支又各有 224 种新选择。只看两步博弈树就有大约 5 万个节点看到四步节点数超过 20 亿。中国象棋的分支因子大概在 40 上下国际象棋在 35 左右围棋更是高达 200 以上。程序想在几秒内落子能展开的树其实非常有限。有一个初学者容易忽略的点程序搜索时没有任何“棋感”它不会像人一样凭经验跳过某些看起来不专业的棋形它只会把所有合法着法一视同仁地列出来。这正是为什么博弈程序经常走出奇怪但有效的招法——这种招法往往是人类棋手靠经验直接忽略的。另外资料里专门强调棋类属于“完全信息动态博弈”。完全信息的意思是双方都能看到全盘棋子不存在隐藏信息动态的意思是双方轮流决策、一步改变一个局面。这两个词保证了博弈树可以被完整构建。与之相对的是牌类对方的牌你看不到博弈树就残缺不全方法也就完全不同。2.2 极大极小搜索轮到我取最大轮到你取最小博弈树搭好之后下一个问题是怎么从树里挑出最优着法答案可以概括成一句话“我取最大你取最小”。轮到我走我会挑对自己最有利的分支也就是取所有子局面的最大值轮到对手走对手一定会挑对我最不利的分支也就是取最小值。这个交替取大取小、层层倒推回根节点的过程就是极大极小搜索。它把“双方都尽力下好”变成了一段纯粹的数学逻辑。把这种思路写成 Python核心逻辑很短def minimax(node, depth, maximizing): # 深度到底或已经分出胜负直接返回评估分 if depth 0 or node.is_terminal(): return evaluate(node) if maximizing: # 轮到己方从所有子局面里挑分数最高的 best -float(inf) for child in node.children(): best max(best, minimax(child, depth - 1, False)) return best else: # 轮到对方对方会挑分数最低的分支 best float(inf) for child in node.children(): best min(best, minimax(child, depth - 1, True)) return best三个参数是关键node是当前棋盘局面depth是剩余搜索层数maximizing表示当前轮到“我方”还是“对方”。maximizingTrue时取所有子节点的最大值False时取最小值。这个交替过程模拟的就是“双方都绝不犯错”的最优博弈。但这段代码有个致命问题它太慢了。国际象棋分支因子约 35每加深一层节点数就要乘以 35。你想看 10 层需要评估约 2 万亿个局面任何普通计算机都扛不住。所以实际程序必须配合剪枝技术也就是下一小节要说的 alpha-beta 剪枝。2.3 alpha-beta 剪枝不值得看的分支直接砍掉alpha-beta 剪枝是为极大极小搜索配套的优化。它的核心思想一句话就能说清当某个分支已经“不可能翻盘”时就不要再往深处看了。假设我在走棋已经发现走 A 点能拿到 5 分优势。接着评估 B 点刚看了两步发现对方有一种应对能把我压到 3 分。这时候 B 点的剩余分支还有必要继续看吗没必要。因为 B 点无论后面怎么走最好结果也不会超过 3 分不可能超过 A 点的 5 分。直接砍掉 B 点的剩余分支省下的时间去搜别的候选着法。带剪枝的代码长这样def alphabeta(node, depth, alpha, beta, maximizing): if depth 0 or node.is_terminal(): return evaluate(node) if maximizing: value -float(inf) for child in node.children(): value max(value, alphabeta(child, depth - 1, alpha, beta, False)) alpha max(alpha, value) if alpha beta: break # 对方已不可能让我选这个分支剪枝 return value else: value float(inf) for child in node.children(): value min(value, alphabeta(child, depth - 1, alpha, beta, True)) beta min(beta, value) if beta alpha: break # 我方已不可能选这个分支剪枝 return value对比无剪枝版本核心区别是多了两个变量alpha表示我方目前能保证的最好结果beta表示对方目前能压到的最差结果。一旦某个分支上alpha不小于beta说明这个分支已经失去继续搜索的价值直接终止。网上偶尔会看到有人把剪枝说成“靠经验猜着砍”这是误解。alpha-beta 剪枝不是启发式技巧它不改变最终结果只减少计算量。我第一次实现后特地把剪枝前后的走法用多局棋做了比对结果完全一致这才放心。在着法排序较优的情况下alpha-beta 能把搜索量降到原来的平方根量级。原本要评估 100 万个节点剪枝后可能只需 1 万个节点这是博弈程序能“多看几步”的根本原因。注意剪枝效果严重依赖着法排序。如果每次搜索都从很差的着法开始alpha 迟迟上不去剪枝率就会很低如果先把优势着法排到前面剪枝效率会大幅提升。2.4 时间与深度竞赛程序真正在纠结的权衡初学博弈编程时最容易纠结的问题就是“到底搜多少层”。答案很直白没有固定值完全取决于时间限制和分支因子。竞赛程序通常有严格的计时规则每步棋必须在几秒内落下。搜索层数每加一耗时往往会变成原来的好几倍。于是实际程序几乎都会用“迭代加深”先搜 1 层时间还有就搜 2 层还有时间就继续加到 3 层。每次都用上一次搜索的着法作为起点时间快用完时手里已经握着当前深度下的最佳着法。迭代加深会重复计算之前层级的节点看起来浪费但实际收益远大于代价。它让你稳稳地用满所有可用时间也避免“某一步搜索太久导致超时判负”的翻车。竞赛里超时判负非常严格算法再漂亮时间用完就是输了。这个血泪经验我体会特别深——最初我把搜索深度调得很高棋力看着不错一上正式对局就频繁超时。后来强制改成迭代加深才把时间和棋力平衡好。资料里还提到一个进阶点alpha-beta 剪枝要配合着法排序才能发挥威力。这很容易理解前面那个 A 点 5 分的例子如果能尽早搜到 A后面的 B 就能尽早被剪掉。常用的排序策略有两种一是先延伸“上一步最优着法”对应的分支二是先用浅层搜索给每个着法粗打分再按分数从高到低进入深层搜索。这两个技巧都很朴实却能让搜索效率拉开数量级差距。3. 棋类介绍与分类选错棋种等于选错战场原讲座用了相当大的篇幅讲棋类介绍和分类这不是凑字数。因为不同棋种的博弈树结构差异巨大搜索难度、评估函数设计、开局库策略全都不同。选错棋种等于拿着一把给五子棋设计的螺丝刀去拆国际象棋。3.1 棋类和牌类的根本区别完全信息与不完全信息要研究机器博弈先要明确对象这里的“棋”基本都不含牌。为什么要把棋和牌分开因为棋局的信息是透明的双方都能看到全部子力和布局属于“完全信息动态博弈”牌类的底牌只有自己能看到属于“不完全信息动态博弈”还带有随机性。这个区别直接决定了计算机的处理方式。完全信息博弈下博弈树是完整的每个节点都代表一个确定的对局状态程序可以通过搜索和评估来决策。不完全信息博弈下很多节点是“概率分支”——你连对手手里有什么都不知道只能估算期望值更多要依靠统计学和推理模型。让一个只会做树搜索的程序去打牌往往会输得一塌糊涂。所以计算机博弈竞赛里的项目几乎都是棋类而不是牌类。选择棋类项目本质上是在选一个“信息完全、规则明确、没有随机性”的决策问题。如果以后有人照搬这套方法去写打牌程序就必须额外处理隐藏信息和概率分支不能直接套用。3.2 走子类、填子类、混合类三种着法形态决定程序架构资料里把棋按着法形态分成了三类这个分类对程序设计影响很大。类别代表棋种规则模块特点搜索与评估侧重走子类中国象棋、国际象棋、苏拉卡尔塔、亚马逊行棋规则复杂涉及移动、吃子、特殊规则子力与位置评估填子类围棋、五子棋、点格棋只有放置没有移动棋形识别、空间评估混合类五道棋、日本将棋放置、移动、吃子并存分阶段设定评估重点走子类开局前棋子已摆好之后双方轮流移动。这类棋的行棋逻辑通常最复杂要处理吃子、将军、易位、禁手等各种特殊状态规则模块的工作量最大。填子类开局前盘面是空的双方轮流往空位放子。行棋逻辑相对简单因为只有“放”没有“移”。但简单不等于容易围棋就是最典型的“规则最简单、博弈最难”的例子它的难点在评估而不在规则。混合类要先放子再走子比如日本将棋和五道棋。程序要同时处理两套规则代码架构如果不够灵活后期几乎必然陷入“改一处动全身”的泥潭。写代码前先把棋种是哪一类想清楚能省下大量重构时间。3.3 从中国象棋到围棋规则简单不等于博弈简单资料里有一个观点很值得记住围棋的规则几乎是最简单的却是计算机博弈难度最大的棋种。把几种棋放在一起对照就能理解为什么。围棋 19×19 棋盘361 个交叉点规则核心就是围地黑白轮流落子最后谁围的地盘多谁赢。规则写出来可能不到 300 字。但它的博弈树分支因子极高第一步就有 361 种选择而且局面评估极难——一个看起来孤立的子可能影响整片棋形。很长一段时间里围棋程序的水平远低于象棋程序原因就在于此。国际象棋正好相反。规则相当繁复王车易位、吃过路兵、兵升变特殊规则一大堆但子力价值体系非常成熟。资料里给了经典参考值兵 1 分马 3 分象 3 分车 5 分后 9 分。这种数值让评估函数的上手难度低很多。中国象棋是 9×10 棋盘红黑双方各 7 个兵种 16 枚棋子还有长将、长捉的判定、六十步不吃子判和、时间约束等特殊规则。它的规则模块比国际象棋更琐碎但子力质量评估同样有成熟经验可用。五子棋更有意思。15×15 棋盘已经被证明先手必胜所以规矩里引入了禁手、换手、金球制等平衡手段。哪怕你写的是后手程序也要清楚哪些先手手段被禁止否则搜索出来的“必胜走法”放在规则里根本不合法。六子棋则是一个巧妙的新设计。它在 19×19 棋盘上玩目标从五连珠变成六连珠但规则改成“先手第一步下一子之后每手下两子”先手优势被大幅削弱博弈复杂度显著提高。这套规则创新不是靠算法而是靠规则设计本身给计算机博弈研究提供了全新课题。3.4 民间棋和滑块游戏竞赛里容易被低估的一类资料列出的民间棋很多一字棋、二虎棋、三通棋、点格棋、苏拉卡尔塔、亚马逊还有单人游戏华容道。很多人会疑惑这也算棋其实这些游戏非常适合用来入门博弈编程因为状态空间往往比象棋小得多调试起来看得清、跑得快。一字棋规则极简走子距离不限至少走一步且可以一次移动多个棋子但必须停在同一个目标棋位上谁先到达目的地谁胜。这种棋用来练习 minimax 和剪枝非常顺手。二虎棋是虎方和犬方的对抗。虎方可以跳吃犬子吃够一定数量就获胜犬方靠围困虎方取胜。胜负条件非常明确评估函数很容易写。点格棋则是另一种类型。它属于填子类把邻近两点连成一边凑够四条边就占下一个格子最后一个占边者还要再连一边。资料特意点出“死格、双环、长链、短链、环”这些概念它们正是写点格棋评估函数时必须识别的局部结构。苏拉卡尔塔很特别。普通走子每步只能走一格且只能沿垂直或对角方向吃子却要沿着棋盘边缘的弧线还必须走完一整个弧。这意味着写合法着法枚举时不能只考虑格子邻接关系还得把弧线路径编进规则逻辑。亚马逊棋融合了移动和设障。每方有 4 个类似国际象棋“后”的棋子每个着法既要移动棋子又要在原地设置一个障碍。无子可动的一方判负所以评估函数要围绕活动空间来设计。至于华容道它是单人滑块游戏目标是把曹操那块最大的方块移到棋盘底部中央的箭头处。虽然不存在“对手”但完全可以看作一棵只有单一决策者的博弈树。棋盘小、状态可视化、调试方便很多人第一次练搜索算法就是拿华容道下手的。这一章的白话总结就是棋不是只有象棋和围棋。不同棋种的规则特性直接决定程序架构和算法选择选棋种本质上是在选“问题的难度档位”。4. 计算机博弈软件的构成一个能下棋的程序由哪几块拼成资料在讲完原理和棋种后切入了一个很实际的话题一个能跑的博弈程序到底由哪几部分组成。这个问题看似基础却是很多新手卡住的根因。4.1 五块标准件界面、规则、搜索、评估、辅助数据一个完整的博弈程序至少包含五块界面、规则模块、搜索模块、评估模块、辅助数据。它们各司其职谁也不要插手谁的活。界面负责显示棋盘、接收玩家输入、显示 AI 落子。听起来不重要但竞赛里界面经常是隐形时间杀手——很多人一开始就钻进制做华丽界面结果核心算法没时间调优。稳妥做法是先做命令行界面棋盘用字符画出来能看清局势就行把力气花在算法上。规则模块是程序的骨架。它要能枚举当前局面的所有合法着法能执行一步棋也能撤销一步棋还要能判断终局。中国象棋的“六十步不吃子判和”、五子棋连珠规则的禁手识别全都得在这里处理干净。规则一旦写错搜索再强也只是在错误分支里空转。这种 bug 特别隐蔽往往要跑几百局才会触发一次。搜索模块是大脑负责在规则模块给出的合法着法上展开博弈树最终返回一个最佳着法。前面讲的 minimax、alpha-beta、迭代加深都在这里实现。评估模块是打分器。搜索不能无限深到某个深度就得停这时必须有一个函数回答当前局面我方占多大优势评估函数的设计质量直接决定搜索到截断深度后的决策准不准。辅助数据包括开局库、残局库、着法排序历史表。开局库能避免程序前几步耗费大量时间去搜开局残局库能精确解决某些子力组合的终局历史表用来提高剪枝效率。它们不属于核心算法但对实战成绩影响很大。模块之间最好保持清晰接口。比如规则模块只暴露“获取合法着法、执行着法、撤销着法、判断终局”四件事搜索模块只依赖这四个接口不直接触碰内部数据结构。换棋种的时候你只需要替换规则模块和评估模块搜索代码基本不动。提示竞赛里规则模块的 bug 比搜索 bug 更难定位。搜索出错通常很快暴露规则出错却只在特定走法组合下触发排查极其耗费时间。建议在写搜索之前先通过大量纯规则对局验证规则模块。4.2 棋局评估函数给局面打分是门手艺活评估函数是计算机博弈里最需要“手艺”的部分。最粗糙的做法是只数棋子但这远远不够。以国际象棋为例资料给出的相对子力值可以当作评估的起点兵 1 分、马 3 分、象 3 分、车 5 分、后 9 分。照这个思路写出最朴素的评估函数代码很短def evaluate(board): # 国际象棋的子力基准分 piece_values { pawn: 1, knight: 3, bishop: 3, rook: 5, queen: 9, king: 1000 } score 0 for piece in board.my_pieces: score piece_values[piece.kind] for piece in board.opponent_pieces: score - piece_values[piece.kind] return score这段代码能跑但棋力非常弱因为它只看了子力完全没看位置。同样是马放在棋盘中央和卡在边角价值差很多。好的评估函数要在子力基础上叠加位置表、兵形结构、王的安危、子力活跃度等因素。不同棋种的评估侧重完全不同。点格棋要看死格、双环、长链、短链、环这类局部结构亚马逊棋要看活动空间因为它的胜负就是“无子可动”围棋的评估最难单个子的价值必须放到整片棋形里看。资料把评估和搜索分开讲正是因为搜索框架是通用的而评估高度依赖具体棋种。有一条原则值得记着评估函数返回的是相对值。正数对己方有利负数对对方有利绝对值大小没有绝对意义。调参时不用纠结“这步该打 5 分还是 6 分”更重要的是让评估值的变化趋势和真实棋局发展一致。4.3 从资料到程序搭建一个最小可用博弈程序的顺序新手最容易犯的错误是搞混“先做哪个模块”。我建议按下面的顺序搭建能省掉大量返工时间。第一步只做规则模块加命令行界面。实现合法着法枚举、执行着法、撤销着法、终局判断再写一个字符画棋盘。这一步先别急着加搜索让两个人类在窗口里对弈用真实对局验证规则模块有没有问题。我和同学当年用两个控制台窗口来回输入着法跑了上百个棋局才基本确认规则没大坑。第二步写一个不剪枝的固定深度 minimax配最简单的子力评估。这时程序已经能动搜索层数很浅棋力很弱。它只要能跑通就说明搜索和评估的接口接对了。第三步加 alpha-beta 剪枝和着法排序。重点观察两件事同样深度下剪枝前后的时间差多少走法是否一致。如果剪枝后的走法和剪枝前有任何不同说明剪枝实现有 bug——正常情况下剪枝不会改变结果。第四步加迭代加深和时间控制。这一步之后程序才具备上场的稳定性不会再因为某一步突然搜索过深而超时。最后一步优化评估函数。此时你已经有了完整可对弈的程序每调一版评估参数都可以让新旧版本互下几十局用胜率量化效果。这个顺序的核心逻辑是先让程序“能正确地下棋”再让它“下得好”。反过来写的话你会一直陷入“到底是规则错了还是搜索错了”的分辨困境里。5. 常见误区与易混概念竞赛新手最容易搞混的五个判断这一章专门说几个初学者几乎都踩过的坑。每个坑都按“易混点 → 为什么混 → 怎么区分”来讲。5.1 误区一搜索层数越多程序一定越强易混点很多人把搜索深度当成棋力的唯一指标认为只要层层加深程序就一定会更强。为什么混直觉上“看得远就是高手”忽略了评估函数这个前提。怎么区分搜索深度的收益高度依赖评估函数的准确度。如果中间层的评估误差很大加深之后反而可能放大系统性偏差——短视野里看到的“真实优势”看深之后也许被错误评估误导走出更差的棋。竞赛里棋力是深度、排序、开局库、残局库、评估精度共同作用的结果单看深度对比没有意义。5.2 误区二评估函数越复杂越好易混点觉得参数越多、特征越全局面判断就越准。为什么混把“复杂”直接等同于“准确”忽略了参数互相干扰的风险。怎么区分评估函数复杂到一定程度后调参难度会爆炸式增长最后往往调出一个只在训练棋局上表现好、换对手就失灵的过拟合程序。竞赛经验是评估函数“够用就好”——先用子力加简单位置表跑通再逐步加入一两个关键特征每增加一个都用大量对局验证它是否真的提升胜率。5.3 误区三博弈程序的核心是搜索评估只是辅助易混点网上讲算法的文章大半在讲搜索评估常被一笔带过于是很多人以为搜索就是全部。为什么混搜索过程很华丽、很有“技术含量”评估看起来只是“打打分”两者曝光度完全不同。怎么区分搜索是把所有分支都看一遍评估才是判断“哪个分支好”的标准。评估标准本身有问题搜索再完备也只是在错误的尺度下找最优。很多竞赛项目里双方搜索算法几乎一样最终拉开差距的恰恰是评估函数的细节——位置表取值、关键结构识别、残局阶段的特殊处理。5.4 误区四先手优势可以忽略易混点觉得程序随机先后手一场对局里先手优势影响不大。为什么混单局里很难察觉搜索深度足够时更会觉得“谁先手都差不多”。怎么区分资料明确指出棋类有个无处不在的“不公平点——先手优势”。五子棋甚至已被证明先手必胜所以正规规则才引入禁手、换手来平衡围棋用贴目抵消先手优势六子棋把“每手一子”改成“先手第一步一子、之后每手两子”本身就是为削减先手优势。写程序时必须把先后手当成一个影响因素先手要敢于积极进攻后手要评估该稳守还是该主动制造混乱评估函数里也常会加入先后手补偿项。5.5 误区五把辅导资料当成棋谱来背易混点以为看完原理就等于会写博弈程序。为什么混原理本身确实短看一遍就懂但“看懂一个算法”和“实现一个能对弈的程序”之间隔着无数调试和优化。怎么区分资料是地图不是行程。它告诉你哪里有山哪里有河真正走过去还得自己一步步踩实。我的建议是每读完一章原理立刻动手实现对应模块验证无误后再读下一章。带着问题读资料读一遍顶三遍。6. 什么时候用这套辅导资料参赛前、做研究、以及别拿它干什么6.1 参加竞赛前先花两小时建立全局认知如果你是第一次参加计算机博弈竞赛这套资料最合适的使用场景就是赛前规划。它帮你把几件关键事一次理清比赛项目里有哪些棋种每个棋种的规则和难度如何一个博弈程序需要哪几个模块搜索与评估是什么关系。花两小时通读一遍心里就有了一张“框架图”。后面写程序的每一步都能对号入座不会走两步就迷路。6.2 研究新棋种时方法学迁移比背代码更有用资料最核心的方法学特点是“基于搜索”。这个思路的价值在于可迁移换一个棋种搜索框架不变变的只是规则模块和评估函数。如果你在做一个不常见的民间棋项目把资料里的分类方法和模块边界理清楚往往能省下好几天重构时间。它不会直接给你一个能跑的代码但能让你在设计阶段就避开最粗的错误。6.3 什么时候别用有隐藏信息或随机因素的博弈这套方法有一个明确的适用边界它面向完全信息动态博弈。如果某个博弈涉及隐藏信息或者每步有随机抽牌、掷骰子那基于博弈树搜索的框架就不够用了。你需要概率建模、期望值评估甚至要转向蒙特卡洛这类随机采样方法。资料本身也把棋类和牌类分得很清楚所以别把它当成万能公式。写到这里我想起自己的经历。第一次参加竞赛前我拿到类似的辅导资料快速扫了一遍就扔到一边觉得都是纸上谈兵不如直接写代码。结果第一版程序规则漏洞百出搜索和评估耦合在一起改一处动全身调了一个月也没达到预期。后来重新把资料里关于软件构成的那部分反复读了几遍才意识到自己最大的问题不是算法不够新而是模块边界没划清。从那以后我每次参加新的博弈竞赛都会强制自己先走一遍这套流程给棋种分类明确它是走子类还是填子类还是混合类画出软件模块图然后才动手写代码。这套资料讲的内容很基础但正因为基础才让后面的每一步都踩在实处。希望这份讲解能帮你在竞赛路上少走弯路把精力花在真正值得打磨的地方。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
