期望搜索原理与实现：爱因斯坦棋博弈AI开发实战

简介：基于期望搜索算法构建的爱因斯坦棋博弈软件，面向计算机博弈大赛参赛者、棋类爱好者及人工智能算法学习者。压缩包共159个文件，约7.38MB，内含Python源码、png界面素材、sample对局样例、xml配置参数以及ttf字体等；其中png与ttf提供图形界面所需的贴图与字体，sample可作为对战输入示例，xml用于记录游戏配置，整体结构清晰，便于直接运行和二次开发。软件以爱因斯坦思想为灵感，采用期望搜索评估棋局走势，具有智能对战、实时走子建议及多种棋类扩展等特性；资源包含完整项目代码、界面资源与样例数据，可帮助读者理解博弈树搜索、期望值计算与策略评估方法，也可作为大赛作品或课程设计的参考。目前已有122人学习下载，适合希望将算法理论落地为完整应用的开发人群。

1. 期望搜索凭什么接管爱因斯坦棋：一个被骰子支配的博弈

基于期望搜索的爱因斯坦棋博弈软件，简单说就是让程序在一个掷骰子决定走哪个子的六乘六棋盘上，用“先把每种骰子点数的后果算成期望，再选最优走法”的方式下棋。第一次跑通这类项目的人多半会惊讶：明明每一步都受骰子支配，AI却能在中盘稳定拉开差距；把同样的搜索换成普通极小极大，立刻又变回“高手下棋靠运气”的观感。它适合正在做博弈AI、想从确定性棋种切到随机棋种的人，也适合拿一款规则不复杂但随机性足够强的棋类做期望搜索实战练手。这篇文章只讲一件事：怎么把规则建模、期望搜索、评估函数和参数调优一次串起来，写出能真正下棋的博弈软件。

2. 期望搜索原理拆解：从minimax到期望节点，为什么它比蒙特卡洛更适合爱因斯坦棋

2.1 minimax在随机游戏上的死穴：对手节点不等于随机节点

极小极大搜索的核心假设是“对手永远下出对我最差的一步”，所以在对手节点取最小值。这个假设对国际象棋、五子棋这类完全确定性的游戏成立，但放到爱因斯坦棋里就漏了一块：决定动哪个子的不是我方也不是对手，而是骰子。骰子没有恶意，它只是按六分之一概率吐出一个点数。如果你硬把所有分支都当成对手的恶意选择，搜索树会系统性高估坏点数的威胁，低估好点数的收益，最后选出来的走法往往不是“期望最优”，而是“在某个特定点数下最抗揍”。这就是随机博弈里minimax翻车的本质：它没有随机节点这个概念。

这里需要澄清一个常见误解：有人会把随机节点粗略地当成“多了一个对手”，于是给每个骰子点数都取最小值。这等于假设骰子每次都会掷出对你最不利的点数，是另一种偏执。正确做法是把随机节点单独建模，对六种点数按概率做加权平均，而不是取极值。这是期望搜索区别于minimax的最小改动，也是整篇文章后续所有代码的地基。

2.2 状态空间的三种节点：max节点、min节点与骰子机会节点

期望搜索把博弈树里的局面分成三类。第一类是决策节点，轮到当前玩家落子，己方取最大值、对方取最小值；第二类是机会节点，也就是“还没掷骰”的等待状态，取值为所有骰子点数对应子节点的概率加权和；第三类是终局节点，直接返回胜负分。放到爱因斯坦棋里，机会节点天然对应“玩家即将掷骰”的状态，决策节点对应“骰子已经掷出、玩家正在选择走法”的状态。

实现时有个小的视角技巧很省事。传统写法里白方取max、黑方取min，代码里要到处判断当前玩家是白还是黑。我一般会让搜索函数始终返回“以当前局面轮到谁为先手视角的价值”，然后递归回溯时统一加负号。这样决策节点只需要写一段max逻辑，对手的最优应对通过负号翻转自然变成当前玩家的最小值，代码量少一半。组合起来就是：机会节点算期望，决策节点取max，负号交给上一层回溯，这就是期望搜索在爱因斯坦棋上的最小闭环。

