计算机博弈入门：从棋类建模到博弈树与Alpha-Beta剪枝

简介计算机博弈竞赛辅导资料面向准备参加计算机博弈竞赛的学生、指导教师及入门研究者围绕机器博弈的基础原理、方法学与典型棋类建立系统认识可用于赛前梳理知识框架、课程辅导和方案设计参考。压缩包内共1个PPT文件大小约2.57MB以讲义课件形式集中呈现东北大学机器博弈研究室关于计算机博弈原理与方法学概述的内容。课件从棋类介绍与分类切入涉及中国象棋、国际象棋、围棋、五子棋、六子棋及点格棋、苏拉卡尔塔、亚马逊、华容道等对象并讲解博弈树、搜索算法、alpha-beta剪枝、棋局评估、博弈树展开与分析、软件构成及基于搜索的方法学特点兼及与计算机科学、数学、人工智能的学科关系。已有330人学习或下载便于读者建立从棋类建模、评估函数到搜索实现的整体脉络也可作为竞赛辅导备课与专题讨论的提纲。1. 计算机博弈是什么让机器往前想几步这件事「计算机博弈竞赛辅导资料」这名字听着有门槛其实它讲的事情离日常很近你坐在棋盘前落子之前总会想我走这步对方大概会怎么应然后我再怎么走——计算机博弈就是把这套往前想几步的动作拆解成机器能执行的计算。一句话定义让机器在规则明确的对抗性棋局里靠搜索加评估选出下一步走哪里。打个比方它像个只会做选择题的考生题目永远只有一道现在该走哪一步。选项几十个它没有直觉可用只能把每个选项背后的分支摊开算分挑分数最高的那个。这份资料的价值也在这里搜索、评估、剪枝这些思路都是在这类棋盘上被反复打磨出来的搞懂它你就摸到了程序如何在爆炸式可能性里做选择的门把手。2. 为什么偏偏是棋类完全信息博弈给机器的天然便利棋类被选作研究对象不是因为它们好玩而是因为它们适合被计算。这个适配性来自两条性质一条决定了机器能不能把局面完整描述出来另一条决定了搜索有没有意义。搞清这两条后面所有关于博弈树、评估函数、剪枝的讨论才有落点。2.1 棋类是完全信息动态博弈牌类不是先把两个词拆开看。完全信息说的是每个参与方对当前局面、规则和已经发生过的所有行动都看得见没有暗着动态说的是双方轮流行动、有先后顺序不是同时落手。棋类通常被归为完全信息动态博弈牌类则归为不完全信息动态博弈——原料里那句不含牌棋牌性质有很大的区别说的就是这道分界线。差别具体在哪中国象棋里红方有几个兵、黑方的车在哪一路双方一目了然机器的任务只是把这个可见局面复制成一份数据结构然后开始推演。换成扑克或麻将对手手里有什么你根本看不到机器必须先建立一个对手可能持有什么的概率分布再在这个分布上做决策。后者的难度维度完全不同——不是算得更深能解决的而是要引入概率推断和不确定性下的决策模型。这解释了为什么棋类成了算法试验田局面可以被完整表示成一个状态快照状态之间的转移由规则唯一确定同一局面反复出现时结果完全一致。这意味着程序可以复现、可以调试、可以对比两组参数谁强谁弱。换成带随机发牌的游戏同样输入两次结果不同会让调参变成玄学。还有一层容易忽略动态意味着回合制。回合制让你一步我一步的推演天然形成树状结构机器可以按层展开。同时行动的对抗问题就没这么规整了需要考虑对方和你同时选择时的组合情况模型的形状都不一样。2.2 人们为什么爱下棋机器就为什么盯上棋原料里列了五条人们为什么喜欢下棋这五条其实每一条都能翻译成机器视角的优势值得逐条对一遍。第一目的在于决出胜负并关联某种收获。对应到程序就是必须有一个明确的终局判定将死、无子可动、连成线、占据格子多。有了这个判定搜索才有终点评估才有目标。第二规则简单明确成功与失败的判定标准简单。这一条对机器极其关键——规则简单意味着走法生成这个函数好写不需要海量常识。很多现实问题难就难在什么算一步合法的操作都说不清棋盘上没有这种模糊地带。第三博弈过程透明、公平不包含任何机会或偶然性唯一的例外是先手优势。无偶然性意味着同样的局面永远得到同样的评估调试时你能确定问题出在代码而不是运气。这也是为什么棋类程序的强弱可以用对局数客观衡量。第四智力和经验决定胜负问题的解决在认识意义上不需要过多的知识。换句话说棋力主要来自算得深和评得准而不是背了多少百科常识。这正好是搜索算法和评估函数能发挥作用的地方。第五变化无穷很难走出完全相同的棋谱。这一条保证了研究不会很快撞到天花板中国象棋平均每步有几十种合法走法走到第六层就是几十亿个局面穷举不动永远有优化空间。看懂这五条对应关系你就明白机器博弈为什么长期是搜索算法的练兵场——它把决策这件事压缩成了一个干净、可判定、可重复的数学问题。2.3 按人数和按着法分类棋不是一种东西棋类内部差别极大乱套一套方法必然翻车。原料给了两条分类线索一条按参与人数一条按着法性质。按人数分双人弈棋占绝大多数象棋、围棋、五子棋都是单人游戏如华容道本质是滑块移动多人游戏如跳棋多方参与。按着法分走子类是开局前双方摆好棋子、开局后轮流走动中国象棋、国际象棋、跳棋、苏拉卡尔塔、亚马逊都属于这类填子类是开局盘面全空、双方轮流放子围棋、五子棋、点格棋是代表混合类则是先填子、到一定条件后转为走子还带吃子五道棋和日本将棋属于这一类。分类维度类别代表棋种对程序设计的直接影响参与人数双人中国象棋、国际象棋、围棋、五子棋直接对应两方对抗模型一方得分即另一方失分单人华容道退化为最短步数搜索没有对手多人跳棋多方利益不一致不再是严格的零和着法类型走子类中国象棋、国际象棋、苏拉卡尔塔、亚马逊存在子力概念评估可以算子力加位置填子类围棋、五子棋、点格棋盘面由空到满评估要看形状、连接与势力混合类五道棋、日本将棋要按阶段切换评估策略前期重布局后期重吃子这张表不是学术洁癖它直接决定你写评估函数时该看什么。走子类棋里一步吃子会让盘面分数立刻跳变子力价值是硬通货填子类棋里落下一子当下不产生任何收益价值要很多步之后才显现所以围棋才那么难——它要求评估函数看懂势力和厚薄这种模糊概念而不是数棋子。具体到盘面参数各棋种差异也很实在中国象棋棋盘 9×10红黑各 7 个兵种、16 枚子还有长将、长捉的限制60 步不吃子判和国际象棋 8×8六个兵种各 16 枚子有王车易位、兵升变、吃过路兵这些特殊规则围棋 19×19靠占地多者胜先手要贴目 5 到 7 目五子棋 15×15无禁手规则下先手优势被证明大到影响竞技性于是有了禁手、换手等规则改良六子棋 19×19先手只下一子、之后每手两子用多给后手一颗子的方式来削先手优势复杂度反而更高。再看几个小众棋种能看出规则设计对程序的影响有多细。一字棋的走子距离不限至少一步、至多走到终点不许逆行可以一次移动一个或多个棋子但必须都停在同一个目标位上二虎棋由虎方先走犬方每次走一子到邻近空位虎方可跳吃且每次只吃一子虎方吃够一定数量获胜犬方则靠围困让虎方全部无法走动取胜三通棋有 64 个正三角形棋位、双方各 32 枚子轮流布子乙方有一次连续下两着的机会先实现三通者胜点格棋靠连边围格最后一个占边者得到这个格子并要再连一边程序里要专门识别死格、双环、长链短链和环苏拉卡尔塔除了吃子外每步只能走一格吃子必须沿弧线走完一整段弧吃光对方才算赢亚马逊每方四个后每个着法包含移动和设障两部分比拼活动范围无子可动判负华容道是滑块类单人游戏一次把一个人物移进空位直到最大那块移到下方中央出口国外常把它和魔方、独立钻石并称为智力游戏里的三大不可思议。把这些摆在一起你会发现棋只是一个笼统的称呼盘面尺寸、子力概念、胜负条件、特殊规则每一样都会改写程序结构。这也正是这份辅导资料要先讲棋类再讲原理的原因——不认清对象方法学就是空转。3. 一台会下棋的程序由什么组成从棋盘模拟到评估函数3.1 棋盘模拟先把棋盘变成程序认得出的样子任何棋类程序的第一层都是把真实棋盘翻译成内存里的结构。常见做法是用一维或二维数组每个格子存一个编码用正负号区分阵营、用数值区分兵种空格存 0。中国象棋就是 9×10 的数组国际象棋 8×8围棋和六子棋 19×19五子棋 15×15。这种表示最直观走一步只需要改两个格子的值撤回一步也只需要改回来。更讲究的实现会用位棋盘把整张棋盘压进几个整数里用位运算一次性算出某一类棋子的所有可达位置。这种做法在评估和走法生成上快得多但可读性差适合已经跑通逻辑之后再做优化。棋盘模拟这一层还负责两件事走法生成和合法性校验。走法生成是当前局面下我方所有合法着法合法性校验负责过滤掉送将、长将违规、禁手这些情况。这两块写错后面搜索再漂亮也没用——这是很多初学者的第一道坎血泪经验是先写一堆单元测试把走法生成测干净再动搜索。3.2 搜索和评估的分工一个管想得远一个管看得准一台会下棋的程序骨架基本是四件套用户界面、棋盘模拟、搜索模块、评估函数。界面负责人机交互和局面显示棋盘模拟负责规则和状态搜索模块负责往前推演评估函数负责在推演尽头给局面打分。搜索和评估是一对互补关系缺一不可。搜索负责想得远把未来若干步的可能走法展开成一棵树评估负责看得准在搜索走不下去的深度上给出一个分数。如果评估很粗糙搜得再深也只是把错误放大如果搜索很浅再准的评估也救不了短视。这两者的取舍是机器博弈里最经典的工程问题。资源有限时你要决定是把算力花在多算两层还是把评估函数写细一点。经验上中等强度的棋类程序往往先优化评估再优化搜索深度因为评估错了搜索只是更快地走到错误结论。3.3 评估函数怎么写子力值这类经验分评估函数是整台程序里最像经验的部分。它不推演只对当前局面打个分正数表示我方占优负数表示不利。最朴素的做法是只算子力。国际象棋里有个流传很广的相对子力值参考以兵为 1马约 3象约 3车约 5后约 9。这些数字不是天上掉下来的而是长期对局统计出来的近似换算关系——一个车大约抵得上一个半马一个后大约抵得上一个车加一个象。# 极简评估函数只算子力正分代表红方占优 PIECE_VALUE { pawn: 100, knight: 300, bishop: 320, rook: 500, queen: 900, king: 20000, } def evaluate(board): score 0 for piece, side in board.pieces(): # side 取 1 表示红方、-1 表示黑方 score side * PIECE_VALUE[piece] return score这段代码的逻辑很直白遍历盘面上所有棋子按兵种查表取分红方加分、黑方减分最后得到一个正负分。参数说明上PIECE_VALUE里的数字是相对刻度不要求绝对精确只要保持比例关系即可王给到两万分是因为王的丢失等于终局必须让任何子力交换都无法弥补。但只算子力的评估函数有明显短板它看不出位置好坏。一个待在角落的马和一个占据中心格的马子力分一样实战价值差很多。所以真实程序会再加一层位置分比如给每个兵种维护一张位置价值表棋子站到好位置额外加分。中国象棋里还要考虑兵过河、车占肋道这些细节围棋里则要评估影响力和连接形状。4. 博弈树怎么展开搜索为什么是机器博弈的方法学内核4.1 博弈树把未来的所有可能摊成一棵树博弈树是把未来摊开的一种画法。树根是当前局面它的子节点是我方所有合法走法形成的局面再往下一层是对手所有合法应对如此交替延伸直到某一方获胜或达到设定的深度。树的规模由两个量决定深度和分支因子。中国象棋平均每步大约有几十种合法走法假设每层 40 个分支只看 6 层就是 40 的 6 次方约 40 亿个节点。这个数量级已经超出普通机器的暴力枚举能力。围棋更夸张19×19 的盘面每步有几百个候选点所以它长期被认为是机器博弈里最硬的骨头研究中常先缩到 9×9 的四分之一盘面来积累方法。理解这种爆炸式增长是理解整套方法学的起点既然穷举不可能就必须想办法少算一些而不算错。4.2 极小极大假设对手一定挑最坑你的那步最基础的搜索框架叫极小极大。逻辑很符合直觉轮到我走时我在所有子节点里挑分数最高的轮到对手走时我假设他会在所有子节点里挑分数最低的——因为他挑得越低对我越不利。这个假设看起来悲观其实是理性的你不是在跟一个会失误的对手下棋而是在评估如果对方每一步都走最优我还能拿到多少分。在这种假设下选出的走法最坏情况下的损失最小。把评估函数和极小极大接起来就得到一段能跑的搜索代码。下面用的是负极大值写法把取最大和取最小合并成一个方向代码短一半def alphabeta(board, depth, alpha, beta, side): # 到达终局或达到深度上限直接返回评估分换成当前行棋方视角 if board.is_game_over() or depth 0: return side * evaluate(board) best -float(inf) for move in board.legal_moves(): board.make(move) # 试走一步 score -alphabeta(board, depth - 1, -beta, -alpha, -side) # 换对手行棋分数取反 board.undo(move) # 撤回恢复局面 best max(best, score) alpha max(alpha, score) if alpha beta: # 对手不会让我走到这个分支 break return best参数说明depth是还能往下搜几层减到 0 就调用评估函数alpha是我方目前能确保的最好分数beta是对手能压低到的最好分数side表示当前行棋方用于把分数统一到同一视角。make和undo必须成对出现这是递归搜索里最容易翻车的地方——漏掉一次 undo盘面就会被逐步污染搜索结果的错误极难定位。4.3 alpha-beta 剪枝为什么能砍掉一大半还不影响结果上面那段代码里的if alpha beta: break就是 alpha-beta 剪枝的全部秘密。它的道理可以用一句话概括如果对手在某个分支上已经有更好的选择他就不会走到这个分支来那这个分支后面的内容算了也白算。举个具体场景。我方在比较两个走法 A 和 B。试完 A 之后已知 A 至少能保证 30 分。现在试 BB 的对手有一手很凶的应对能把我方压到 10 分——这时已经没有必要继续算 B 的其他变化了因为不管剩下那些变化多好对手都不会选择它们B 的上限就是 10比 A 的 30 差。整枝剪掉。剪枝不改变最终答案只减少计算量。在走法排序理想的情况下同样的时间大约能多搜一倍的深度这个提升是实打实的。所以真实程序都会在搜索前对走法排序先试吃子、先试上次搜索里表现好的走法排序越准剪得越狠。剪枝也有前提它要求评估函数和搜索过程是确定性的不能有随机成分同时剪枝的正确性依赖对手永远选最优这个假设。如果引入随机开局库或非确定性的评估剪枝的边界条件要重新检查。4.4 剪枝救不了的地方地平线效应和越算越蠢搜索深度不是越深越好这是初学者最容易踩的坑。原因叫地平线效应程序在深度上限处被迫停手用评估函数给局面打分而那个局面可能正处在一次交换的中途——比如我刚吃掉对方一个车还没被反吃回来。评估函数看到的是我多一个车于是给出高分程序高高兴兴选了这条路实战里下一步就被人吃回去。这类问题的根源不是搜索错了而是看得见的边界和真实的终局对不上。缓解办法有几种在叶子节点之前多做一层静态搜索专门把吃子交换算到底把评估函数写得平滑一些让局面的过渡不那么剧烈或者在搜索中检测重复局面避免在循环里打转。另一个反直觉的现象是奇数层和偶数层效果差异。因为搜索是双方交替的某些战术在不同深度下的评价会来回摆动多搜一层反而变弱的情况确实存在。遇到这种波动先别怀疑代码写错了多半是评估函数在某个特定局面下有系统性偏差。5. 几个最容易搞混的地方棋类博弈和你想的不是一回事5.1 误区一计算机博弈就是深度学习搜索已经过时了这是当下最普遍的混淆。因为新闻里下棋的程序总跟神经网络绑在一起很多人以为传统搜索是上一代技术。为什么会混两类内容经常出现在同一篇报道里而且都叫AI 下棋外行看不出层次差别。怎么区分看问题的重心。基于搜索的方法关注的是在有限时间里如何高效地展开博弈树alpha-beta 剪枝、走法排序、置换表都属于这一脉基于学习的方法关注的是如何从大量对局里自动获得评估能力。前者的结论是可解释的、可验证的后者能给出人类说不清理由的直觉判断。两者不是替代关系——在同一个程序里神经网络常常只是替换掉了原来手工编写的评估函数搜索框架依然在下面跑。搞竞赛辅导先把搜索这条主干吃透再看学习方法是叠加还是替换顺序不能反。5.2 误区二规则越简单程序就越好写直觉上五子棋规则比围棋简单得多程序应该容易得多。实际情况要分两层看。为什么会混把规则描述的复杂度和程序实现的复杂度当成同一件事。怎么区分规则简单只说明走法生成和胜负判定好写不代表搜索空间小。围棋规则一句话能说完但每步候选点极多、局面评估极其模糊所以难度公认最大。反过来某些规则繁琐的小众棋走法类型有限、评估维度单一反而容易做出不错的程序。判断一个棋种好不好做要同时看三件事分支因子有多大、评估函数能不能写得准、有没有成熟的参考资料。5.3 误区三换个棋种只要把棋盘尺寸改一下这条误区在动手阶段杀伤力最大。很多人写完一个五子棋程序觉得改成象棋只需要换掉棋盘大小和胜负条件。为什么会混表面上看都是轮流落子、连成线或吃掉对方的框架长得像。怎么区分回到着法分类上看。走子类棋有子力概念棋子本身携带价值一步棋能直接改变盘面分数填子类棋盘面从空到满落下的子当下不产生收益价值延后体现混合类棋前期填子后期走子评估策略要分阶段切换。这三类的评估函数几乎是两套东西一个以子力为主一个以形状和势力为主。更别说特殊规则——王车易位、兵升变、吃子必须经过完整弧线、每次移动多个棋子但必须停在同一位置这些都会渗透到走法生成里。换棋种不是换参数是换模型。5.4 误区四先手优势是细节不影响大局原料里提到棋类的公平性有个例外——先手优势。很多人把它当成可以忽略的小事。为什么会混业余对局里水平差距远大于先手差距感觉不出来。怎么区分看竞技规则怎么处理它。围棋用贴目来补偿后手五子棋在无禁手规则下先手优势大到影响竞技性于是发展出禁手、换手等限制六子棋干脆改成先手只下一子、之后每手两子用给后手多一颗子来削平优势。这些设计说明先手优势是规则层面必须正面处理的问题。落到程序上执先和执后的策略往往要分别调同一个评估函数在两种颜色下表现不一致是常见现象。5.5 误区五搜索越深棋力一定越强前面讲过地平线效应这里再强调一次它的实践含义。为什么会混深度是最容易看见、最容易调的参数加一层就感觉变强了。怎么区分看提升来自哪里。如果评估函数粗糙加深只是把误差传播得更远如果走法排序很差剪枝效率低加深的代价是时间成倍增长却换不来有效信息。判断方法很朴素在同一批测试局面上对比不同深度下的选点如果深层选点和浅层选点经常互相矛盾且没有明显优劣说明问题出在评估而不是深度。这时候该做的是补位置分、加静态搜索、检查终局判定而不是继续堆层数。6. 什么时候用得上这份资料从入门选棋到竞赛备赛的边界讲清边界比讲清原理更实用。这份资料覆盖面很宽从棋类介绍到原理、软件构成、棋局评估、博弈树展开都有但它不是万能的也不适合所有人。它适合的场景很明确你准备参加计算机博弈类竞赛需要一个从棋是什么到程序怎么写的整体框架你在做课程设计或毕业设计想找一个规则清晰、可验证、有评测标准的题目你教别人编程想用棋盘这种直观载体讲清搜索与评估的分工。这几种情况下先把棋类分类、走法类型、完全信息这一串概念捋顺再动手写代码能省掉大量返工。它不适合的场景同样明确想直接拿现成代码交差的人会失望因为资料的重心在原理与方法学不在某个棋种的完整实现想深挖某个具体算法数学证明的人也会觉得不够因为这是概论层面的梳理。另外如果你的目标棋种是带随机发牌或不完全信息的游戏那第 2 章那套完全信息的前提假设就要重新审视不能照搬。你的处境建议从哪里入手需要绕开的地方完全没接触过机器博弈先看棋类介绍与分类挑一个走子类小棋种练手别一上来选围棋评估函数写不出来会卡死会写代码但不懂搜索直接看博弈树与评估函数先把极小极大跑通别急着加剪枝先确认基础搜索的结果正确参加过比赛但成绩一般重点看评估函数与走法排序对比不同深度下的选点别盲目加深先排查地平线效应想换一个棋种重做先按着法分类判断新棋种属于走子、填子还是混合别以为改个棋盘尺寸就能复用我自己的习惯是每次开一个新棋种之前先逼自己用三句话写清楚它的分类归属、胜负条件、评估维度写不出来就说明还没读懂规则这时候写代码一定翻车。这套动作我坚持了很多年比任何调试技巧都省时间。希望帮到你。本文还有配套的精品资源点击获取