期望搜索实战：用Expectimax实现爱因斯坦棋AI

简介一套基于期望搜索算法的爱因斯坦棋博弈软件面向计算机博弈大赛参赛者、棋类爱好者及高校师生。项目以Python编写通过期望搜索分析棋局并制定策略同时提供实时反馈与多种棋类支持兼顾对弈和教学用途。压缩包共159个文件、7.38MB内含PNG界面资源、sample样本数据、XML配置、TTF字体、patch补丁及master/head等工程对象覆盖界面渲染、数据组织与算法逻辑多个模块结构清晰便于直接查看源码和二次开发。目前已有122人学习下载。软件以爱因斯坦式思维切入博弈决策适合研究期望搜索在实际棋类对战中的落地方式也可作为计算机博弈大赛备赛、课程设计与个人项目的参考资料。读者可从中获取完整的Python项目工程、图形界面素材和样本数据用于复现核心算法或改造自己的博弈程序。1. 期望搜索与爱因斯坦棋为什么这个组合值得你花一个周末做了几年棋牌 AI我越来越觉得“骰子棋”才是博弈搜索里最被低估的试炼场。普通象棋用 Minimax 就能跑得不错但一旦引入骰子局面不再是一棵纯对抗树而是“随机分支 对抗分支”的混合体。这时候期望搜索Expectimax才是正统解法而爱因斯坦棋——这是一款 5×5 棋盘、六枚带编号棋子、靠掷骰决定哪枚棋子能走的德式桌游——恰好把随机性和策略性揉到了同一盘棋里。它不像围棋那样深不可测也不像井字棋那样一眼望穿规则简单到新手十分钟能上手但搜索树的形状比同规模的象棋复杂得多。这篇文章会带你从头实现一个能下完整盘棋的期望搜索引擎包括骰子建模、动作生成、评估函数设计和五个我实际踩过的坑。适合有一定 Python 基础、想理解“随机博弈怎么用程序算清楚”的开发者也适合想做课程设计或桌面 AI 项目但不想撞车的人。2. 先把规则盘清楚爱因斯坦棋的棋盘、走法与骰子建模很多人写博弈树翻车不是因为搜索算法写错而是规则建模从一开始就漏了细节。爱因斯坦棋的规则看似简单但骰子与棋子的对应关系、底线判定、吃子规则这三件事每一件都有隐蔽的边角。这一章先把规则翻译成数据结构再落成可执行的代码。2.1 规则棋盘建模坐标系的选型决定后面所有代码的写法爱因斯坦棋的棋盘是 5×5双方各 6 枚棋子编号从 1 到 6。开局的摆法很讲究白棋在左下角两行各放三枚第 0 行和第 1 行黑棋在右上角两行各放三枚第 3 行和第 4 行。每一位玩家的目标都是让任意一枚棋子冲到对方的底线——对白方来说就是第 4 行对黑方来说是第 0 行。我一般用(row, col)元组表示坐标row 从 0白方底线到 4黑方底线col 从 0 到 4。白方棋子只能向 row 增大的方向前进黑方棋子只能向 row 减小的方向前进。每枚棋子的移动方向有三个直走一格不改变列号以及斜前方两格。直走可以吃子斜走只能进入空格。这个区别非常关键它意味着“吃子”和“位移”是两套规则不能共用同一个移动生成函数。方向向量的定义决定了后面所有动作枚举的写法。白方的三个方向是(1, 0)、(1, -1)、(1, 1)黑方对应的就是(-1, 0)、(-1, -1)、(-1, 1)。为什么不把方向做成黑方也用正方向因为那样坐标换算和吃子判断都会多一层 if。让每个玩家持有自己的方向表语义最直观。棋子编号与位置的对应关系我建议用字典而不是列表。原因是下落子的时候需要频繁地按编号查位置、按位置查编号字典双向维护的成本最低。如果你追求极致性能可以用两个长度为 7 的数组下标就是棋子编号这样查询是 O(1) 且没有哈希开销。我自己的实现先用字典确认逻辑正确后再优化成数组别一上来就写高性能代码调试期会痛不欲生。2.2 骰子概率表与随机节点把“运气”变成可计算的概率分布爱因斯坦棋每回合先掷一颗六面骰子掷出的点数决定玩家可以移动哪一枚棋子。比如掷出 3就只能移动编号为 3 的棋子。这里有一个容易忽略的规则变体如果骰子点数对应的棋子已经到达对方底线也就是已经赢了玩家可以任选一枚棋子移动。这个“自由选择”规则在标准规则里存在但很多教程的简化版本会把它裁掉。从博弈树的角度看骰子就是一个典型的 chance 节点它有 6 个分支每个分支的概率是 1/6。如果某个点数对应的棋子已经到达底线则该分支内部不再继续按骰子分叉而是变成一个由当前玩家自由选择的确定性动作。这个细节直接决定搜索树的形状——骰子节点下挂的不是 6 个等价的走法列表而是“对应点数棋子的全部合法走法”其中最多有一个分支会展开成多倍的动作。我在代码里把概率表做成一个显式的列表而不是每次现场计算DICE [1, 2, 3, 4, 5, 6] DICE_PROB {1: 1/6, 2: 1/6, 3: 1/6, 4: 1/6, 5: 1/6, 6: 1/6}这样做的理由是期望搜索在计算期望值时需要按概率加权求和如果你在搜索函数里硬编码1/6将来想支持“加权骰子”或者“命运牌”这类扩展就得改搜索函数。把概率表独立出来搜索代码只关心prob从哪里来不关心它是 1/6 还是别的值。代码的耦合度低调试的时候也能单独打印某个点数的概率值验证分叉是否正确。掷骰之后轮到当前玩家行动此时是一个确定性的行棋节点。所以一个完整的回合在搜索树上的形态是chance 节点掷骰→ max 节点当前玩家选动作→ 对手的 chance 节点对手掷骰→ 对手的 max 节点如此交替。这个交替关系必须画清楚因为后面写递归函数时is_chance_node的判断条件就依赖这个结构。2.3 动作生成器合法走法的枚举与去重动作生成是每次搜索调用最频繁的函数它的性能直接决定搜索深度。常见做法是写一个generate_moves(board, player, die_value)函数接收当前棋盘、玩家和骰子点数返回所有合法动作的列表。每个动作可以用一个(from_pos, to_pos)元组表示吃子不需要额外标记因为目标位置有敌方棋子与否已经蕴含在to_pos里了。生成动作的核心逻辑是先取出骰子点数对应的那枚棋子检查它是否还在棋盘上、是否已经到达底线。如果不在棋盘上被吃掉了那这枚棋子无法行动——这是新手最容易忘的边界情况。规则上是“只能移动编号 X 的棋子”但如果编号 X 的棋子被吃了玩家不能随意选择其他棋子而是相当于被迫放弃这一回合直接进入对手回合。def generate_moves(board, player, die_value): piece_pos board.pieces[player][die_value] if piece_pos is None: return [] # 对应棋子已被吃掉本回合无合法动作 row, col piece_pos if row player_goal_row(player): # 已到达底线按自由选择规则尝试所有棋子的合法动作 moves [] for p in range(1, 7): pos board.pieces[player][p] if pos is not None: moves.extend(_piece_moves(board, player, p, pos)) return moves return _piece_moves(board, player, die_value, piece_pos)_piece_moves负责单枚棋子的方向检查遍历该玩家的三个方向向量计算目标坐标然后判断目标格是否越界、是否被己方棋子占据。如果目标是空格加入动作如果目标是敌方棋子且方向是直走列号不变加入动作斜方向碰到敌方棋子则跳过。逻辑说明这里把“自由选择”规则的判断放在动作生成器而不是搜索函数里是有意的。如果放在搜索函数里你需要在 chance 节点的每个分支再做一次分支判断逻辑分散且容易重复生成动作。动作生成器统一处理之后搜索树的分支数在源头就收敛了。参数die_value是这次掷骰的结果由 chance 节点传入动作生成器本身不关心骰子的概率是多少。参数说明player_goal_row(player)返回白棋的 4 或黑棋的 0_piece_moves里的方向表来自 2.1 定义的DIRECTIONS[player]。如果你后面加入“任意选子”的变体规则只需要改generate_moves的中间分支搜索函数完全不用动。3. 期望搜索算法从 Minimax 到 Expectimax 的改动量比你想象的小如果你已经写过 Minimax那么期望搜索的核心思路可以一句话概括把对手节点里的最小值运算替换成按骰子概率加权的期望值运算。但这句话落地时有三处细节要补随机节点的终止条件、对手模型的选型、以及剪枝策略的失效。这一章从这三个点展开。3.1 Minimax 的局限没有随机节点的博弈树是残缺的经典的 Minimax 假设博弈双方轮流走棋每一步都是确定性的。这个假设在象棋、五子棋、黑白棋里成立因为走子完全由棋手决定。但爱因斯坦棋的每一步之前都多了一个掷骰动作而掷骰的结果不由任何一方控制。如果强行用 Minimax你有两种粗糙的做法一是把所有骰子结果当成等概率的对手步来枚举然后把 6 个分支的值取平均——这实际上已经是期望搜索的雏形二是只考虑“最可能的骰子点数”也就是把随机性砍掉只搜一个分支。第二种做法在实战中会输得很惨因为对手的回合同样有骰子你忽略随机性等于忽略对手所有的可能的应变。更本质的问题在于 Minimax 的语义是“最小化对手的最佳收益”而随机节点的语义是“计算所有可能结果的概率加权值”。玩家的策略要在随机结果之上取最优对手的策略也要在随机结果之上取最优。二者像是两层夹心玩家选动作时看的是“对手下一步掷骰后能拿到的最优值”的期望而不是一个确定的最小值。所以搜索树的每个切面都要分清楚当前是决策节点还是机会节点处理方式完全不同。3.2 Expectimax 的核心区别把 min 节点换成 chance 节点期望搜索的递归结构和 Minimax 几乎一致差别就在节点类型上。我给出一个 Python 风格的伪代码实现方便你直接对照自己的代码改def expectimax(board, depth, current_player, is_chanceFalse): # 终止条件深度耗尽或已分胜负 if depth 0 or board.is_terminal(): return evaluate(board, current_player) # 机会节点掷骰阶段对每个骰子面求期望值 if is_chance: total 0.0 for die in DICE: prob DICE_PROB[die] # 当前玩家掷骰掷完后仍由当前玩家走棋 val expectimax(board, depth, current_player, is_chanceFalse, diedie) total prob * val return total # 决策节点当前玩家选择对自己最有利的走法 moves generate_moves(board, current_player, die) if not moves: # 无子可动相当于跳过回合交给对手掷骰 return expectimax(board, depth - 1, opponent(current_player), is_chanceTrue) best -float(inf) for move in moves: board.apply(move) # 走完一步后轮到对手掷骰 val expectimax(board, depth - 1, opponent(current_player), is_chanceTrue) board.undo(move) best max(best, val) return best逻辑说明递归的入口永远从决策节点开始因为轮到玩家行动时先要落子落子之后对手才掷骰。函数用is_chance区分两类节点。chance 节点遍历 6 个骰子面把子节点的值按 1/6 加权求和决策节点遍历当前骰子点数下的全部合法走法取最大值。die参数在决策节点是必需的但在 chance 节点阶段它还没有被“掷出”所以必须传下去到下一层决策节点。这也是和 Minimax 最大的结构差异Minimax 的递归深度每次减一而这里的depth只在走棋节点递减掷骰节点不递减。参数说明depth是搜索的最大层数这里指“决策节点的层数”。如果你想让搜索深度 4意味着每个玩家各走 4 步而骰子节点夹在中间不消耗深度。很多初写者把 chance 节点也减深度结果搜索只能看 2 步棋棋力大幅下降。evaluate函数的输入是棋盘和当前玩家注意这里的“当前玩家”指的是正要走棋的一方也就是评估函数的视角。评估函数的值是站在这个玩家角度算的搜索里通过 max/min 来保证视角一致。这段代码还有一个细节board.apply(move)之后子节点是opponent(current_player)的 chance 节点。因为当前玩家走完一步轮到对手掷骰和走棋。递归回来后board.undo(move)恢复棋盘这是搜索算法的常规内存管理方式避免每次生成新棋盘对象导致内存爆炸。3.3 轮到谁落子对手模型的两种假设期望搜索里有一个容易含糊的问题当轮到你走棋时你把对手当什么在 Minimax 里对手被建模成“总是选对我不利的走法”所以取 min。在期望搜索里对手同样要掷骰、走棋但骰子的随机性应该按期望处理而对手走棋时的“恶意”则按 min 处理。常见做法是对手的决策节点用 min 而不是 max。因为对于当前玩家来说对手会选择让对手受益最大的走法也即让当前玩家收益最小的走法。所以决策节点要区分“当前 max 玩家”和“当前 min 玩家”而不是笼统地“走棋的人取 max”。def expectimax(board, depth, maximizing_player, current_player, is_chance, dieNone): if depth 0 or board.is_terminal(): return evaluate(board, maximizing_player) if is_chance: total 0.0 for d in DICE: total DICE_PROB[d] * expectimax( board, depth, maximizing_player, current_player, False, d ) return total moves generate_moves(board, current_player, die) if not moves: return expectimax( board, depth, maximizing_player, opponent(current_player), True, None ) if current_player maximizing_player: best -float(inf) for move in moves: board.apply(move) val expectimax( board, depth - 1, maximizing_player, opponent(current_player), True, None ) board.undo(move) best max(best, val) return best else: best float(inf) for move in moves: board.apply(move) val expectimax( board, depth - 1, maximizing_player, opponent(current_player), True, None ) board.undo(move) best min(best, val) return best逻辑说明这里用maximizing_player固定表示搜索树的根节点玩家current_player表示当前递归到谁走棋。评估函数始终返回根节点玩家的视角分数。这样 max 节点和 min 节点的区别就是current_player maximizing_player这个布尔判断。chance节点不区分玩家因为骰子的概率独立于玩家身份。这段代码比上一版更完整因为它正确处理了“双方都有骰子随机性”的交替结构。参数说明die在 chance 节点置为None到决策节点时才传入具体的骰子点数。一旦某个玩家“无子可动”它相当于跳过回合代码直接递归到对手的 chance 节点depth 不减——这个处理也和规则语义一致因为跳过回合本身没有消耗玩家的行棋步数。如果你发现搜索在某个局面下异常浅多半是 depth 被机会节点消耗了检查点就在这里。4. 评估函数决定棋力上限位置分、逃生分与行动自由度的权重标定搜索深度只能让你看到更多步但树底部的叶子节点总得有个数值来决定取舍。如果评估函数只看“离底线还有多远”AI 会变成一根筋往前冲被对方堵死也不回头如果评估函数太复杂又会让搜索速度骤降。这一章讲清楚评估函数里应该放哪些特征、用什么样的权重结构以及如何用手工对局来标定参数。4.1 为什么评估函数是这局的胜负手期望搜索在叶子节点上的表现直接受到评估函数的影响。可以这样理解搜索深度是望远镜评估函数是判断镜片是否清晰的磨工。望远镜倍数再高镜片磨歪了看到的依然是一片模糊。在爱因斯坦棋里骰子的随机性让搜索树的平均分支因子比象棋低——通常一个骰子点数对应的合法走法只有 24 个——所以搜索深度 6 并不难达到。但评估函数如果只会数“谁离底线更近”AI 会在中盘做出大量看似推进、实则送死的决定。更麻烦的是评估函数的错误会被期望搜索放大。因为期望节点会把多个分支的值加权求和如果某个分支的评估值严重失真比如把 4 步后被堵死的棋算成高分它的分值会平均到其他分支上导致整个局面判断都偏移。这跟 Minimax 完全不同Minimax 的 min 节点会掩盖一部分错误估值只取最小值而期望节点是求和错误信息会直接叠加。所以评估函数的准确度比搜索深度更值得花时间。4.2 特征工程位置分、存活分、到达分、行动自由度评估函数的设计我一般从四个特征起步每个特征都有明确的棋理依据第一个是位置分。棋盘 5×5 很小每前进一步都意味着离胜利更近一步。位置分可以简单地按“距离底线的行数”加权白方第 row 行的棋子得分为 row × 10黑方为 (4 - row) × 10。这个线性分数简单但有效。第二个是到达分。到达对方底线的棋子是赢棋的直接条件应当给予极高的奖励。但要注意砲对方的底线之后这局棋已经结束搜不到这一步就该结束。所以到达分的意义更多是引导搜索优先推进离底线仅一步的棋子而不是真的在被评估的局面中出现。第三个是存活分。每枚棋子的价值不是均等的。靠近底线的棋子比刚出发的棋子更有价值因为它距离胜利更近但同时它也更脆弱更容易被对方斜走切入。存活分可以按棋子当前行号做指数加权让 AI 在“冒险深入”和“稳扎稳打”之间做权衡。第四个是行动自由度。即当前玩家的所有棋子中有多少枚还没有被吃且未到达底线。行动自由度越高掷骰后“掷出无用点数”的概率越低。这个特征在实战中非常有效因为有的时候牺牲一枚棋子反而让其他棋子获得更多行动机会——这种交换在评估函数里会反映为自由度的增加。def evaluate(board, player): score 0.0 for p in range(1, 7): pos board.pieces[player][p] if pos is None: continue row pos[0] if player WHITE: score row * 10 # 位置分 if row 4: score 1000 # 到达分 else: score (4 - row) * 10 if row 0: score 1000 # 存活分越接近底线权重越大指数形式 score 2 ** min(row, 4 - row) * 0.5 # 行动自由度己方可行动棋子数越多越好 movable [p for p in range(1, 7) if board.pieces[player][p] is not None] score len(movable) * 3.0 # 对手的威胁对手离我底线的距离越近扣分越多 for p in range(1, 7): pos board.pieces[opponent(player)][p] if pos is None: continue opp_row pos[0] if player WHITE: score - (4 - opp_row) * 12 # 对手越靠下对我威胁越大 else: score - opp_row * 12 return score逻辑说明这个评估函数把四个特征线性组合。位置分的权重 10 是基准值到达分是 1000 以确保搜索只要有一步能赢就必选存活分的衰减指数 0.5 让中盘的棋子也有一定的保底价值。行动自由度的权重 3.0 看起来不大但在期望搜索里它会与骰子概率互相作用每多一枚可行动棋子期望值就会提升约 3 × (1/6) 0.5这个值在多轮搜索中会累积。对手威胁项用 12 的权重略高于位置分是为了让 AI 不只顾自己冲线当对手逼近底线时愿意回防。参数说明你看到的 10、1000、0.5、3.0、12 都是初始值它们不是拍脑袋拍出来的而是从“先保证不下出明显失误”这个目标出发的。1000 很大程度上确保了搜索不会在临近胜利时走错步12 的威胁权重让防守行为在期望上不亏。后面如果要调参建议一次只动一个数字并用同一组开局连下 20 盘对比胜率单独动多个参数的结果很难归因。4.3 权重调参手工标定做不到的时候就用简单自对弈权重参数的调整是评估函数最费时间的一环而且多少有点玄学。我的经验是先用肉眼观察几盘完整的对局找出 AI 最明显的决策失误比如明明对手下一步能到底线它却不防守针对失误去调相应特征的权重。这个循环重复三四轮之后肉眼能发现的问题基本就没了剩下的全靠自对弈统计。自对弈的常见做法是让两个不同权重的 AI 互相对打统计胜率。每局结果是一个样本权重调整的方向由“新权重的胜率是否显著高于旧权重”决定。就是这个方向的判断往往是模糊的——因为骰子的随机性让单局胜负噪声很大你必须下足够多的盘数才能看出差异。我会用 50 到 100 盘来评估一组权重胜率差超过 5 个百分点才认为有区分度。别再少于 20 盘就去下结论那和抛硬币没什么两样。自对弈还有一个不容易察觉的好处它可以暴露规则实现里的 bug。如果两边权重完全相同胜负应该各半但某些规则 bug 会让某一方占据固定优势——比如落子方向向量定义反了。所以在调权重之前先跑 10 盘双 AI 同权重对局检查胜率是否接近 50%。这一步能帮你省下大量排查隐蔽逻辑错误的时间。5. 避坑期望搜索实现中我踩过的五个坑这一章写给那些已经把代码跑起来、但发现 AI 棋力鬼畜或者速度奇慢的人。以下五个坑都是我实际调试过程中遇到过的每一条都按“现象 → 原因 → 解决”的顺序写你可以直接对照自己的代码检查。5.1 坑一负无穷初始值让期望节点算出错误估值现象搜索进行到某个局面时评估值突然变成接近-inf的负数导致 AI 宁愿不动也不走任何棋。原因我在决策节点初始化best -float(inf)然后遍历合法动作更新最大值。如果某个动作的分支下子树递归返回的是-inf——通常是因为这个分支的某个叶子节点遭遇了无动作的递归链路——那么这个-inf会被 max 保留下来继续传给上一层的 chance 节点。chance 节点把-inf乘以 1/6 加起来整个期望值就变成了负无穷。解决在决策节点里如果moves为空直接返回评估值而不是递归在 chance 节点里对每一个子节点递归前先判空。另外可在expectimax入口统一加一个“合法动作列表为空则立即求值返回”的短路判断。这个判断要放在所有终止条件之后、递归之前确保空动作不会污染上层期望。5.2 坑二把对手走棋也错当成了期望节点现象AI 明明掷骰后有几个点数无法行动但搜索结果显示它把这些“无效点数”也按 1/6 加权了导致 AI 高估了某些局面的价值。原因我在第一次实现时把“玩家掷骰”和“对手掷骰”统一建模成 chance 节点但在对手回合里对手的决策节点也被错标成了 chance。仔细看规则会发现掷骰是机会节点掷完之后的走棋是决策节点。对手的走棋必须按 min 处理因为对手会选对它最有利的走法。如果对手的走棋也按期望处理等于假设对手随机乱走评估出来的局面价值会系统性偏高。解决在递归函数里用is_chance和current_player两个参数区分。is_chance只表示“当前是否处在掷骰阶段”与玩家身份无关一旦进入决策节点就根据current_player maximizing_player判断用 max 还是 min。这样对手的决策节点永远是 min骰子节点永远是期望。5.3 坑三评估函数的“到达分”把棋子送进了死胡同现象AI 的棋子总是义无反顾地冲到最前线然后被对手的两枚棋子夹住既不能前进也不能横向逃逸白白浪费优势。原因到达分权重 1000 太高导致搜索极度偏好把棋子往底线推。在离底线只剩一格时AI 会忽略所有防守和逃脱路线因为它认为“下一步就能赢”但对手的骰子恰好可以走出一步堵住去路——这一层随机性在搜索深度不够时根本看不到。解决把到达分的权重从 1000 降到 300同时给“即将到达底线的棋子”增加一个周围空格评估。如果这枚棋子的三个前方方向都被堵住它就不应该得高分。具体做法是在evaluate里扫描每个棋子周围三格的占用情况被包围的棋子扣除 50 分。调完这些之后AI 的推进策略明显更稳健不再无脑冲线。5.4 坑四搜索深度一上去速度就崩缓存命中率上不来现象把搜索深度从 4 调到 6单步耗时从 0.1 秒涨到 3 秒且局面缓存命中率不到 15%。原因缓存键用的是棋盘状态的字符串序列化每次搜索都做一次str(board.state)速度慢且占内存。更关键的是爱因斯坦棋的棋盘具有对称性同一局面对镜像位置来说评估值应当相同。比如白方在 (2, 1) 的棋子和白方在 (2, 3) 的棋子在列方向上是镜像关系。字符串序列化无法映射这些等价局面所以缓存命中率上不去。解决把缓存键改成规范化后的棋盘状态。做法是计算棋盘状态的镜像值取两个值的较小者作为缓存键。具体实现可以用一个元组(tuple(whites), tuple(blacks))然后取原状态和“列镜像状态”的字典序最小值存进去。这个改动后缓存命中率从 15% 提到了 50% 左右搜索深度也就能撑到 6 了。注意镜像只在列方向做行方向不对称因为底线方向不同行镜像不合法。5.5 坑五自对弈调权重时把“输赢”当成了唯一标签现象调整权重之后AI 对局胜率变高了但具体走出的棋反而更“抽搐”——有时明明能安心推进却偏偏选择绕路。原因胜率是最终目标但它太稀疏了。一盘棋几十步只有最后一步才决定胜负中间的每一步对胜率的贡献都被掩盖了。用胜率做反馈来调权重相当于在黑匣子里瞎调某组权重胜率高但你不知道是因为中盘决策变好了还是因为最后几步运气好。解决自对弈时要多记录中间状态。我会在每步决策后记录“搜索评估值”和“最终胜负”然后用这些数据检查权重是否有明显的反向案例——比如所有胜利的对局里某个特征的平均值反而更低。更实用的做法是加一个“翻盘率”指标如果 AI 在中盘评估为劣势但最终赢了说明它的某个特征权重可能过低或过高。把反馈信号拆细之后权重的调整方向才会更明确。这一步就是手动调参转向半自动化调参的起点。6. 进阶把期望搜索从“能下”推到“能赢”的三个具体技巧当你把基础版跑通、AI 已经能完整体验对局之后接下来就是常规优化阶段了。我这边最有效的是三个技巧延迟评估、对称缓存加宽搜索、以及用快照数据反向检查评估函数。每个技巧的改动量都不大但合在一起能让棋力上一个台阶。第一个技巧是延迟评估。搜索深度较深时叶子节点的评估值很容易因为“只差一步就到底线”而被高估。延迟评估的做法是在到达最大深度时不要立即调用评估函数而是强制往下多搜索几层直到局面趋于稳定——比如某方的所有棋子都已经脱离开局位置或者双方的距离底线差距已经明显拉大。这会增加一点点搜索时间但因为骰子棋的分支因子不大多搜两层通常可接受换来的评估准确性提升非常值得。第二个技巧是保存并复用可以继续搜索的“半截结果”。搜索到深度上限返回时评估值其实是基于多层信息的。你可以把这个评估值存起来当成浅搜索的叶子节点值用。具体实现是在缓存里保存的不只是状态和值还包括搜索深度。下次搜索时如果当前状态在缓存里且缓存深度小于当前搜索深度直接使用缓存值作为下界。这个技巧也叫迭代加深的“转置表替换策略”在随机博弈里同样有效能让同样时间下的有效深度提升一档。第三个技巧是快照数据反向检查。我已经习惯每次自对弈结束后把每个局面的评估值、实际走法、最终胜负存成一份对局记录。跑完 50 盘之后我会随机抽 10 个局面手动判断这个评估值是否符合直觉。这个习惯救过我很多次——有一回我发现评估函数对“黑方已到 0 行”的局面返回了正分才意识到黑方的到达判定方向写反了。没有快照回放这种隐蔽 bug 很难被找到因为对局看起来还能正常下完。这三个技巧加在一起我的期望搜索 AI 从“偶尔赢初学者”进步到“稳定赢得过我自己”。更难得的是我逐渐体会到期望搜索的优雅之处它不试图消除随机性而是把随机性当作博弈结构的一部分来求解。好运或坏运只影响某一回合而策略的好坏决定长期胜率。希望这个思路和这些实现细节能帮到你——下棋 AI 的路子一通换到其他带随机性的决策问题也就一通百通了。本文还有配套的精品资源点击获取