企业官网建设流程全解析

简介：这份计算机博弈竞赛辅导资料面向准备参赛的高校学生、指导教师以及人工智能与搜索算法方向的自学者，旨在帮助读者在赛前建立从棋类规则认知到博弈程序实现的整体知识框架。压缩包内仅有1个PPT文件，约2.57MB，以课堂讲义课件形式组织，便于集中讲授、培训串讲或按章节自学。内容覆盖棋类介绍与分类、计算机博弈基本原理、博弈软件构成、棋局评估、博弈树展开与分析、基于搜索的方法学特点及学科关系，并列举中国象棋、国际象棋、围棋、五子棋、六子棋等典型棋类；读者可结合棋局评估中的启发式搜索、alpha-beta剪枝与蒙特卡罗树搜索，以及博弈树的构建、展开和搜索流程，对照理解算法与棋类对象之间的对应关系。已有331人学习，适合用于赛前梳理知识脉络、定位薄弱环节，也可作为竞赛培训提纲和课程复习材料。

1. 计算机博弈竞赛到底考什么：先看清棋盘，再谈算法

很多人拿到计算机博弈竞赛的题，第一反应是背 alpha-beta 剪枝的公式，上场才发现卡住自己的是“长将怎么判”“五子棋禁手怎么算”“六子棋一回合两子怎么生成着法”。计算机博弈竞赛考的是一个闭环：把棋类规则无歧义地翻译成数据结构和着法生成器，用博弈树搜索在时限内找到足够好的一步，再用自洽的评估函数给叶子打分。机器博弈类题目里最被轻视的棋类介绍与分类，恰恰是失分最集中的地方——完全信息动态博弈的题面，一个特殊规则写错，后面所有搜索都白算。这份辅导资料适合已会写递归、准备参赛或答辩的人。

2. 棋类与分类考点：规则差异如何决定着法生成器的写法

2.1 三种盘面类型：走子类、填子类、混合类的建模分野

面试里问“给你一个没见过的棋，你怎么建模”，面试官最想听的不是你认识多少棋，而是你能不能先判断它属于哪一类。按着法分，棋分三种：走子类是开局摆满、轮流移动，中国象棋、国际象棋、跳棋、苏拉卡尔塔、亚马逊都属这一类；填子类是空盘开局、轮流落子，围棋、五子棋、点格棋属这一类；混合类是先填后走，某些民间五道棋和日本将棋的规则里同时存在填子、走子、吃子。

这三类对应三套完全不同的着法生成逻辑，选错了后面全是返工。走子类的着法是一个二元组“起点到终点”，生成时要过滤自家棋子占位、越界、兵种行棋限制，还要单独处理“走后是否自己被将军”这种合法性检查；填子类的着法就是一个坐标，状态空间单调递增、棋子只增不减，没有吃子，所以它的难点不在生成速度而在形状判断，围棋的气与提子、五子棋的连子形状都属于这一层；混合类必须做成阶段机，同一个棋盘对象在阶段一接受“填子”类型的着法，在阶段二接受“走子”类型的着法，中间还要触发一次盘面转换。

提示：建模时把“着法类型”做成枚举而不是布尔开关，后面写搜索时可以直接按类型分派，避免在深层递归里反复做 if 判断。

一个反直觉的点是，按参与人数分类在笔试里分值不高但很爱考：双人弈棋占绝大多数，单人游戏以华容道这类滑块类为代表，多人棋如跳棋。单人游戏没有对手，博弈树退化成一棵带重复状态的搜索树，考的是状态去重和最短步数，跟双人博弈的极大极小完全是两套思路。答题时说清“单人游戏用图搜索加访问集去重，双人零和博弈用极大极小”，这一句就能把两类题分开。

2.2 典型棋种参数速记：棋盘、子力、胜负判定

这一张表是必须背下来的，竞赛题和答辩追问都从这里出。资料里给出的参数不要记混，尤其是棋盘尺寸和特殊规则这两列。