2.3 为什么选期望搜索而不是蒙特卡洛：三个选型理由

很多随机棋类项目会选择蒙特卡洛树搜索，因为它几乎不需要规则以外的知识，随机模拟打到底就能统计胜率。但爱因斯坦棋有它的特殊性：骰子点数只有六个，概率分布完全已知，分支数远小于围棋。这种情况下期望搜索的优势非常明确。第一，期望搜索不需要大量采样就能得到精确的骰子概率，六分之一就是六分之一，不会因为采样次数不够而抖动；第二，期望搜索天然支持“越搜越深”，迭代加深到四层以后仍有稳定的时间控制；第三，代码结构简单，不需要维护蒙特卡洛树里的置信区间和阈值参数，对一个六乘六小棋盘来说，期望搜索的性价比明显更高。

用一张表对比三种方案的取舍会更清楚：

从落地角度看，如果你只是要一个能跑通并持续优化的爱因斯坦棋AI，期望搜索是投入产出比最高的起点。等搜索深度和评估函数都做到瓶颈了，再考虑用蒙特卡洛做叶子评估也不迟。

3. 爱因斯坦棋博弈建模：把规则写成能搜索的代码框架

3.1 状态表示与初始排布：棋盘、玩家与骰子

写博弈软件的第一步不是搜索，而是把规则压缩成一个可复现的数据结构。我习惯用dataclass表示局面，字段就三个：棋盘矩阵、当前轮到谁、以及“骰子是否已经掷出”。骰子用一个可选整数表示，None代表还没掷，1到6代表已掷出的点数。这样设计可以直接区分机会节点和决策节点，搜索函数看一眼state.dice就能知道该走哪条分支。

from dataclasses import dataclass from typing import List, Optional, Tuple WHITE, BLACK = 1, -1 N = 6 INF = float("inf") @dataclass class State: board: list # 6x6矩阵，正数为白方棋子，负数为黑方棋子，0为空 player: int # 当前轮到谁：WHITE 或 BLACK dice: Optional[int] # None 表示还没掷骰，1~6 表示已掷出的点数 def initial_state() -> State: board = [[0] * N for _ in range(N)] # 白方左上角放1~6；黑方右下角对称放-1~-6 for i, num in enumerate([1, 2, 3]): board[0][i] = num board[1][i] = num + 3 for i, num in enumerate([1, 2, 3]): board[5][5 - i] = -num board[4][5 - i] = -(num + 3) return State(board=board, player=WHITE, dice=None)

这段代码把白棋放在前两行、前三列，黑棋放在后两行、后三列，形成对角对称的初始布局。为什么不用随机摆放？因为初始排布会影响早期搜索的期望值，固定开局方便做A/B对比，也方便复现同一盘棋。需要注意的是board里用正负号区分颜色，同时数字本身代表棋子编号1到6，这个编号在搜索中会被反复用到，是爱因斯坦棋规则的关键载体。

3.2 合法走法生成：骰子点数、离线自由选择与三种移动方向

爱因斯坦棋的走法只有一格，且只能朝对方底线方向移动，分直前方和两个斜前方，共三种可能目标格。真正让走法生成器复杂的是骰子规则：如果掷出的点数对应的棋子还在棋盘上，就必须移动那枚棋子；如果那枚棋子已经被吃，就可以自由选择任意一枚在盘棋子。这个“离线即自由”的逻辑是规则里最容易写错的地方，也是期望值计算里最有意思的部分。

def legal_moves(state: State) -> List[Tuple[int, int, int, int]]: """返回 (起始行, 起始列, 目标行, 目标列) 的列表，仅用于已掷骰状态""" moves = [] if state.dice is None: return moves pieces = [] for r in range(N): for c in range(N): v = state.board[r][c] if v * state.player > 0: pieces.append((r, c, v)) # 关键规则：骰子点数的棋子在场上则只能动它，否则自由选择 forced = [p for p in pieces if abs(p[2]) == state.dice] selected = forced if forced else pieces dr = 1 if state.player == WHITE else -1 for r, c, v in selected: for dc in (-1, 0, 1): nr, nc = r + dr, c + dc if not (0 <= nr < N and 0 <= nc < N): continue if state.board[nr][nc] * state.player > 0: continue # 目标格是己方棋子，不能落子 moves.append((r, c, nr, nc)) return moves

