简介这套计算机博弈竞赛辅导资料源自东北大学机器博弈研究室的教学课件面向参赛选手、相关课程学习者和博弈算法研究者系统梳理竞赛所需的基础理论与方法框架。PPT共1个文件压缩包约2.57MB内容集中、篇幅紧凑适合按模块快速查阅与备赛复习。课件重点覆盖计算机博弈的基本原理、方法学概述、典型棋类介绍、博弈软件的构成、棋局评估以及博弈树展开与分析等核心议题同时结合中国象棋、国际象棋、围棋、五子棋、六子棋及民间棋类案例讲解搜索算法、Alpha-Beta剪枝、启发式评估等关键技术帮助读者理解从棋局建模到博弈搜索的完整链路。资料也涉及机器博弈的方法学特点与学科关系对初学者构建认知框架、对竞赛选手梳理知识体系均有实用价值。目前已有326人学习适合作为计算机博弈课程辅导与竞赛备赛的参考材料。1. 计算机博弈竞赛辅导资料到底在教什么一个可复现的备赛闭环「计算机博弈竞赛辅导资料」不是给你一堆算法流程图就算完事。计算机博弈大赛每年都有很多学生队伍卡在同一个位置规则看懂了搜索算法也会背可程序一上赛场就超时、崩溃或者输给看起来更“傻”的对手。辅导资料真正该解决的是这条闭环——选棋种、写搜索、调评估、配时间控制、跑回归测试。这篇文章就按这条线讲一套大多数棋种都能套用的最小方案。准备参加全国大学生计算机博弈大赛的学生或者带新手入门做项目的老师都适合按这个章节顺序走。你不需要先刷完一整本人工智能导论先把后面的代码跑起来再逐步换成自己棋种的规则就会明白这类比赛拼的不是灵感而是能不能把搜索深度、评估函数和时间分配三件事同时做对的工程能力。2. 选型和理论先定棋种再选搜索算法与评估函数的理由2.1 棋种决定工作量为什么零和完备信息游戏最适合入门计算机博弈大赛的项目并不只有象棋、围棋。常见组别有亚马逊棋、六子棋、苏拉卡尔塔棋、爱恩斯坦棋、点格棋和黑白棋规则复杂度差异很大。我的建议是第一次参赛优先选规则简单、分支因子适中、胜负判定明确的棋种。零和完备信息游戏天然适合用搜索树建模——没有隐藏信息没有随机性每一步都可以推演到底。用一张表快速对比几个热门棋种棋种规则实现成本平均分支因子评估函数难度新手友好度黑白棋低8~15中高六子棋中20~40中中苏拉卡尔塔棋中20~30高中亚马逊棋高60~120高低规则实现成本决定起步速度。亚马逊棋虽然策略很深但“放置障碍块”这一动作会让走法生成逻辑多出一大截六子棋每轮落两子分支因子直接翻倍黑白棋的合法走法生成和落子翻转逻辑一个下午就能写完。所以我后面的演示代码用黑白棋你实际参赛时再把局面生成部分换掉就行。这里要泼一盆冷水选错棋种的代价比算法不会写更大。我见过有队伍整个备赛期都在跟规则细节搏斗直到开赛前一周才开始调搜索最后程序能走棋但深度只有两层。计算机博弈大赛比的是程序之间的对抗不是规则翻译能力把棋种选到自己的可完成范围内才算把辅导资料用对了一半。拿到一个棋种的官方规则文档后不要急着写代码。先把三件事圈出来合法走法的完整定义、终局判定条件、时间与步数限制。这三件事决定了你的数据结构、搜索终止条件和时间控制模块怎么写。很多队伍翻车不是因为算法不懂而是规则文档里的“重复局面判和”和“连续空着判负”这类小字没看到。2.2 搜索算法选型minimax、alpha-beta 与 MCTS 的适用边界先厘清几个概念minimax 是理论alpha-beta 是 minimax 的加速实现MCTS 是另一条路。竞赛中最常用的组合是 alpha-beta 加置换表MCTS 只在评估函数极难写、或者分支因子极大的棋种里才体现出优势。算法核心思想适合场景主要代价minimax双方轮流转置最大/最小收益深度小、教学验证节点数爆炸alpha-beta剪掉不影响根节点结果的子树分支因子 10~40 的棋种很吃走法排序MCTS多次模拟采样按胜率选点评估函数难写、分支因子极大模拟次数要够代码调试难为什么优先选 alpha-beta竞赛读秒通常给到每步 1~3 秒这个时间内 alpha-beta 配合走法排序和置换表能稳定搜到 6~10 层。MCTS 需要大量模拟才能稳定如果落子前只能做几千次模拟质量反而波动很大。对黑白棋、六子棋、亚马逊棋这类评估特征清晰的棋种alpha-beta 是性价比最高的方案。选型时一定要看两个参数分支因子 b 和搜索深度 d。朴素 minimax 的节点量是 O(b^d)alpha-beta 最差也是 O(b^d)但最佳情况下能降到 O(b^(d/2))。这意味着如果走法排序做得好同样时间可以多搜接近一倍的深度。反过来如果走法排序没做alpha-beta 可能退化成 minimax这时候换 MCTS 也不会更好因为问题出在代码上不是算法上。MCTS 不是不能用而是它需要你额外维护一棵策略树和一个 UCT 公式。UCT 的核心是置信区间上界表达式是胜率 C * sqrt(ln(N) / n)其中 N 是父节点访问次数n 是当前子节点访问次数。C 值通常取 0.2~1.0调起来很玄学。如果你的棋种评估函数已经能给出比较靠谱的分数我建议你别折腾 MCTS把精力放在搜索排序和置换表上收益更直接。2.3 评估函数是黑匣子特征怎么提权重怎么定评估函数把局面好坏映射成一个数值数值越大对己方越有利。对新手来说最稳的写法是组合多个可解释特征而不是一上来搞神经网络。常用特征就这么几类子力数量、行动力、位置价值、威胁结构。我习惯用线性加权eval w1 * 子力差 w2 * 行动力差 w3 * 位置分差权重初值可以参考这张表特征初值范围说明子力差1.0兜底项保证基本棋理行动力差0.3~0.5黑白棋早期很重要让程序别走死位置分差0.2~0.4用标准位置表角部权重高威胁结构0.5~1.0棋种特有如连续子、稳定子权重怎么定第一步人工给初值跑几局自对弈看趋势。第二步拿真实比赛日志做回归记录每个局面的特征值和最终胜负用梯度下降去拟合。大多数手工特征能覆盖的棋种这两步就够。别上来就调十来个特征特征越多过拟合越严重换个对手就翻车。评估函数还要保持平滑。不要在某个特征上设固定阈值导致分数跳变比如“连成四子就加 1000 分”这会让搜索树里相邻节点的分数剧烈波动剪枝质量直接下滑。我一般把子力权重固定在 1.0行动力 0.4位置表单独归一化这样每次调参都能快速定位是哪个特征出了问题。再补一个容易忽略的细节评估函数的值域要稳定。如果你用三个特征最好先分别归一化到接近的数量级再乘权重。否则其中一个特征天然就是几百的数值另一个只有零点几线性回归出来的权重会被大数特征主导小特征就白提了。我经常见到新手把“子力差”算成实际棋子数差最大能到 64而“行动力差”只有 -15~15结果搜索几乎只看子力其他特征形同虚设。3. 用 alpha-beta 框架搭一个最小博弈程序核心代码与参数说明3.1 局面表示与走法生成数组起步位棋盘是进阶方向竞赛程序追求速度通常用位棋盘但教学代码里二维数组更容易读。下面的黑白棋 Board 类用 0、1、-1 分别表示空、黑子、白子。用 -1 表示白子而不是 2是为了计算双方分数时可以直接做数值乘法。class Board: def __init__(self): self.board [[0] * 8 for _ in range(8)] self.board[3][3] -1 self.board[3][4] 1 self.board[4][3] 1 self.board[4][4] -1 self.current_player 1 # 黑先 def legal_moves(self, player): moves [] opp -player for r in range(8): for c in range(8): if self.board[r][c] ! 0: continue for dr, dc in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]: nr, nc r dr, c dc found_opp False while 0 nr 8 and 0 nc 8 and self.board[nr][nc] opp: nr dr nc dc found_opp True if found_opp and 0 nr 8 and 0 nc 8 and self.board[nr][nc] player: moves.append((r, c)) break return moves def apply_move(self, move, player): r, c move self.board[r][c] player opp -player for dr, dc in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]: nr, nc r dr, c dc flip [] while 0 nr 8 and 0 nc 8 and self.board[nr][nc] opp: flip.append((nr, nc)) nr dr nc dc if flip and 0 nr 8 and 0 nc 8 and self.board[nr][nc] player: for fr, fc in flip: self.board[fr][fc] player这段代码的核心是方向数组[(-1,-1), ... (1,1)]它保证了八个方向都能检测到“夹住”对方的子。legal_moves里遇到第一个能翻转的方向就break因为只要有一个方向合法这个位置就是合法落子点。apply_move先落子再沿八个方向收集中间要翻的子最后统一翻转。参数说明棋盘尺寸固定 8x8current_player需要在走法生成和搜索时保持一致。如果你换棋种要改的只有board的数据结构和两个方法搜索层不用动。这就是“用同一个搜索框架适配多个棋种”的最小结构。位棋盘是把每行、每列存成 64 位整数用位运算一次判断整条线速度能快好几倍建议在比赛前完成迁移。3.2 核心搜索带走法排序的 negamax 剪枝评估函数和搜索是绑在一起的。下面用 negamax 写 alpha-beta它把“我方最大化、对方最小化”统一成“每层取负最大”代码比分 alpha/beta 两个分支短很多。def evaluate(board): coin_diff sum(row.count(1) for row in board.board) - sum(row.count(-1) for row in board.board) mobility_diff len(board.legal_moves(1)) - len(board.legal_moves(-1)) return coin_diff * 1.0 mobility_diff * 0.4 def negamax(board, depth, alpha, beta, player): moves board.legal_moves(player) if depth 0: return evaluate(board) * player if not moves: if not board.legal_moves(-player): return evaluate(board) * player return -negamax(board, depth - 1, -beta, -alpha, -player) # 走法排序按位置表预估值排序好的在前 moves.sort(keylambda m: pos_score[m[0]][m[1]], reverseTrue) best -float(inf) for m in moves: new_board Board() new_board.board [row[:] for row in board.board] new_board.current_player board.current_player new_board.apply_move(m, player) val -negamax(new_board, depth - 1, -beta, -alpha, -player) if val best: best val if best alpha: alpha best if alpha beta: break return bestnegamax返回值对当前走棋方是“优势分数”乘上player后黑方取正白方取负。depth 0时直接返回评估分数不再展开叶子节点。not moves时先看对方有没有合法走法如果双方都无棋可下就是终局否则让对方继续走这里用递归调用来模拟“空着”。moves.sort用的pos_score是提前定义好的 8x8 位置表。排序不是可有可无它直接决定剪枝效率。参数上alpha 初始给-infbeta 给inf每层尝试收紧。new_board.board [row[:] for row in board.board]是浅拷贝二维列表因为在apply_move里只修改元素不会改变行引用所以足够安全。比赛版本一定要改成撤销机制或增量更新否则每次拷贝都会成为性能瓶颈。3.3 终局判定与胜负分数不要把评估函数当终局结果很多新手把评估函数直接用来判断谁赢这是错的。评估函数是给中间节点估算的终局必须按规则统计实际盘面。黑白棋的终局条件很简单双方都无合法走法。def is_terminal(board): return not board.legal_moves(1) and not board.legal_moves(-1) def final_score(board): black sum(row.count(1) for row in board.board) white sum(row.count(-1) for row in board.board) return black - whiteis_terminal在搜索递归里会频繁调用所以能早返回就早返回。final_score返回的是黑方减去白方的子数正数黑胜负数白胜。如果你想存到日志里看建议同时记录黑白子数而不是只记差值后面分析输棋原因时“怎么输”和“输多少”是两回事。如果棋种规则里有平局比如六子棋先成六连者胜、无平局但苏拉卡尔塔棋可能有重复局面判和搜索时就需要单独维护一个历史哈希表检测重复局面直接返回 0 分。这个坑在第五章会展开。3.4 时间控制迭代加深是比赛不掉链子的底线竞赛环境每步给的时间是秒级固定深度搜索很可能出问题深度设小了浪费时间深度设大了直接超时判负。迭代加深的做法是逐层加深每层完成后再想想是否继续。def search_root(board, depth): moves board.legal_moves(board.current_player) if not moves: return None best_move moves[0] best_score -float(inf) alpha -float(inf) beta float(inf) for m in moves: new_board Board() new_board.board [row[:] for row in board.board] new_board.current_player board.current_player new_board.apply_move(m, board.current_player) val -negamax(new_board, depth - 1, -beta, -alpha, -board.current_player) if val best_score: best_score val best_move m if best_score alpha: alpha best_score return best_move, best_score def iterative_deepening(board, max_depth, time_limit): import time start time.time() best_move None for depth in range(1, max_depth 1): move, score search_root(board, depth) best_move move used time.time() - start if used time_limit * 0.8: break return best_movesearch_root只展开根节点再调用 negamax。注意 root 也要做 alpha-beta 更新否则第一层走法之间的剪枝信息没有传递下去。iterative_deepening的time_limit * 0.8是一个经验阈值留出 20% 余量做协议通信、结果保存和异常处理。参数说明黑白棋中max_depth可以给 12time_limit按比赛平台给 3 秒。六子棋分支因子稍大建议max_depth给 10。如果你的程序在第 6 层已经用掉超过 80% 时间就停在 6 层返回结果而不是继续冲 7 层。要记住竞赛判负的条件是“超时”不是“层数太低”。4. 调参的五个关键环节深度、宽度、边界与开局库4.1 搜索深度与分支因子为什么深度加 1 不意味着时间翻倍所有调参都围绕一个公式展开节点总数 分支因子^深度。但加了 alpha-beta 后实际节点数不是这么算的它强烈依赖走法排序。排序好时alpha-beta 的节点量接近 O(b^(d/2))所以从 8 层升到 9 层时间可能只多 1.5 倍而不是 b 倍。排序差时时间会按 b 倍尺度恶化。所以第一步不是盲目加深度而是先把每层时间分布记下来。我通常给程序加一个统计数组time_per_depth[d]跑 20 盘自对弈后看各层耗时曲线。如果某层耗时从上一层的 2 倍直接跳到 8 倍说明走法排序没起到作用要先回头修排序而不是降深度。深度上限还要考虑棋种特性。象棋类残局阶段分支因子小可以多搜两层黑白棋中盘分支因子大到了残局阶段又可以加深。如果你做的是固定深度就会发现残局时大量时间被浪费。正确做法是让iterative_deepening的max_depth随合法走法数量动态调整走法少于 8 个时最大深度加 2。动态深度调整的边界条件是如果当前局面已经能确定为必胜或必败继续搜下去只会浪费时间。我习惯在进入迭代加深前先跑一遍快速终局检测如果某个走法能立刻触发终局就不需要进入搜索直接返回这个走法。这一招在黑白棋尾盘和六子棋成六局面里特别有用。4.2 走法排序贪心排序与杀手启发走法排序是 alpha-beta 的命脉。最简单的排序是根节点用位置表内部节点用上一步的“杀手走法”优先。杀手启发的意思是某个深度上有几步棋经常把对手的 beta 剪断那就在下次搜索到同一深度时先试它们。killer_moves {} def get_ordered_moves(moves, depth): if depth in killer_moves: killer killer_moves[depth] moves [m for m in moves if m ! killer] [m for m in moves if m killer] return moves def on_beta_cut(move, depth): killer_moves[depth] move参数说明killer_moves按深度索引每个深度只存一步棋。on_beta_cut在alpha beta时调用记录让剪枝发生的走法。这套机制在六子棋上效果明显因为威胁往往沿着同一类路线生成。贪心排序和杀手启发可以同时用先用位置表跑一遍把高分走法放前面搜索中再用杀手判定提前截断。注意杀手启发仅用一步别存一个列表否则排序开销会抵消收益。还有一种排序思路是“历史启发”把 beta 截断的走法在全局字典里累计次数每次排序时按次数降序。杀手启发是历史启发的一个简化版本。如果你发现走法排序已经做到位但深度仍然上不去可以检查评估函数的调用次数。评估函数每调用一次都要扫描整个棋盘很昂贵。可以把评估函数改成增量维护在apply_move时同步更新子力差和行动力差而不是每次重新算。4.3 评估函数权重从人工调优到离线参数拟合评估函数调参不要只靠感觉。常见做法是准备一小时内跑完的 100 盘自对弈日志每盘记录每个局面的特征向量和最终胜负然后用简单线性回归拟合。以黑白棋为例特征x1是子力差x2是行动力差x3是位置分差。最终的胜率函数可以假设为胜率 ≈ w1x1 w2x2 w3*x3我自己初值总是给w11.0, w20.4, w30.3然后跑 200 盘快速评估。如果程序总是在优势局面下崩盘检查是不是w1太大导致程序贪吃子而忽略位置如果程序总是“慢”下棋偏保守检查w3是否覆盖到角部邻格。离线拟合时有一个坑样本相关性太高。同一局棋里相邻局面高度相关直接回归出来的权重会偏向某几盘棋。解决办法是在每盘棋里只隔 4 步采样一次并且把胜负结果做平滑。这样拟合出的权重更稳定也不会过拟合到某条对局线路上。拟合之后一定要做交叉验证。把 100 盘日志拆成 80 盘训练、20 盘验证跑三次取平均。如果训练集上表现好、验证集上表现差说明权重记住了特定对手的风格而不是通用棋理。这时候要么减少特征数要么加大采样间隔。评估函数不是越复杂越好复杂到一定程度后每加一个特征都是在给过拟合添柴火。4.4 边界处理空着、平局与重复局面边界处理是搜索代码里最容易出隐蔽 bug 的地方。黑白棋有空着苏拉卡尔塔棋和爱恩斯坦棋有重复局面判和点格棋有“谁最后画线谁得分”的附属规则这些都是边界条件。处理空着时要避免无限递归。我的做法是在negamax里记录一个pass_count连续两次空着直接判终局。处理重复局面用一个 Zobrist 哈希表记录当前路径上的局面计数计数大于 1 按平局返回 0 分。注意这里只能查“当前路径”不能查“全局历史”因为全局历史里有些局面是搜索中途经过的不代表理论重复。边界参数还有一个容易被忽略的点合法走法为空不一定代表终局必须先验证对方是否也无棋可下。我曾经在这里翻过车把“无合法走法”直接判负结果遇到对方可以走的空着局面程序等于送了一手。如果你用的棋种有“将军”“威胁”“必应手”这类强制走法还要给搜索层加一个“强制应对”标记。例如中国象棋里被将军时必须先应将搜索时如果发现根节点未应对将军就将该走法直接滤掉。这个过滤要放在走法生成之后、排序之前否则会把非法走法带入 alpha-beta导致评估分数毫无意义。4.5 开局库与残局库把时间留给中局开局库不是必须但能显著提高胜率。做法很简单从往届对局或高水平程序的自对弈日志里提取前 6~12 步的棋谱保存成“局面哈希 - 走法”的映射。搜索到这些局面时直接返回库里的走法相当于把中局思考时间省下来给更复杂的局面。残局库实现成本高对多数棋种不推荐。但你可以做一个更轻量的“残局策略表”在残局阶段合法走法少于 5 个用简单的终局搜索替代评估函数。比如黑白棋残局阶段直接做全盘搜索因为剩余可下位置有限几步之内就能算到底。参数上max_depth可以提高到 18~20因为残局分支因子低。开局库要定期更新。如果总是输给某类开局就把那些开局从库里删掉或替换成变化。不要迷信“库越大越好”库太大占内存加载慢还容易在开局阶段被对手的冷门招法打乱阵脚。开局库的存储格式建议用文本文件每行一条走法序列加上最终胜率。这样你可以用脚本直接清洗数据删掉那些胜率低于 50% 的开局。千万不要把开局库和主程序编译在一起否则每次更新都要重新编译调试周期会被拉得很长。5. 计算机博弈大赛备赛避坑从崩溃、超时到玄学输棋5.1 崩溃递归栈溢出与未初始化的评估变量现象程序跑着跑着直接退出或报maximum recursion depth exceeded。比赛平台上没有友好报错往往只给一个“程序异常结束”。原因搜索深度设置过高递归调用时每一帧又携带了庞大对象更常见的是评估函数里引用了未初始化的数组在某个冷门局面下读取越界。解决把iterative_deepening的max_depth设一个保守值然后在递归函数里增加深度上限判断。所有查表操作先判边界棋盘 8x8 就保证索引在 0~7。还有一个习惯在每个函数入口做个assert board is not None当年排查越界时省了我一整天。另外要检查递归函数的局部变量大小。比赛平台的栈空间可能比本地小如果你在negamax里创建了整个Board对象作为参数每一层的栈开销会非常大。解决办法是把Board改成成员变量用撤销机制代替拷贝。我见过一个队伍把数组拷贝放在循环里结果深度一上 8 层就栈溢出改成撤销后轻松搜到 12 层。5.2 超时读秒机制下的时间分配错误现象程序在局面接近中盘时突然超时日志显示前几步只花了 0.2 秒后面某一步花掉了 2.8 秒。原因固定深度搜索在中盘分支因子突增时节点量远超预期。iterative_deepening如果每层都完整跑完才检查时间就会出现“这一层跑不完但又不能返回上一层结果”的尴尬。解决在negamax里也插入时间检查每递归一定层数就判断time.time() - start hard_limit超时立即抛异常或返回一个当前最优值。异常抛到 root 层时返回上一层的best_move。这就是把时间控制从“层间”下沉到“节点级”。建议把 hard_limit 设为比赛时限的 0.9留 0.1 给结果提交。这里有个容易被忽视的细节搜索超时不仅仅取决于深度还取决于评估函数是否被缓存。如果评估函数每次都重新扫描棋盘中盘大连环翻转时耗时就会飙升。我给黑白棋实现过增量评估在apply_move时只更新被翻转的那条线上的子力变化评估函数变成 O(1)。这个改动让同样深度下的耗时降了一半多。5.3 置换表失效Zobrist 哈希初始化与错误命中现象加置换表后程序变慢甚至偶发错误走法看起来像“玄学”。原因Zobrist 哈希表初始化时没有用固定随机种子导致同一局面的哈希值在每次启动程序后都不同。更严重的是置换表里存了只适用于 alpha-beta 某个窗口的结果直接在不同窗口下复用产生错误剪枝。解决用固定种子初始化随机数保证调试时可复现。置换表保存时记录三个字段哈希值、深度、bound 类型精确值/下界/上界。只有当前搜索深度小于等于缓存深度时才能复用bound 类型要对上。我在六子棋项目里遇到过 1000 步后棋力突然变弱最后发现是置换表覆盖策略太激进把深层精确值被浅层上界覆盖了。正确的覆盖策略是深度越深越要保留。注意 Zobrist 哈希并不是只用于置换表。它还被用来做开局库索引、重复局面检测、对局日志的 key。如果你在这些模块里用了同一个哈希函数但随机数种子不相同就会出现“开局库查不到局面”的诡异问题。我建议单独写一个init_zobrist(seed)函数所有模块共用同一组随机数避免状态漂移。5.4 协议解析对手非法走法、等待超时与走法格式现象对局中自己的程序一切正常但对手迟迟不发走法然后被裁判判超时。或者对手返回了非法走法自己的程序没有拒绝直接进入异常状态。原因比赛平台的对局协议里通常要等待对手指令、处理结束标记、校验走法格式。新手程序往往只处理了“标准成功路径”没做防御性解析。解决把所有外部输入都当不可信数据。收到走法后先验证坐标是否在棋盘内、该位置是否为空、走法是否在合法走法列表里。不合法就立刻报错退出而不是尝试修正。等待处理用超时循环每次循环检查截止时间避免死等。这样做还有个好处如果对手掉线你的程序能主动申请判胜而不是跟着一起卡死。协议解析另一个坑是符号格式有的平台用a1这种列行表示有的用1a还有的用纯数字索引。统一在程序入口做一次转换内部全部用(row, col)元组导出走法时再转成平台格式。永远不要在搜索代码里直接拼接协议字符串否则一旦协议调整就要全链路排查。5.5 迭代加深与开局库冲突浅层结果不稳定导致最后一步踩雷现象程序在开局库覆盖范围外第 1 层搜索返回一个看起来很合理的走法但到第 6 层时这个走法的排序突然掉到很后面最终又选回第 1 层的走法导致局面不如直接搜第 5 层的程序。原因迭代加深每一层都重新执行search_root如果某层的走法排序依赖前一层的杀手启发浅层搜出的“最优”走法其实只对浅层有效。中盘时评估函数对浅层深度不敏感就会频繁改选。解决默认保留上一层的best_move只有在当前层搜索分数明显高于上一层时才切换。这个“明显”可以用阈值控制例如当前层分数比上一层大 0.3 才切换到新走法。这个技巧能有效减少棋子来回抖动也避免在残局阶段因为下一层的分数噪声改变策略。如果你用了开局库还要保证开局库的回退逻辑正确当库里的走法导致搜索层立即超时时要能退回到迭代加深的结果。我见过一个程序开局库里存了过多冷门走法某一局恰好命中一个库中走法但该走法在残局阶段根本没法继续程序被逼入被动。回退逻辑其实很简单库走法只作为初始best_move一旦迭代加深在更深层找到了明显更优的走法就允许覆盖库结果。6. 把辅导资料用起来以对战日志驱动复习和模型迭代6.1 自对弈与样本记录把赢棋归因到具体搜索节点调参不能只靠主观感觉。我给每个参赛程序加一个日志输出每步记录当前局面哈希、选择走法、搜索深度、评估分数、搜索耗时。对完一局后这个日志能直接回答“为什么这步选了它”“为什么在优势时走出昏招”。{ step: 42, hash: 8f3a2c9b1e7d5a04, move: e6, depth: 8, score: 1.7, time_ms: 182 }注意hash字段我用的是 Zobrist 哈希它能把一个局面压缩成 64 位整数方便在两台机器上对比。如果某一盘棋在重放日志后出现了与现场不一致的走法先检查哈希是否冲突。Zobrist 冲突概率极低但不是零比赛前可以用一千个随机局面做碰撞测试。6.2 用残局测试集做回归验证每次改动前先跑一遍每次改评估函数权重或搜索排序前先把 20 个残局局面跑一遍记录胜负和分数。只要发现之前能赢的局面现在赢不了立即回滚。残局测试集可以从往届对局里截取也可以手工设置边界局面比如“只剩一个空位”“双方都无合法走法”这种极端情况。我自己带新手时有个习惯每次改代码之前先把当前版本标记为“baseline”跑完全部测试集记录每个局面的期望分数。改动后对照差异如果差异超过阈值就检查是不是引入回归。计算机博弈竞赛的进步不是靠一次大改而是靠这种可重复的小步迭代叠出来的。这个习惯救过我一次有一版评估函数改动让我的程序在自对弈里胜率提升了近 10%但残局测试集显示它会在“双活四”局面下选择退让。如果只看自对弈胜率这个 bug 会被带到赛场上。所以每一次“看起来更好的改动”都要用测试集兜底。希望帮到你——把搜索、评估、时间控制和回归验证连成一条线你的计算机博弈大赛备赛就不再是东一榔头西一棒子而是每一步都能看到自己程序的成长。本文还有配套的精品资源点击获取 计算机博弈竞赛备赛指南：从搜索算法到评估函数调优
简介这套计算机博弈竞赛辅导资料源自东北大学机器博弈研究室的教学课件面向参赛选手、相关课程学习者和博弈算法研究者系统梳理竞赛所需的基础理论与方法框架。PPT共1个文件压缩包约2.57MB内容集中、篇幅紧凑适合按模块快速查阅与备赛复习。课件重点覆盖计算机博弈的基本原理、方法学概述、典型棋类介绍、博弈软件的构成、棋局评估以及博弈树展开与分析等核心议题同时结合中国象棋、国际象棋、围棋、五子棋、六子棋及民间棋类案例讲解搜索算法、Alpha-Beta剪枝、启发式评估等关键技术帮助读者理解从棋局建模到博弈搜索的完整链路。资料也涉及机器博弈的方法学特点与学科关系对初学者构建认知框架、对竞赛选手梳理知识体系均有实用价值。目前已有326人学习适合作为计算机博弈课程辅导与竞赛备赛的参考材料。1. 计算机博弈竞赛辅导资料到底在教什么一个可复现的备赛闭环「计算机博弈竞赛辅导资料」不是给你一堆算法流程图就算完事。计算机博弈大赛每年都有很多学生队伍卡在同一个位置规则看懂了搜索算法也会背可程序一上赛场就超时、崩溃或者输给看起来更“傻”的对手。辅导资料真正该解决的是这条闭环——选棋种、写搜索、调评估、配时间控制、跑回归测试。这篇文章就按这条线讲一套大多数棋种都能套用的最小方案。准备参加全国大学生计算机博弈大赛的学生或者带新手入门做项目的老师都适合按这个章节顺序走。你不需要先刷完一整本人工智能导论先把后面的代码跑起来再逐步换成自己棋种的规则就会明白这类比赛拼的不是灵感而是能不能把搜索深度、评估函数和时间分配三件事同时做对的工程能力。2. 选型和理论先定棋种再选搜索算法与评估函数的理由2.1 棋种决定工作量为什么零和完备信息游戏最适合入门计算机博弈大赛的项目并不只有象棋、围棋。常见组别有亚马逊棋、六子棋、苏拉卡尔塔棋、爱恩斯坦棋、点格棋和黑白棋规则复杂度差异很大。我的建议是第一次参赛优先选规则简单、分支因子适中、胜负判定明确的棋种。零和完备信息游戏天然适合用搜索树建模——没有隐藏信息没有随机性每一步都可以推演到底。用一张表快速对比几个热门棋种棋种规则实现成本平均分支因子评估函数难度新手友好度黑白棋低8~15中高六子棋中20~40中中苏拉卡尔塔棋中20~30高中亚马逊棋高60~120高低规则实现成本决定起步速度。亚马逊棋虽然策略很深但“放置障碍块”这一动作会让走法生成逻辑多出一大截六子棋每轮落两子分支因子直接翻倍黑白棋的合法走法生成和落子翻转逻辑一个下午就能写完。所以我后面的演示代码用黑白棋你实际参赛时再把局面生成部分换掉就行。这里要泼一盆冷水选错棋种的代价比算法不会写更大。我见过有队伍整个备赛期都在跟规则细节搏斗直到开赛前一周才开始调搜索最后程序能走棋但深度只有两层。计算机博弈大赛比的是程序之间的对抗不是规则翻译能力把棋种选到自己的可完成范围内才算把辅导资料用对了一半。拿到一个棋种的官方规则文档后不要急着写代码。先把三件事圈出来合法走法的完整定义、终局判定条件、时间与步数限制。这三件事决定了你的数据结构、搜索终止条件和时间控制模块怎么写。很多队伍翻车不是因为算法不懂而是规则文档里的“重复局面判和”和“连续空着判负”这类小字没看到。2.2 搜索算法选型minimax、alpha-beta 与 MCTS 的适用边界先厘清几个概念minimax 是理论alpha-beta 是 minimax 的加速实现MCTS 是另一条路。竞赛中最常用的组合是 alpha-beta 加置换表MCTS 只在评估函数极难写、或者分支因子极大的棋种里才体现出优势。算法核心思想适合场景主要代价minimax双方轮流转置最大/最小收益深度小、教学验证节点数爆炸alpha-beta剪掉不影响根节点结果的子树分支因子 10~40 的棋种很吃走法排序MCTS多次模拟采样按胜率选点评估函数难写、分支因子极大模拟次数要够代码调试难为什么优先选 alpha-beta竞赛读秒通常给到每步 1~3 秒这个时间内 alpha-beta 配合走法排序和置换表能稳定搜到 6~10 层。MCTS 需要大量模拟才能稳定如果落子前只能做几千次模拟质量反而波动很大。对黑白棋、六子棋、亚马逊棋这类评估特征清晰的棋种alpha-beta 是性价比最高的方案。选型时一定要看两个参数分支因子 b 和搜索深度 d。朴素 minimax 的节点量是 O(b^d)alpha-beta 最差也是 O(b^d)但最佳情况下能降到 O(b^(d/2))。这意味着如果走法排序做得好同样时间可以多搜接近一倍的深度。反过来如果走法排序没做alpha-beta 可能退化成 minimax这时候换 MCTS 也不会更好因为问题出在代码上不是算法上。MCTS 不是不能用而是它需要你额外维护一棵策略树和一个 UCT 公式。UCT 的核心是置信区间上界表达式是胜率 C * sqrt(ln(N) / n)其中 N 是父节点访问次数n 是当前子节点访问次数。C 值通常取 0.2~1.0调起来很玄学。如果你的棋种评估函数已经能给出比较靠谱的分数我建议你别折腾 MCTS把精力放在搜索排序和置换表上收益更直接。2.3 评估函数是黑匣子特征怎么提权重怎么定评估函数把局面好坏映射成一个数值数值越大对己方越有利。对新手来说最稳的写法是组合多个可解释特征而不是一上来搞神经网络。常用特征就这么几类子力数量、行动力、位置价值、威胁结构。我习惯用线性加权eval w1 * 子力差 w2 * 行动力差 w3 * 位置分差权重初值可以参考这张表特征初值范围说明子力差1.0兜底项保证基本棋理行动力差0.3~0.5黑白棋早期很重要让程序别走死位置分差0.2~0.4用标准位置表角部权重高威胁结构0.5~1.0棋种特有如连续子、稳定子权重怎么定第一步人工给初值跑几局自对弈看趋势。第二步拿真实比赛日志做回归记录每个局面的特征值和最终胜负用梯度下降去拟合。大多数手工特征能覆盖的棋种这两步就够。别上来就调十来个特征特征越多过拟合越严重换个对手就翻车。评估函数还要保持平滑。不要在某个特征上设固定阈值导致分数跳变比如“连成四子就加 1000 分”这会让搜索树里相邻节点的分数剧烈波动剪枝质量直接下滑。我一般把子力权重固定在 1.0行动力 0.4位置表单独归一化这样每次调参都能快速定位是哪个特征出了问题。再补一个容易忽略的细节评估函数的值域要稳定。如果你用三个特征最好先分别归一化到接近的数量级再乘权重。否则其中一个特征天然就是几百的数值另一个只有零点几线性回归出来的权重会被大数特征主导小特征就白提了。我经常见到新手把“子力差”算成实际棋子数差最大能到 64而“行动力差”只有 -15~15结果搜索几乎只看子力其他特征形同虚设。3. 用 alpha-beta 框架搭一个最小博弈程序核心代码与参数说明3.1 局面表示与走法生成数组起步位棋盘是进阶方向竞赛程序追求速度通常用位棋盘但教学代码里二维数组更容易读。下面的黑白棋 Board 类用 0、1、-1 分别表示空、黑子、白子。用 -1 表示白子而不是 2是为了计算双方分数时可以直接做数值乘法。class Board: def __init__(self): self.board [[0] * 8 for _ in range(8)] self.board[3][3] -1 self.board[3][4] 1 self.board[4][3] 1 self.board[4][4] -1 self.current_player 1 # 黑先 def legal_moves(self, player): moves [] opp -player for r in range(8): for c in range(8): if self.board[r][c] ! 0: continue for dr, dc in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]: nr, nc r dr, c dc found_opp False while 0 nr 8 and 0 nc 8 and self.board[nr][nc] opp: nr dr nc dc found_opp True if found_opp and 0 nr 8 and 0 nc 8 and self.board[nr][nc] player: moves.append((r, c)) break return moves def apply_move(self, move, player): r, c move self.board[r][c] player opp -player for dr, dc in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]: nr, nc r dr, c dc flip [] while 0 nr 8 and 0 nc 8 and self.board[nr][nc] opp: flip.append((nr, nc)) nr dr nc dc if flip and 0 nr 8 and 0 nc 8 and self.board[nr][nc] player: for fr, fc in flip: self.board[fr][fc] player这段代码的核心是方向数组[(-1,-1), ... (1,1)]它保证了八个方向都能检测到“夹住”对方的子。legal_moves里遇到第一个能翻转的方向就break因为只要有一个方向合法这个位置就是合法落子点。apply_move先落子再沿八个方向收集中间要翻的子最后统一翻转。参数说明棋盘尺寸固定 8x8current_player需要在走法生成和搜索时保持一致。如果你换棋种要改的只有board的数据结构和两个方法搜索层不用动。这就是“用同一个搜索框架适配多个棋种”的最小结构。位棋盘是把每行、每列存成 64 位整数用位运算一次判断整条线速度能快好几倍建议在比赛前完成迁移。3.2 核心搜索带走法排序的 negamax 剪枝评估函数和搜索是绑在一起的。下面用 negamax 写 alpha-beta它把“我方最大化、对方最小化”统一成“每层取负最大”代码比分 alpha/beta 两个分支短很多。def evaluate(board): coin_diff sum(row.count(1) for row in board.board) - sum(row.count(-1) for row in board.board) mobility_diff len(board.legal_moves(1)) - len(board.legal_moves(-1)) return coin_diff * 1.0 mobility_diff * 0.4 def negamax(board, depth, alpha, beta, player): moves board.legal_moves(player) if depth 0: return evaluate(board) * player if not moves: if not board.legal_moves(-player): return evaluate(board) * player return -negamax(board, depth - 1, -beta, -alpha, -player) # 走法排序按位置表预估值排序好的在前 moves.sort(keylambda m: pos_score[m[0]][m[1]], reverseTrue) best -float(inf) for m in moves: new_board Board() new_board.board [row[:] for row in board.board] new_board.current_player board.current_player new_board.apply_move(m, player) val -negamax(new_board, depth - 1, -beta, -alpha, -player) if val best: best val if best alpha: alpha best if alpha beta: break return bestnegamax返回值对当前走棋方是“优势分数”乘上player后黑方取正白方取负。depth 0时直接返回评估分数不再展开叶子节点。not moves时先看对方有没有合法走法如果双方都无棋可下就是终局否则让对方继续走这里用递归调用来模拟“空着”。moves.sort用的pos_score是提前定义好的 8x8 位置表。排序不是可有可无它直接决定剪枝效率。参数上alpha 初始给-infbeta 给inf每层尝试收紧。new_board.board [row[:] for row in board.board]是浅拷贝二维列表因为在apply_move里只修改元素不会改变行引用所以足够安全。比赛版本一定要改成撤销机制或增量更新否则每次拷贝都会成为性能瓶颈。3.3 终局判定与胜负分数不要把评估函数当终局结果很多新手把评估函数直接用来判断谁赢这是错的。评估函数是给中间节点估算的终局必须按规则统计实际盘面。黑白棋的终局条件很简单双方都无合法走法。def is_terminal(board): return not board.legal_moves(1) and not board.legal_moves(-1) def final_score(board): black sum(row.count(1) for row in board.board) white sum(row.count(-1) for row in board.board) return black - whiteis_terminal在搜索递归里会频繁调用所以能早返回就早返回。final_score返回的是黑方减去白方的子数正数黑胜负数白胜。如果你想存到日志里看建议同时记录黑白子数而不是只记差值后面分析输棋原因时“怎么输”和“输多少”是两回事。如果棋种规则里有平局比如六子棋先成六连者胜、无平局但苏拉卡尔塔棋可能有重复局面判和搜索时就需要单独维护一个历史哈希表检测重复局面直接返回 0 分。这个坑在第五章会展开。3.4 时间控制迭代加深是比赛不掉链子的底线竞赛环境每步给的时间是秒级固定深度搜索很可能出问题深度设小了浪费时间深度设大了直接超时判负。迭代加深的做法是逐层加深每层完成后再想想是否继续。def search_root(board, depth): moves board.legal_moves(board.current_player) if not moves: return None best_move moves[0] best_score -float(inf) alpha -float(inf) beta float(inf) for m in moves: new_board Board() new_board.board [row[:] for row in board.board] new_board.current_player board.current_player new_board.apply_move(m, board.current_player) val -negamax(new_board, depth - 1, -beta, -alpha, -board.current_player) if val best_score: best_score val best_move m if best_score alpha: alpha best_score return best_move, best_score def iterative_deepening(board, max_depth, time_limit): import time start time.time() best_move None for depth in range(1, max_depth 1): move, score search_root(board, depth) best_move move used time.time() - start if used time_limit * 0.8: break return best_movesearch_root只展开根节点再调用 negamax。注意 root 也要做 alpha-beta 更新否则第一层走法之间的剪枝信息没有传递下去。iterative_deepening的time_limit * 0.8是一个经验阈值留出 20% 余量做协议通信、结果保存和异常处理。参数说明黑白棋中max_depth可以给 12time_limit按比赛平台给 3 秒。六子棋分支因子稍大建议max_depth给 10。如果你的程序在第 6 层已经用掉超过 80% 时间就停在 6 层返回结果而不是继续冲 7 层。要记住竞赛判负的条件是“超时”不是“层数太低”。4. 调参的五个关键环节深度、宽度、边界与开局库4.1 搜索深度与分支因子为什么深度加 1 不意味着时间翻倍所有调参都围绕一个公式展开节点总数 分支因子^深度。但加了 alpha-beta 后实际节点数不是这么算的它强烈依赖走法排序。排序好时alpha-beta 的节点量接近 O(b^(d/2))所以从 8 层升到 9 层时间可能只多 1.5 倍而不是 b 倍。排序差时时间会按 b 倍尺度恶化。所以第一步不是盲目加深度而是先把每层时间分布记下来。我通常给程序加一个统计数组time_per_depth[d]跑 20 盘自对弈后看各层耗时曲线。如果某层耗时从上一层的 2 倍直接跳到 8 倍说明走法排序没起到作用要先回头修排序而不是降深度。深度上限还要考虑棋种特性。象棋类残局阶段分支因子小可以多搜两层黑白棋中盘分支因子大到了残局阶段又可以加深。如果你做的是固定深度就会发现残局时大量时间被浪费。正确做法是让iterative_deepening的max_depth随合法走法数量动态调整走法少于 8 个时最大深度加 2。动态深度调整的边界条件是如果当前局面已经能确定为必胜或必败继续搜下去只会浪费时间。我习惯在进入迭代加深前先跑一遍快速终局检测如果某个走法能立刻触发终局就不需要进入搜索直接返回这个走法。这一招在黑白棋尾盘和六子棋成六局面里特别有用。4.2 走法排序贪心排序与杀手启发走法排序是 alpha-beta 的命脉。最简单的排序是根节点用位置表内部节点用上一步的“杀手走法”优先。杀手启发的意思是某个深度上有几步棋经常把对手的 beta 剪断那就在下次搜索到同一深度时先试它们。killer_moves {} def get_ordered_moves(moves, depth): if depth in killer_moves: killer killer_moves[depth] moves [m for m in moves if m ! killer] [m for m in moves if m killer] return moves def on_beta_cut(move, depth): killer_moves[depth] move参数说明killer_moves按深度索引每个深度只存一步棋。on_beta_cut在alpha beta时调用记录让剪枝发生的走法。这套机制在六子棋上效果明显因为威胁往往沿着同一类路线生成。贪心排序和杀手启发可以同时用先用位置表跑一遍把高分走法放前面搜索中再用杀手判定提前截断。注意杀手启发仅用一步别存一个列表否则排序开销会抵消收益。还有一种排序思路是“历史启发”把 beta 截断的走法在全局字典里累计次数每次排序时按次数降序。杀手启发是历史启发的一个简化版本。如果你发现走法排序已经做到位但深度仍然上不去可以检查评估函数的调用次数。评估函数每调用一次都要扫描整个棋盘很昂贵。可以把评估函数改成增量维护在apply_move时同步更新子力差和行动力差而不是每次重新算。4.3 评估函数权重从人工调优到离线参数拟合评估函数调参不要只靠感觉。常见做法是准备一小时内跑完的 100 盘自对弈日志每盘记录每个局面的特征向量和最终胜负然后用简单线性回归拟合。以黑白棋为例特征x1是子力差x2是行动力差x3是位置分差。最终的胜率函数可以假设为胜率 ≈ w1x1 w2x2 w3*x3我自己初值总是给w11.0, w20.4, w30.3然后跑 200 盘快速评估。如果程序总是在优势局面下崩盘检查是不是w1太大导致程序贪吃子而忽略位置如果程序总是“慢”下棋偏保守检查w3是否覆盖到角部邻格。离线拟合时有一个坑样本相关性太高。同一局棋里相邻局面高度相关直接回归出来的权重会偏向某几盘棋。解决办法是在每盘棋里只隔 4 步采样一次并且把胜负结果做平滑。这样拟合出的权重更稳定也不会过拟合到某条对局线路上。拟合之后一定要做交叉验证。把 100 盘日志拆成 80 盘训练、20 盘验证跑三次取平均。如果训练集上表现好、验证集上表现差说明权重记住了特定对手的风格而不是通用棋理。这时候要么减少特征数要么加大采样间隔。评估函数不是越复杂越好复杂到一定程度后每加一个特征都是在给过拟合添柴火。4.4 边界处理空着、平局与重复局面边界处理是搜索代码里最容易出隐蔽 bug 的地方。黑白棋有空着苏拉卡尔塔棋和爱恩斯坦棋有重复局面判和点格棋有“谁最后画线谁得分”的附属规则这些都是边界条件。处理空着时要避免无限递归。我的做法是在negamax里记录一个pass_count连续两次空着直接判终局。处理重复局面用一个 Zobrist 哈希表记录当前路径上的局面计数计数大于 1 按平局返回 0 分。注意这里只能查“当前路径”不能查“全局历史”因为全局历史里有些局面是搜索中途经过的不代表理论重复。边界参数还有一个容易被忽略的点合法走法为空不一定代表终局必须先验证对方是否也无棋可下。我曾经在这里翻过车把“无合法走法”直接判负结果遇到对方可以走的空着局面程序等于送了一手。如果你用的棋种有“将军”“威胁”“必应手”这类强制走法还要给搜索层加一个“强制应对”标记。例如中国象棋里被将军时必须先应将搜索时如果发现根节点未应对将军就将该走法直接滤掉。这个过滤要放在走法生成之后、排序之前否则会把非法走法带入 alpha-beta导致评估分数毫无意义。4.5 开局库与残局库把时间留给中局开局库不是必须但能显著提高胜率。做法很简单从往届对局或高水平程序的自对弈日志里提取前 6~12 步的棋谱保存成“局面哈希 - 走法”的映射。搜索到这些局面时直接返回库里的走法相当于把中局思考时间省下来给更复杂的局面。残局库实现成本高对多数棋种不推荐。但你可以做一个更轻量的“残局策略表”在残局阶段合法走法少于 5 个用简单的终局搜索替代评估函数。比如黑白棋残局阶段直接做全盘搜索因为剩余可下位置有限几步之内就能算到底。参数上max_depth可以提高到 18~20因为残局分支因子低。开局库要定期更新。如果总是输给某类开局就把那些开局从库里删掉或替换成变化。不要迷信“库越大越好”库太大占内存加载慢还容易在开局阶段被对手的冷门招法打乱阵脚。开局库的存储格式建议用文本文件每行一条走法序列加上最终胜率。这样你可以用脚本直接清洗数据删掉那些胜率低于 50% 的开局。千万不要把开局库和主程序编译在一起否则每次更新都要重新编译调试周期会被拉得很长。5. 计算机博弈大赛备赛避坑从崩溃、超时到玄学输棋5.1 崩溃递归栈溢出与未初始化的评估变量现象程序跑着跑着直接退出或报maximum recursion depth exceeded。比赛平台上没有友好报错往往只给一个“程序异常结束”。原因搜索深度设置过高递归调用时每一帧又携带了庞大对象更常见的是评估函数里引用了未初始化的数组在某个冷门局面下读取越界。解决把iterative_deepening的max_depth设一个保守值然后在递归函数里增加深度上限判断。所有查表操作先判边界棋盘 8x8 就保证索引在 0~7。还有一个习惯在每个函数入口做个assert board is not None当年排查越界时省了我一整天。另外要检查递归函数的局部变量大小。比赛平台的栈空间可能比本地小如果你在negamax里创建了整个Board对象作为参数每一层的栈开销会非常大。解决办法是把Board改成成员变量用撤销机制代替拷贝。我见过一个队伍把数组拷贝放在循环里结果深度一上 8 层就栈溢出改成撤销后轻松搜到 12 层。5.2 超时读秒机制下的时间分配错误现象程序在局面接近中盘时突然超时日志显示前几步只花了 0.2 秒后面某一步花掉了 2.8 秒。原因固定深度搜索在中盘分支因子突增时节点量远超预期。iterative_deepening如果每层都完整跑完才检查时间就会出现“这一层跑不完但又不能返回上一层结果”的尴尬。解决在negamax里也插入时间检查每递归一定层数就判断time.time() - start hard_limit超时立即抛异常或返回一个当前最优值。异常抛到 root 层时返回上一层的best_move。这就是把时间控制从“层间”下沉到“节点级”。建议把 hard_limit 设为比赛时限的 0.9留 0.1 给结果提交。这里有个容易被忽视的细节搜索超时不仅仅取决于深度还取决于评估函数是否被缓存。如果评估函数每次都重新扫描棋盘中盘大连环翻转时耗时就会飙升。我给黑白棋实现过增量评估在apply_move时只更新被翻转的那条线上的子力变化评估函数变成 O(1)。这个改动让同样深度下的耗时降了一半多。5.3 置换表失效Zobrist 哈希初始化与错误命中现象加置换表后程序变慢甚至偶发错误走法看起来像“玄学”。原因Zobrist 哈希表初始化时没有用固定随机种子导致同一局面的哈希值在每次启动程序后都不同。更严重的是置换表里存了只适用于 alpha-beta 某个窗口的结果直接在不同窗口下复用产生错误剪枝。解决用固定种子初始化随机数保证调试时可复现。置换表保存时记录三个字段哈希值、深度、bound 类型精确值/下界/上界。只有当前搜索深度小于等于缓存深度时才能复用bound 类型要对上。我在六子棋项目里遇到过 1000 步后棋力突然变弱最后发现是置换表覆盖策略太激进把深层精确值被浅层上界覆盖了。正确的覆盖策略是深度越深越要保留。注意 Zobrist 哈希并不是只用于置换表。它还被用来做开局库索引、重复局面检测、对局日志的 key。如果你在这些模块里用了同一个哈希函数但随机数种子不相同就会出现“开局库查不到局面”的诡异问题。我建议单独写一个init_zobrist(seed)函数所有模块共用同一组随机数避免状态漂移。5.4 协议解析对手非法走法、等待超时与走法格式现象对局中自己的程序一切正常但对手迟迟不发走法然后被裁判判超时。或者对手返回了非法走法自己的程序没有拒绝直接进入异常状态。原因比赛平台的对局协议里通常要等待对手指令、处理结束标记、校验走法格式。新手程序往往只处理了“标准成功路径”没做防御性解析。解决把所有外部输入都当不可信数据。收到走法后先验证坐标是否在棋盘内、该位置是否为空、走法是否在合法走法列表里。不合法就立刻报错退出而不是尝试修正。等待处理用超时循环每次循环检查截止时间避免死等。这样做还有个好处如果对手掉线你的程序能主动申请判胜而不是跟着一起卡死。协议解析另一个坑是符号格式有的平台用a1这种列行表示有的用1a还有的用纯数字索引。统一在程序入口做一次转换内部全部用(row, col)元组导出走法时再转成平台格式。永远不要在搜索代码里直接拼接协议字符串否则一旦协议调整就要全链路排查。5.5 迭代加深与开局库冲突浅层结果不稳定导致最后一步踩雷现象程序在开局库覆盖范围外第 1 层搜索返回一个看起来很合理的走法但到第 6 层时这个走法的排序突然掉到很后面最终又选回第 1 层的走法导致局面不如直接搜第 5 层的程序。原因迭代加深每一层都重新执行search_root如果某层的走法排序依赖前一层的杀手启发浅层搜出的“最优”走法其实只对浅层有效。中盘时评估函数对浅层深度不敏感就会频繁改选。解决默认保留上一层的best_move只有在当前层搜索分数明显高于上一层时才切换。这个“明显”可以用阈值控制例如当前层分数比上一层大 0.3 才切换到新走法。这个技巧能有效减少棋子来回抖动也避免在残局阶段因为下一层的分数噪声改变策略。如果你用了开局库还要保证开局库的回退逻辑正确当库里的走法导致搜索层立即超时时要能退回到迭代加深的结果。我见过一个程序开局库里存了过多冷门走法某一局恰好命中一个库中走法但该走法在残局阶段根本没法继续程序被逼入被动。回退逻辑其实很简单库走法只作为初始best_move一旦迭代加深在更深层找到了明显更优的走法就允许覆盖库结果。6. 把辅导资料用起来以对战日志驱动复习和模型迭代6.1 自对弈与样本记录把赢棋归因到具体搜索节点调参不能只靠主观感觉。我给每个参赛程序加一个日志输出每步记录当前局面哈希、选择走法、搜索深度、评估分数、搜索耗时。对完一局后这个日志能直接回答“为什么这步选了它”“为什么在优势时走出昏招”。{ step: 42, hash: 8f3a2c9b1e7d5a04, move: e6, depth: 8, score: 1.7, time_ms: 182 }注意hash字段我用的是 Zobrist 哈希它能把一个局面压缩成 64 位整数方便在两台机器上对比。如果某一盘棋在重放日志后出现了与现场不一致的走法先检查哈希是否冲突。Zobrist 冲突概率极低但不是零比赛前可以用一千个随机局面做碰撞测试。6.2 用残局测试集做回归验证每次改动前先跑一遍每次改评估函数权重或搜索排序前先把 20 个残局局面跑一遍记录胜负和分数。只要发现之前能赢的局面现在赢不了立即回滚。残局测试集可以从往届对局里截取也可以手工设置边界局面比如“只剩一个空位”“双方都无合法走法”这种极端情况。我自己带新手时有个习惯每次改代码之前先把当前版本标记为“baseline”跑完全部测试集记录每个局面的期望分数。改动后对照差异如果差异超过阈值就检查是不是引入回归。计算机博弈竞赛的进步不是靠一次大改而是靠这种可重复的小步迭代叠出来的。这个习惯救过我一次有一版评估函数改动让我的程序在自对弈里胜率提升了近 10%但残局测试集显示它会在“双活四”局面下选择退让。如果只看自对弈胜率这个 bug 会被带到赛场上。所以每一次“看起来更好的改动”都要用测试集兜底。希望帮到你——把搜索、评估、时间控制和回归验证连成一条线你的计算机博弈大赛备赛就不再是东一榔头西一棒子而是每一步都能看到自己程序的成长。本文还有配套的精品资源点击获取