简介面向计算机博弈竞赛参赛者、指导教师及人工智能方向学习者的辅导课件围绕赛项所需的基础理论与棋类对象展开可用于入门梳理、备赛授课和知识查漏。压缩包共1个PPT文件约2.57MB以课堂讲义形式组织便于按章节演示与集中复习。内容涵盖棋类介绍与分类、计算机博弈基本原理、博弈软件构成、棋局评估、博弈树展开与分析以及基于搜索的方法学特点和与计算机科学、数学、人工智能的学科关系并涉及alpha-beta剪枝、启发式搜索、蒙特卡罗树搜索等典型方法同时以中国象棋、国际象棋、围棋、五子棋、六子棋及部分民间棋类为例说明规则特征与博弈难点。已有331人学习适合用来建立从棋类建模、搜索剪枝到评估函数设计的整体框架。1. 电脑下棋到底在算什么从一个不会累的棋手说起计算机博弈竞赛辅导资料这几个字第一次看到容易以为是教人下棋的文档。它更像给一个不会累的棋手做体检先看棋盘怎么变成数据再看机器怎么在有限时间里挑一步最后看评估函数凭什么说这步好。不懂计算机博弈的人看竞赛新闻常觉得机器下棋是黑匣子拆开看它由棋类规则、搜索、评估、软件结构几块拼起来。一句话定义计算机博弈是让计算机在规则明确的对抗游戏里做决策。它不神秘也不等于“背棋谱”。搞懂这套骨架再看象棋、围棋、五子棋的差别就不会只记住“机器赢了”而能说出它赢在哪一层。这份资料值得翻是因为它把棋类、软件构成、棋局评估、博弈树展开串成了一条认知线而不是只给一堆算法名字。2. 为什么棋类适合机器博弈完全信息动态博弈的底层条件计算机博弈先要选对象。棋类之所以成为经典试验场不是因为规则好玩而是因为它把“对抗”压缩成了机器能读、能算、能比较的形式。某高校实验室的课程讲义里先把棋类放在“完全信息动态博弈”这一格再把牌类放在“不完全信息动态博弈”这一格。这个分类不是学术装饰它决定了机器要不要猜、要不要记概率、要不要处理看不到的信息。2.1 棋类和牌类的分水岭完全信息与不完全信息完全信息通俗地说就是双方都能看到棋盘上的全部状态也知道之前每一步怎么走的。动态指的是双方轮流行动不是同时出手。象棋、国际象棋、围棋、五子棋、六子棋都落在这个范围里。机器下棋时它面对的是一个“摊开的局面”棋子在哪、轮到谁、走过哪些着法都能写进数据结构。牌类不一样。你看到自己的手牌看不到对方的手牌发牌还带随机性。机器要做决策就得处理“我不知道你有什么”的不确定性甚至要算概率。棋类把这一层削掉了剩下的难点集中在搜索和评估上。这也是为什么很多计算机博弈入门资料先从棋类讲起它把问题边界划得比较干净适合先建立“局面—着法—搜索—评估”的完整链条。但完全信息不等于完全可算。围棋棋盘19×19双方轮流落子信息全公开可机器仍然很难因为分支太多、局面评估太难写。信息透明只是让问题可描述不代表问题变简单。这个区别要先立住否则后面容易把“知道全部局面”误当成“能轻松算出最优解”。提示完全信息只说明状态可见不说明计算量小围棋就是最典型的反例。2.2 人们喜欢下棋的五个理由怎么变成机器能算的条件讲义里列过人们喜欢下棋的几个理由要决出胜负规则简单明确过程透明公平智力和经验决定胜负变化无穷。把这五条翻译成机器语言正好对应计算机博弈能成立的几个条件。第一目标明确胜负判定能写成函数机器才知道往哪优化。第二规则简单走法生成和合法性判断能写成代码机器才不会在“这步能不能走”上卡死。第三过程透明局面状态能完整记录搜索树才有稳定的节点。第四智力经验起作用说明评估函数有东西可写子力、位置、机动性都能变成分数。第五变化无穷说明搜索空间足够大才值得研究算法而不是查表就完事。这五条也解释了为什么棋类适合做竞赛题目。竞赛需要一个可比较的环境同样规则、同样时间约束、同样胜负标准不同程序才能放在一起跑。象棋有长将、长拖这类约束还有连续60步不吃子判和五子棋有禁手、换手、金球制改进六子棋先手下一子然后每手下两子用来削减先手优势。这些规则细节看着琐碎却直接影响搜索和评估。机器不是只算“怎么连成五子”它还要算“哪些走法在规则上根本不允许”。从方法学上看机器博弈的主线是“基于搜索”。把对局看成一棵树根节点是当前局面边是合法着法子节点是走完一步后的新局面。机器在树上展开、比较、剪枝最后选一个分数最高的着法。这个思路不保证每一步都完美但它在有限时间内给出可执行的决策。棋类规则简单正好让这棵树长得比较规整棋类变化无穷又让这棵树大到不能蛮力遍历。计算机博弈的很多方法都是在这对矛盾里长出来的。2.3 规则简单不等于容易复杂度藏在搜索树里初学者常把“规则简单”当成“机器容易下”。规则简单只意味着单步判断不复杂不代表整棵树小。象棋棋盘9×10红黑各7个兵种、16枚棋子每个兵种的行棋规则和活动范围不同国际象棋棋盘8×8兵、马、象、车、后、王各有走法还有王车易位、兵升变、吃过路兵。围棋棋盘19×19规则更短但每一步的可能落点更多局面好坏也更难用几个数字说清。五子棋棋盘15×15规则简单到几句话却已经被证明先手胜所以正式对局要用禁手、换手等规则去平衡。六子棋棋盘19×196子连珠为胜先手下一子后每手两子复杂度显著提高。棋类棋盘与棋子规则特点机器博弈的难点象棋9×10红黑各7兵种16子兵种走法不同有长将、长拖、60步不吃子判和走法生成细规则约束多国际象棋8×8双方各16子王车易位、兵升变、吃过路兵相对子力值约为兵1、马3、象3、车5、后9中局搜索宽评估要兼顾王安全围棋19×19轮流落子占地多者胜先手贴目常见5到7目分支极多局面评估难写五子棋15×15先手优势明显靠禁手、换手、金球制改进胜负判定近搜索深度和规则处理要配合六子棋19×196子连珠为胜先手一子后每手两子复杂度高先手优势被规则削弱这张表只列几个代表。讲义里还提到走子类、填子类、混合类走子类是开局摆好、轮流走动象棋、国际象棋、跳棋属于这类填子类是开局盘面无子、轮流放入围棋、五子棋、点格棋属于这类混合类是先填后走某些民间棋和将棋类混合棋属于这类。按参与人数还可分为双人、单人、多人双人弈棋占绝大多数。分类不是为了背名词而是为了判断一个棋种适不适合做竞赛题走子类通常着法生成复杂填子类通常分支多混合类规则层次多。选题时先看它落在哪一类比一上来就挑算法更稳。3. 从棋盘到算法计算机博弈软件的四个零件一个能下棋的程序不是“算法”一个词就能概括。讲义把软件构成拆成用户界面、棋盘模拟、搜索算法、评估函数四块。这个拆法很实用界面负责对局管理和展示棋盘模拟负责规则和数据搜索算法负责在博弈树上找路评估函数负责给局面打分。四块缺一块程序要么不能走要么走得没章法。竞赛辅导资料的价值也在于把这四块分别讲清楚而不是只丢一个“搜索”概念。3.1 棋盘模拟先把规则写成数据棋盘模拟要回答三个问题局面长什么样、哪些着法合法、走完一步后局面怎么变。最直接的做法是用二维数组表示棋盘用整数编码棋子。比如象棋棋盘9列10行0表示空位正数表示一方棋子负数表示另一方棋子。走法生成时遍历己方棋子按照兵种规则产生候选着法再过滤掉让自己被将的着法。合法性判断里还要处理长将、长拖、60步不吃子判和等规则。# 用二维数组表示棋盘9列10行0为空位正负号区分双方 board [[0 for _ in range(9)] for _ in range(10)] def is_inside(x, y): # 判断坐标是否落在棋盘内 return 0 x 9 and 0 y 10 def generate_moves(board, side): moves [] # 伪代码遍历己方棋子按兵种规则产生候选着法 for x in range(9): for y in range(10): piece board[y][x] if piece 0 or piece * side 0: continue # 这里按兵种调用不同走法生成器 moves.extend(generate_piece_moves(board, x, y, piece)) # 过滤掉走完后自己被将的着法 return [m for m in moves if not leaves_king_in_check(board, m, side)]这段伪代码的重点不是具体兵种怎么走而是“局面表示—走法生成—合法性过滤”的顺序。参数board是当前局面side表示轮到哪一方moves是候选着法列表。generate_piece_moves要按兵种分别实现leaves_king_in_check要在模拟走子后检查王是否被攻击。很多程序翻车不在搜索而在走法生成漏了规则比如漏掉王车易位、漏掉吃过路兵、漏掉禁手判断搜索再深也会把非法着法当成好棋。棋盘模拟是地基地基歪了上面的算法越强越危险。3.2 搜索算法博弈树怎么展开搜索算法把当前局面当成根节点把每一步合法着法当成边把走完后的新局面当成子节点。机器在树上往下展开到了限定深度或时间就用评估函数给叶子节点打分再把分数往回传。国际象棋、象棋这类棋常用极大极小搜索轮到己方时选分数最高的着法轮到对方时假设对方选分数最低的着法。这个假设很朴素却撑起了很多棋类程序。搜索树一展开就会膨胀。象棋每步有几十种走法往下看几层就是几十的几次方。围棋更夸张每步上百个落点蛮力展开很快就撑不住。所以搜索算法要解决的不是“展开整棵树”而是“在有限时间里展开最有价值的部分”。这就引出深度限制、时间控制、剪枝、走法排序。讲义把“博弈树展开与分析”单独列出来是因为它决定了程序能不能在比赛时限内给出着法而不是算到一半超时。搜索还要处理“ horizon effect ”也就是水平线效应机器只看有限深度刚好看不到更深处的坏结果就可能把一步棋误判为好棋。比如它牺牲一个子换来看似不错的局面但再往下两步会被将死搜索没看到评估函数就给了高分。解决思路不是无限加深而是配合更好的评估、延展搜索、静态搜索。竞赛里时间固定搜索深度和评估质量要一起调单拉一边往往不够。3.3 评估函数机器眼里的好坏评估函数负责给局面打分。国际象棋里常用相对子力值兵1、马3、象3、车5、后9。这个分值不是绝对真理而是经验近似。除了子力还要看位置车占开放线、马在中心、王的安全、兵形结构。象棋里还要看子力、控制区域、将的安全、过河兵。围棋更难因为“地盘”不是几个子力值能直接加出来的所以早期围棋程序在评估上吃了很多亏。评估函数不是越复杂越好。一个可解释、可调、和搜索配合得好的评估比堆几十个特征的评估更稳。评估函数输出一个分数搜索用它比较局面分数尺度要一致否则搜索会偏好某类特征。比如子力权重设得过高程序可能一味吃子不管王的安全位置权重设得过高程序可能为了“好看的位置”放弃实际利益。竞赛辅导资料里讲棋局评估重点通常不是给一个万能公式而是讲清楚评估要覆盖哪些维度、权重怎么调、什么时候该简化。3.4 用户界面与对局管理别小看外围用户界面和对局管理看起来是外围实际影响很大。界面要显示棋盘、接收走子、提示合法着法对局管理要计时、记录棋谱、判断胜负和和棋。竞赛环境里程序还要处理时间约束、走子超时、非法着法判负。很多初学者把精力全放在搜索上结果比赛时界面卡住、计时不准、规则判断漏了直接翻车。棋盘模拟和界面之间的边界也要清楚规则判断放在棋盘模拟里界面只负责展示和交互不要两处各写一套规则否则很容易不一致。注意界面不是装饰层它负责对局流程和时限规则判断最好集中在棋盘模拟里避免两套逻辑打架。4. 棋局评估与搜索alpha-beta 剪枝和蒙特卡罗树搜索各管什么棋局评估和搜索是一对搭档。评估函数说“这个局面大概多好”搜索说“我往下看几步再判断”。讲义里提到启发式搜索、alpha-beta剪枝、蒙特卡罗树搜索这三个词常被混在一起。通俗地说启发式搜索是用经验规则引导搜索方向alpha-beta剪枝是在极大极小搜索里砍掉不可能影响结果的分支蒙特卡罗树搜索是用随机模拟来估计局面价值。它们解决的问题不同不能互相替代。4.1 评估函数不是算命评估函数不是预言下一步一定赢它只是给当前局面一个近似分数。机器搜索到叶子节点时不可能继续往下算到终局只能用评估函数估一个值。这个值准不准取决于特征选得对不对、权重调得好不好。象棋里子力值比较直观国际象棋有通行的相对子力值围棋的地盘评估就难得多。评估函数错得离谱搜索越深越可能沿着错误方向走。评估函数还要和搜索深度匹配。浅层搜索时评估函数要能抓住短期利益深层搜索时评估函数要能判断长期结构。一个评估函数在浅层好用不代表深层也好用。竞赛里常见做法是先用简单评估跑通流程再逐步加特征、调权重。不要一上来就堆复杂评估否则调参变成玄学出了问题也不知道是哪一项特征惹的祸。4.2 alpha-beta 剪枝为什么能少看一半alpha-beta剪枝建立在极大极小搜索上。它维护两个边界alpha表示己方已经能找到的最好分数beta表示对方能让己方得到的最差分数。搜索过程中如果某个分支的结果已经不可能影响上层决策就停止展开这个分支。通俗地说你在比较几个方案已经知道某个方案再算下去也不会比当前最好方案更好就不用继续算了。def alphabeta(board, depth, alpha, beta, maximizing, side): # depth还能往下搜几层alpha/beta当前搜索窗口 if depth 0 or game_over(board): return evaluate(board, side) if maximizing: best -inf for move in generate_moves(board, side): new_board make_move(board, move) score alphabeta(new_board, depth - 1, alpha, beta, False, -side) best max(best, score) alpha max(alpha, best) if alpha beta: break # 对方不会让这个分支发生剪掉 return best else: best inf for move in generate_moves(board, -side): new_board make_move(board, move) score alphabeta(new_board, depth - 1, alpha, beta, True, side) best min(best, score) beta min(beta, best) if alpha beta: break # 己方已有更好选择剪掉 return best这段伪代码里depth控制搜索深度alpha和beta是搜索窗口maximizing表示当前轮到哪一方做最大化选择side用于评估函数判断视角。剪枝的关键是走法排序先搜好棋alpha-beta越早找到高下限越容易剪掉后面的坏分支。搜索顺序不好剪枝效果会大打折扣。剪枝不改变最优结果的前提是窗口和回传逻辑正确如果评估函数或走法生成有 bug剪枝会把错误放大。4.3 蒙特卡罗树搜索用随机模拟代替深度评估蒙特卡罗树搜索走的是另一条路。它不急着给每个局面写一个精确评估而是从当前局面出发做大量随机模拟看哪条路胜率高。经典流程包括选择、扩展、模拟、回传先按一定策略选一个节点扩展新节点从新节点开始随机走到终局再把结果回传更新节点统计。围棋这类评估函数难写的棋蒙特卡罗树搜索曾经是很重要的突破方向。它的优点是减少对人工评估的依赖缺点是模拟次数要多算力消耗大。随机模拟不是乱下选择阶段要平衡“探索”和“利用”多试试没把握的分支也多走胜率高的分支。工程上还要控制模拟深度、模拟策略、时间预算。竞赛里如果时间短蒙特卡罗树搜索可能还没收敛就超时如果评估函数已经比较可靠传统搜索加alpha-beta反而更直接。4.4 搜索和学习的边界讲义把机器博弈的方法学特点概括为“基于搜索”。搜索是主线把对局看成树在树上找下一步。学习是另一条线从数据或自我对弈中调整评估和策略。两者不是对立关系。传统棋类程序靠搜索加人工评估现代方法常把学习得到的评估网络放进搜索里。对初学者来说先把搜索链路走通再理解学习在哪里介入比一上来追新词更稳。学科关系也不复杂计算机博弈和计算机科学、数学、人工智能都有交叉。计算机科学提供数据结构和工程实现数学提供搜索、概率和优化工具人工智能提供评估、学习和决策框架。这份资料把这些关系摆在前面是为了让读者知道自己在学哪一层而不是把“计算机博弈”当成一个孤立技巧。5. 常见误区与易混概念计算机博弈不是背棋谱这么简单初学者看计算机博弈容易被几个词带偏搜索深度、评估函数、蒙特卡罗、深度学习、竞赛辅导资料。每个词单独看都懂放在一起就容易混。下面挑五个最常见的易混点按“易混点—为什么混—怎么区分”拆开说。提前把边界厘清后面看资料和写程序都少走弯路。5.1 误区一搜索越深越强易混点把搜索深度直接当成棋力。为什么混很多程序提升棋力时确实会加深搜索比赛新闻也爱说“算得更深”。怎么区分深度是必要条件不是充分条件。搜索再深评估函数错了也会沿着错误方向走水平线效应会让机器在有限深度内看不到更远的坏结果时间固定时深搜还可能挤掉走法排序和规则检查的时间。判断一个程序强不强要看搜索深度、评估质量、走法排序、规则处理是否配合而不是只盯层数。5.2 误区二评估函数越复杂越好易混点把特征数量当成评估水平。为什么混复杂评估看起来“考虑得多”容易让人放心。怎么区分评估函数要可解释、可调、尺度一致。国际象棋用兵1、马3、象3、车5、后9这种相对子力值简单但有效象棋还要看将的安全、子力位置、过河兵。特征堆太多权重互相打架调参变成玄学出了问题也很难定位。好的评估不是特征最多而是和搜索配合得最稳。5.3 误区三围棋和象棋的难度可以直接比易混点用“哪个棋更复杂”做跨棋种比较。为什么混都叫棋规则都能写出来直觉上容易排个高低。怎么区分难度要分维度。象棋的分支因子和规则细节多走法生成复杂围棋的分支更多局面评估更难写。一个难在规则层次一个难在评估和搜索空间。竞赛选题时不是比“哪个更高级”而是看你的算法、算力、时间更适合哪一类。5.4 误区四蒙特卡罗树搜索等于深度学习易混点把蒙特卡罗树搜索和深度学习当成一回事。为什么混现代棋类新闻里这两个词经常一起出现听起来像同一个东西。怎么区分蒙特卡罗树搜索是一种搜索方法靠模拟和统计选分支深度学习是学习表示和策略的方法常用来提供评估或策略网络。蒙特卡罗树搜索可以单独用深度学习也可以不靠它。把两者分开才知道自己在调搜索预算还是在调模型。5.5 误区五竞赛辅导资料等于代码模板易混点把辅导资料当成现成引擎。为什么混资料名字里有“竞赛”“辅导”容易让人期待直接能跑的代码。怎么区分这份资料的重点是原理、分类、软件构成、棋局评估、博弈树展开它帮你建立概念地图不替代工程实现。棋盘模拟、走法生成、搜索剪枝、界面计时都要自己写或自己调。资料解决“知道该做什么”代码解决“把它做出来”。两件事不能混。提示看资料时先问它讲的是概念、方法还是成品代码三类内容的用法不一样。6. 什么时候该用这份资料从棋类分类到竞赛选题的边界判断这份计算机博弈竞赛辅导资料适合在你需要建立整体认知时用。比如课程刚入门想知道棋类为什么分完全信息和不完全信息准备竞赛选题想判断走子类、填子类、混合类各难在哪写程序前想先弄清棋盘模拟、搜索算法、评估函数、用户界面四块怎么分工。它也能帮你理解棋局评估和博弈树展开的关系避免一上来就扎进某个算法细节。不适合的情况也要说清想要现成引擎代码直接拿去做竞赛这份资料不干这事想深挖某个搜索算法的源码实现它也不是源码手册想部署到特定平台它不给平台操作步骤。把资料当“概念地图”用收益最大把它当“成品工具箱”用容易失望。你的目标适不适合用这份资料原因搞懂计算机博弈的基本概念适合覆盖棋类分类、软件构成、评估与搜索准备竞赛选题适合能帮你判断棋种类别和难点想直接拿现成代码参赛不适合资料重原理不替代工程实现想深挖某个算法源码不适合需要更专门的代码和论文材料想理解评估函数和搜索的关系适合有棋局评估和博弈树展开的完整线索选题时可以先按分类缩小范围走子类规则细适合练走法生成和规则判断填子类分支多适合练搜索和评估混合类层次多适合练模块拆分。再看时间预算竞赛时限紧先选规则清楚、评估可写的棋种别一上来挑评估最难写的。最后看资料能帮你到哪一步它帮你把问题拆开具体实现还要自己补。我以前看资料只盯算法名字觉得“用了alpha-beta”或“用了蒙特卡罗”就厉害结果规则判断漏了、计时没管好比赛里直接翻车。从那以后我每次翻一份博弈资料都会先看它有没有把棋盘表示、搜索停止条件、评估依据讲清楚再决定要不要花时间。希望帮到你。完整资料在下载页按项目说明获取即可先拿它把概念地图搭起来再往具体棋种和算法里走。本文还有配套的精品资源点击获取