这里有三个参数值得解释。dr决定前进方向，白方行号递增、黑方行号递减，这是规则中“只能前进”的体现。dc遍历负一、零、一，对应左斜、直走、右斜三个方向，爱因斯坦棋里不存在横向走和后退。selected的挑选逻辑写完后要重点自测：如果掷出三号且三号已被吃，此时pieces里没有三号，selected会变成全部在场棋子，这才是自由选择的本意；如果你在代码里给这种情况额外乘以某个概率权重，后面期望搜索的概率就会算错，这一点在第5章专门说。

3.3 终局判定与胜负走向：影响搜索值的两个规则细节

终局判定直接影响搜索的返回值和评估函数的边界，必须写得干净。爱因斯坦棋有两种获胜方式：任意一枚棋子走到对方底线，或者吃光对方全部棋子。因为棋盘是六乘六，白方到达第五行即算胜利，黑方到达第零行即算胜利；吃光对方则直接在棋子遍历时判断。

def terminal(state: State) -> int: """返回 0=未终局，WHITE=白胜，BLACK=黑胜""" white_alive = False black_alive = False for r in range(N): for c in range(N): v = state.board[r][c] if v > 0: white_alive = True if r == N - 1: return WHITE elif v < 0: black_alive = True if r == 0: return BLACK if not white_alive: return BLACK if not black_alive: return WHITE return 0

这里有两个细节会深刻影响搜索值。第一，到达底线比吃光全部棋子更容易发生，所以搜索树里“前进”类走法的价值天然比“吃子”类走法高，评估函数必须反映这一点。第二，当一个棋子到达底线时，游戏立刻结束，不再检查其他条件，所以在搜索递归的第一步就要调terminal，否则后续节点会访问到已经不存在意义的状态。另有一个容易被忽略的点：棋盘初始时双方各六子，如果在某一步吃掉了对方的最后一个子，终端判定优先于走子合法性检查，不要在吃光后还试图生成后续走法。

4. 期望搜索引擎实现与参数标定：迭代加深、置换表与走法排序

4.1 核心递归：决策节点取max、机会节点取期望、回溯取负

搜索内核怎么写直接决定棋力和调试难度。我采用的约定是：search函数返回“以state.player为视角的价值”，白方胜为正值、黑方胜为负值。决策节点在当前玩家视角取max，策略评估后交给上层时加负号，把对手的意图翻转回己方价值。机会节点则对六个点数做等概率平均，这个平均不能被剪枝破坏，否则期望值计算会出现系统性偏差。

def search(state: State, depth: int, alpha: float, beta: float, cache: dict) -> float: t = terminal(state) if t: return 10000.0 if t == state.player else -10000.0 if depth <= 0: return evaluate(state, state.player) key = (str(state.board), state.player, state.dice, depth) if key in cache: return cache[key] if state.dice is None: # 机会节点：六种点数等概率全展开，不参与alpha-beta剪枝 total = 0.0 for dice in range(1, 7): s2 = State(board=state.board, player=state.player, dice=dice) total += search(s2, depth - 1, -INF, INF, cache) value = total / 6.0 else: # 决策节点：当前玩家视角取max，通过负号回溯对手价值 best = -INF for move in legal_moves(state): s2 = apply_move(state, move) val = -search(s2, depth - 1, -beta, -alpha, cache) best = max(best, val) alpha = max(alpha, val) if alpha >= beta: break value = best cache[key] = value return value

解释两个关键参数。第一个是alpha和beta，我只在决策节点使用窗口剪枝，机会节点内部强制传全开区间，这是为了保证期望值精确。如果让机会节点带着窗口继续向下剪，前面分支的剪枝结果会被平均进去，最后算出来的期望值就带上了“剪枝误差”。第二个是depth的消耗方式：每掷一次骰子算一层，每走一步棋也算一层，所以一个完整回合消耗两层。这个设定对时间预算影响很大，后面参数表里会看到。apply_move函数在前一章基础上翻转player并把dice重置为None，表示走完后轮到对手等待掷骰。

