期望搜索实战：用Expectimax构建带骰子随机性的爱因斯坦棋AI

简介：基于期望搜索算法的爱因斯坦棋博弈软件是一款面向棋类爱好者、学生、教师及计算机博弈大赛参赛者的智能对战程序，利用期望搜索评估局面并制定策略，以Pygame构建简洁界面，支持多种棋类规则切换。资源包共159个文件，压缩后约7.38MB，内含Python源码、55张PNG界面素材、sample示例数据、XML配置、TTF字体、patch补丁及Git仓库完整对象（master/head/index等），可还原项目开发环境与版本演进历史。目前已有122人学习下载，适合课程设计、竞赛备赛及算法研究，尤其适合需要理解博弈树搜索与期望值评估策略的读者。通过阅读源码和配套素材，读者可以理解期望搜索算法在棋类对弈中的具体实现、实时反馈与走法建议的交互设计，以及包含大量Git对象和配置文件的工程目录组织方式，便于二次开发与维护。

1. 爱因斯坦棋的随机性与期望搜索：为什么直接套 Minimax 会翻车

带骰子的棋类 AI 有个通病：直接套 Minimax，棋力上不去，剪枝优化做得再细也白搭。爱因斯坦棋就是典型——5x5 棋盘、双方各 6 枚编号棋子、每回合掷骰决定能动哪颗子。随机性不是点缀，而是规则核心。Minimax 默认对手每一步都取最优，但在这里，骰子 1/6 概率落在哪颗子上，直接决定了你根本"没有选择"。期望搜索（Expectimax）正是为这类带机会节点的博弈设计的：把骰子节点当概率加权平均，行动节点才做 max/min。这篇笔记写给想把爱因斯坦棋做成可对战软件的开发者，也写给被随机棋类胜率卡住、想从搜索结构上找突破的人。读完你能自己实现一个可跑的期望搜索博弈软件，并知道参数怎么调、坑在哪里。

2. 把爱因斯坦棋规则写进代码：棋盘、走法生成与骰子建模

2.1 规则版本先定死：骰子、编号与不可动分支

爱因斯坦棋不同平台规则有细微差异，动手前必须把版本钉死。我采用的是一套较为通行的规则：5x5 棋盘，双方各 6 枚棋子，编号 1 到 6，初始摆在靠近己方的两行；每回合掷一枚六面骰，掷出几就必须移动编号几的己方棋子；每颗子只能朝对手方向直走或斜走一格，不能后退；目标格是空位或对方棋子时可以走，是己方棋子则非法；若掷出编号的棋子已被吃掉或完全不能动，则该回合空过。先走到对方底线或吃光对方全部棋子的一方获胜。

这套规则里最大的非对称点在第 6 条——"空过"。它不是一个错误处理，而是概率空间里真实存在的一个分支。期望搜索里如果把不可动分支漏掉，六个骰子面的概率加起来不是 1，评估值会出现系统性偏差。后面第 5 章我会专门展开这条踩坑记录，这里先记住结论：骰子建模必须把"无合法走法"当成一个合法分支处理，概率同样是 1/6。

2.2 棋盘与棋子的最小实现：用坐标而不是向量

我一般用 Python 做原型，坐标采用 (row, col)，row=0 为黑方底线，row=4 为白方底线。棋子状态用字典存：编号映射到坐标，这样骰子点数可以 O(1) 查出对应棋子位置。棋盘用 5x5 二维数组，元素为棋子归属方和编号，空位为 None。

SIZE = 5 # 黑方在上方(row=0一侧)，白方在下方(row=4一侧) # pieces 结构: {'black': {1: (r,c), 2: (r,c), ...}, 'white': {...}} class Board: def __init__(self): self.grid = [[None] * SIZE for _ in range(SIZE)] self.pieces = {} self.pieces['black'] = { 1: (0, 0), 2: (0, 1), 3: (0, 2), 4: (0, 3), 5: (0, 4), 6: (1, 2) } self.pieces['white'] = { 1: (4, 0), 2: (4, 1), 3: (4, 2), 4: (4, 3), 5: (4, 4), 6: (3, 2) } for side, dic in self.pieces.items(): for pid, (r, c) in dic.items(): self.grid[r][c] = (side, pid)

这段代码把"棋盘布局"和"编号到坐标的映射"分开存，是为了后面走法生成时不被棋盘遍历拖慢。5x5 棋盘只有 25 个格子，暴力遍历也不是不行，但搜索树每层要调几千次走法生成，能省则省。用字典存棋子位置，骰子点数一出来，直接定位到棋子，不需要全盘扫描。

