猜数字游戏,计算机求解,八步以内求解决策树

作者:半瓶墨水   链接:http://www.2maomao.com/blog/guess-num-resolution/

猜数字游戏

这个游戏的规则比较简单,一般两个人玩,一方出数字,一方猜。出数字的人要想好一个没有重复数字的4位数,不能让猜得人知道。猜的人就可以开始猜。每猜一个数字,出数者就要根据这个数字给出几A几B,其中A前面的数字表示位置正确的数的个数,而B前的数字表示数字正确而位置不对的数的个数。

如正确答案为5234,而猜的人猜5346,则是1A2B,其中有一个5的位置对了,记为1A,而3和4这两个数字对了,而位置没对,因此记为2B,合起来就是1A2B。

接着猜的人再根据出题者的几A几B继续猜,直到猜中为止。

次数限制
有的时候,这个游戏有猜测次数上的限制。根据计算机测算,这个游戏,如果以最严谨的计算,任何数字可以在7次之内猜出。而有些地方把次数限制为6次或更少,则会导致有些数可能猜不出来。而有些地方考虑到人的逻辑思维难以达到计算机的那么严谨,故设置为8次甚至10次。也有的没有次数上的限制。

前几天,突然想起来,研究生时候研究的猜数字程序求解问题,当时想做出一个完全决策树,根据这个树,任何数字都可以在8次以内求解。

解题思路很简单:

#1. 生成所有的四位不重复的0-9的数字组合的集合
#2. 随便找四个数字,比如0123
#3. 根据用户返回结果(xAyB),砍掉集合里面不符合结果的
#4. 根据现有数字组合,猜下一个,主要技术含量在这里:
#  a. 贪心算法,每次都找当前步骤里最优的
#  b. “最优”的定义:
#   b1. 选择一个组合
#   b2. 把这个组合和剩下的组合进行匹配,统计xAyB出现的次数,
#   __比如0A0B出现了10次,1A3B出现了0次等等
#   b3. 如果xAyB的所有可能出现的机会最为均等,那么这个选择的“区分度”就很大
#   __这个可以通过信息量理论进行衡量,也可以简化为通过“最小标准差”来衡量
#   b4. 遍历所有组合,找出“区分度”最大的
#5. 重复步骤3, 4,直到用户给出4A0B或者集合里面只剩下一个元素

首先在python-cn上面发起了关于如何快速生成所有数字组合的讨论
抛砖引玉,讨论的结果中居然有十多种方法,体现了不同的思路,具体的讨论参见:
函数性能:列出四个不重复数字(0-9)的所有组合

相关代码在这里:
生成四位不重复数字(0-9)的所有组合,比如8765, 9876, 0123
生成四位不重复数字(0-9)的所有组合

后来实现了上面所得解题思路,代码在这里:猜数字游戏的八步以内求解程序.

为了验证一定能在八步以内求解,我决定做个决策树生成程序,这个决策树的节点代表着每次猜测,树枝代表着xAyB这样的选择。
猜数字游戏8步以内的完全求解决策树生成程序

我实验过将这个决策树直接用于计算机求解,速度没的说,基本上就是8个以内的dict元素get操作和比较操作就能搞定。

参见:代码发芽网上所有标签(Tag) 为 猜数字 的文章

3 条评论 发表在“猜数字游戏,计算机求解,八步以内求解决策树”上

  1. htc说道:

    (目前我得到的)最多步数为6,最优平均步数=4.788293651

  2. 半瓶墨水说道:

    @htc 6是不可能的,我用全局最优算法尝试过了

留下回复