国际象棋的子力值是另一道必答题：以兵为 1，马约 3、象约 3、车约 5、后约 9。注意“象约 3”和“马约 3”是经验值不是精确值，答辩被问到“为什么后是 9 而不是 8 或 10”，正确的答法是“这是长期对局统计出来的等价交换比例，不是理论推导，评估函数里可以按棋种和相位微调”。围棋的子力值则是另一套东西，围棋没有子力值，只有目数和厚薄，把国际象棋那套搬过去会当场翻车。

2.3 真题演练：十分钟给一个陌生棋种写规则建模清单

题目通常长这样：“给你点格棋（或苏拉卡尔塔），写出程序需要的数据结构与关键判定。”答题思路固定成四张表，按顺序说，面试官会觉得你有工程直觉。

第一步，初始局面表。点格棋开局盘面无子、只有点和未连的边，所以要存的不是棋子而是边的状态和格子的归属；苏拉卡尔塔开局是满盘棋子，要存的是坐标到棋子类型的二维数组。第二步，着法生成表。点格棋的着法是“连一条尚未连的边”，苏拉卡尔塔的着法是“移动一格”或“沿弧吃子”，后者要预先把所有完整弧线枚举成路径表，否则递归里现算弧线会慢一个数量级。第三步，终局判定表。点格棋是“所有边连完”，苏拉卡尔塔是“一方棋子被吃光或无法行动”。第四步，非法着法与特殊约定表，点格棋要注意最后一个占边者获得格子后必须再连一边，苏拉卡尔塔要注意“不可不走”。

用代码块把第一、二步落成接口，答辩时白板也能写出来：

class GameState: """所有棋种共用的状态接口，换棋种只换实现不改搜索""" def legal_moves(self): """返回当前走子方的全部合法着法，类型由 move_type 区分""" raise NotImplementedError def make_move(self, move): """落子/走子，必须可被 undo_move 完全逆操作""" raise NotImplementedError def undo_move(self, move): """撤销，搜索里每个 make 都要配对一次 undo，否则血泪教训""" raise NotImplementedError def is_terminal(self): """终局判定：胜负或和棋，必须返回明确的三态值""" raise NotImplementedError def evaluate(self): """叶子节点打分，视角统一为当前走子方""" raise NotImplementedError

这段接口的关键在三点：legal_moves把特殊规则全部收口在一个函数里，搜索层不需要知道任何棋种细节；make_move与undo_move必须严格配对，很多人的搜索跑两次结果不一样，就是 undo 漏恢复了某个计数器；evaluate的视角约定写在注释里，这是后面所有符号错误的源头。把这三条讲清楚，比背十个棋种规则更能拿分。

3. 博弈树与搜索考点：极大极小、剪枝与置换表

3.1 负极大值写法：一个符号错误能毁掉整局棋

极大极小在纸面上很好懂，MAX 层取最大、MIN 层取最小，但真写起来最容易翻车的地方是视角。资料里强调的“基于搜索”的方法学，落到代码上最省事的写法是负极大值：不分 MAX 层和 MIN 层，每一层都取“对当前走子方最有利”的最大值，靠递归时取负来体现对手的立场。这样代码只有一份，剪枝窗口的传递也简单。

INF = float("inf") def negamax(board, depth, alpha, beta): # 终局或到达深度上限：直接返回评估值（走子方视角） if depth == 0 or board.is_terminal(): return board.evaluate() best = -INF for move in board.legal_moves(): board.make_move(move) # 关键：子节点取负，同时把窗口反转后传下去 score = -negamax(board, depth - 1, -beta, -alpha) board.undo_move(move) if score > best: best = score if best > alpha: alpha = best # 抬高下界，代表当前走子方已有更好选择 if alpha >= beta: break # 上界被击穿，对手不会让我走到这里 return best

这段代码有四个参数要能讲清。depth是剩余深度，每递归一层减一，减到零就用评估函数代替继续展开；alpha是当前走子方能保证拿到的下界，beta是对手不会允许超过的上界；递归里的-beta, -alpha是窗口反转，顺序不能写成-alpha, -beta，写反了剪枝会剪掉正确分支；break的条件是alpha >= beta，等号不能丢，丢了会多做无用搜索，虽然结果不错但节点数明显变多。