4.2 迭代加深与时间预算：一步棋在1.5秒内交卷

固定深度搜索有个问题：深度设小了棋力不够，设大了可能超时。常见做法是迭代加深，从深度一开始逐步加深，每层都完整搜索一遍，时间到了就停止增长，直接采用上一次完整深度的最佳走法。这样即使时间预算只有1.5秒，程序也能保证交出一个至少完成了一层搜索的合法走法，而不是卡在半途。

def choose_move(state: State, time_budget: float = 1.5, max_depth: int = 6) -> Optional[Tuple]: if state.dice is None: raise ValueError("必须先把骰子掷好再调用choose_move") moves = legal_moves(state) if not moves: return None best_move = moves[0] cache = {} deadline = time.time() + time_budget depth = 1 while depth <= max_depth and time.time() < deadline: candidate = None best_val = -INF for move in moves: s2 = apply_move(state, move) val = -search(s2, depth - 1, -INF, INF, cache) if val > best_val: best_val = val candidate = move if candidate is not None: best_move = candidate depth += 1 return best_move

这段代码的关键点是cache跨深度复用。每层搜索的key里包含depth字段，所以深度加深不会误用上一层的结果。best_val每次从负无穷重新开始，因为不同深度的绝对价值不可比，不能用上一层的best_val作初值。遍历走法时我用的是初始moves列表，它在整个迭代过程中不变，因为骰子已经掷定，不会新增走法。

4.3 走法排序与置换表：把分支因子压到能搜三层

期望搜索的分支因子比国际象棋还难看：一到六六个点数，每个点数最多三个目标格，自由选择时可能更多。如果不做优化，深度过三后基本等不出结果。我用的两个主要手段是走法排序和置换表。走法排序的价值在于决策节点的alpha-beta剪枝更早生效——把吃子和前进的走法排在前面，搜索能更快找到高质量分支，从而剪掉后面一堆平庸分支。

置换表的key必须包含board、player、dice和depth四个字段。很多人第一次写会落下dice，导致已掷骰和未掷骰的局面对撞缓存，搜索值彻底混乱。另一个容易踩的性能坑是缓存清理策略：表无限增长会拖慢哈希查找，我一般限制到20万到50万项，超出后整表清空重建。清空带来的损失远小于缓存污染导致的棋力波动。

4.4 参数表：深度、概率处理与缓存大小的推荐起点

下面这组参数是我在类似六乘六随机棋类上常用的起点，适合作为第一版跑通实验的配置：

这组参数不是玄学，背后是爱因斯坦棋的规则结构：骰子六分之一概率不算小，任何一个点数分支被删除都会直接改变期望值；而决策节点里走法之间价值差异大，排序后剪枝效果明显。如果你看到搜索结果抖动剧烈，先检查置换表key是否包含dice，再检查机会节点是否被意外剪枝，这两处是绝大多数期望搜索项目的前两个坑。

5. 避坑手册：期望搜索在爱因斯坦棋上的五个翻车现场

5.1 在期望节点上滥用Alpha-Beta剪枝，胜率反而暴跌

现象：代码改后搜索速度快了，但自对弈胜率从58%掉到46%，而且深度越高跌得越明显。原因：期望节点的值是六个分支的加权平均，任何分支的缺失都会直接把期望值拉偏；Alpha-Beta剪枝的原则只对min和max节点成立，它认为“这个分支不可能改变最终选择”，但期望节点里每个分支都贡献概率质量，不存在“不可能改变”。解决：机会节点全部展开，不参与剪枝，alpha和beta只向下传给真正的决策节点。如果你需要用窗口控制搜索规模，考虑用“全开区间传给机会节点内部”的方式，宁可牺牲部分剪枝效率也不能让期望值失真。

5.2 骰子概率合并不当：自由选择不是多出来的分支

