[算法讨论]猜数字游戏 - Bulls and Cows

523066680

在线猜数字游戏链接：http://www.codetiger.win/extra/

先注册账号，然后通过 post 提交并获取返回的数据，像这样

1. $res = $ua->post(
   
2.        $website,
   
3.        [ username=>$user, password =>$pass, number=>$n, send=>'answer' ]
   
4. );
   

复制代码

返回 JSON 格式的参考数据：
{"code":150,"A":0,"B":2,"count":49721,"tokens":"8550662099813553"}

游戏规则和JSON参数说明请见主页（这个网站和竞赛是一个小朋友搞的，后生可畏）

另外，提供一点资料
www.cs.nccu.edu.tw/~chaolin/papers/science3203.pdf
这个文档是中文的，讲了两个数字游戏，关于这次的游戏的分析和解法在后半部分。

---------------------------------------------------------------------------------------

基础的解题方案可以参考上面给出的PDF的后半部分。
服务器随机生成 [0-9] 组成的 4 位不重复数字（可以是0开头）。按照概率知识，可以有 10*9*8*7 = 5040 种情况

假设 服务器生成的谜底数字是 9567 ，我们post过去的数字是 0123， 则返回 A = 0, B = 0
如果提交的数字是 9276，则返回 A = 1, B = 2 表示1个数字位置和内容相同；有两个数字位置不对，但数值相同。

最基本的猜数策略在PDF中有给出，例如 Post 提交的数字是 0123，返回 A = 0，B = 3
我们可以将所有可能的数字集合 5039 种排列（不含0123）和 0123 碰撞，产生14种 AB 值，筛选出 A0B3 的同类排列，暂时称为子集合S，
答案就在S的元素中（因为这些数字和0123碰撞测试，也产生A0B3）。

第二回合从S中取一个数字 t ，POST给服务器，根据返回的AB值，进一步缩小集合（找出和数字t碰撞后反馈同为 AB 的子集）。。。以此类推
直到猜中为止。

猜题者请注意判断服务器返回的 tokens ，如果猜题过程中 tokens 产生变化，说明这一回合的目标已经被别人猜中了。（也可能是自己猜中了～）

当然，这只是基础策略，还有很大优化空间。

523066680

回复 2# rubyish

我先举一个本地猜数字的例子（包含一个测试盒子，guess 函数），写的比较粗糙：

1. use IO::Handle;
   
2. STDOUT->autoflush(1);
   
3. 
   
4. our @nums;
   
5. our $nums;
   
6. generate(\@nums);                       #初始化随机4位数
   
7. $nums = join("", @nums);
   
8. 
   
9. our @orders;
   
10. permute( [0 .. 9] , [], 4, \@orders);   #0-9取4个数的所有组合
    
11. 
    
12. print "Rand Number: $nums\n";
    
13. 
    
14. my $AB;
    
15. my $guess = "0123";
    
16. 
    
17. while (1)
    
18. {
    
19.     $AB = guess( $nums, $guess );
    
20.     print "$guess - $AB\n";
    
21.     last if ( $AB eq "40" );
    
22. 
    
23.     reduce( \@orders, $guess, $AB );    #缩小可选数组的范围
    
24.     $guess = shift @orders;
    
25. }
    
26. 
    
27. =function
    
28.     reduce   根据反馈的AB值，缩小集合范围
    
29.     guess    测试盒，给出两个数字，返回 AB 值
    
30.     generate 生成4位不重复的随机数
    
31.     permute  生成 0-9 排成 4位数(不重复)的所有组合
    
32. =cut
    
33. 
    
34. sub reduce
    
35. {
    
36.     my ($oref, $guess, $AB) = @_;
    
37.     my @temparr;
    
38.     my $TAB;
    
39.     my $idx = 0;
    
40. 
    
41.     for my $e ( @$oref )
    
42.     {
    
43.         $TAB = guess( $e, $guess );
    
44.         push @temparr, $e if ( $TAB eq $AB );
    
45.     }
    
46. 
    
47.     @$oref = @temparr;
    
48. }
    