2.3 走法生成的关键：方向向量与己方碰撞

移动规则是"只朝对方方向走一步，可直可斜"。黑方向下（row+1），白方朝上（row-1），方向向量正好互为相反数。斜向有左斜和右斜两个选择，加上直行，每颗子最多三个候选目标格。

def _step_candidates(self, r, c, side): dr = 1 if side == 'black' else -1 # 黑向下，白向上 for dc in (-1, 0, 1): nr, nc = r + dr, c + dc if 0 <= nr < SIZE and 0 <= nc < SIZE: yield nr, nc def legal_moves(self, side, die): if die not in self.pieces[side]: return [] # 该编号棋子已被吃，空过分支 r, c = self.pieces[side][die] moves = [] for nr, nc in self._step_candidates(r, c, side): target = self.grid[nr][nc] if target is None: moves.append(((r, c), (nr, nc))) # 走空位 elif target[0] != side: moves.append(((r, c), (nr, nc))) # 吃对方棋子 # 目标格是己方棋子时合法走法为空，直接跳过 return moves

legal_moves返回空列表时，调用方必须把它理解为"该点数空过"，而不是"出错了"。这是整个期望搜索概率模型的地基。另外注意：吃子走法和走空位在走法生成层面没有区别，都是一个坐标移动；真正的差异体现在评估函数里——吃掉对方编号越大的棋子，对后续骰子分支的影响越大，因为对方少了一个可动编号，空过概率会上升。这个联动效应是爱因斯坦棋评估函数里最值得挖掘的特征之一。

def dice_branches(self, side): result = [] for die in range(1, 7): moves = self.legal_moves(side, die) result.append((die, moves)) return result

dice_branches一次性生成当前回合六个骰子面的完整分支。注意它没有过滤掉空 moves 的分支——前面强调过，空过也是概率空间的一部分。这个函数的返回值会被期望搜索直接消费，所以它的正确性直接影响整个 AI 的棋力。写完之后建议先用一个手工摆好的局面验证：某个编号的棋子被吃时，对应分支 moves 是否为空；某个棋子被己方棋子堵死时，是否产生了"能走却被堵"的误判。

3. 用期望搜索构建 AI：机会节点、对手节点与搜索深度

3.1 从 Minimax 到 Expectimax：随机节点为什么不做 max/min

Minimax 的基本假设是：每一步都由某个玩家做出确定性最优选择。轮到己方取 max，轮到对手取 min。爱因斯坦棋的问题在于，每个回合开始前还有一个"掷骰子"环节，它不是由任何玩家控制的，而是概率事件。把骰子当 max 分支处理，等于假设骰子每次都会给你想要的点数；当 min 分支处理，等于假设骰子每次都给你最差的点数。两种都是错的，正确做法是把骰子节点的值定义为"六个骰子面值的期望"。

期望搜索的节点类型因此有三种：己方行动节点取 max、对手行动节点取 min、骰子节点取概率加权平均。这里的关键在于：骰子节点后面跟着的还是行动节点。掷出点数 3 之后，该点数可能有多颗子能走（实际只有一颗，因为按编号移动），也可能一颗都不能走。能走时，是当前行动方从合法走法里选最优——这是 max 或 min 节点；不能走时，直接过渡到对方回合，不产生行动选择。所以搜索树的形态是"骰子节点 -> 行动节点 -> 骰子节点"交替出现。

3.2 期望搜索的代码实现：骰子分支如何算平均值

下面这段是核心搜索函数。我采用"每个骰子分支消耗一层深度"的写法，即 depth 表示"掷骰并行动"的回合数，这样深度语义更接近棋手理解的"看几步棋"。

def expectimax(board, depth, ai_side, current_side): winner = board.winner() if winner is not None: return 10000.0 if winner == ai_side else -10000.0 if depth == 0: return evaluate(board, ai_side) expectation = 0.0 for die in range(1, 7): prob = 1.0 / 6.0 moves = board.legal_moves(current_side, die) if not moves: # 空过分支：不产生走法选择，直接换人 v = expectimax(board, depth - 1, ai_side, opponent(current_side)) expectation += prob * v continue values = [] for move in moves: board.apply(move) values.append(expectimax(board, depth - 1, ai_side, opponent(current_side))) board.undo(move) if current_side == ai_side: branch_value = max(values) # 己方掷出此点，取最优走法 else: branch_value = min(values) # 对方掷出此点，假设对方取最优 expectation += prob * branch_value return expectation