还有一个常被追问的细节：evaluate()必须返回“轮到走子的一方”的分数，而不是固定红方为正。国际象棋里白方视角为正、中国象棋里红方视角为正，这些都可以在内部实现，但对外接口必须统一，否则搜索结果会出现“越优的局面越不走”的鬼故事。

3.2 alpha-beta 剪枝：剪掉的是什么，为什么结果不变

剪枝的数学含义要能一句话说清：当某个节点的上界已经不优于祖先节点已知的下界时，这个节点剩下的分支无论多好都不会改变根节点的选择，所以可以安全跳过。它剪掉的是“不可能影响最终决策的分支”，不是“评估不准确的分支”，所以窗口正确时 alpha-beta 与全量极大极小返回同一个根节点值，只是访问节点数变少。

复杂度必须背：分支因子 b、深度 d 时，全量搜索是 O(b^d)，理想排序下的 alpha-beta 最好情况接近 O(b^(d/2))，相当于同样时间能多搜一倍深度；最坏情况仍是 O(b^d)，一步都剪不掉。这句话后面通常跟着一道追问：“怎么让它接近最好情况？”答案是走法排序——先搜吃子着法、先用历史启发里曾经剪枝成功的着法、先用杀手着法，把最可能引发剪枝的分支排在前面。迭代加深在这里很划算：先用浅层搜一遍拿到一个大概排序，再用深层搜，虽然重复计算了浅层，但排序带来的剪枝收益通常远大于重复开销。

置换表是同一层的另一个高频考点。它的作用是同一局面通过不同着法顺序到达时，直接复用上次的搜索结果。实现上用 Zobrist 哈希给每个局面算一个 64 位键，存“键 → 深度、分值、边界类型（精确值/下界/上界）、最佳着法”。这里最常见的错误是只存了分值没存深度，导致浅层搜索的结果覆盖了深层结果，程序在关键局面突然变傻；正确做法是命中时比较深度，只有表里的深度不小于当前剩余深度才可直接采用，否则只能借用它的最佳着法来排序。

3.3 真题演练：手算一棵树的剪枝，再用代码验证

典型题面是给一棵三层的树，根为 MAX，三个子节点 A、B、C 为 MIN，每个 MIN 下三个叶子，问 alpha-beta 从左到右遍历时访问了哪些叶子。设 A 下叶子为 3、5、2，B 下为 7、4、6，C 下为 1、8、9。

手算过程如下：根节点初始窗口为负无穷到正无穷。进入 A，A 的三个叶子依次得 3、5、2，A 作为 MIN 层取最小得 2，根节点拿到 2 后下界抬到 2。进入 B，B 的第一个叶子 7 让 B 的上界降到 7，仍大于根的下界 2，继续；第二个叶子 4 让 B 的上界降到 4，仍大于 2，继续；第三个叶子 6 不改变 B 的最小值 4，B 返回 4，根的下界抬到 4。进入 C，C 的第一个叶子 1 让 C 的上界降到 1，此时根的下界 4 已经不小于 1，剪枝触发，C 的另外两个叶子 8 和 9 不再访问。

九次叶子评估被压到七次。这个例子的价值不在数字，而在答辩时的补充说明：如果走法排序把 C 排到最前，根节点会先拿到 1，那么 B 的第一个叶子 7 之后就会触发剪枝，B 的后两个叶子也能省掉，总访问数降到五次。这句话说出来，等于告诉面试官你知道“剪枝效率取决于排序而不是算法本身”。

4. 棋局评估与软件构成：评估函数为什么不是玄学

4.1 评估函数四件套：子力、位置、机动性、相位

评估函数是搜索的眼睛，写歪了搜索越深错得越离谱。工程上常用四类特征做线性加权：子力、位置、机动性、相位。子力是最粗的一层，国际象棋按兵 1、马 3、象 3、车 5、后 9 折算；位置用位置表，给每个兵种在每个格子上一个附加值，比如马在中心比在边角高，王在中局要躲、残局要往中心靠；机动性统计合法着法数量，着法多通常意味着活动空间大；相位用来在中局和残局之间切换权重，残局里王的位置表要整体反过来用。