现象：某次重构后AI特别喜欢在对方小号棋子离线时主动送子，后来发现模拟统计里骰子点数出现概率不再均匀。原因：代码在“该点数棋子离线”时把自由选择实现成了一条额外分支，相当于把某个点数从六分之一抬成了三分之一。这是对规则的理解错误：离线自由选择改变的是“可以动哪些棋子”，不是“该点数出现的概率”。解决：骰子循环永远固定遍历一到六，每个点数权重恒为六分之一；在该点数下再检查对应棋子是否在场，决定走法生成器走“强制移动”还是“自由选择”。想验证这一点，跑一万次掷骰并统计各点数被选中的次数，差值应该在统计误差内。

5.3 评估函数贪吃：吃掉对方小号子可能是负收益

现象：调参时把“棋子数差”的权重调大，AI开始狂吃小号子，结果中盘经常被对手的“自由选择”反推。原因：爱因斯坦棋里吃掉对方n号子，对手以后再掷到n时就可以自由移动任意棋子，相当于把对方的一个固定走法解锁成万能走法。编号越小的棋子越容易被频繁掷到，这个解锁收益越高。解决：评估函数不能只数棋子，要给“远端自由度”做补偿。常见做法是统计双方离线棋子中最小的编号，给己方离线小号子适度加分，抵消掉对方吃子带来的灵活性收益。这个权重需要自对弈标定，从2.0左右起步，敏感度很高。

5.4 随机种子不固定：调参变成摸黑

现象：同一套权重上午胜率68%，下午换台机器变51%，找不到代码改动点。原因：对局里骰子序列完全不同，单局甚至几百局的胜负波动都被随机性吃掉了。解决：所有对局脚本入口用random.Random(seed)显式传入种子，评估函数对比用同一批种子跑同样的对局序列。每轮参数调整后至少跑一千局，记录胜率标准差。电子游戏里这叫可复现实验，博弈AI里这是调参底线；不复现的优化等于没有优化。

5.5 置换表缓存污染：已掷骰与未掷骰状态互相串味

现象：搜索速度上来了，但相同局面下棋路时好时坏，排查发现缓存命中率高达45%却仍然出昏招。原因：置换表key漏了state.dice字段。一个未掷骰的等待状态和一个已掷骰的决策状态共享同一个key，搜索值被互相覆盖。这个bug隐蔽在棋力波动里，很难靠看棋发现。解决：key必须包含board、player、dice、depth四个字段；进一步保险起见，把置换表按“已掷骰”和“未掷骰”拆成两张，逻辑上更不容易串。缓存上限到达后整表清空是安全的，因为搜索值只用于当前一步决策，不需要长期保留。

6. 验证与进阶：固定种子自对弈与rollout叶子评估

6.1 固定种子自对弈脚本：看胜率而不是看棋感

棋感会骗人，统计不会。我习惯把两个不同配置的AI放在同一批种子里对弈，记录谁先到胜局数。脚本骨架是循环掷骰、调choose_move、走子，直到terminal返回结果。固定种子序列后用相同初始化重跑，胜率变化超过两个百分点基本可以认定是配置差异，而不是运气。

6.2 用快速终局模拟替代静态叶子评估：同深度再拉3到8个点

静态评估函数再调也有上限，因为它是人对棋形的压缩理解。更进一步的常见做法是在搜索叶子节点跑快速终局模拟：从叶子状态开始，用简单策略（优先吃子、其次向着底线冲）随机掷骰打到底，重复32到64次，用胜率替代静态评估值。这一招对随机棋类尤其有效，因为期望搜索的叶子正好是“尚未掷骰”的等待状态，模拟天然能覆盖未来骰子分布。代价是每片叶子慢几十倍，所以一般只接在深度二到三的搜索树后面，并且rollouts控制在32到64次。实测下来，同深度比纯静态评估能再拉3到8个胜率点，值得投入。

6.3 我的验证习惯：没有基线对比的改进都不算数

我的习惯是先保存一套“深度二加静态评估”的基线配置，以后每改动一个评估权重、每加深一层搜索，都跑同一批种子对比。低于60%胜率的改动直接丢弃，高于60%才继续观察。期望搜索这个方向做到最后，瓶颈往往不是搜索深度而是评估函数对“自由选择”的理解是否准确。如果你准备从这个标题开始动手，我的建议是先把第3章的规则框架跑通，再加上第4章的期望搜索，最后再回头调评估函数。希望帮到你。

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