49. 
    
50. sub guess
    
51. {
    
52.     my ($nums, $guess) = @_;
    
53. 
    
54.     my @nums = split("", $nums);
    
55.     my @guess = split("", $guess);
    
56. 
    
57.     my ($A, $B) = (0, 0);
    
58. 
    
59.     for my $i ( 0 .. $#guess )
    
60.     {
    
61.         if ( $guess[$i] == $nums[$i] )
    
62.         {
    
63.             $A++;
    
64.         }
    
65.         else
    
66.         {
    
67.             $B++ if ( $nums =~/$guess[$i]/ );
    
68.         }
    
69.     }
    
70. 
    
71.     return $A . $B;
    
72. }
    
73. 
    
74. sub generate
    
75. {
    
76.     #从10个数字中随机挑选出4个
    
77.     my $aref = shift;
    
78.     my $len = 4;
    
79.     my [url=home.php?mod=space&uid=17981]@ele[/url] = (0..9);
    
80.     my $range = 10;
    
81.     my $get;
    
82. 
    
83.     for ( 1 .. $len )
    
84.     {
    
85.         $get = int(rand($range));
    
86.         push @$aref, $ele[$get];
    
87.         splice(@ele, $get, 1);
    
88.         $range--;
    
89.     }
    
90. }
    
91. 
    
92. sub permute
    
93. {
    
94.     my ( $a, $b, $n, $aref ) = @_;
    
95.     my $last = $#$a;
    
96. 
    
97.     if ( $#$b >= ($n-1) )
    
98.     {
    
99.         push @$aref, join("", @$b);
    
100.         return;
     
101.     }
     
102. 
     
103.     for my $idx ( 0 .. $last )
     
104.     {
     
105.         permute( [ @$a[0 .. $idx-1, $idx+1 .. $last] ], [ @$b, $a->[$idx] ], $n, $aref );
     
106.     }
     
107. }

复制代码

输出样板
Rand Number: 0954
0123 - 10
0456 - 21
0467 - 11
0586 - 11
0954 - 40

523066680

遍历测试：

1. Times: 26751, average: 5.307738
   
2. 1, 1
   
3. 2, 11
   
4. 3, 80
   
5. 4, 556
   
6. 5, 2277
   
7. 6, 1929
   
8. 7, 183
   
9. 8, 3

复制代码

523066680

回复 5# 本友会机友会摄友会

哈哈哈，怂了吧，真碰到题目还是不敢来了，算法固定的？优化算法去查了没有？
敢不敢实现一个先跑起来？最坏情况指标、平均情况指标、反馈个数指标 这些都懂？
踢馆要是只有这种水平，就不要出来丢 powershell 的脸了

比赛方式；
比猜题速率，线下各自使用程序统计不同的用户每分钟猜中多少次。设定一个截止日期结束比赛，参加者可以在结束前不断优化算法以提高猜题速率。

Get 这个地址可以获得当前时间每个用户的猜中次数，从而统计猜题速度
http://www.codetiger.win/extra/score.json
{"adad":194301,"vic3":160852,"BatchScript":89139,"coadsa":850,"robot":397,"llsd":139,"sdafasdf":75,"sfwfssf":0,"1111111111":0}


关于公平性：
网站是一个深圳中学生建的，我这里 ping 该网站的返回结果是（体现了网络响应速度）：

正在 Ping www.codetiger.win [43.251.105.212] 具有 32 字节的数据:
来自 43.251.105.212 的回复: 字节=32 时间=13ms TTL=54
来自 43.251.105.212 的回复: 字节=32 时间=12ms TTL=54
来自 43.251.105.212 的回复: 字节=32 时间=14ms TTL=54
来自 43.251.105.212 的回复: 字节=32 时间=15ms TTL=54

即使不敢应战，起码跑个本地的让我们瞧瞧 powershell 的强大？

523066680

回复 7# rubyish

估值。
普通的筛选法，是在每一层，在可选元素中选第一个，没有任何优化。
这种方案测完5040种情况的统计结果大致如下，平均需要猜 5.56 次：

1. Times: 28024, average: 5.560317
   
2. 1, 1
   
3. 2, 13
   
4. 3, 108
   
5. 4, 596
   
6. 5, 1668
   
7. 6, 1768
   
8. 7, 752
   
9. 8, 129
   
10. 9, 5

复制代码

如果在每一层，我们在可选数字中，做一些判断，把判断为较好的数字选为下次测试的数字，最大回合数/平均回合数就能减少。
比如百度百科提到的最大反馈指标：用子集合中的每一个元素去碰撞集合，看哪一个数字碰撞时得到更多的反馈类型
举个例子，当前缩小集合是 S = (1032,1230,1302,2031,2301,2310,3012,3201,3210)
用这些元素分别碰撞整个数组，得到不同的反馈，反馈越多的，说明下一层子集合的平均量越小。（当前总数/反馈数）
1032 - 04,22,40
1230 - 04,22,13,40
1302 - 04,13,22,40
2031 - 13,04,40,22
2301 - 04,22,40
2310 - 22,13,04,40
3012 - 04,22,13,40
3201 - 04,13,22,40
3210 - 04,22,40

按这种方案，可以选 1230,1302,2310,3012,3201 中的一个。当然，还可以进一步优化，做更准确的的评估。
以及碰撞的集合不一定是在 S集合内，可以是整个5040种排列和 S集合碰撞

使用最大反馈估值（在较高估值的结果中选第一项），测试结果是：

1. Times: 27139, average: 5.384722
   
2. 1, 1
   
3. 2, 3
   
4. 3, 44
   
5. 4, 515
   
6. 5, 2124
   
7. 6, 2151
   
8. 7, 202

复制代码

523066680

回复 9# rubyish

关于效率，我用 NTYProf 分析自己代码的时候发现 是AB反馈函数耗时最多，这个函数改为内联C函数处理就快多了

1. =info
   
2.     523066680, 2017-08
   
3. =cut
   
4. 
   
5. use Inline C;
   
6. 
   
7. my $AB = "00";
   
8. bullcow("0123", "5280", $AB);
   
9. print $AB;
   
10. 
    
11. __END__
    
12. __C__
    
13. void bullcow(char *stra, char *strb, char *AB)
    
14. {
    
15.     int idx;
    
16.     char a = '0';
    
17.     char b = '0';
    
18. 
    
19.     for ( idx = 0; idx < 4; idx++ )
    
20.     {
    
21.         if ( stra[idx] == strb[idx] )
    
22.             a++;
    
23.         else
    
24.             if ( strchr(stra, strb[idx]) != 0 )
    
25.             {
    
26.                 b++;
    
27.             }
    
28.     }
    
29. 
    
30.     AB[0] = a;
    
31.     AB[1] = b;
    
32. }

复制代码

原来四五十秒的大批量测试，用内联C可能不到1秒完成。

我才发现你整个程序都用C实现的，这个涉及到树分支的筛选和构造，我觉得用完全C太累了，还是脚本操作方便

===============================================================

进一步优化，如果要用某个优化指标的方案去测试5040个数字，最好的方法是把优化指标的搜索顺序生成结构树。
比如 $tree->{0123} = { '01' => {子集合以及下一级反馈}, '02' => {子集合以及下一级反馈} .....  '30'=>{子集合以及下一级反馈} }
将树导出，需要用的时候加载使用，这样就不用每次都进行筛选，循着树的分支选取下一个数字。

523066680

生成搜索树（没有估值，从每个子集中选第一项作为下一层的猜测数），内联C

1. =info
   
2.     Code By 523066680, 2017-08-10
   
3.    
   
4.     选择第一项
   
5.     $k = shift @keyset;
   
6. 
   
7.     选择中间项
   
8.     $k = splice @keyset, int(($#keyset+1)/2), 1;
   
9. =cut
   
10. 
    
11. use Inline C;
    
12. use IO::Handle;
    
13. use Data::Dumper;
    
14. use File::Slurp;
    
15. STDOUT->autoflush(1);
    
16. $Data::Dumper::Indent = 1;
    
17. $Data::Dumper::Sortkeys = 1;
    
18. 
    
19. #生成所有排列
    
20. my @orders;
    
21. permute( [0 .. 9] , [], 4, \@orders);
    
22. 
    
23. print "Step 1, make tree\n";
    
24. my $tree;
    
25. #树的起点固定为 - "0123"，首层的可选排列有5040种
    
26. $tree = { "0123" => {} };
    
27. maketree( $tree, \@orders, 0 );
    
28. 
    
29. #生成 Perl 树结构，以及 JSON 树结构
    
30. print "Step 2, dump tree\n";
    
31. write_file("./Tree.txt", Dumper $tree);
    
32. 
    
33. sub maketree
    
34. {
    
35.         my ($ref, $arr, $lv) = @_;
    
36.         my $AB = "00";
    
37.     my $k;
    
38.     my @keyset;
    
39.    
    
40.     #将所有项按字符排序
    
41.     @keyset = sort { $a cmp $b } keys %$ref;
    
42. 
    
43.     #选择第一项
    
44.     $k = shift @keyset;
    
45. 
    
46.     #生成反馈节点 {$AB}，以及每个反馈下的数字集合 {$e}
    
47.         for my $e ( @$arr )
    
48.         {
    
49.                 bullcow( $k, $e, $AB );
    
50.                 if ($AB ne "40")
    
51.                 {
    
52.             $ref->{$k}{$AB}{$e} = {};
    
53.                 }
    
54.         }
    
55. 
    
56.     #从首层(相对地)节点中删除 $k 以外的项
    
57.     grep { delete $ref->{$_} } @keyset;
    
58. 
    
59.     #对于每一个反馈，递归筛选新的数字集合、生成子节点
    
60.     for my $ab ( keys %{ $ref->{ $k } } )
    
61.     {
    
62.         maketree( $ref->{$k}{$ab}, [ keys %{$ref->{$k}{$ab}} ], $lv+1 );
    
63.     }
    
64. }
    
65. 
    
66. sub permute
    
67. {
    
68.     my ( $a, $b, $n, $aref ) = @_;
    
69.     my $last = $#$a;
    
70. 
    
71.     if ( $#$b >= ($n-1) )
    
72.     {
    
73.         push @$aref, join("", @$b);
    
74.         return;
    
75.     }
    
76. 
    
77.     for my $idx ( 0 .. $last )
    
78.     {
    
79.         permute( [ @$a[0 .. $idx-1, $idx+1 .. $last] ], [ @$b, $a->[$idx] ], $n, $aref );
    
80.     }
    
81. }
    
82. 
    
83. __END__
    
84. __C__
    
85. void bullcow(char *stra, char *strb, char *AB)
    
86. {
    
87.     int idx;
    
88.     char a = '0';
    
89.     char b = '0';
    
90. 
    
91.     for ( idx = 0; idx < 4; idx++ )
    
92.     {
    
93.         if ( stra[idx] == strb[idx] )
    
94.             a++;
    
95.         else
    
96.             if ( strchr(stra, strb[idx]) != 0 )
    
97.             {
    
98.                 b++;
    
99.             }
    
100.     }
     
101. 
     
102.     AB[0] = a;
     
103.     AB[1] = b;
     
104. }

复制代码

523066680

回复 13# rubyish

其实就是把搜索的过程以及可能遇到的情况都保存到结构树里，实际测试的时候顺着树节点跑就是了（省去了反复筛选的过程）。

1. =info
   
2.     523066680 2017-08
   
3. =cut
   
4. 
   
5. use IO::Handle;
   
6. use File::Slurp;
   
7. STDOUT->autoflush(1);
   
8. 
   
9. #加载树结构
   
10. my $tree = eval read_file("tree.txt");
    
11. my $ref = $tree;
    
12. 
    
13. my $AB;
    
14. my $guess;
    
15. my $secret = "9876";
    
16. print "Target Number: $secret\n";
    
17. ($guess) = keys %$ref;
    
18. 
    
19. while (1)
    
20. {
    
21.     $AB = guess( $secret, $guess );
    
22.     print "[$AB] $guess\n";
    
23. 
    
24.     last if ( $AB eq "40" );
    
25. 
    
26.     #迭代树节点，提取下一节点的猜数
    
27.     if ( exists $ref->{$guess}{$AB} )
    
28.     {
    
29.         $ref = $ref->{$guess}{$AB};
    
30.         ($guess) = keys %{$ref};
    
31.     }
    
32.     else
    
33.     {
    
34.         die "Something wrong\n";
    
35.     }
    
36. }
    
37. 
    
38. sub guess
    
39. {
    
40.     my ($secret, $guess) = @_;
    
41.     my ($A, $B) = (0, 0);
    
42.     my $t;
    
43. 
    
44.     for my $i ( 0 .. 3 )
    
45.     {
    
46.         if ( substr($secret, $i, 1) eq substr($guess, $i, 1) )
    
47.         {
    
48.             $A++;
    
49.         }
    
50.         else
    
51.         {
    
52.             $t = substr($guess, $i, 1);
    
53.             $B++ if ( $secret =~/$t/ );
    
54.         }
    
55.         $i++;
    
56.     }
    
57. 
    
58.     return $A . $B;
    
59. }
    

复制代码

最大反馈指标的搜索树，以及普通搜索树
http://523066680.ys168.com/
目录 Perl/猜数字游戏bullscows

523066680

回复 16# rubyish

用结构树猜数字，遍历5040种情况，可以秒出结果（print 消耗不计入内）

其他预期估值公式汇总
http://www.pepsplace.org.uk/Trivia/Moo/Moo.pdf

举几个例子，
Minimise the square of the variance - 最小化平方差估值
对于某一层得到的反馈，将每个反馈下的可能集合（子集合）的数量分别统计为 t1 t2 t3 .. tn
对这些t值分别平方、求和，再除以反馈数量n， (t1^2+t2^2+ ... tn^2)/n，值越小，就能越快缩小范围。
（本质就是在追求最大反馈量的同时，确保各反馈下子集合数量的均衡，不会相差太大。）

公式末尾有个函数 -f(1)，如果该最小值属于5040种排列但不属于当前子集合，返回0；如果属于当前子集合，返回1
也就是：如果子集合种也包含最小估值，则优先选择子集合种的元素。

Square root - 平方根估值
(t1*sqrt(t1) + t2*sqrt(t2) .... tn*sqrt(tn) )/n - f(1)

Information content - Dr J. Larmouth 给出的算法。
sum( t1*log(t1) ... tn*log(tn) )  / n - f(2*log(2)) , f() 函数参考前面的说明，猜数字属于子集合时返回 2*log(2)，否则返回0
平均回合数为 5.239

经过 rubyish 提醒，Larmouth 的算法应该为
sum( t1*log(t1) ... tn*log(tn) ) - f(2*log(2)) ，当时习惯性地加了 /n，Sorry。

523066680

回复 18# rubyish

用C实现比较繁琐，你的C代码我也没有仔细看，结果不一致可能是实现细节有差别。
我把完整的生成树和遍历测试的代码发到网盘了，你对比下。

http://ys-h.ys168.com/205774914/ ... %96%B9%E6%A1%88.zip

http://523066680.ys168.com/
perl/猜数字游戏/Larmouth方案.zip