简介这份计算机博弈竞赛辅导资料出自东北大学机器博弈研究室是一份面向计算机博弈竞赛选手与研究学习者的系统讲义。内容从棋类介绍与分类讲起覆盖中国象棋、国际象棋、围棋、五子棋、六子棋以及一字棋、二虎棋、三通棋、点格棋等民间棋类并逐步展开计算机博弈的基本原理、方法学概述、软件构成、棋局评估与博弈树展开分析能够帮助读者建立从规则认知到算法实现的完整知识框架。资源包仅含1个PPT文件整体大小2.57MB便于直接下载后按章节浏览学习。目前已有326人学习下载适合作为竞赛备赛、课程辅助或自学入门的参考资料。这份讲义在棋类规则之外还重点梳理了基于搜索的机器博弈方法学特点以及计算机博弈与人工智能、数学等学科的关联对于理解博弈树搜索、评估函数设计等核心概念具有直接的指导价值。1. 计算机博弈竞赛辅导资料先搞懂你比的是哪种棋再谈算法计算机博弈大赛备赛最常踩的坑不是搜索算法写不出来而是拿到题目后直接上手写 minimax连棋类本身的博弈性质都没搞清楚。东北大学机器博弈研究室的这套辅导讲义第一讲就把中国象棋、国际象棋、围棋、五子棋、六子棋以及点格棋、苏拉卡尔塔、华容道这些棋类全部过了一遍看起来像科普实际上是在给算法选型划定边界走子类、填子类、混合类的博弈树结构完全不同评估函数的设计起点也不同连胜负判定都牵涉到不同的实现复杂度。适合正在备赛计算机博弈竞赛、或者刚进实验室想快速建立全局认识的人。2. 棋类分类与搜索复杂度走子类、填子类和混合类的选型差异2.1 完全信息动态博弈为什么棋类比牌类更适合搜索课件里反复强调一个判断棋类是完全信息动态博弈牌类是不完全信息动态博弈。这个区别直接决定搜索引擎能不能用。完全信息意味着任意时刻双方都清楚盘面上的全部状态没有隐藏手牌没有随机发牌搜索树的每个节点都是确定的。计算机可以从当前局面出发枚举所有合法走法逐层展开理论上不存在信息盲区。牌类就不行。对方手里有什么牌你不知道搜索树的叶子节点带概率分布评估函数要考虑期望值还要建模对手的隐藏信息复杂度立刻上升一个量级。这也是为什么竞赛项目几乎全是棋类不会拿斗地主当标准题。选型时还有一个容易被忽略的点不确定性来源。围棋、中国象棋、国际象棋都不含随机因素先手优势是唯一的不公平点。课件里专门提到围棋贴目 5-7 目、六子棋用先手下一子、之后每手两子的规则来削弱先手优势这些都是规则层对搜索公平性的修正。如果你做的棋类没有这些机制评估函数里就要手动加入先手补偿项否则同一套引擎先后手胜率会明显偏向一方。2.2 竞赛棋类的规则参数表与复杂度对照把课件里提到的棋类整理成一张参数表备赛选题时直接对着看棋类棋盘兵种/棋子数行棋方式胜负判定相对实现难度中国象棋9×107 兵种 × 16 子走子各兵种规则不同将死、困毙长将判负60 步不吃子判和中高国际象棋8×86 兵种 × 16 子走子含王车易位、兵升变、吃过路兵王被将死中围棋19×19单兵种填子占地多者胜贴目 5-7极高五子棋15×15单兵种填子五子连珠禁手限制先手低六子棋19×19单兵种填子先手一子后续两子六子连珠低点格棋点阵棋盘无固定棋子连线成格占据方格多者胜低亚马逊棋盘上的后每方 4 子移动设障无子可动判负中这里的相对实现难度是我按竞赛经验估的不是课件原话。五子棋、六子棋规则最简单适合快速出基线版本中国象棋和国际象棋规则细节多王车易位、吃过路兵、长将判负这些边角规则容易写漏适合有耐心做规则层的人围棋搜索空间太大19×19 全盘在竞赛时限内基本搜不了几层课件里也说当前侧重解决 9×9 的 1/4 棋盘。2.3 六子棋、点格棋的选型优势从规则细节看实现成本六子棋值得单独说。它由吴毅成教授发明棋盘 19×19先手第一手只下一子之后每手两子只要形成六子连珠即胜。这个规则有两个好处一是没有禁手这类复杂约束合法性判断非常简单二是先手优势被结构性削弱评估函数不需要额外加先手补偿。对准备竞赛的新手来说六子棋是从零写出一个完整引擎的最低成本路径。点格棋则是另一个极端规则简单到极致却暗藏策略深度。将邻近两点连成一边四边构成方格时最后一个占边者得格并强制再连一边。课件特别提到死格dead box、双环double cross、长链long chain、短链short chain、环circle这些概念说明评估函数不能只看当前得格数还要预测链条结构——强迫对手打开长链往往是翻盘关键。如果你对博弈论感兴趣点格棋比五子棋更有研究空间。常见做法是先做一个规则完整的基线版本确保走法生成和终局判定正确再考虑搜索和评估。因为规则层的 bug 最难查一旦终局判定错了后面的评估和搜索全都建立在错误基础上。3. 博弈树展开与alpha-beta剪枝评估函数和深度控制的落地参数3.1 博弈树展开节点定义、走法生成与停止条件博弈树展开是搜索引擎的核心循环课件里提到的基于搜索的方法学特点落到代码上就是递归展开节点。先用一个最小节点定义class GameNode: def __init__(self, board, side_to_move): self.board board # 当前盘面 self.side side_to_move # 轮走方1 为红/先手-1 为黑/后手 self.children [] # 子节点列表 self.value None # 评估值展开后回填 def generate_moves(self): 生成当前方所有合法走法 moves [] for piece in self.board.pieces_of(self.side): for target in self.board.legal_targets(piece): moves.append((piece.position, target)) return moves def make_move(self, move): 执行走法返回新节点 new_board self.board.clone() new_board.apply_move(move) return GameNode(new_board, -self.side) def is_terminal(self): 终局判断将死、无子可动、达到最大深度等 return self.board.has_winner() or self.board.is_stalemate()逻辑说明这个节点类把走子类棋的通用结构抽象出来了。generate_moves返回所有合法走法make_move生成子节点并把轮走方取反is_terminal决定是否继续展开。注意轮走方字段用 1/-1 而不是红黑字符串后面评估函数可以直接乘以子力值判断攻防方向。参数说明side_to_move的符号约定贯穿整个引擎约定为 1 表示搜索树当前层要最大化的一方-1 表示要最小化的一方这样在评估函数里可以统一写成score * node.side。如果你用字符串red/black后面 alpha-beta 里的正负号逻辑会写得很痛苦。课件里对展开停止条件没有展开讲实际竞赛中一般设三个达到预设深度、盘面终局、剩余时间不足。第三个条件尤其重要后面避坑章会细说。3.2 评估函数设计子力值、位置权重与先手修正评估函数决定搜索树的叶子节点值多少钱。课件里给了国际象棋的相对子力值兵 1、马 3、象 3、车 5、后 9这个表是所有评估函数的基础。但只有子力值是不够的还要加位置权重和先手修正。def evaluate(board, side_to_move): 返回当前盘面从先手视角的评估值正数表示先手优 score 0.0 # 1. 子力值 for piece in board.pieces_of(1): score piece.value # 兵 1、马 3、象 3、车 5、后 9 for piece in board.pieces_of(-1): score - piece.value # 2. 位置权重示例马走中有利 for piece in board.pieces_of(1): score position_table[piece.kind][piece.rank][piece.file] for piece in board.pieces_of(-1): score - position_table[piece.kind][piece.rank][piece.file] # 3. 先手修正如果规则没有贴目/换手机制加一个常数 if board.rules.has_no_komi(): score 0.1 return score逻辑说明第一段统计双方子力差第二段叠加位置权重表第三段是规则层没有先手补偿时的修正项。位置表的数值来自棋理经验比如马在中心比在边角更有控制力兵在拱过头之后价值递减直接在表里配权重就行。参数说明position_table是每个兵种一张 8×8 或 9×10 的浮点表经典做法是把开局、中局、残局分开配三张按棋局阶段插值切换。先手修正系数 0.1 是经验值五子棋可以往上调到 0.5因为先手优势被证明是必胜的。我一般会在评估函数里加一条调试开关def evaluate(board, side_to_move, debugFalse): if debug: print(fmaterial{material_score}, position{position_score}, komi{komi_score})这条开关在引擎出现莫名走劣时很有用能快速定位是子力统计错了还是位置表写反了。3.3 alpha-beta剪枝与深度控制代码与参数说明有了博弈树和评估函数下一步就是把朴素搜索改成带剪枝的版本def alpha_beta(node, depth, alpha, beta, maximizing): if depth 0 or node.is_terminal(): return node.evaluate() moves node.generate_moves() if maximizing: value -float(inf) for move in moves: child node.make_move(move) value max(value, alpha_beta(child, depth - 1, alpha, beta, False)) alpha max(alpha, value) if alpha beta: break # beta 剪枝 return value else: value float(inf) for move in moves: child node.make_move(move) value min(value, alpha_beta(child, depth - 1, alpha, beta, True)) beta min(beta, value) if alpha beta: break # alpha 剪枝 return value逻辑说明alpha是当前路径上先手方能保证得到的最低分beta是后手方能保证的最高分区间不断收窄。当alpha beta时当前节点剩余分支不必再搜因为父节点已经能确定这条路不如已知选项好。剪枝不影响最终结果只减少搜索量。参数说明depth在竞赛中一般不写死而是用迭代加深iterative deepening先搜 1 层再搜 2 层直到时间用完。这样超时后至少有一个完整深度的走法可用不会出现想了一手却超时判负的情况。更实用的做法是给深度加一个动态判断def search_with_timeout(node, max_time_ms): start time.time() best_move None depth 1 while time.time() - start max_time_ms * 0.8: current_best search_root(node, depth) if current_best is not None: best_move current_best depth 1 return best_move注意时间余量搜索本身耗时会比迭代加深的预估超出不少留 20% 缓冲是血泪经验最后一层经常搜不完但best_move已经保存了上一层结果不至于空手而归。4. 计算机博弈软件构成四层架构与规则层实现细节4.1 软件四层构成界面层、规则层、搜索层、评估层课件里把计算机博弈软件分为用户界面、棋盘模拟、搜索算法、评估函数四个部分。实际工程化我会把它拆成四层每一层职责单一层间只通过数据结构交互层级职责关键输出依赖界面层棋盘绘制、走子交互、对局日志用户的走法指令规则层提供合法性校验规则层走法生成、合法性检查、终局判定、和棋判定合法走法列表、局面状态无只依赖棋盘数据结构搜索层博弈树展开、alpha-beta剪枝、迭代加深最佳走法规则层的走法生成评估层评估函数、位置表、残局知识局面分值无纯数值计算这个分层最直接的好处是调试时可以单独测每一层。规则层有 bug走法生成就会漏棋或产生非法走法搜索层有 bug剪枝过了头导致走法变劣评估层有 bug引擎会走出多送一子的昏招。四层分开后每层都可以写独立测试用例定位问题不用从界面一路追到底层。4.2 规则层实现要点合法性校验、终局判定与和棋规则规则层是整个引擎正确性的地基也是最容易出隐蔽 bug 的地方。我先说合法性校验。以中国象棋为例兵种的行棋规则和活动范围不同马走日字但蹩马腿象走田字但塞象眼士只走九宫斜线将帅只能在九宫内直行一步。这些规则看着简单组合起来很容易漏掉边界条件。def legal_targets(board, piece): targets [] if piece.kind 马: for dx, dy in [(-2,-1), (-2,1), (2,-1), (2,1), (-1,-2), (-1,2), (1,-2), (1,2)]: target (piece.rank dx, piece.file dy) if not board.in_board(target): continue leg (piece.rank dx // 2, piece.file dy // 2) # 马腿位置 if board.blocked(leg): continue if not board.blocked(target) or board[target].side ! piece.side: targets.append(target) return targets逻辑说明马的八方向日字走法leg是马腿位置如果马腿被棋子占住就不能走这是中国象棋和国际象棋马规则的显著差异——国际象棋的马不怕蹩腿。代码里判断目标格是空位或对方棋子可吃同方棋子则排除。参数说明dx // 2和dy // 2是马腿相对马位置的偏移因为日字走法的横纵位移是 ±2 和 ±1 的组合腿在中间一格。这段代码写得是否严谨直接决定搜索层会不会生成非法走法。终局判定也有顺序问题。中国象棋的胜负判定优先序是被将死、被困毙、长将判负、60 步不吃子判和。常见做法是每走一步都检查走子方的合法性如果一方无合法着法且被将军则判负无合法着法但未被将军则是困毙。长将判负需要在走法历史里检测循环重复局面60 步不吃子需要记录吃子时间戳。这两个状态都建议放在规则层的对局对象里不要放到界面层否则换界面会导致规则丢失。4.3 引擎与界面分离UCCI协议的实践建议竞赛对局往往需要两个程序互相下棋这就涉及通信协议。常见做法是采用 UCCIUniversal Chinese Chess Interface或 XBoard 协议把引擎做成命令行程序界面进程向引擎发送局面和走子指令引擎返回最佳走法。# 引擎标准输入输出示例 position startpos moves h2e2 h9g7 go depth 12 bestmove e2e4逻辑说明position指令告诉引擎当前局面和已走过的棋步go指令触发搜索并返回最佳走法。这样引擎只负责算界面只负责画两个进程之间是弱耦合比赛时甚至可以人机对战。参数说明depth 12指定搜索深度竞赛组委会通常会要求固定深度或固定时间内返回走法。我一般会在命令行参数里加一个配置项让引擎支持go depth N和go time N两种模式前者用于调试后者用于正式比赛。5. 竞赛避坑从规则实现到评估函数的五类常见翻车5.1 中国象棋长将与 60 步不吃子判定顺序写反导致误判现象引擎连续将军把对手将死结果裁判判定我方长将犯规直接判负还有的对局明明双方 60 步没吃子程序却一直不走和。原因长将判负和 60 步不吃子判和都属于对局历史检测必须在每次走子后、切换轮走方之前判定。常见错误是把和棋检测放在终局判定之后导致局面已经循环播放了十几回合还傻搜。解决把重复局面检测放在搜索层之外的对局对象里维护一个局面哈希表记录相同局面出现次数。长将检测看是否连续将军超过阈值60 步记录从上次吃子到当前步数的间隔。判定的优先级是先查长将再查步数最后才是正常胜负。5.2 五子棋禁手与六子棋换手规则细节漏实现现象五子棋引擎死活不认禁手黑棋双三取胜被当成有效着法六子棋对战前期优势巨大但对手换手后我方反而被吊打。原因五子棋禁手规则三三禁手、四四禁手、长连禁手属于规则层的终局判定分支很多人只实现五子连珠把禁手漏了直接导致引擎走法生成和目标判定不一致。六子棋的换手规则是后手可以在特定阶段选择交换执子没实现这个机制引擎就意识不到先手那手棋是在给对手铺路。解决五子棋在is_terminal里区分白胜黑禁手负黑五连获胜三种状态禁手检测放在黑棋落子之后立刻做。六子棋则要在界面层加入换手确认步骤在规则层记录换手状态位评估函数按当前执色方向计算。这类规则细节最容易在项目收尾时遗漏建议一开始就照着完整规则文档逐条核对。5.3 评估函数漏位置权重中局送子问题的排查现象引擎搜索深度 8 层局面评估也正常但中局总是白送一个马或炮对手用同一套引擎就永远不会犯这个错。原因子力值只算静态价值没乘位置权重。一个被压在自己底线动弹不得的马和一个占据中心控制全盘的马子力价值相同但实际作用天差地别。评估函数看不到位置差异搜索树就会认为换子不吃亏连续走出亏位棋。解决给每个兵种配一张位置权重表数值范围控制在子力值的 10%-30%。比如马的价值 3中心位置权重给 0.5边角给 -0.3这样同样一个马在不同位置的分差就能被搜索层感知到。位置表的数值不用精调先用对称分布的简化表再对特定棋类实测调整。5.4 搜索超时判负固定深度导致的时间失控现象迭代加深到第 10 层时单步耗时突增到十几秒对手落子后我方直接超时判负。原因迭代加深每一层的耗时是上一层的好几倍如果直接depthN固定深度碰上局面走法特别多的中局搜索时间会指数级上涨。尤其是有吃子延展capture extension的引擎某些分支会被额外展开好几层时间完全不可控。解决用时间预算替代固定深度迭代加深每次进入下一层之前检查已用时间超过预算的 80% 就停。另外把窗口从(-inf, inf)收窄到上一层的(alpha-1, beta1)可以在不损失精度的前提下让剪枝更早生效大幅加速后续层。5.5 点格棋死格与双环评估偏差的来源现象点格棋引擎按当前得格数做评估前中局一路领先残局被对手连吃一串长链翻盘。原因点格棋的策略核心是链条博弈死格、双环、长链、短链这些结构决定了最终得格归属。如果评估函数只统计当前已占方格数看不到谁开链谁吃亏的结构性因素残局就会主动打开长链送给对手连吃。解决在评估函数里加入链结构分析计算盘面上死格数量、短链和长链的数量。经验法则是短链优先闭合长链留给对手开。如果竞赛时限允许可以用动态规划精确计算残局得格数但多数情况下统计链数量加位置权重的简化评估足够打到前几名。6. 把资料变成基线一个最小搜索循环的落地验证把课件里的原理真正落到一份能跑的代码需要走通一个闭环走法生成 → 评估 → 搜索 → 落子。下面是最小可运行版本我用它来验证自己写的规则层和评估层是否自洽。def engine_move(board, max_time_ms3000): 迭代加深入口返回最佳走法 root GameNode(board, 1) start time.time() best_move None for depth in range(1, 64): if time.time() - start max_time_ms * 0.8: break current_best, value search_root(root, depth, -float(inf), float(inf)) if current_best is not None: best_move current_best print(fdepth{depth}, value{value}, move{best_move}) return best_move def search_root(node, depth, alpha, beta): 根节点单独处理记录最佳走法 best_score -float(inf) best_move None for move in node.generate_moves(): child node.make_move(move) score alpha_beta(child, depth - 1, alpha, beta, False) if score best_score: best_score score best_move move alpha max(alpha, score) return best_move, best_score验证方法很简单让两个引擎互相下同一局面先手执行engine_move后手也执行engine_move跑 50 局统计胜率分布。如果引擎是在自身上调试 bug这个闭环能暴露 90% 的规则层问题——比如走法生成漏了某种边界搜索会连续选到非法走法盘面直接崩掉。从那以后我每次写完规则层都会先跑一遍同策略自对弈双方用同一套评估函数但搜索深度不同如果深度浅的一方偶尔赢深度深的大概率是评估函数的某个权重反了。这个习惯帮我省下了大量赛后复盘时间。希望帮到你。本文还有配套的精品资源点击获取