简介基于期望搜索的爱因斯坦棋博弈软件是一份面向计算机博弈大赛参赛者、棋类爱好者及编程学习者的Python项目资源。该项目以爱因斯坦棋为对局场景通过期望搜索算法评估局面并给出决策适合用于算法研究、课设或竞赛二次开发。压缩包共159个文件大小约7.38MB内容以项目源码与资源文件为主55个png图像为界面与棋子素材另有xml配置、sample示例、ttf字体及py程序文件等整体目录将代码、素材和配置分离结构较完整便于按模块阅读。目前已有122人学习下载。配套资料可帮助读者快速理解期望搜索在棋类博弈中的落地方式包含完整工程入口、界面渲染与算法配置可复用整套界面与算法框架进行扩展改造也可直接作为计算机博弈大赛的参赛方案参考。1. 期望搜索与爱因斯坦棋这个组合要解决什么我在做一个人机对弈的爱因斯坦棋博弈软件时第一版 AI 直接套了 minimax结果它像没见过骰子一样永远按最坏点数去设计走法经常被随机落子的玩家打得很难看。后来把博弈树里的骰子节点换成期望搜索才真正把“掷出几就走几号棋子”这个随机环节装进搜索流程里。期望搜索适合爱因斯坦棋是因为它的随机性来自明确的均匀骰子而不是庞大不可枚举的随机局面你不需要大量采样直接对 6 个点数做加权求和就能得到精确的期望值。这篇文章面向想自己实现或改造此类棋牌 AI 的开发者我会从规则建模、搜索算法、评估函数、常见坑点到调参技巧一路拆开讲。2. 爱因斯坦棋规则建模状态表示、骰子规则与移动生成2.1 用一张 5x5 棋盘和 pieces 字典表示状态爱因斯坦棋的核心难点不在棋盘大而在“骰子决定棋子编号”以及“被吃的棋子可能回场”。我建议把棋盘建模成 5x5 坐标用pieces[color][num]记录每个编号棋子的位置而不是只用二维数组存颜色。二维数组能快速判断占用但定位“某编号棋子现在在哪”会变成一次全盘扫描对期望搜索来说每种骰子点数都要生成一次移动列表扫描次数太多。下面是我在项目里使用的最小状态模型class EinSteinState: N 5 # 白方从下方开始黑方从上方开始 # 白方起始三角编号 1-6 按顺序放入 START { 0: [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)], 1: [(4, 4), (4, 3), (3, 4), (3, 3), (2, 4), (2, 3)], } def __init__(self): self.occ {} # (r, c) - (color, number) self.pieces {0: {}, 1: {}} for color, cells in self.START.items(): for i, cell in enumerate(cells): num i 1 self.pieces[color][num] cell self.occ[cell] (color, num) self.turn 0 # 0 表示白方1 表示黑方这套表示把“某个编号的棋子在不在棋盘上”变成一次字典查询比遍历二维数组快很多。occ负责碰撞和吃子判断pieces负责按骰子编号快速取棋子。如果你玩的爱因斯坦棋版本要求黑方编号镜像排列把START[1]的列表顺序反过来即可搜索算法不需要动。黑棋和白棋共用同一个N5棋盘起始三角各占 6 个格子中间区域留给棋子互相吃和追逐。坐标我用(row, col)row 0 是白方底线row 4 是黑方底线。这个约定在后续计算“到终点距离”时非常方便统一用国王距离就行。2.2 移动生成骰子点数、吃子与复活规则爱因斯坦棋的回合规则是掷出一个 1 到 6 的骰子你必须移动编号对应的棋子。这个“必须”很关键它让每个决策节点的合法动作集合完全由骰子结果决定。棋子移动一步可以走到相邻的八个方向之一目标格如果为空就走过去如果是对方棋子就吃下如果是自己的棋子就不能走。被吃掉的棋子还有一个常见规则掷到对应编号时可以把棋子放回自己起始三角的空位。我在这套实现里采用“回到起始三角空位”的变体并且只生成第一个空位作动作避免动作集合过大。如果你要严格还原某些平台的“固定回场点”只需要修改place分支的候选格列表。def legal_moves(self, die): color self.turn moves [] cur self.pieces[color].get(die) if cur is not None: r, c cur for dr in (-1, 0, 1): for dc in (-1, 0, 1): if dr 0 and dc 0: continue nr, nc r dr, c dc if not (0 nr self.N and 0 nc self.N): continue if (nr, nc) in self.occ and self.occ[(nr, nc)][0] color: continue # 自己的棋子挡路 moves.append((move, die, (r, c), (nr, nc))) else: # 棋子被吃或尚未入场放回起始三角的空位 for cell in self.START[color]: if cell not in self.occ: moves.append((place, die, None, cell)) break if not moves: moves.append((pass,)) return moves这段代码有三个值得注意的参数点。第一八方向用dr和dc双层循环实现包含了横、竖和两条斜线如果你的规则只允许接邻走不包含斜向把abs(dr) abs(dc) 1加进条件即可。第二吃子逻辑没有单独写因为目标格是否有敌方棋子不影响移动合法性只要不是自己的棋子就能进。第三pass动作是为了防止“当前编号棋子在棋盘外且起始三角全满”时动作列表为空否则期望搜索里会出现概率空洞。应用动作时最需要注意的是吃子后要把被吃方的pieces置为None否则后面用骰子编号找棋子时仍然会找到旧坐标def apply(self, move): import copy ns copy.deepcopy(self) if move[0] move: _, num, src, target move color ns.turn ns.occ.pop(src) if target in ns.occ: enemy_color, enemy_num ns.occ[target] ns.pieces[enemy_color][enemy_num] None ns.occ[target] (color, num) ns.pieces[color][num] target elif move[0] place: _, num, _, target move color ns.turn ns.occ[target] (color, num) ns.pieces[color][num] target # pass 不改棋盘 ns.turn 1 - ns.turn return ns这里我用deepcopy保证每次搜索分支互不污染缺点是状态复制开销大。等你把搜索深度调到 6 以上建议改成共享棋盘加撤销栈否则单步搜索节点会成倍膨胀。2.3 终局判断先进入对方起始三角即胜爱因斯坦棋的终局规则在不同线上平台有细微差别但我实现时采用最主流的一条任意棋子进入对方起始三角区域立刻获胜不需要吃光所有棋子。这个规则对期望搜索影响很大因为评估函数里必须把“一步踏入对方三角”看作极高价值而不是普通吃子。def terminal_result(self): for color in (0, 1): for num, pos in self.pieces[color].items(): if pos is None: continue if pos in self.START[1 - color]: return color return None注意这个判断不能写成“所在格被对方棋子占据”才算因为进入空的目标格同样获胜。你只要进入对方起始三角走完这一步就结束所以搜索里的终局节点通常出现在某个移动动作之后而不是移动之前。3. 期望搜索实现从 max/min 节点到机会节点的代码落地3.1 为什么最小最大搜索直接套会翻车爱因斯坦棋是双人零和博弈表面看起来可以用 minimax。但你仔细拆解一轮行动先掷骰子再选择走法。骰子不是对手也不是队友它只按均匀概率产生结果。minimax 的min层会把所有骰子点数当作“对手会选择对我最不利的点数”这会导致搜索得到的是最坏情况下的最优解而不是期望意义上的最优解。举例说假设当前你掷到 1 立刻能冲进对方三角获胜但掷到别的点数会被反杀。minimax 会把“掷到 1 获胜”和“掷到别的点数被反杀”统统按最坏值处理最终 AI 宁可走一个四平八稳的中间步。而真实对局里骰子每个点数出现概率都是 1/6你应该把六条分支的收益做加权平均然后选择平均期望最高的动作。这就是期望搜索的核心差别机会节点不再取min而是取概率加权和。当然你也可以用蒙特卡洛树搜索去近似这个期望值但对 5x5 棋盘、6 个骰子点数的游戏来说精确枚举骰子分支并不贵。期望搜索在这个博弈软件里比 MCTS 更容易解释也不会因为采样不足产生波动。这是我把期望搜索作为首选的原因。3.2 期望搜索的递归结构与核心代码期望搜索的递归结构有三类节点当前行动方的决策节点、骰子机会节点、终局叶子节点。在每层递归里我先对 6 个骰子点数做循环再在给定点数下枚举合法移动最后把决策节点的最优收益乘以对应概率累加。下面是完整的搜索函数def expectimax(state, depth, root): winner state.terminal_result() if winner is not None: return 10000 if winner root else -10000 if depth 0: return evaluate(state, root) total 0.0 for die in range(1, 7): moves state.legal_moves(die) if state.turn root: best -1e9 for mv in moves: v expectimax(state.apply(mv), depth - 1, root) best max(best, v) else: best 1e9 for mv in moves: v expectimax(state.apply(mv), depth - 1, root) best min(best, v) total (1.0 / 6.0) * best return total逻辑说明root是调用搜索时固定不变的根玩家视角。当state.turn root当前层是“我”选择走法取最大值当state.turn ! root当前层是“对方”选择走法取最小值。骰子没有出现在max/min分支里而是包在外层循环六个结果各乘 1/6。这样每个递归调用正好推进一个完整回合这一回合包括“掷骰子”和“走一步”所以depth的单位是回合不是半回合。这个实现有一个容易忽略的参数细节depth 0时直接返回静态评估值没有先判断当前层是否可能终局。实际使用时应该先判断terminal_result再判断depth否则会出现“明明已经获胜却因为搜索深度为 0 而把胜利局面估成普通分数”的问题。终局判断必须放在深度判断之前代码里我已经这样处理。3.3 评估函数与四个搜索参数期望搜索的搜索层负责概率评估层负责静态优劣。爱因斯坦棋的评估函数我拆成三个特征棋子到对方起始三角的最小国王距离、存活棋子数、当前能一步吃到的对方棋子数量。def king_dist(pos, cells): r, c pos return min(max(abs(r - r2), abs(c - c2)) for r2, c2 in cells) def evaluate(state, root): score 0.0 for color in (0, 1): sign 1.0 if color root else -1.0 dist_sum 0.0 alive 0 capture_chances 0 for _, pos in state.pieces[color].items(): if pos is None: continue alive 1 dist_sum king_dist(pos, state.START[1 - color]) for _, pos in state.pieces[color].items(): if pos is None: continue r, c pos for dr in (-1, 0, 1): for dc in (-1, 0, 1): if dr 0 and dc 0: continue nr, nc r dr, c dc if (nr, nc) in state.occ and state.occ[(nr, nc)][0] ! color: capture_chances 1 score sign * (-2.0 * dist_sum 10.0 * alive 3.0 * capture_chances) return score这里king_dist用的是国王走法距离因为棋子一步最多斜一格对每个目标格取切比雪夫距离再对所有目标格取最小值。alive权重给大因为少一个棋子就少一个骰子点数的应对能力被吃的编号意味着该点数可能只能回场移动选择大幅受限。capture_chances是进攻性特征但它只统计一步能吃的候选不能代表长期计划。搜索参数方面我用下面这张表作为初始配置参数值说明搜索深度4 到 6 回合深度越大越慢6 回合在标量 Python 里约 1 秒左右骰子枚举恒定 1/6六个点数全展开不做采样超时控制单步 300ms超过时间返回当前迭代加深的最好结果叶子评估距离/存活/吃子权重按 2 / 10 / 3 起步如果你的博弈软件面向实时人机对弈我建议先固定深度 4 跑通整局再开迭代加深升到 6。深度每加一层搜索时间大约膨胀 6 倍因为每个回合都多展开一次骰子循环。对爱因斯坦棋这种小棋盘游戏6 回合已经能让 AI 具备明显的进攻意识超过 8 回合收益就开始递减。4. 避坑期望搜索在爱因斯坦棋上的五个常见翻车点4.1 骰子平均被 -inf 污染搜索输出 NaN现象搜索跑着跑着返回值变成-inf或者NaNAI 从此开始乱走甚至直接跳过回合。原因我在最初版本里把best统一初始化为-1e9在对手分支也用了同一个初值。结果某个骰子点数下合法动作列表为空对手分支没有任何min可比较best保留负无穷再乘上 1/6 就把整层期望值拉成负无穷。期望搜索里机会节点必须对每个点数都产出一个有限值任何一个分支异常都会污染整个平均值。解决两个办法同时用。第一legal_moves末尾永远补一个pass动作保证动作列表不可能为空。第二max分支初值用负大数min分支初值用正大数不要混用。我后来还在total ...前加了assert abs(best) 1e8的调试断言这类问题再也没出现过。4.2 用 minimax 替代期望搜索AI 变成“最坏情况主义者”现象AI 在优势局面下不敢冲终点反而缩在后面防守或者在多个可行走法里选了一个当前收益低但“最坏也坏不到哪去”的方案。原因这是把骰子节点错误地当成min节点的必然结果。minimax 认为对手能替我们选择骰子点数所以会优先避开那些“掷到某个数就输”的分支哪怕这个点数只有 1/6 概率。实际上骰子均匀随机你应该为每个点数乘以 1/6 再相加而不是取最小值。解决把for die in range(1, 7)的循环从min(best, v)改成加权累加。更稳妥的做法是像我第 3 章代码那样把骰子循环直接放在递归函数里不要试图在 minimax 外面套一层“伪随机”否则很容易把概率节点放错位置。4.3 深度按半回合设置导致双方搜索回合数不对称现象AI 用深度 11 时表现很好换成深度 12 反而变弱或者同一局面白方视角比黑方视角明显傻。原因搜索深度如果用“移动步数”来定义会出现一方多搜索了一个完整回合。举例说深度 5 可能让白方搜索了 3 个己方回合和 2 个对方回合黑方做根节点时又变成另一种结构。期望搜索的结果对搜索层数很敏感奇数半回合和偶数半回合的评估差异会被骰子概率放大。解决把深度单位固定为“完整回合”每层递归只减一并且同时包含“掷骰子”和“走一步”两个过程。我做自对弈测试时对比了深度 4、5、6 三档发现偶数和奇数之间的差异明显小于“完整回合1”的变化这验证了回合深度的稳定性。4.4 复活规则实现不一致测试用例总翻车现象同一个棋谱在本地复现时AI 合法动作比线上平台少或者某个棋子被吃后线上能回场本地搜索却只能pass。原因爱因斯坦棋存在多种规则变体。有的平台规定被吃棋子只能从固定入口回场有的规定回到底线任意空位有的规定入口被占则该回合跳过。如果只按其中一种规则写legal_moves换一个平台做对照测试棋谱立刻对不上。解决把规则差异做成配置项不要在搜索函数里写死。我先定义了PLACE_TO_ANY_EMPTY True和ENTRY_ONLY False两个开关再写一个规则测试脚本对每个骰子点数、每个状态跑一遍合法动作数量。换规则时只改这组开关搜索算法完全不动这样能快速定位是规则问题还是搜索问题。4.5 评估函数只看吃子AI 错过直接获胜现象棋盘上有一个子下一步就能踏入对方起始三角AI 却跑去吃另一个无关的棋子导致获胜晚了一步被对方反杀。原因评估函数给capture_chances的权重太高而“接近终点”只体现在距离特征里。距离特征和获胜之间存在断层距离从 2 变到 1 可能意味着下一回合能赢但静态评估只多算了2 * 1分吃子特征却一次加 3 分搜索就会选择吃子。解决在评估函数外层加分阶段判断如果移一步后terminal_result会返回当前玩家直接给1000分支分而不是依赖评估函数。另一个办法是把距离特征改成“是否一步可达终点”的布尔值权重至少给到 50。实战中我两个都做了确保 AI 在临门一脚时优先终结比赛。5. 进阶置换表、迭代加深与自对弈调参5.1 置换表缓存期望值而不是缓存最佳走法期望搜索的树里骰子节点是确定的 1/6 组合所以从不同路径到达同一个棋盘状态时后续期望值是相同的。这种重复在爱因斯坦棋里不算多但吃子回场机制会产生少量重复状态值得用置换表缓存。实现时一定把depth和root放进缓存键因为不同搜索深度下叶子评估边界不同不同根玩家视角下的收益方向也不同def expectimax_tt(state, depth, root): key (state.encode(), depth, root) if key in self.tt: return self.tt[key] if depth 0 or state.terminal_result() is not None: val evaluate(state, root) if depth 0 else \ (10000 if state.terminal_result() root else -10000) self.tt[key] val return val total 0.0 for die in range(1, 7): moves state.legal_moves(die) # max/min 分支同普通 expectimax ... self.tt[key] total return totalstate.encode()我建议把pieces的六个坐标加上turn拼成元组不要用二维数组全盘编码否则键太长且生成慢。置换表不能当后悔药用一旦规则或评估权重改变直接清空表再开新局不要复用旧数据否则会调出奇怪的行为。5.2 迭代加深把时间预算和搜索深度解耦期望搜索没有 alpha-beta 剪枝那种天然加速但可以用迭代加深给博弈软件一个平滑的难度曲线。先用深度 1 搜索保存最佳走法再用深度 2 搜索把上一层的首选走法放在动作列表第一位往往能提前命中较优分支。每次超时检查放在骰子循环外层而不是动作循环内部否则检查次数太多会拖慢速度。我一般把单步时间预算设为 300ms。如果深度 4 能在 50ms 内完成就继续尝试深度 5如果深度 5 超过 300ms就返回上一层的走法。这样人机对弈不会因为偶尔一次长搜索卡顿AI 弱棋和高棋之间的差距只是深度不同逻辑完全一致。5.3 自对弈调参先固定搜索深度再动评估权重评估函数的三个初始权重距离 2、存活 10、吃子 3不是拍脑袋拍出来的。我的做法是写一个自对弈脚本让同样的期望搜索用不同权重打几百局固定深度 4统计胜率。先调距离和存活的比值再调吃子权重最后才调搜索深度。一个常见的调参误区是同时改深度和权重这样你分不清胜率变化到底来自哪个变量。我会把深度固定为 4先从(2, 10, 3)跑到(4, 10, 3)看接近终点的权重是否让 AI 更快获胜然后再从(4, 10, 3)跑到(4, 10, 5)看进攻性是否过度。每个参数组合至少跑 200 局用胜率而不是单局好看来判断。我现在做任何策略类棋牌 AI 的第一版都会先问一句随机环节在哪个位置如果存在骰子这类机会节点大概率应该先期望搜索而不是 minimax。这个判断帮我少走了很多弯路也希望帮到你。本文还有配套的精品资源点击获取