简介消灭星星自动求解程序是一套基于QT框架开发的休闲游戏自动消除工具面向对游戏AI、蒙特卡洛方法感兴趣的C开发者以及希望研究单步最优决策策略的进阶玩家。程序内置蒙特卡洛求解核心通过模拟大量消除组合、评估预期得分并选择最优动作平均得分可达5500以上同时配备GUI界面便于直观观察运行过程。压缩包共60个文件约12.13MB包含6个C源文件与6个头文件、工程配置pro/qrc、已编译的exe可执行程序、运行所需DLL与国际化QM语言包、界面图片等类型覆盖源码、二进制、配置与资源工程与依赖相对完整适合还原可编译调试的开发环境。已有603人学习下载。借助源码与可运行程序读者可以理解局面生成、组合搜索、得分评估、剪枝优化与GUI联动等关键实现体验从算法设计到界面集成的完整流程是一份兼顾演示与分析的实用游戏AI范例。1. 消灭星星自动求解从“手动点爆”到“让程序自己点”的完整方案大概一年前我接到一个很具体的需求某公司运营同学想在活动开始前把一个高分局的“消灭星星”盘面自动跑完要求不是随便能通关而是分数尽可能高、步骤可回放。当时我以为这不就是全选最大的同色块连点几轮嘛结果手动模拟两局之后就发现坑非常多。所谓“消灭星星自动求解”本质上是在给定一个 N×M 彩色网格和消除规则后搜索一条点击序列让总分最大或者棋盘被清空它背后是组合优化问题不是图像识别问题。这篇文章把我实际在用的建模、DFS 回溯、剪枝、避坑和蒙特卡洛兜底方案完整写出来适合想自己写求解器、或者拿这种小游戏练搜索算法的人跟着复现。我自己也是踩了“状态表示不对后面的努力全白费”的坑之后才把下面这套固定下来。2. 自动求解先过建模关棋盘、连通组和重力规则动手写搜索之前必须先回答一个最基础的问题一次“点击”到底改变了什么。如果这一步不锁死后面所有搜索树都是在错误的世界上空转。2.1 状态表示把一张棋盘变成一个可哈希的整数矩阵我把棋盘定义成二维整数矩阵0表示空位1~4表示不同颜色的星星。颜色数量这里用colors4实际“消灭星星”常见是 4 或 5 色颜色越少同色连通越多分支因子越大搜索越难。生成一个测试棋盘很简单import random def new_board(width10, height10, colors4, seedNone): if seed is not None: random.seed(seed) return [[random.randint(1, colors) for _ in range(width)] for _ in range(height)] def board_key(board): # 搜索算法里要用 dict 做记忆化list 不能做 dict 的 key return tuple(tuple(row) for row in board)board_key这一步极其重要。Python 里二维 list 是可变对象不能直接放进 dict 的 key就算硬塞也会在运行中因为内容被修改导致状态错乱。我的习惯是每个状态进入递归函数时立刻转成元组后面所有 memo、缓存都以这个元组为准。10×10 的棋盘一次完整元组转换大概几微秒这个开销换来的去重收益往往能省下几个数量级的搜索时间。状态表示的选型还有一个隐含取舍要不要把“当前分数”也放进状态里我的答案是不要。搜索时同一个棋盘可能通过不同步骤路径到达把分数留在搜索循环外层累加才能让 memo 命中时直接复用子树结论如果把分数放进 key同一个盘面会因为累计值不同被当成两个状态缓存基本失效。2.2 连通组、重力掉落与列聚合三条规则的实现点击一个位置会消除和它相邻同色的整个连通块。求连通块我用的是最简单直接的 flood fill 栈扫描def find_groups(board): height len(board) width len(board[0]) if height else 0 visited [[False] * width for _ in range(height)] groups [] for r in range(height): for c in range(width): if board[r][c] 0 or visited[r][c]: continue color board[r][c] stack [(r, c)] visited[r][c] True cells [] while stack: cr, cc stack.pop() cells.append((cr, cc)) for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc cr dr, cc dc if (0 nr height and 0 nc width and not visited[nr][nc] and board[nr][nc] color): visited[nr][nc] True stack.append((nr, nc)) groups.append((color, cells)) return groups这里用栈模拟递归 flood fill避免递归太深。扫描顺序是从左上到右下每个未访问的颜色格触发一次扩张。返回的groups里每个元素是(color, cells)cells是坐标列表。我建议保留 color 字段因为后续剪枝需要按颜色统计剩余格数不需要再扫一遍棋盘。消除动作的模拟比很多人想象中更讲究。点击一组星星后先删掉这些格然后同一列的星星在重力作用下向下掉落空列会被右侧列补过来这是“消灭星星”最常见的一类规则def apply_move(board, cells): height len(board) width len(board[0]) new_board [row[:] for row in board] for r, c in cells: new_board[r][c] 0 # 每一列做重力掉落从上往下清扫把非 0 值依次放在底部 for c in range(width): column [new_board[r][c] for r in range(height)] kept [v for v in column if v ! 0] empty height - len(kept) for r in range(height): if r empty: new_board[r][c] 0 else: new_board[r][c] kept[r - empty] # 空列整体左移 kept_cols [] for c in range(width): col [new_board[r][c] for r in range(height)] if any(v ! 0 for v in col): kept_cols.append(col) result [[0] * len(kept_cols) for _ in range(height)] for c, col in enumerate(kept_cols): for r in range(height): result[r][c] col[r] return resultapply_move是后面所有搜索正确性的基石。它有两个隐蔽点一是重力必须先整列处理不能按行遍历否则上方掉落的星星可能被错误覆盖二是空列聚合顺序要保持从左到右不能反过来。如果你写的版本和真实游戏规则不一致会出现“模拟器里清得很爽放到游戏客户端一跑就崩”的现象。注意不同“消灭星星”变体的重力规则不完全一样。有的版本空列不聚合有的版本聚合方向相反。动手前先定死规则最好写一个GRAVITY_MODE开关我当时就是为这事吃了亏后面在避坑清单里详细展开。3. 核心求解器带回溯的 DFS 搜索怎么写不碰壁建模完成之后搜索本身反而简单。我用的核心方案是 DFS 回溯加记忆化从当前棋盘出发枚举所有合法点击递归消除下去最后把整条路径的总分拿回来。3.1 最小可跑求解循环从空盘递归到输出点击路径先看一个不剪枝、只做记忆化的最小版。它适合 4×4、5×5 这种小盘面10×10 会非常慢但逻辑是完整的def solve_board(board, score_fnlambda n: n * (n - 1) * 5): memo {} def dfs(board): key board_key(board) if key in memo: return memo[key] groups find_groups(board) if not groups: memo[key] (0, []) return memo[key] best_score -1 best_path None # 动作排序先尝试最大的连通组这是最朴素的启发式 groups.sort(keylambda g: len(g[1]), reverseTrue) for color, cells in groups: move_gain score_fn(len(cells)) next_board apply_move(board, cells) sub_gain, sub_path dfs(next_board) total_gain move_gain sub_gain if total_gain best_score: best_score total_gain best_path [(cells[0][0], cells[0][1])] sub_path memo[key] (best_score, best_path) return memo[key] return dfs(board)这段代码有两个关键参数score_fn是得分函数默认用n*(n-1)*5这是“消灭星星”系列比较通用的一套计分公式memo记录的是“从当前棋盘出发能得到的最高分以及对应路径”。best_path里我用cells[0][0], cells[0][1]作为点击位置因为组内任意一个位置效果相同取第一个坐标就能代表整个动作。这段逻辑里最容易被忽略的是groups.sort。表面看它只是让大组先试实际上在配合剪枝时它决定了你能多快找到一个好解。如果每次先把小组试完你得到的最优下限会很差后面剪枝几乎剪不动。先大组后小组能保证早期就出现一个质量不错的可行解后续剪枝才有参照物。递归出口是find_groups返回空。这一步等价于“棋盘上没有任何可消除的连通块”也就是游戏死局。注意死局不是看剩余星星数量而是看是否存在大小 ≥ 2 的同色连通块。一个颜色如果分成两个不连通的单格同样不能点。3.2 几个必须精调的参数动作排序、得分公式和剪枝阈值上面的最小版只保证正确不保证快。真正要落地到 10×10 盘面必须引入一组可配置参数。我通常把它们集中在 solver 入口方便做网格搜索调优def solve_board(board, score_fnlambda n: n * (n - 1) * 5, candidate_limit8, use_memoTrue, max_depth64): ...candidate_limit表示每一层只试排序后前 N 个组。如果设成8意思是我认为最优解总是包含一个“当前可用的较大组”的动作这会把一部分极端路径剪掉但换来超高速度。想要严格最优化就把它设成0或一个很大的数。很多第一次写自动求解的人不敢剪这个结果 10×10 跑一小时没结果我一般从candidate_limit5起步逐步往上加。max_depth是递归深度上限。10×10 的盘面最多也就几十次消除设成width*height//2通常够用如果递归超过这个深度还没清空说明出现了异常分支直接截停返回当前累计分。这个参数本质上是给搜索一个“后悔药”宁可取近似解不让程序死循环。use_memo开关对应记忆化。在候选限制已经生效的前提下记忆化依然能明显加速因为不同路径可能到达同一盘面。但要注意第 5 章避坑清单里说的“存路径导致内存暴涨”所以我会让 memo 只存分数不存路径或者限制 memo 条数上限。得分公式score_fn也值得单独拿出来说。很多人只改一行公式但没意识到它会影响动作排序结果如果一个版本里8个星星得分极高搜索会优先保大组另一个版本里连续消除有额外奖励搜索策略会完全不同。我建议代码里不要写死n*(n-1)*5全部通过参数传入这样换一个游戏变体时不用重写求解器。4. 剪枝与估值让 DFS 从“跑不完”变成“秒出结果”最小版 DFS 在 6×6 盘面可能已经卡顿10×10 必须靠剪枝和估值撑起来。这里三条路同时做贪心法给搜索一个下限上限函数做分支裁剪Zobrist 缓存让裁判命中更快。4.1 贪心估值为搜索托底贪心策略是“每次找最大连通组点掉反复进行”。它速度极快而且因为大组得分高结果通常不差。它的最大价值不是作为最终解而是给 DFS 提供初始最优下限def greedy_solve(board, score_fnlambda n: n * (n - 1) * 5): board [row[:] for row in board] total 0 path [] while True: groups find_groups(board) if not groups: break groups.sort(keylambda g: len(g[1]), reverseTrue) color, cells groups[0] total score_fn(len(cells)) path.append((cells[0][0], cells[0][1])) board apply_move(board, cells) return total, path在 DFS 加入剪枝时先跑一遍贪心把greedy_score作为best_score的初始值。后续搜索中只要某条分支“当前已得分 理论上限”小于best_score就直接砍掉。效果非常明显。单纯贪心的问题也很明显它只看局部最大组完全不管“现在点掉小组会不会让后面合成更大组”。所以贪心是保底不是终点。4.2 用上限函数狠剪分支DFS 最怕的就是在“明显没希望”的分支里一直挖。我常用一个很宽松但实现简单的上限假设某种颜色剩余的所有星星能在一次消除中全部拿走算一个理论上界。实际这是不可能达到的但正因为够保守不会误删最优解def upper_bound(board, score_fnlambda n: n * (n - 1) * 5): color_count {} for row in board: for v in row: if v: color_count[v] color_count.get(v, 0) 1 return sum(score_fn(cnt) for cnt in color_count.values())在 DFS 的循环里这样用remaining_upper upper_bound(next_board, score_fn) if move_gain remaining_upper best_score: continue这个剪枝的直觉是哪怕之后每一步都完美也不可能超过这个上界如果都已经低于当前最好就没必要继续。它剪掉的不是“可能的最优解”而是“确定不如当前解”的分支。越早跑出高贪心分数这个剪枝越猛。4.3 Zobrist 缓存和深度限制给搜索加两道保险记忆化用board_key是安全但慢的。10×10 棋盘每次转元组加上字典查询其实有很大开销。如果你追求极致性能可以把状态哈希改成 Zobrist 哈希每个颜色在每格位置分配一个随机 64 位整数棋盘哈希值等于所有非空格随机数的异或import random _zobrist_table {} _zobrist_cache {} def zobrist_init(board, colors4): height len(board) width len(board[0]) for c in range(1, colors 1): for r in range(height): for col in range(width): _zobrist_table[(c, r, col)] random.getrandbits(64) def zobrist_key(board): h 0 for r, row in enumerate(board): for c, v in enumerate(row): if v: h ^ _zobrist_table[(v, r, c)] return hZobrist 的好处是apply_move之后只需要把被清除格子的随机数异或掉再对新掉落的星星异或进去不用重新扫描全盘。不过这里我要说实话对这个量级的棋盘元组记忆化已经够用Zobrist 更适合大规模搜索当“快速去重过滤器”。如果追求工程简化直接元组就行。深度限制和迭代加深是同一个思路。我习惯先跑一个max_depth8的浅搜索拿到一个不错结果再逐步把max_depth加到 16、24每次都在上次结果基础上提高。这样即使时间不够手里也始终有一个可用解。注意candidate_limit 和 max_depth 都会有损最优性。如果你做的是算法比赛想要理论上严格最优请把 candidate_limit 调大到不限如果你做的是“给玩家一个能跑的高分方案”那这两刀非常值得。5. 避坑清单自动求解最容易翻车的五个现场这里是我反复踩过的坑每一条都按“现象 → 原因 → 解决”写照着排查能省很多时间。5.1 现象清空一组后上面的星星没掉下来后续步骤全是错的模拟器和真实游戏跑了两步就开始分叉点下去之后画面和我算出来的完全对不上。原因几乎都是重力实现错误有人逐行扫描把本应在同一列下落的星星按“行优先”塞进去了有人在空列聚合时把顺序搞反右列顶到了最左而不是按原顺序左移。解决办法是按列生成列表过滤掉 0前面补满空位再写回空列聚合时一定要保留原来的列顺序。我建议单独写一个测试函数给一个 3×3 固定棋盘手算一次期望输出跑完断言通过再进搜索。5.2 现象dict 报错unhashable type: list第一次写搜索时我直接把二维 list 放进 memo 当 key程序跑两步就炸。原因很简单list 是可变的不能哈希。解决方法是入口立刻转元组而且要在进入递归前转不要等到递归内部再转。另一个隐蔽问题是把board_key存成全局变量递归返回后棋盘没恢复导致缓存错乱这种情况反而更危险。5.3 现象记忆化命中率很高搜索速度却更慢加了 memo 之后反而卡死这是最容易让人怀疑人生的时刻。我排查后发现memo 里不仅存了分数还把best_path整个列表也存了下来。当子节点路径很长时一个状态保存几 KB 路径很轻松几万个状态就把内存打满而且递归深处大量列表拼接复制CPU 全部消耗在拷贝上。解决方法是 memo 只保存分数路径在搜索外层通过回溯单独重建或者用“只存路径长度不超过某阈值”的方案。对工程落地来说memo 里存一个(score, path_len)就够用了。5.4 现象分数和游戏对不上搜索越优化分越低有人把得分公式写成n*n*5还有人忘了“剩余星星扣分”的规则。自动求解器再聪明也是优化一个错误的目标函数。现象就是求解器给出“最高分”方案实际游戏里一跑分数差一大截。我的习惯是先把计分规则抽成一个score_fn然后录一段真实游戏的点击序列在离线环境重放分数对不上就先调公式不要动搜索逻辑。5.5 现象死局判定太早把能清空的盘面判成无解搜索走到一半提前退出理由是我统计剩余颜色数量发现每种颜色都只剩一个格子就认定无解。这是错的两个同色单格如果相邻它们会组成一个可点击的连通块。正确判定死局的唯一标准是find_groups返回空列表也就是“没有一个连通块大小 ≥ 2”。计数只能作为启发式不能当终止条件。我还见过更隐蔽的错误把单格星星当作已消除导致后续重力规则错乱这种问题只有用回放工具才能查出来。6. 进阶玩法蒙特卡洛兜底与离线验证DFS 加剪枝在大多数盘面上表现不错但遇到搜索空间特别大的开局还是会超时。我最后的兜底方案是蒙特卡洛模拟不追求精确最优只要求“这一步点下去之后随机走 200 次平均分高”。6.1 用蒙特卡洛模拟给每一步打分对当前棋盘的每个候选动作执行后进入一个随机贪心策略快速玩到结束重复多次取平均分def rollout(board, score_fn, steps30): board [row[:] for row in board] total 0 for _ in range(steps): groups find_groups(board) if not groups: break groups.sort(keylambda g: len(g[1]), reverseTrue) # 前 5 个组里随机挑一个兼顾探索 choice random.choice(groups[:5]) color, cells choice total score_fn(len(cells)) board apply_move(board, cells) return total def mc_best_move(board, score_fn, rollouts200): groups find_groups(board) best_move None best_avg -1 for color, cells in groups: next_board apply_move(board, cells) total 0 for _ in range(rollouts): total rollout(next_board, score_fn) avg total / rollouts if avg best_avg: best_avg avg best_move (cells[0][0], cells[0][1]) return best_move这招的价值在于当 DFS 因为时间限制没有完成搜索你可以立刻退化成“每走一步都蒙特卡洛评估”的在线模式。参数rollouts是关键我一般 100 到 500太少随机噪声大太多实时性受影响。6.2 离线验证一整局自动求解结果不管用 DFS 还是蒙特卡洛最后都要有一层离线验证否则你根本不知道求解器有没有在“自嗨”。我的验证脚本是这样写的把初始棋盘和动作序列保存下来然后通过回放重跑一遍整局确认每一步都合法、得分合得上、终局状态正确。def replay_validate(initial_board, moves, score_fnlambda n: n * (n - 1) * 5): board [row[:] for row in initial_board] total 0 for x, y in moves: groups find_groups(board) target None for g in groups: if (x, y) in g[1]: target g break if target is None: raise ValueError(f非法点击: ({x}, {y})该位置不属于任何可消除块) total score_fn(len(target[1])) board apply_move(board, target[1]) return total, board回放不只在校验分数还在校验规则一致性。我现在的习惯是每次改apply_move或score_fn都用同一组固定种子的盘面做回归测试通过后再跑随机盘面。这件事看起来笨但救过我很多次尤其是当你把一个看起来无害的“性能优化”加进剪枝之后只有离线回放能立刻暴露它偷偷剪掉最优解的问题。如果你也想做“消灭星星自动求解”我的建议是先只做贪心再上 DFS最后再加蒙特卡洛不要一上来就搞 Zobrist 和复杂剪枝。搜索算法的教训都在边界条件里不在算法本身。希望帮到你。本文还有配套的精品资源点击获取