必须能讲清一个限制：评估函数是启发式的，没有“正确值”，只有“和胜负相关性高的值”。所以调参不能靠感觉，要靠自对弈统计——改一组权重，跑几百盘自对弈，看胜率变化。面试官问“你怎么知道评估函数变好了”，标准答案是“固定搜索深度和时限，跑自对弈对比胜率，同时看平均每步耗时有没有明显恶化”，只答“感觉棋走得更好看了”会被追问到答不出来。

亚马逊这类棋的评估要特别注意：它没有吃子，胜负由“无子可动”决定，所以子力项完全不存在，评估必须换成活动范围、连通区域大小、障碍密度这些量。点格棋同理，它的评估核心是链的奇偶性和死格数量，谁掌握长链的最后一个边，谁就能连吃一串格子。把中国象棋那套子力评估硬套到这类棋上，是典型的“背了公式不会用”。

4.2 软件构成分层：哪一层出问题，症状长什么样

一份能跑的博弈软件可以拆成七层，每层故障的表现完全不同，答题时按层报症状比笼统说“程序有点问题”专业得多。

棋盘表示这一层值得单独说：数组表示直观但慢，位棋盘用几个 64 位整数表示整个盘面，走子变成位运算，速度快但可读性差、调试痛苦。竞赛里如果棋盘规模在 8×8 或 9×10 这种量级，位棋盘是加分项；如果棋盘不规则（比如三通棋的 64 个三角形棋位、点格棋的边与格），硬上位棋盘会把自己绕进去，这时候用邻接表加坐标映射更稳。

4.3 真题演练：大优局面走自杀着法，怎么定位

这是一道几乎必问的排错题。现象是程序在中局明显占优时，突然把自己的车送到对方兵口下。答题时按“先怀疑符号、再怀疑规则、最后怀疑搜索”的顺序排查。

第一嫌疑是评估视角。如果evaluate固定返回红方为正，而负极大值里每一层都把它当成“走子方视角”直接用，黑方走子时就会把红方的好局面当成自己的好局面，于是拼命帮对手走棋。修正方式是在评估出口统一换视角：

def evaluate_for_side(board): # 内部统一按红方为正计算，出口再翻转成走子方视角 red_score = board.evaluate_red() return red_score if board.side_to_move == RED else -red_score

第二嫌疑是着法生成漏了合法性检查。中国象棋里“走完之后自己被将军”的着法必须过滤掉，很多实现只在生成阶段检查兵种走法，忘了走完后做一次被将检测，于是程序会主动送将。第三嫌疑是置换表污染或 undo 不彻底，表现为同一局面两次搜索结果不同，这时把置换表关掉再跑一遍，如果结果正常就锁定是置换表深度字段的问题。

4.4 蒙特卡罗树搜索：另一条路线怎么答

资料里棋局评估部分提到了蒙特卡罗树搜索，很多竞赛题会给一个围棋 9×9 的场景让你比较两条路线。MCTS 不依赖人工评估函数，靠大量随机模拟统计胜率，四个阶段是选择、扩展、模拟、回传，选择阶段用 UCB 平衡“ exploitation（当前胜率高的分支）和 exploration（访问次数少的分支）。

import math def ucb(child, parent_visits, c=1.414): # 第一项是利用：该子节点的平均胜率 # 第二项是探索：访问次数越少，加分越多 return child.wins / child.visits + c * math.sqrt(math.log(parent_visits) / child.visits)

参数c控制探索强度，取大了会到处乱试，取小了会死盯一条线；child.visits为零时要单独返回无穷大，否则除零。答题时的对比结论要清楚：alpha-beta 依赖评估函数质量、适合分支因子可控的棋种（象棋、国际象棋、五子棋），MCTS 依赖模拟次数、适合分支因子极大且难以设计评估的棋种（围棋），两者不是替代关系，围棋 9×9 这种规模上 MCTS 更省心，而象棋上纯 MCTS 在相同时限下通常打不过带剪枝的搜索。

5. 易错点：五类一答就露怯的规则与搜索失分点

