简介面向计算机博弈竞赛选手与初学者的辅导课件源自东北大学机器博弈研究室《计算机博弈原理与方法学概述》第一讲系统讲解机器博弈的核心原理与方法。内容按棋类介绍与分类、基本搜索算法、剪枝策略、棋局评估、博弈树展开与分析、博弈软件构成、学科关系等模块展开涵盖中国象棋、国际象棋、围棋、五子棋、六子棋以及一字棋、二虎棋、三通棋、点格棋等典型棋类。这能帮助读者快速建立从规则到算法、从评估到软件实现的整体认知。课件还点明棋类属于完全信息动态博弈并从复杂度差异解释了不同棋种在搜索与评估设计上的难点。包内为一份PPT演示文稿压缩包大小约2.57MB已吸引329人学习适合作为备赛入门、课程自学或教学参考也可作为机器博弈基础知识体系的快速阅读材料。1. 计算机博弈竞赛辅导资料从一张讲义开始的入门地图搜计算机博弈竞赛的备赛资料最常见的两个结果一堆论文和一堆源码。论文把原理讲得很严谨但你看完还是不知道第一步该写什么源码能跑、能赢棋但要反推它为什么这么设计得花很长时间。我手里这份某高校机器博弈研究室的辅导讲义恰好把这两者之间的缝隙补上了它从棋类分类讲到博弈树从评估函数讲到搜索剪枝最后落到软件构成和学科关系。它不解决某个具体棋类怎么写而是解决你面对任何陌生棋类时怎么把规则翻译成搜索问题。适合两类人马上要参赛、需要一个全局框架的选手以及刚开始接触博弈树、想让入门不走弯路的学生。2. 棋类家族谱系为什么“完全信息动态博弈”决定了搜索方案2.1 棋与牌的分界完全信息与动态博弈意味着什么讲义开篇就划了一条硬线棋类属于完全信息动态博弈牌类属于不完全信息动态博弈。这条线不是分类学上的较真它直接决定了你程序里搜索器怎么写。完全信息意味着盘面上任何信息对双方都是可见的不存在“对手手里扣着几张牌”这种隐藏状态。于是博弈过程可以抽象成状态转移每个局面是一个节点一步棋是一条边从初始局面开始双方轮流选择走法最终走到胜负判定节点。只要规则允许任何局面理论上都能枚举出来搜索的完备性有了根基。动态博弈意味着双方交替行动每一方做决策时都能看到对方上一次行动的结果。这跟单人的华容道有本质区别华容道只有一个人移动滑块不存在对手所以它的求解可以只用单向搜索而双人棋类必须在“对方也会走最优手”这个前提下做对抗搜索。哪怕你的程序里只有一个搜索函数它在扩展节点时也必须同时模拟对手的反应这就是博弈树和普通状态树的最大差异。讲义在“人们为什么喜欢下棋”这一页列了五个理由规则简单明确、胜负判定简单、过程透明公平、智力和经验决定胜负、变化无穷。翻译成工程语言就是规则适合形式化、胜负条件适合编码、搜索空间大但有规律可挖掘。这正是计算机博弈竞赛选棋类而不是牌类作为研究对象的核心原因——牌类要处理概率推断和对手建模复杂度直接跳了一个数量级不适合作为入门赛道。2.2 十一种典型棋类的棋盘参数与胜负判定速查表讲义用一整个章节铺开了十几类棋从主流到冷门都有。我按棋盘、子数、判定规则和实施难度把它们整理成一张速查表备赛时对照着看会很方便棋类棋盘规格双方子数核心规则与胜负判定备赛要点中国象棋9×10各16子7个兵种将死或困毙长将、长捉受限60步不吃子判和规则细节多适合练规则解析和局面编码国际象棋8×8各16子王被杀即输王车易位、兵升变、吃过路兵子力值体系完整评估函数入门首选围棋19×19轮流落子占地多者胜贴目5-7规则最简单但搜索难度最大入门先用9×9五子棋15×15轮流落子五子连珠胜已证明先手胜引入禁手、换手必须处理禁手规则否则竞赛规则直接判负六子棋19×19先手1子后每手2子六子连珠胜每手两子导致分支因子大搜索压力显著高于五子棋一字棋路径棋盘尺寸不限每方多子先到目标点者胜至少走一步至多到终点不准逆行规则简单适合做搜索框架的最小验证集二虎棋未固定虎犬布阵虎方与犬方子数不同虎吃够犬子胜犬围困虎至不能动胜双方目标不对称评估函数设计有参考价值三通棋64个小正三角形各32枚先实现三通者胜乙方有一次连下两着权利可模拟连续行动权的搜索逻辑点格棋点阵连边轮流连边四方成格得格并再连一边格多者胜关注死格、双环、长链、短链、环等结构苏拉卡尔塔未固定轮流走子沿弧线吃子吃光对方子胜吃子走法特殊走法生成容易写错亚马逊未固定各4个“后”移动后设障无子可动者判负先扩张后困敌评估函数要算活动空间华容道滑块棋盘单人将曹操移到出口单人搜索不含对手博弈适合热身这张表的信息量主要在前四行。中国象棋和国际象棋的分支因子和子力体系都有成熟参照适合作为第一个完整项目围棋和六子棋复杂度高适合作为进阶目标。冷门棋类的价值在于训练你“拿到一段文字规则翻译成可执行代码”的能力这个能力才是竞赛里最值钱的。2.3 按着法分类走子类、填子类、混合类如何影响搜索器设计讲义在中后段给了一个很实用的分类维度——按着法拆分。这个维度对程序架构的影响比棋种本身的名气更直接。走子类棋包括象棋、国际象棋、跳棋、牛角棋、苏拉卡尔塔、亚马逊。共同特点是开局前双方已摆好棋子之后轮流走动。这类棋的走法生成模块相对好写每类棋子都有固定的行棋规则你只需要把规则逐条编码再处理特殊规则比如国际象棋的王车易位、吃过路兵。搜索压力集中在“每一步选择多”中国象棋常见估计分支因子在40-45之间国际象棋约35-40属于中等规模。填子类棋包括围棋、五子棋、点格棋。开局盘面无子双方轮流放入棋子。这类棋的走法生成几乎没有规则负担——所有空格都可落子但评估函数难度骤升。因为你需要评判“一个还没连成形的棋形值多少钱”这是典型的局面建模问题比子力值求和难得多。尤其是围棋19×19棋盘上合法落点超过250个分支因子爆炸所以讲义才强调“当前侧重解决1/4棋盘Go 9×9”。混合类棋以五道棋、日本将棋为代表。开局先填子填到一定条件后转为走子。这类棋的搜索器设计最难的地方在于阶段切换填子阶段和走子阶段的评估指标不一样搜索策略也要跟着换。如果你的第一个竞赛项目是这类棋建议先分别实现两个阶段的搜索器再考虑统一调度。直接从全局搜索入手很容易陷入“两个阶段互相干扰”的泥潭。3. 博弈树展开、评估函数与α-β剪枝把规则翻译成搜索3.1 博弈树展开与节点爆炸为什么“完整展开”只在残局成立博弈树的概念不复杂初始局面是根节点每一步合法走法产生一个子节点双方轮流扩展走到胜负判定就形成叶节点。理论上只要把整棵博弈树展开找到所有叶节点中对我方最优的那个路径就是完美对局策略。问题是树长得太快。用分支因子b和平均对局深度d表示树的节点数大约是b^d这个量级。国际象棋分支因子约35、对局深度常在80-100层35的80次方是个天文数字围棋就更不用提了。所以“完整展开”只在一个场景下可行——残局。当棋盘上棋子数量很少分支因子降到可能只有10-20深度也缩短程序才有能力在限定时间内搜到终局。这也是为什么大多数棋类程序采用“有限深度搜索评估函数截断”的方案搜索到固定深度就停用评估函数给当前局面打分把“精确解”降级成“近似最优”。讲义的“机器博弈的方法学特点”一节明确点出这门学科的特色就是基于搜索。但这个搜索不是盲目枚举而是三层配合一是控制搜索深度算到当前能承受的层数就收手二是在每个深度边界用评估函数打分作为截断值三是用剪枝策略跳过明显不优的分支把计算资源集中在有希望的路线上。理解了这个结构再看后面所有算法就顺了。3.2 评估函数从子力值到局面特征的建模顺序评估函数是对“棋盘上当前谁占优”的数值化回答。讲义给了一个朴素但有效的起点——子力值。国际象棋的相对子力值参考是兵1、马3、象3、车5、后9王不参与子力交换但程序里通常会给一个很大的值比如10000避免搜索中出现“送王”这种非法局面。子力值只是第一层。只用子力值的程序有个通病它看不出“位置”的价值。同一个马在角落和在中心完全是两个棋子同一个兵刚走出第一步和冲到对方底线升变威胁量级也不一样。所以常见做法是在子力值之上加位置特征中心控制、子力活跃度、兵形结构、王的安全度。一步步加每加一个特征就做一次回归验证不要一口气堆十个特征进去。还有一个很容易被漏掉的项——先手优势。讲义里明确提到棋类的“不公平点先手优势”并给出围棋贴目5-7、五子棋禁手和换手这些补偿机制。程序里也要做同样的补偿常见做法是给先手一个很小的加分项比如0.1到0.5个子力分消掉搜索器“盲目争先手”的倾向。这个值不能拍脑袋定要靠自对弈调。3.3 α-β剪枝窗口、走法顺序与搜索深度的耦合minimax是博弈树搜索的基础方法己方层取子节点最大值对方层取子节点最小值逐层回传。问题在于它要遍历所有节点复杂度还是b^d。α-β剪枝做的事情很直接维护一个窗口α表示己方已知的下界至少能拿到多少分β表示对方已知的上界最多让己方拿多少分。搜索过程中一旦出现β≤α说明当前分支已经不可能影响最终选择直接剪掉。窗口收得越紧剪掉的节点越多。理想情况下走法排序足够好时节点数能降到接近O(b^(d/2))相当于同样时间内可以多搜一倍的深度。这个收益在竞赛里非常可观。但剪枝效率不是白来的它高度依赖走法排序。如果每次扩展节点时最优走法排第一位α很快被抬升、β很快被压低剪枝效果最好如果走法排序差α和β迟迟不动剪枝就退化成几乎不剪。最常见的工程解法是迭代加深先用浅层深度比如2层搜索完整一遍把当前认为最好的走法记录为主变路线下一轮搜索时把主变路线上的走法排在走法列表最前面。这样既得到了更好的排序又能配合时间预算控制搜索深度——时间还剩就加一层超时就回退一层。3.4 最小骨架minimax加alpha-beta的Python实现下面这段代码是我按讲义思路整理的通用搜索骨架。它不绑定某个具体棋种走法生成和局面更新留出接口你只需替换成自己棋类的实现就能直接跑通搜索主流程。# 通用博弈树搜索骨架minimax alpha-beta 剪枝 # 局面 board 用字符串表示红方大写、黑方小写. 为空位 import math PIECE_VALUES {P: 1, N: 3, B: 3, R: 5, Q: 9, K: 10000} def evaluate(board): # 评估函数按子力值求和己方为正、对方为负 # 这只是一个基线版本竞赛里要叠加位置表和兵形特征 score 0 for ch in board: if ch .: continue sign 1 if ch.isupper() else -1 score sign * PIECE_VALUES[ch.upper()] return score def generate_moves(board, maximizing): # 占位实现按具体棋类规则返回所有合法走法 # 返回 [(from_index, to_index, captured), ...] return [] def apply_move(board, move): # 占位实现返回执行走法后的新局面 return board def minimax(board, depth, alpha, beta, maximizing): # depth剩余搜索深度depth0 时用评估函数截断 # alpha己方下界beta对方上界 # maximizingTrue 表示本轮轮到己方走棋 if depth 0: return evaluate(board) moves generate_moves(board, maximizing) if maximizing: best -math.inf for move in moves: child apply_move(board, move) value minimax(child, depth - 1, alpha, beta, False) best max(best, value) alpha max(alpha, value) # 己方下界抬升 if beta alpha: break # 剪枝对方已不会选这条线 return best else: best math.inf for move in moves: child apply_move(board, move) value minimax(child, depth - 1, alpha, beta, True) best min(best, value) beta min(beta, value) # 对方上界压低 if beta alpha: break return best def best_move(board, depth): # 搜索入口返回当前局面下最优走法 best None alpha, beta -math.inf, math.inf for move in generate_moves(board, True): child apply_move(board, move) value minimax(child, depth - 1, alpha, beta, False) if value alpha: alpha value # 等价于使用上层窗口做选择 best move return best这段代码的逻辑链路是best_move遍历第一层所有走法对每个走法递归调用minimax递归到depth0时用evaluate截断返回局面分数中间每一层都执行α抬升或β压低一旦窗口关系失衡就剪枝。剪枝条件统一是beta alpha两侧共用这一个判断。关键参数有三个depth决定搜索深度竞赛环境下通常用时间预算动态确定——先试固定的3到4层看单步耗时再逐步加深alpha和beta的初始值固定为负无穷和正无穷表示一开始对结果没有任何假设走法排序的质量直接决定剪枝效率这也是为什么工程代码里几乎都会加迭代加深和置换表本质都是为了让好走法尽早出现在列表中。把这套骨架理解透再换上具体棋类的generate_moves和apply_move你就拥有了一个可继续迭代的竞赛基线。4. 计算机博弈软件构成与学科关系先搭框架再谈算法4.1 软件四模块棋盘表示、搜索器、评估函数与界面讲义把计算机博弈软件拆成了几个组成部分用户界面、棋盘模拟、搜索算法、评估函数。对竞赛项目来说我倾向于把它收敛成四个更贴近编码的模块。棋盘表示是底层数据结构决定你写走法生成和评估函数时的体验。常见做法有三种数组棋盘最简单二维数组或一维字符串都行适合原型位棋盘bitboard用一个整数类型表示某一方的所有棋子位置走法生成和攻击检测效率高象棋和国际象棋类项目用得多Zobrist哈希不是一种棋盘表示但常用于局面判重和置换表键值生成竞赛里做重复局面检测几乎必备。建议第一个版本先用数组棋盘把逻辑跑通性能不足时再换位棋盘不要一开始就上复杂结构。搜索器和评估函数是核心逻辑。搜索器按时间预算分配搜索深度负责返回当前局面的最佳走法评估函数把局面转成数值。这两块的上文已经完整展开不再重复。界面模块最容易被参赛新手高估权重——比赛时通常只要求你暴露一个接口给一个局面返回一步棋。图形界面用命令行打印棋盘就够了把精力留给搜索。我在实际项目里的做法是先写一个print_board的文本渲染能看清子力位置即可图形界面到最后有剩余时间再做。4.2 学科交叉为什么评估函数是数学建模而不是编码问题讲义在“学科关系”部分提到计算机博弈与计算机科学、数学、人工智能的关系。很多新人把博弈程序当成纯编码项目一上来就写搜索函数遇到瓶颈时不知道该往哪个方向排查。其实这三个学科对应的是三类不同的工作。搜索算法属于计算机科学里的算法设计与分析研究的是复杂度、数据结构、剪枝策略它解决的是“怎么搜得更快”评估函数本质上是数学建模问题要你把一个开放局面映射成一个数值考虑哪些特征、每个特征权重多大这是建模和特征工程的活而人工智能在这个语境下指的是让程序通过自我对弈、强化学习等方式自动改进策略属于进阶方向。定位错了排错思路就会混乱——搜索慢去调评估函数、评估不准去改剪枝条件都是浪费时间的典型操作。4.3 开发优先级从“能走子”到“能比赛”的四个验收阶段我见过不少参赛队伍栽在同一个坑里先花两周做界面和动画再花一周写规则最后只剩两天调搜索。规划得按阶段推进而且每个阶段要有明确验收标准。第一阶段是规则解析与走法生成。把棋盘表示、合法走法生成、胜负判定全部写完。验收方式写一份针对规则边界的单元测试比如国际象棋的王车易位、吃过路兵五子棋的禁手判定。第二阶段是随机对弈。让两个“随机走子”的程序互下跑上百局保证不越界、不出现非法走法、能正常终局。这一步能筛掉绝大多数规则实现漏洞。第三阶段接入评估函数与固定深度搜索让程序能稳定击败随机对弈版本。第四阶段再优化搜索效率加迭代加深、置换表、开局库和残局库。按这个顺序走每一步都能验证不会出现“开发到一半不知道程序是不是已经坏了”的黑匣子状态。5. 避坑记录五类常见翻车现场与排查思路5.1 长将死循环和棋规则缺失让必胜局面超时判负现象程序在明显必胜的残局里反复将军不推进也不终局直到比赛超时判负。原因博弈树搜索里重复走子会形成循环路径。象棋规则里的长将、长捉限制以及“60步不吃子判和”的强制和棋规则如果没在程序里实现搜索器就不知道“局面重复三次应该停止”这个终止条件于是反复在两个局面之间来回跳。解决在搜索器里加局面哈希表用Zobrist哈希记录出现过的局面遇到相同哈希值且是重复局面时按规则判定为和棋或直接降低该路径的评估分。同时实现步数计数器超过60步无吃子强制平局。这两个条件都要成为搜索树的合法叶节点而不是等到对局结束后再处理。5.2 评估只有子力分程序为什么主动送马换兵现象程序的评估系统只有子力值时它会走出“送马换兵”这类明显吃亏的棋。子力分上亏了2分但程序认为局面“可以接受”。原因子力分只是静态数值它反映了“你有什么”不反映“你的子放在哪”。一匹马在自家底线和一匹马在对方腹地控制着大片格子子力值完全相同实际价值天差地别。程序没有位置概念自然看不出亏。解决在子力值基础上叠加位置特征常见做法是给每类棋子建一张位置权重表中心格权重高、边角低再加上基础特征如图王安全、兵的推进度。每加一个特征就用自对弈做消融验证确认这个特征确实带来正向收益而不是自我感觉良好。5.3 五子棋禁手缺失自测没崩比赛现场却爆冷现象本地自测时程序赢了比赛时对手使用换手规则程序直接懵住或者程序自己走出禁手落点被判负。原因五子棋已被证明先手必胜所以竞赛普遍采用禁手、换手、三手交换、五手两打这类补偿规则。讲义里明确列了“禁手、换手、金球制”。很多开发者在原型阶段只实现“五子连珠胜”这一条基本规则禁手规则没写程序不知道“三三禁手”“四四禁手”“长连禁手”这些非法落点。解决把规则解析独立成一个模块不要混进走法生成器的硬编码分支里。禁手判定用单独的函数实现并写一组针对禁手的测试用例每种禁手类型至少一个落点样例确保能正确拒绝非法着法。竞赛准备阶段先把规则说明里所有特殊条款逐条核销一条都不能漏。5.4 固定深度搜索残局比中局还慢的根因现象中局搜索3层只需要几十毫秒到了残局子力变少了反而每步要卡一秒多。原因一个常见误解是“棋少就一定搜得快”。固定搜索深度下残局分支因子不一定下降。比如尼姆棋、长距离走子的棋类子力减少后每个子能走的位置反而变多走法生成列表长度不减反增加上残局评估精度要求高固定深度搜索会在该算得更深的地方卡住。解决用自适应深度替代固定深度。设定一个子力数量的阈值低于阈值时把搜索深度上限提高两到三层同时加入安静搜索处理“水平线效应”——评估点位于强迫交换序列中间时先跳过不吃子走法等局面稳定后再打分。残局的搜索重心应该放在“能不能杀”“几步杀”这类精确搜索上。5.5 调参失误把“后”从9改成10棋路反而越走越保守现象手动调参把“后”的子力值从9提到10后程序棋风突变开局大量时间移动王不敢出子交战离线自对弈胜率反而下降。原因评估函数里的各项权重是一个相互约束的系统单独调高某一项会打破整体平衡。“后”的价值提高后程序把所有子力都视为不可牺牲资产主动兑子变少、进攻性下降评估分长期偏向“保守囤积”棋盘上的实际控制力却在流失。解决不要单点手调子力值。相对子力值的框架参考来自领域经验比如兵1、马3、象3、车5、后9这套体系已经被大量实践验证过改动前先问一句“我要修正的到底是哪个缺陷”。如果确实需要调用消融测试的方式验证每次只改一个参数固定对照组跑几百局自对弈胜率提升超过阈值才保留。这个过程是评估函数调优的基本功也是最容易出“玄学”的环节。6. 把讲义变成竞赛基线三个验证信号与我的迭代习惯6.1 三个信号判断引擎是否“真的会下棋”第一个信号是走法一致性。在同一局面、同一搜索深度下关闭随机种子后重复搜索多次最佳走法应保持稳定。如果输出漂移明显说明评估函数对局面判断不够敏感搜索器在几个相近分支间反复横跳。第二个信号是单步耗时曲线。让程序跑完整盘快棋记录每一步的搜索耗时正常的曲线应相对平稳有明显的递增只出现在残局加深搜索时如果某一步突然膨胀检查是不是走法生成器在特定局面产生了大量异常分支。第三个信号是残局杀棋能力。把程序丢进一个几步杀的局面看它能不能在允许的搜索深度内找到杀棋路径。能稳定找到说明搜索与评估的衔接是通的找不到优先检查评估函数的“将死惩罚”是否设置正确。6.2 验收习惯每次提版前强制走过一遍的检查我现在每次给参赛版本提测都固定走一遍检查清单第一规则解析模块的单测全绿尤其是禁手类、判和类边界第二关闭随机种子后的最佳走法一致性测试通过第三自对弈至少300局统计先手胜率、平均对局长度确认没有回归第四确认时间预算控制逻辑正常超时保护生效。这套习惯是从一次代价不小的翻车里养成的——当时给评估函数加了一个“象控制中心”的特征离线自对弈后胜率反而掉了一截排查发现它和已有的“中心控制”特征高度线性相关相当于把同一件事加权了两遍。从那以后我每次调评估函数都强制做一遍相关性与消融测试。资料里的原理看着简单真正落地时全是这类细节堆出来的。希望帮到你。本文还有配套的精品资源点击获取