逻辑分成四步。第一步，遍历六个骰子面，每个面概率固定为 1/6，不需要考虑骰子是否公平之外的因素。第二步，判断该点数是否有合法走法：没有则空过，递归进入对方回合；有则对每个合法走法分别递归。第三步，把同一骰子面下的多个走法结果合并：当前行动方是 AI 自己时取 max，是对手时取 min。第四步，六个骰子面的分支值按概率加权求和，得到当前节点的期望值。

参数上最常见的疑问是"depth 减 1 放在哪里"。我建议放在每次递归调用里，而不是放在机会节点整体。原因很简单：空过分支和行动分支消耗的"回合数"是相同的，都是一次完整的掷骰行动轮。如果只在行动后减深度、空过不减，AI 会被迫偏好"能动的局面"，因为能动才能让搜索继续向下延伸，这个偏好是评估函数里没有的隐性偏差。

3.3 深度、分支因子与迭代加深：实盘响应时间怎么控制

爱因斯坦棋的分支因子比围棋小得多：每个骰子面最多一个合法走法（因为编号唯一），所以每个行动节点最多 3 个候选走法（直行、左斜、右斜），其中还有可能被己方棋子或边界过滤。理论上每层搜索最多展开 6 个骰子面乘以 3 个走法，约 18 个节点，但实际大部分骰子面只有 1 到 2 个走法，很多面直接空过。深度 4 的搜索规模通常在一万到十万节点之间，纯 Python 单线程也扛得住。

不过决策耗时不能只看平均节点数。如果某个局面中多颗棋子都接近对方底线，每个骰子面都有 2 到 3 个候选，分支因子会明显膨胀。我一般不用固定深度，而是用迭代加深加时间预算：

def choose_move(board, ai_side, time_budget_ms=100): best_move = None for depth in range(2, 8): start = time.time() move, value = search_root(board, depth, ai_side) elapsed = (time.time() - start) * 1000 if elapsed > time_budget_ms: break best_move = move if abs(value) >= 9000: # 已发现必胜走法，不再加深 break return best_move

search_root是最上层单独写的函数：遍历当前骰子面的所有可能，对每个可能选出最优走法，返回 (走法, 评估值)。迭代加深的收益是"随时可以中断"，即使上一次深度没有算完，手里也有上一轮完整的结果。实际对局中我会把时间预算设为 100 毫秒到 200 毫秒，深度通常落在 4 到 5。超过 5 层以后，收益明显变小，因为骰子随机性的方差会让深层评估值的置信度下降，这属于期望搜索本身的边界。

4. 评估函数与搜索参数：让 AI 看得再深也不怕骰子

4.1 评估函数拆清楚：别把赢棋条件混进特征分

评估函数是期望搜索里最容易偷懒也最容易出错的部分。常见的反例是：把"吃子"权重设得很高，AI 就会满盘追杀对方大子，结果对方一颗小卒子跑到了底线，直接输了。这说明评估函数里"终局条件"和"局面特征"必须严格分离。

终局条件永远在搜索函数开头单独判断，返回大分差；评估函数只处理"还没结束"的局面。我采用的评估特征有三类。第一是材料差：双方存活棋子数量差值，权重 10。第二是前进距离：每颗棋子离对方底线的行数差，权重 1.2。第三是机动性：当前局面下六个骰子面中可动面数量，权重 0.5。最后这条很多人忽略——可动面越多，说明骰子掷出空过的概率越低，间接代表局面掌控力。

def evaluate(board, ai_side): opp_side = opponent(ai_side) material = (len(board.pieces[ai_side]) - len(board.pieces[opp_side])) progress = 0.0 for side in (ai_side, opp_side): direction = 1 if side == 'black' else -1 base = 0 if side == 'black' else 4 for pid, (r, c) in board.pieces[side].items(): d = abs(r - base) # 已走距离，越大越接近对方底线 sign = 1 if side == ai_side else -1 progress += sign * d mobility = count_movable_faces(board, ai_side) return 10.0 * material + 1.2 * progress + 0.5 * mobility

注意 mobility 只统计 AI 自己的可动面数，不统计对方的。原因是对手可动面数已经通过对局过程隐含在棋子位置里了，再单独加一项会让它被重复计算。count_movable_faces的实现就是对六个骰子面依次调legal_moves并计数，五个格子的小棋盘开销很低，可以放心调用。这个评估函数的三个权重初始为 10 / 1.2 / 0.5，我建议先用默认值跑一批自对弈，再按胜率微调，不要拍脑袋频繁改动。

4.2 搜索参数怎么设：从节点预算到概率裁剪的边界