第一类，把 alpha-beta 说成“近似算法”。错在把剪枝理解成丢弃信息，于是答出“剪枝会牺牲一点正确性换速度”。这是硬伤：剪枝的前提是数学上可证明不影响根节点取值，剪掉的分支在当前窗口下不可能成为最优选择。正确的答法是先给结论“结果与全量极大极小完全一致”，再补一句“前提是窗口传递正确、置换表深度字段没写错”，把可能出错的工程条件也点到，比单说一句“不影响”更可信。

第二类，评估函数视角混乱。错在内部用固定一方为正，外部又按走子方取最大，结果双方都朝同一个方向使劲。为什么错：负极大值的每一层都隐含“当前走子方希望分值越大越好”，评估出口必须跟着翻转。怎么答对：统一在评估出口做一次视角转换，并在答辩时主动说“我在接口注释里写死了视角约定，所有调用方都用同一个出口”，这一句能顺带证明你写过多大的工程。

第三类，中国象棋规则细节记不全。错在只答“将死对方获胜”，被追问长将、60 步不吃子判和、重复局面时答不上来。为什么错：这些规则在程序里要落成计数器，不是文字条款——60 步不吃子需要一个不吃子步数计数器，长将需要一个重复局面检测，任何一个没实现，程序就会在实战里该判和时继续乱走甚至判错胜负。怎么答对：按“胜负判定、和棋判定、非法着法”三类分列，每类给出对应要维护的状态变量。

第四类，五子棋先手优势答反。错在说“五子棋双方完全公平，先手没有优势”。事实是五子棋在无限制规则下先手已被证明必胜，所以才有禁手、换手、金球制这些限制先手的规则设计。为什么错：把“规则简单”等同于“对先手公平”，而资料里明确写了五子棋已被证明先手胜。怎么答对：先说结论“先手必胜所以必须限制”，再解释禁手约束的是先手方的特定走法，换手和金球制则是从制度上削减先手收益，两条路径目的相同。

第五类，把棋类和牌类混成一类，说博弈树能解决一切。错在忽略“完全信息”和“不完全信息”的分界。棋类是完全信息动态博弈，盘面全部可见，所以博弈树可以完整展开；牌类是不完全信息动态博弈，对手手牌未知，标准的博弈树用不了，要引入信息集、概率分布或者博弈论里的均衡概念。怎么答对：先分类再给方法，一句话“完全信息用搜索，不完全信息要处理信念状态”，然后补一个例子说明搜索在这类问题上会退化。

6. 面试答辩怎么答：三分钟讲清一个博弈项目

答辩现场的时间通常只有三到五分钟，讲不完所有细节，所以要按固定骨架压缩：问题与约束、表示与着法生成、搜索、评估、结果。下面这张表是我总结的对应关系和示范答法，照着练三遍就能脱稿。

这套骨架有两个高频追问要提前备好。第一个是“你的剪枝效率怎么样”——不要只答“挺高的”，要给可量化的东西，比如“理想分支因子 b 取 30，实测有效分支因子在 8 左右，说明排序起作用了”。第二个是“如果给你加一个没见过的棋种，你要改多少代码”——标准答案是“只改状态类里那五个接口，搜索层和评估框架不动”，这一句直接把你的设计能力亮出来。

押题方向上，我判断三道题出现概率最高：一道是“解释 alpha-beta 为什么不影响结果并手算一棵树”，一道是“评估函数怎么设计、怎么验证它变好了”，还有一道是“棋类和牌类的区别，不完全信息怎么处理”。这三道题覆盖了搜索、评估、分类三个模块，把它们的答案压缩成三分钟版本背熟，其余问题基本都是这三条的变体。

说个自己的教训。早些年准备这类答辩，我习惯从“计算机博弈的意义”讲起，铺两分钟背景，结果评委一句“你具体做了什么”就把节奏打乱，后面全在补窟窿。从那以后我每次讲项目，第一句话都强制走一遍“棋种、规模、时限、我这步做了什么”的模板，先给结论再展开细节。希望帮到你。

本文还有配套的精品资源，点击获取