简介计算机博弈竞赛辅导资料是一套面向竞赛选手、高校学生及机器博弈入门研究者的PPT讲义用于系统建立从棋类规则到博弈树搜索、评估与软件实现的知识框架。内容以东北大学机器博弈研究室的教学讲义为蓝本依次涵盖棋类介绍与分类、计算机博弈基本原理、方法学概述、博弈软件构成、棋局评估、博弈树展开与分析等模块并具体讲解中国象棋、国际象棋、围棋、五子棋、六子棋及一字棋、二虎棋、点格棋等典型棋种便于对照规则理解搜索算法与评估策略。包内为单个PPT文件大小约2.57MB结构紧凑适合在竞赛辅导、课程教学或自学复习时直接作为提纲使用。目前已有326人学习下载适合需要快速梳理机器博弈知识脉络的备赛者。1. 计算机博弈竞赛辅导资料先选赛项再谈算法第一次带学生报名计算机博弈大赛时我手里的计算机博弈竞赛辅导资料比谁都厚光规则文档就打印了两百页。准备到第二周才发现资料的用法不是从头读到尾而是按赛项倒着看先定你要下哪种棋再挑出搜索、评估、时间控制三块能直接落地的章节。计算机博弈这个方向备赛环环相扣赛项决定评估函数怎么设计评估函数决定搜索深度够不够用搜索深度决定你对时间控制的把握而时间控制直接决定线上平台会不会判你超时。这篇内容就按这条路线来先从一堆赛项里选出投入产出比最高的那个再搭一个最小可跑的搜索引擎把调参和线上判负的坑一次说清。适合正在备赛的学生也适合刚接手竞赛指导、想在第一年少走弯路的老师。2. 计算机博弈选哪个赛项评估函数深度不齐备赛体量差三倍2.1 博弈项目的四种类型完备信息、运气成分、并行性与状态空间计算机博弈大赛不是“棋类人工智能比赛”这么简单。打开赛项列表项目横跨好几类有五子棋、中国象棋这样的完备信息棋类有亚马逊棋、苏拉卡尔塔棋这样的两人序贯博弈也有包含随机发牌和隐藏信息的牌类项目。我的习惯是先把它们按四个维度分类再对着自己的备赛周期做减法。类型信息是否完备是否有随机性状态空间量级备赛体量简化棋类五子棋、六子棋完备无10^15 以下低两人序贯博弈亚马逊棋等完备无10^28 左右中棋类中国象棋、国际象棋完备无10^46 左右中高牌类斗地主等不完备有组合爆炸高备赛体量差异巨大核心在于评估函数是否容易“读局面”。牌类项目因为看不到对手手牌需要做蒙特卡洛采样和对手建模备赛二十天很难稳定。而五子棋的评估函数几乎是一张白纸连子数、活三、冲四都是可以直接手工量化的特征。这里没有“高级项目更值得做”的说法只有“辅导资料能不能在四到六周里变成可跑引擎”的现实。状态空间量级直接决定搜索深度瓶颈。以五子棋为例15×15 棋盘合法空位在开局阶段有 200 个以上但通过邻位裁剪和走法排序Alpha-Beta 搜索可以稳定下到 8 到 10 层中国象棋在同样配置下通常只能到 6 层左右因为平均分支数更高局面评估还得考虑子力、位置、威胁三个维度。辅导资料里讲搜索算法不会告诉你不同项目对深度的“及格线”完全不同选赛项时就必须先知道这一点。2.2 按“搜索能见度”选赛项为什么新手优先选五子棋或亚马逊棋“搜索能见度”是我自己常用的判断口径给定一个局面程序员能不能用不超过十个手工特征近似解释“这个局面哪边好”。搜索能见度越高评估函数越容易设计搜索引擎就能越早接手。五子棋的搜索能见度极高。活二、活三、冲四、连五每个棋手都能说出判断依据把它们翻译成代码只需扫描四个方向、统计连续子长度。我一般建议新手队伍优先选五子棋两周就能把搜索、评估、时间控制整个闭环跑通剩下一半以上精力可以投入到权重调优和开局库上。其次是亚马逊棋规则里带“放障碍”这一步复杂度适中但评估函数更容易走向“控制力评估”需要同时看皇后行动自由度和障碍区的连通性难度比五子棋高半档。围棋这类项目搜索能见度低评估函数不是线性组合能概括的多见于高水平队伍。为什么说赛项选择决定备赛成败我们队连续两年做不同项目第一年选了需要蒙特卡洛的牌类规则读了两周AI 行为仍然很不稳定第二年换五子棋一周出能吃子的引擎三周出能赢人的版本。赛项不同辅导资料的用法完全不同前者需要把大量时间花在随机模拟的方差控制上后者只需要盯住评估权重和搜索效率两个点。2.3 辅导资料怎么组织把规则文档读成状态机而不是背下来很多队伍拿到资料先打印规则然后开会通读这是最大的浪费。我建议把每一份规则文档转成一张“状态机确认表”让代码去替人记住规则。表格至少包含五列规则条目、对应代码函数、边界条件、测试用例、是否已通过。比如五子棋的禁手规则不要只写“黑棋三三禁手”要具体到“坐标为 (7,7) 的黑棋同时形成两个活三必须在走法生成器中判非法”。把这样一条一条拆完资料里最有价值的部分变成代码仓库的测试用例而不是一个只能靠人脑记忆的 PDF。常见做法是每周安排一次“规则走查”让写走法生成器的队员对着棋规逐条过测试用例而不是让所有人背规则。这样一周后资料内化进代码里剩下的时间都留给算法调优。资料归档也可以按这个思路组织rules/ 放棋规和拆解表格code/ 放走法生成、评估、搜索三块源码tests/ 放规则测试用例opens/ 放过往对局和开局统计logs/ 放每次调参的胜率记录。辅导资料不该是一摞打印件它应该长在代码仓库里每次提交都对应一次可验证的规则确认或胜负变化。3. 用Alpha-Beta搜索搭一个最小可跑引擎从走法产生到评估函数3.1 走法生成与棋盘表示先定数据结构再谈速度竞赛 AI 的骨架是“走法生成 评估 搜索”。三者里最先写的应该是走法生成器因为搜索和评估都得基于合法的走法列表工作。我一般用数组表示棋盘不用位棋盘。位棋盘虽然在象棋里性能更高但五子棋这种 15×15 的棋盘数组的访问开销可以忽略代码可读性却好很多。下面这个结构就是五子棋的走法生成器#include vector using Board std::vectorstd::vectorint; // 0空1黑2白 std::vectorstd::pairint,int GenerateMoves(const Board b, int radius) { std::vectorstd::pairint,int moves; int N (int)b.size(); // 只在已有棋子周围radius格内生成候选大幅缩小搜索分支 for (int r 0; r N; r) { for (int c 0; c N; c) { if (b[r][c] ! 0) continue; bool near false; for (int dr -radius; dr radius !near; dr) { for (int dc -radius; dc radius !near; dc) { if (dr 0 dc 0) continue; int nr r dr, nc c dc; if (nr 0 nr N nc 0 nc N b[nr][nc] ! 0) { near true; } } } if (near) moves.emplace_back(r, c); } } return moves; }这段代码把候选落点限制在已有棋子周围 radius 格内。我一般开局设 2中盘设 1 或 2残局设 2。radius 太大则搜索分支数暴涨太小则容易漏掉关键落点比如对手已经成四时你必须在贴身位置堵radius1 就可能漏掉边角应对。注意这里没做去重或排序走法排序放到 3.3 里处理生成器只负责“不重不漏地给出合法候选”。3.2 评估函数怎么设计手工特征比神经网络更稳评估函数是辅导资料里最不能照抄的部分。神经网络在别处很热但在竞赛的有限算力和时间下手工特征更稳。下面是一个五子棋“连子模式计数”评估函数扫描所有方向的连续子序列并打分int EvaluateLines(const Board b, int player) { int score 0; int N (int)b.size(); int dirs[4][2] {{1,0},{0,1},{1,1},{1,-1}}; for (int r 0; r N; r) for (int c 0; c N; c) { if (b[r][c] ! player) continue; for (auto d : dirs) { int len 1, block 0; int nr r d[0], nc c d[1]; // 向正方向延伸 while (nr 0 nr N nc 0 nc N b[nr][nc] player) { len; nr d[0]; nc d[1]; } if (nr 0 || nr N || nc 0 || nc N) block; else if (b[nr][nc] ! 0) block; // 向反方向延伸 nr r - d[0]; nc c - d[1]; while (nr 0 nr N nc 0 nc N b[nr][nc] player) { len; nr - d[0]; nc - d[1]; } if (nr 0 || nr N || nc 0 || nc N) block; else if (b[nr][nc] ! 0) block; // 五连直接给大分 if (len 5) score 100000; else if (len 4 block 0) score 10000; // 活四 else if (len 4 block 1) score 5000; // 冲四 else if (len 3 block 0) score 1000; // 活三 else if (len 3 block 1) score 100; // 眠三 } } return score; }这个函数没有刻意避免重复统计同一个连子因为左右两方都会以同样方式重复统计对称的误差在 Min-Max 比较中不会影响走法选择。评估总分数可以写成eval score_me - score_opp * weight_opp我一般把对手权重设为 1.1 到 1.3让 AI 更倾向防守。参数调整规律活三 1000 对活四 10000这两个权重差太大时 AI 会过度保守错过反打机会差太小时 AI 对冲四不敏感容易在几步内丢掉必胜形。权重实测比重理论更靠谱先跑 100 局量级再改别凭感觉拍。3.3 Alpha-Beta搜索框架迭代加深与时间控制搜索框架是迭代加深的 alpha-beta用 Negamax 写法统一“我”和“对手”的评估视角。迭代加深的好处是可以随时在时间片到达时停掉而且上一轮搜索结果可以作为当前轮走法排序的参考让剪枝更有效。int NegaMax(Board b, int depth, int alpha, int beta, int player) { if (depth 0) return EvaluateLines(b, player) - EvaluateLines(b, 3 - player); auto moves GenerateMoves(b, 2); if (moves.empty()) return 0; // 走法排序上轮最优走法优先其次按离中心距离排序 for (auto mv : moves) { b[mv.first][mv.second] player; int val -NegaMax(b, depth - 1, -beta, -alpha, 3 - player); b[mv.first][mv.second] 0; if (val beta) { return beta; // 剪枝 } if (val alpha) alpha val; } return alpha; }这里用-NegaMax(b, depth-1, -beta, -alpha, 3-player)实现交换视角避免分别写 Max 和 Min 两套逻辑。很多新手翻车都翻在评估符号上在 Max 层返回正分在 Min 层忘了取负结果 AI 变成“主动送死”。迭代加深的调用层这样写int BestMove(Board b, int maxTimeMs, int player) { int best -1; for (int depth 1; depth 12; depth) { auto start std::chrono::steady_clock::now(); int alpha -1000000, beta 1000000; auto moves GenerateMoves(b, 2); // 按上轮最优和中心距离排序 for (auto mv : moves) { b[mv.first][mv.second] player; int val -NegaMax(b, depth - 1, -beta, -alpha, 3 - player); b[mv.first][mv.second] 0; if (val alpha) { alpha val; best mv.first * 15 mv.second; } auto now std::chrono::steady_clock::now(); if (std::chrono::duration_caststd::chrono::milliseconds(now - start).count() maxTimeMs) { return best; // 时间到返回已完成搜索的最好走法 } } } return best; }maxTimeMs 是每步思考时限我一般设为平台限制的 70%比如限制 1 秒就设 700ms留 300ms 给网络传输与系统调度。depth 上限 12 对五子棋来说已经很深实际一般在 6 到 10 层之间就会因时间触发返回。时间检查放在走法循环外层而不是每次递归里能把额外开销压到最低又能在极端情况下及时退出。4. 让AI从“能下”到“能赢”辅导资料里的调参四步4.1 时间控制与深度阈值开局、中盘、残局三档同样一个 AI满盘均匀搜索和分阶段控制时间胜率差距很大。我一般把对局按落子数量分三档开局前 10 手、中盘、残局。开局阶段不需要长搜因为棋形稀疏深度 4 到 6 已经足够中盘是决定胜负的主战场把 70% 的时间预算都留在这里残局则要仔细读秒因为胜负可能就在一两手。阶段手数范围五子棋每步时间迭代加深上限开局1-10 手150ms6中盘11-60 手700ms10残局60 手以后800ms12这个表是经验值。如果平台是每方总时间限制比如每方 15 分钟我会把时间预算转成“每步动态时间”开局固定短思考中盘按剩余时间除以预估剩余手数来分配残局至少留足 5 分钟。时间控制代码不要写在搜索引擎内部最好放在比赛管理线程里因为引擎本身不知道每方时长和当前手数。4.2 评估权重校准用自对弈胜率代替直觉活三 1000、活四 10000这个比例看起来合理但真正判断权重是否合适得让两个版本互相下。我写过一个最小的自对弈脚本过程是让 A 参数版本先手B 参数后手跑 100 局交换先后手再跑 100 局统计胜率。def play(engine_a, engine_b, first, games20): wins {engine_a: 0, engine_b: 0, draw: 0} for i in range(games): # 裁判模块维护棋盘、调用双方走法、判断终局 cmd [engine_a if first else engine_b, --time500, --modecui] winner run_referee(cmd, engine_b if first else engine_a) wins[winner] wins.get(winner, 0) 1 first not first return wins if __name__ __main__: # 参数版本A活三1000/活四10000版本B活三800/活四12000 results play(./gomoku_a, ./gomoku_b, firsta, games80) print(results)run_referee 是裁判模块负责棋盘状态序列化、超时判负和终局检查。自对弈的坑同一参数对称版本互相下容易陷入“双方同样错误”的共谋所以权重校准至少要跟踪单局平均步数、常用开局分布。如果改动后的胜率仍在一半附近说明改动方向无效回滚到上一版。我们队在实际调参里权重比例浮动超过 20% 但胜率还在 50% 上下浮动的情况很常见这种时候最该做的是回归测试而不是继续调。4.3 开局库最接近“辅导资料”的加分项竞赛辅导资料里最容易被忽略的是开局库。五子棋和其他棋类一样前几步的走法组合不多与其让 AI 花时间搜索不如离线算好存起来。常见做法是第一周先跑几千局自对弈记录下前 8 手所有能拿高胜率的走法第二周把这些走法编成一张哈希表键是“前 8 手的紧凑棋盘哈希”值是对应走法坐标比赛引擎每步先查开局库命中就走库着法不命中再走搜索。开局库的规模不用大300 个高频开局就已经能覆盖大部分对局。但要注意库着法只能在前 8 到 15 手使用过了这个手数必须切回搜索否则“库不对局”会让 AI 在残局前早早落后。开局库的实现还有一个注意点哈希时要把棋盘旋转和镜像一起处理否则同样开局换了个方向就查不到等于白建。我一般会在建库脚本里生成 8 个对称变换的哈希把命中率提升不少。5. 备赛避坑搜索崩溃、评估失效、超时判负的排查清单竞赛备赛里翻车最多的地方不在算法理论而在工程细节。下面这四条是我带队这两年踩得最多的坑每一条都按“现象、原因、解决”的顺序讲清楚。5.1 搜索半天不落子置换表与剪枝失效现象设置深度 4但某一步搜索超过 10 秒才落子。原因不是机器慢而是两种情况走法列表太多导致剪枝没触发或者搜索逻辑进入重复扫描。五子棋 15×15 的空位高达 200 个没有走法排序时 alpha-beta 剪枝几乎不生效实际搜索量接近全排列。解决先加入上一轮最优走法优先排序再给搜索加置换表Zobrist 哈希后缓存局面分。检查剪枝是否真的生效可以在 debug 模式下打印每个深度展开的节点数改进前走法排序depth4 时节点数是几十万量级改进后应降到几千到几万。如果节点数没有明显变化说明排序逻辑没有真正执行先查走法列表是否被覆盖排序。5.2 局面分乱跳导致“转圈”评估特征未归一化现象AI 在相近局面里反复选不同走法看起来像犹豫。原因是评估函数里活三权重和冲四权重数量级差太远分数一波动就让搜索误以为局面翻转。解决先把所有特征分归一到 0 到 1 区间再分配权重复核最后检查 alpha-beta 返回的分数边界是否一致。我一般在权重调参后立刻跑 50 局“自对弈旁观”看单局里每步的估值曲线如果上下波动超过 3 倍就说明权重比例有问题。活三 1000 和活四 10000 之间如果是 10 倍差距AI 会选择性地无视活三威胁因为冲四带来的分数变化才值得搜索这种“选择性失明”不是搜索深度能弥补的。5.3 线上平台超时判负时钟函数选错现象本机测试每步平均 0.8 秒比赛平台上一手就判超时。很多人用 clock() 计时计算的是 CPU 时间在线上多核环境下受调度影响严重尤其 C 里 clock() 可能把多线程的等待也算进去或算偏。解决换成 steady_clock 或系统单调时钟并且把每步时间上限调成平台限制的 70%给网络延迟和调度留余量。另外比赛程序的输出接口必须同步干净别在走法输出后还残留 debug 日志否则输出阻塞也会造成超时。还有一个容易被忽略的点残局阶段如果 AI 判定“必败”不要在搜索里继续穷举到底直接认输并快速输出节省整盘时间用于后面比赛。5.4 规则实现出错把棋规翻译成单元测试现象AI 偶尔下出非法落子或者对禁手判断不一致。这是规则阅读和代码实现不一致导致的。解决为每个规则建立测试用例。以五子棋“三三禁手”为例至少要有四个用例单纯活三不判禁、双活三判禁、被堵死的眠三不参与、边界坐标为 (0,0) 的三三是否合法。把这些用例放进自动测试每次改评估或走法生成器先跑测试再上搜索。测试用例类型输入局面期望结果单纯活三黑棋三连一侧空不判禁手双活三交叉黑棋两方向同时活三判禁手眠三不参与三连一侧被堵不判禁手边界三三黑棋在 (0,0) 附近双活三按规则判定我见过至少三个队伍在比赛当天因为禁手规则判错直接判负都是因为测试没有覆盖边界。规则测试不是竞赛之外的事它本身就是辅导资料数据化的核心。6. 赛前一个月值得投入的对抗自测把“会下”变成“会赢”赛前一个月算法基本定型剩下的问题只有一个你改的每一版到底比上一版强多少这需要把自对弈变成一个固定流程而不是偶尔跑几局的临时动作。我习惯用一个简单的 bash 循环做批量自对弈让两个引擎版本各执先手 20 局并把结果追加到 CSV 里。每行记录先手方、后手方、胜者、步数、每步平均耗时。有了这些数据胜负率就不再是“感觉强了”而是能算出来的数字。#!/bin/bash # 自对弈胜率统计engine_a 和 engine_b 各执先手20局 for i in $(seq 1 20); do if [ $((i % 2)) -eq 1 ]; then ./referee --engine a --engine b --first a --time 500 result_a.csv else ./referee --engine a --engine b --first b --time 500 result_b.csv fi done统计时我会算两个指标胜率和胜方平均步数。胜率接近 60% 说明改动方向有效胜率接近 50% 但胜方平均步数显著变短说明 AI 变成了“速攻型”这在中盘优势稳固时是好事在劣势局面里却容易加速崩盘要结合开局分布一起看。用胜率换 Elo 近似值也行70% 胜率对应约 150 分差距这是可以在辅导资料里写进“验证方法”的常用换算。最后说一个带队的血泪习惯赛前一周把所有参数冻结任何新想法只记进实验笔记不在赛前三天改动。我们有一年就是赛前一天改了权重自认为解决了“冲四不敏感”的问题结果当天遇到强防守对手时整体行为失常。现在每次参赛我都会训练队伍遵守“冻结参数”纪律所有改动必须先回到实验笔记验证超过 200 局再决定是否上线。计算机博弈竞赛的备赛本质上是一种工程训练。辅导资料给的是起点真正让 AI 变强的是你每天记录的胜负数据和每一次回滚。希望这些方法和坑点能帮到你。本文还有配套的精品资源点击获取