搜索参数比评估权重更影响实际体验。我常用的一组参数是：时间预算 150 毫秒、迭代加深初始深度 2、最大深度 6、终局判定分数 10000。这组参数在普通笔记本上单步耗时稳定在 20 到 100 毫秒之间，深度通常能走到 4 到 5。

关于概率裁剪要泼一盆冷水：期望搜索里对骰子分支做裁剪的收益远小于 Minimax 里的 alpha-beta 剪枝。因为每个骰子面概率相同、分支又少，剪掉任何一个都会直接破坏概率归一化。真正值得做的是对行动节点的 alpha-beta 剪枝——在 max/min 节点上可以安全剪枝，因为候选走法之间仍是确定性选择关系。不过 5x5 棋盘分支太窄，剪枝收益有限，我一般只在深度超过 5 时才开启。

4.3 转置表：节省重复搜索，但别让旧骰子污染新局面

转置表在期望搜索中的作用比 Minimax 里更微妙。爱因斯坦棋没有"玩家轮流移动"的固定回合结构——骰子点数决定行动方，而空过会直接跳到对手回合。同一个棋盘布局，可能对应"黑方刚掷完骰子待行动"和"白方刚掷完骰子待行动"两种不同状态。如果转置表的 key 只存棋盘格子布局，这两类状态会被混在一起，评估结果就废了。

正确的 key 必须包含四个要素：棋盘布局快照、当前行动方、骰子点数（如果是在行动节点缓存）、或者当前阶段（骰子节点/行动节点）。代价是转置表的命中率下降，但正确性优先。我通常在深度大于等于 4 时才启用转置表，浅层搜索的重复局面不多，不值得花序列化和哈希的开销。

5. 期望搜索落地避坑：从错算概率到平局误判的 5 个教训

5.1 骰子分支漏算"不可动"导致期望虚高

现象：AI 早期表现激进，经常主动送吃大子，胜率却上不去。排查发现搜索树里六个骰子面的概率加起来不等于 1。

原因：实现骰子分支时，直接过滤掉了legal_moves返回空列表的情况，只对可动分支做递归。空过分支被丢弃后，期望值等于"骰子总能动"的加权平均，AI 高估了自己后续回合的行动能力，于是敢走冒险棋。

解决：dice_branches里保留空 moves 分支，并在expectimax中显式处理"无走法则递归换人"。最好写一个 debug 函数打印每个骰子面的概率和 value，人工核对总和是否为 1。

5.2 评估函数把吃子权重抬高，导致 AI 送对方到家门口

现象：AI 见到能吃的子就追，哪怕对方另一颗子已经冲到底线前一步也视而不见，最终被一子偷家。

原因：材料差权重大于前进距离权重，且吃子带来的短期增益明显，搜索在有限深度内会优先选择"立刻吃子"的分支。这里的核心问题是赢棋条件（先到对方底线）没有独立于评估函数，被材料差稀释了。

解决：终局必须在搜索入口单独判断并返回大分差；评估函数中材料权重和前进距离权重的比值建议控制在 10 : 1.2 左右，并定期用终局局面回归测试。我在测试中专门构造了一组"对面即将到底、我方有吃子机会"的局面，确保 AI 每次都选择回防或冲刺而不是贪吃。

5.3 固定深度导致黑匣子式棋力波动

现象：同一套参数下，AI 有时强得离谱，有时连一步送死棋都看不出来。

原因：深度固定时，某些局面恰好能算到关键节点的深处，另一些局面因为分支稠密只能算到较浅位置，有效搜索深度不一致。更隐蔽的是——深度为偶数时 AI 倾向于保守等待，奇数时倾向激进进攻，这个波动跟实际局面无关，完全是奇偶性带来的系统性偏差。

解决：放弃固定深度，改用迭代加深加时间预算。时间预算保证每步思考量稳定，不会再出现"这步秒出、那步想半天"的体验差。如果必须固定深度，至少把深度设为奇数，因为爱因斯坦棋的胜负步数通常较短，奇数深度能多覆盖一次自己的行动。

5.4 转置表缓存了"旧骰子系统"导致重复局面误判

现象：AI 在接近终局的局面里反复走同一个循环动作，既不出击也不防守，像卡住了一样。

原因：转置表 key 只包含棋盘格子布局，不包含阶段信息。同一个布局可能来自不同骰子面和不同行动方，缓存的值被错误复用到另一个阶段，导致搜索认为该局面已经评估过并返回了历史值。

