1A2B猜数字游戏最优策略

• 项目目的: 探究1A2B猜数字游戏的最小步骤
• tags: 概率论, 暴搜, 搜索优化, NP问题, 启发式搜索
• 代码repo

• 变种规则:
  • 允许提交”1111”作为答案/提交重复数字(这就没法算1A2B了)
    • “mastermind规则”: 即, 5543的题目猜5255的话, 判定1A4B
  • 5位数/多位数
• minmax
  • 即有两个最优条件: 己方最优/对手最劣. 所以比较判定的值为”max-min”
• 搜索算法
• alpha-beta
  • 剪枝, alpha和beta是某分支能产出的上下界, 当分支明显不符时, 就剪枝

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

• 这文章给出了结论: 最多七轮能由算法解出. 没有算法能在6轮内解出 -> 最优轮数的比较
  • 评判标准2: 评价轮数的比较: 目前最佳是4.34轮

v1: 暴搜

欢迎来到1A2B暴力解法助手！每轮我会给出一个四位不重复数字，请输入反馈（如2A1B或21）。
第1轮，我的猜测是：0123
请输入反馈（如2A1B或21）：10
第2轮，我的猜测是：0456
请输入反馈（如2A1B或21）：01
第3轮，我的猜测是：4178
请输入反馈（如2A1B或21）：01
第4轮，我的猜测是：5729
请输入反馈（如2A1B或21）：22
第5轮，我的猜测是：5927
请输入反馈（如2A1B或21）：13
第6轮，我的猜测是：7529
请输入反馈（如2A1B或21）：13
第7轮，我的猜测是：9725
请输入反馈（如2A1B或21）：40
太棒了！我在第7轮猜中了答案：9725

• 核心算法: 维护一个candidates四位数组, 然后每轮筛去不符合的

v2, 给candiate打分, 而非均概率抽取

• 其他任务:
  • 1, 数学上限的计算, 最优步骤数的计算
• 某博主的测试结果:
  • 1, 使用启发式算法的运算速度要远远低于直觉算法。很明显的，在本问题中，计算启发函数的值占用了大量的资源，而且其时间复杂度是超越了指数的级数级别
  • 2, 本问题已经被证明是NP-hard问题，因此目前为止还不存在多项式复杂度的运算方法

小结

• 1, 暴搜收益极高, 搜索优化的收益就不太高了(均值从5.5降到5.3而已), 且计算速度/功耗都更多负担
• 2, NP问题
• 3, HDU-1172
• 其他笔记/随感:
  • 1, 九宫格(8数码), 16宫格(15数码)挪数字: 也是经典现实游戏: 吴昊品游戏
  • 2, 自己果然没什么探究精神… “暴搜/16GB内存/4060ti/24小时期限”硬上, 完全不讲究优雅…