1A2B猜数字游戏最优策略

发表于 分类于 评论数：

把“猜数字”玩成算法题：这篇文章从零构建 1A2B 的最优求解思路，给出一个可靠基线（暴力一致性筛选），再用更聪明的“选猜”策略把平均轮数拉到约 4.3x。附交互示例、复现实验与参考资料。

游戏规则与术语

  • 四位数，数字不重复，允许前导零（若不允许，可在实现中切换开关）。
  • 判定规则：xAyB。A 表示数字与位置均正确的个数，B 表示数字对但位置不对的个数。
  • 本文默认使用 Mastermind 风格的严格计分：如答案 5543，猜 5255 计 1A4B（允许重复输入时的定义）。若限制“输入也不重复”，则保持标准 1A2B 的去重计分。

目标与评价标准

  • 目标：在“最坏情况轮数最小”的前提下，兼顾“平均轮数最小”。
  • 已知下界与上界：
    • 文献结论表明四位不重复数字的最坏情况上界为 7 轮；不存在 6 轮内保证解出的算法。
    • 当前较优的平均轮数约为 4.34（不同实现/假设略有差异）。参考：Bullscows 综述。

基线方案 v1：一致性暴力筛选

  • 思想：维护候选集合 candidates（所有可能答案）。任意给出一个猜测 guess，观察返回的 xAyB，将与该反馈“不一致”的候选全部剔除。下一轮在剩余候选里继续猜。
  • 复杂度与表现：实现简单、鲁棒性高；平均轮数通常在 5.x 左右，是性价比极高的基线。
  • 交互示例：
1
2
3
4
5
6
7
8
9
欢迎来到 1A2B 助手！每轮我会给出四位不重复数字，请输入反馈（如 2A1B 或 21）。
第1轮，我的猜测是：0123
请输入反馈：10
第2轮，我的猜测是：0456
请输入反馈：01
……（若干轮筛减）
第7轮，我的猜测是：9725
请输入反馈：40
太棒了！我在第7轮猜中了答案：9725

改进 v2：给“候选/询问”打分，优先问“信息量大”的问题

  • 直觉：不是每个候选都同样好。当我们挑选下一次“要问的数字”时，应选择能把候选空间“切得更均匀”的那个，使得最坏分支尽可能小——这正是极大极小（minimax）的味道。
  • 做法：
    1. 对每个可作为“询问”的四位数 q，枚举它对所有候选答案产生的反馈分布，将候选按反馈分桶。
    2. 记该分桶的“最大桶大小”为 score(q)。优先选择使 score(q) 最小的 q（最坏情况最小化）。
    3. 实践中常在“仅限候选内挑选”和“允许从全空间挑选”间权衡；后者可带来更整齐的分割，但计算更重。
  • alpha-beta 是否有用：若将其抽象为博弈树，alpha-beta 提供的是对对抗搜索的剪枝框架；本问题评估函数昂贵、分支宽，但并非典型轮替对抗，因此更实用的是“分布统计 + 最坏桶最小化”的启发式。可把 alpha-beta 视作复杂情形下的工程优化而非必需品。

复杂度与问题性质

  • 相关工作指出该类问题为 NP-hard，因而不存在已知的多项式时间最优算法；启发式带来的计算开销显著高于基线，但能换来平均轮数小幅提升。
  • 参考：

实验与结果快照

  • 基线（一致性筛选）：平均约 5.5 轮左右（与你的生成策略、是否允许全空间提问有关）。
  • 启发式（最坏桶最小化）：可降至约 5.3/5.2，进一步结合更强的选猜与缓存，可靠近 4.3x 的前沿水平。
  • 代价：每轮需要对大量“询问”做分布统计，时间与内存压力上升，工程上需做剪枝与缓存。

如何运行（复现）

  • 仓库：见上方“代码仓库”。
  • 关键开关：
    • 是否允许前导零/是否允许输入重复数字
    • 仅在候选集中选猜 vs. 从全空间选猜
    • 评分策略：最坏桶最小化/期望桶大小最小化/混合策略
  • 建议：先跑 v1 作为基线，再逐步开启评分与缓存，观测“平均轮数—耗时”的折中。

结论与要点

  • 一致性暴搜是“既简单又强大”的基线；启发式的收益有限但稳定，适合对“步数更苛刻”的追求。
  • 对于视频/文章演示，建议：
    • 先用小样本可视化“候选集合如何被一次猜测切分”。
    • 对比“随机选猜 vs. 评分选猜”的候选坍缩速度与最坏路径。
    • 给出“我能否 6 步必解？”的悬念，再给出“理论上不可能”的答案，提升记忆点。

附：一次完整的人机交互样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[第0次] 请输入一个四位数字: 1234
0A2B
[第1次] 请输入一个四位数字: 5678
0A1B
[第2次] 请输入一个四位数字: 3456
0A1B
[第3次] 请输入一个四位数字: 7890
0A1B
[第4次] 请输入一个四位数字: 9512
0A2B
[第5次] 请输入一个四位数字: 2061
2A2B
[第6次] 请输入一个四位数字: 6021
恭喜你猜对了!

参考与延伸阅读

  • Bullscows 最坏/平均轮数讨论与数据集整理：https://slovesnov.users.sourceforge.net/index.php?bullscows

  • HDU-1172 相关题目，可用于在线评测与算法练习

  • 其他笔记/随感:

    • 1, 九宫格(8数码), 16宫格(15数码)挪数字: 也是经典现实游戏: 吴昊品游戏
    • 2, 自己果然没什么探究精神... "暴搜/16GB内存/4060ti/24小时期限"硬上, 完全不讲究优雅...