解决：key 里必须带上"当前行动方"和"阶段标记"（骰子阶段还是行动阶段），再加上步数计数器，用来排除重复局面导致的平局误判。我在转置表结构里加了一个version字段，每次搜索开始时递增，缓存项只在本轮搜索内生效，不跨回合复用。

5.5 每步重搜但搜索树根没刷新，棋力忽高忽低

现象：AI 前几步计算认真，中间某步突然选择了明显很差的走法，之后又恢复正常。

原因：部分实现为了性能，在每步之间复用上一回合的搜索树或缓存结果。但爱因斯坦棋每步掷骰后局面已经变了，复用的树根是旧骰子点的旧走法集，等于在错误的状态上做决策。

解决：每次掷骰后强制清空本步搜索缓存，从新根节点开始。这里的代价很小——5x5 棋盘深度 4 的搜索也就几万节点，重新算比复用一个错误缓存更省调试时间。我在选择走法前先打印一遍待选走法集合，确认集合与当前骰子点号一致，再进搜索。

6. 进阶验证：用自对弈和骰子模拟器校准期望搜索 AI

6.1 批量自对弈：先过一个基础胜率门槛

写一个自对弈脚本，让期望搜索 AI 对战一个"贪吃加前进"的基线策略 AI。基线策略规则很简单：能吃子就吃，没得吃就朝底线走，若多点可选则随机。这个基线棋力不高，但能暴露期望搜索 AI 的基础缺陷——比如明明能看清两步杀却走错，那就是搜索或评估实现有问题。

def battle(agent_a, agent_b, rounds=200, max_steps=120): win_a = win_b = draw = 0 total_steps = [] for i in range(rounds): board = Board() black_agent = agent_a if i % 2 == 0 else agent_b white_agent = agent_b if i % 2 == 0 else agent_a for step in range(max_steps): winner = board.winner() if winner: break side = 'black' if step % 2 == 0 else 'white' agent = black_agent if side == 'black' else white_agent move = agent(board, side) if move: board.apply(move) w = board.winner() if w == 'black': win_a += 1 if black_agent is agent_a else 0 win_b += 1 if black_agent is agent_b else 0 else: draw += 1 total_steps.append(step) return win_a, win_b, draw, sum(total_steps) / len(total_steps)

这个脚本里我先手轮换放在对局编号的奇偶上，避免先手优势干扰胜率统计。max_steps=120是为了兜底——理论上每回合都有可能空过，不能无限等下去。运行 200 局后，期望搜索 AI 对基线策略的胜率一般应该超过 70%，平均步数在 40 到 60 之间。如果胜率低于这个水平，先回去检查骰子分支概率和评估函数的终局判断。

6.2 骰子模拟器：验证机会节点的概率假设

期望搜索里最核心的假设是每个骰子面概率相等且独立。真实对局里，骰子点数对应的棋子可能已经被吃，导致该面空过；也可能棋子被己方棋子堵死，同样空过。我用一个模拟器统计"每个点数实际可动的频率"，与搜索里的 1/6 加权假设做对比：

def dice_distribution(board, side, trials=10000): movable_counts = [0] * 6 for _ in range(trials): die = random.randint(1, 6) if board.legal_moves(side, die): movable_counts[die - 1] += 1 return [c / trials for c in movable_counts]

如果某个点数长期不可动（比如编号 6 的棋子已被吃），模拟器会显示该点可动频率趋近 0。把这份统计和搜索树里该分支的出现频率对比，能快速发现"概率模型假设"和"实际规则实现"之间的偏差。这个验证在规则有改动时尤其重要——比如有人把骰子改成 1 到 6 但棋子只有 5 颗，必须重新推导空过概率。

6.3 决策日志：把每步的评估值留下来复盘

AI 棋力问题最难受的一点是"看不出哪步错"。我习惯在每次choose_move后写一行 JSONL 日志，包含当前局面、骰子点数、候选走法、每个走法的评估值、最终选择。复盘时看到"候选里有直接冲到底线的一步，评估值却低于一步吃子"，立刻就明白评估函数偏了，不需要反复黑箱试参数。

log_entry = { "step": step_count, "side": side, "die": die, "candidates": [str(m) for m in moves], "values": [round(v, 2) for v in branch_values], "chosen": str(move) }

评估值values和候选走法一一对应，这是最有用的调试素材。对比多局日志后我总结出一个习惯：先校准"终局判断"——确保所有必赢局面返回 10000 而不是 9999；再校准"前进距离"——让 AI 在有吃子和有冲刺两种选择时偏向后者；最后才动材料权重。这个顺序踩过太多次，希望帮到你。

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