[算法讨论]猜数字游戏 - Bulls and Cows
本帖最后由 523066680 于 2017-09-02 14:20 编辑在线猜数字游戏链接：http://www.codetiger.win/extra/
先注册账号，然后通过 post 提交并获取返回的数据，像这样
$res = $ua->post(
$website,
[ username=>$user, password =>$pass, number=>$n, send=>'answer' ]
);
返回 JSON 格式的参考数据：
{"code":150,"A":0,"B":2,"count":49721,"tokens":"8550662099813553"}
游戏规则和JSON参数说明请见主页（这个网站和竞赛是一个小朋友搞的，后生可畏）
另外，提供一点资料
www.cs.nccu.edu.tw/~chaolin/papers/science3203.pdf
这个文档是中文的，讲了两个数字游戏，关于这次的游戏的分析和解法在后半部分。
---------------------------------------------------------------------------------------
基础的解题方案可以参考上面给出的PDF的后半部分。
服务器随机生成 组成的 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 产生变化，说明这一回合的目标已经被别人猜中了。（也可能是自己猜中了～）
当然，这只是基础策略，还有很大优化空间。
KBD?:em21::em21:
min MAX, or min average??? 本帖最后由 523066680 于 2017-08-23 11:52 编辑
回复 2# rubyish
我先举一个本地猜数字的例子（包含一个测试盒子，guess 函数），写的比较粗糙：
use IO::Handle;
STDOUT->autoflush(1);
our @nums;
our $nums;
generate(\@nums); #初始化随机4位数
$nums = join("", @nums);
our @orders;
permute( , [], 4, \@orders); #0-9取4个数的所有组合
print "Rand Number: $nums\n";
my $AB;
my $guess = "0123";
while (1)
{
$AB = guess( $nums, $guess );
print "$guess - $AB\n";
last if ( $AB eq "40" );
reduce( \@orders, $guess, $AB ); #缩小可选数组的范围
$guess = shift @orders;
}
=function
reduce 根据反馈的AB值，缩小集合范围
guess 测试盒，给出两个数字，返回 AB 值
generate 生成4位不重复的随机数
permute生成 0-9 排成 4位数(不重复)的所有组合
=cut
sub reduce
{
my ($oref, $guess, $AB) = @_;
my @temparr;
my $TAB;
my $idx = 0;
for my $e ( @$oref )
{
$TAB = guess( $e, $guess );
push @temparr, $e if ( $TAB eq $AB );
}
@$oref = @temparr;
}
sub guess
{
my ($nums, $guess) = @_;
my @nums = split("", $nums);
my @guess = split("", $guess);
my ($A, $B) = (0, 0);
for my $i ( 0 .. $#guess )
{
if ( $guess[$i] == $nums[$i] )
{
$A++;
}
else
{
$B++ if ( $nums =~/$guess[$i]/ );
}
}
return $A . $B;
}
sub generate
{
#从10个数字中随机挑选出4个
my $aref = shift;
my $len = 4;
my @ele = (0..9);
my $range = 10;
my $get;
for ( 1 .. $len )
{
$get = int(rand($range));
push @$aref, $ele[$get];
splice(@ele, $get, 1);
$range--;
}
}
sub permute
{
my ( $a, $b, $n, $aref ) = @_;
my $last = $#$a;
if ( $#$b >= ($n-1) )
{
push @$aref, join("", @$b);
return;
}
for my $idx ( 0 .. $last )
{
permute( [ @$a ], [ @$b, $a->[$idx] ], $n, $aref );
}
}
输出样板
Rand Number: 0954
0123 - 10
0456 - 21
0467 - 11
0586 - 11
0954 - 40
反馈指标
本帖最后由 523066680 于 2017-08-23 11:54 编辑遍历测试：Times: 26751, average: 5.307738
1, 1
2, 11
3, 80
4, 556
5, 2277
6, 1929
7, 183
8, 3 本帖最后由 523066680 于 2017-08-24 18:36 编辑
回复 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 具有 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 的强大？
回复 6# 523066680
根据计算机测算，如果采用严谨的猜测策略，任何数字最多7次就可猜出（即达到 4A0B）。
Caiyong Pusude xiefa: Faxian you gaoda 8, 9 ci de
my @new = grep { ... } @old;
7 ci shi ruhe dacheng de?
本帖最后由 523066680 于 2017-08-30 10:23 编辑
回复 7# rubyish
估值。
普通的筛选法，是在每一层，在可选元素中选第一个，没有任何优化。
这种方案测完5040种情况的统计结果大致如下，平均需要猜 5.56 次：
Times: 28024, average: 5.560317
1, 1
2, 13
3, 108
4, 596
5, 1668
6, 1768
7, 752
8, 129
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集合碰撞
使用最大反馈估值（在较高估值的结果中选第一项），测试结果是：
Times: 27139, average: 5.384722
1, 1
2, 3
3, 44
4, 515
5, 2124
6, 2151
7, 202
本帖最后由 rubyish 于 2017-08-31 00:58 编辑
回复 8# 523066680
1 1
2 9
3 44
4 344
5 1831
6 2480
7 331
AVE = 5.531548
real 23m15.507s
user 23m13.891s
sys 0m0.697s
Queshi zai 7 ci zhinei
Wode ave shi 5.53
Nide shi 5.38
Question:
1: Ruhe dadao 5.38 de ave?
2: 23m, taimanle, ruhe OPT?
3Q~~
# include <stdio.h>
# include <string.h>
# define OK 0x40
# define get_a(A) A >> 4
# define get_b(A) 0xF & A
# define show(a) printf ("[ %d%d%d%d ]", a, a, a, a);
# define copy(A, B) memcpy (A, B, 4)
# define COPY(A, B) memcpy (A, B, 20160)
// 20160 == 5040 * 4
# define TEST 5040
typedef char kar;
kar TOTO;
kar MAYBE;
int COUNT;
int LEN;
int AB (kar*, kar*);
void make (int);
kar* gimme (void);
void grep (kar*, int);
void test (void);
/* ____________________ MAIN ____________________ */
int main (){
make (0);
test ();
}
/* _____________________ SUB _____________________ */
void test () {
for (int v = 0; v < TEST; v++) {
printf ("%d\n", v + 1);
COPY (MAYBE, TOTO);
kar *ans = TOTO;
kar *gue = TOTO;
LEN = 5040;
// show (ans);
// puts ("");
int x;
for (x = 1; x < 15; x++) {
// show (gue);
int ab = AB (ans, gue);
// int a= get_a (ab);
// int b= get_b (ab);
// printf (" %d AB = %d %d\n", x, a, b);
if (ab == OK) break;
grep (gue, ab);
gue = gimme ();
}
COUNT++;
}
puts ("-----------------");
int ave = 0;
for (int i = 1; i < 15; i++) {
printf ("%d\t%d\n", i, COUNT);
ave += i * COUNT;
}
printf ("AVE = %f\n", ave / (double)TEST);
}
void grep (kar *gue, int ab){
int I = 0;
for (int i = 0; i < LEN; i++) {
int ab2 = AB (MAYBE, gue);
if (ab2 == ab)
copy (MAYBE, MAYBE);
}
LEN = I;
}
kar* gimme (){
static int var[] = { 0, 5, 9, 12, 14 };
if (LEN == 1) return MAYBE;
int best = 0;
int max= 0;
for (int i = 0; i < 5040; i++) {
int test = { 0 };
for (int j = 0; j < LEN; j++) {
int ab = AB (TOTO, MAYBE);
int a= get_a (ab);
int b= get_b (ab);
int I= var + b;
test++;
}
int toto = 0;
for (int i = 0; i < 15; i++)
if (test) toto++;
if (toto > max) {
max= toto;
best = i;
}
}
return TOTO;
}
int AB (kar *ans, kar *gue){
int ab = { 0 };
for (int i = 0; i < 4; i++) {
if (ans == gue) ab++;
else
for (int j = 0; j < 4; j++)
if (ans == gue) ab++;
}
return (ab << 4) | ab;
}
void make (int lev){
static kar num;
static int I = 0;
static int has;
if (lev == 4) {
copy (TOTO, num);
return;
}
for (int i = 0; i <= 9; i++) {
if (has) continue;
has = 1;
num = i;
make (lev + 1);
has = 0;
}
}
本帖最后由 523066680 于 2017-08-31 08:59 编辑
回复 9# rubyish
关于效率，我用 NTYProf 分析自己代码的时候发现 是AB反馈函数耗时最多，这个函数改为内联C函数处理就快多了
=info
523066680, 2017-08
=cut
use Inline C;
my $AB = "00";
bullcow("0123", "5280", $AB);
print $AB;
__END__
__C__
void bullcow(char *stra, char *strb, char *AB)
{
int idx;
char a = '0';
char b = '0';
for ( idx = 0; idx < 4; idx++ )
{
if ( stra == strb )
a++;
else
if ( strchr(stra, strb) != 0 )
{
b++;
}
}
AB = a;
AB = b;
}
原来四五十秒的大批量测试，用内联C可能不到1秒完成。
我才发现你整个程序都用C实现的，这个涉及到树分支的筛选和构造，我觉得用完全C太累了，还是脚本操作方便
===============================================================
进一步优化，如果要用某个优化指标的方案去测试5040个数字，最好的方法是把优化指标的搜索顺序生成结构树。
比如 $tree->{0123} = { '01' => {子集合以及下一级反馈}, '02' => {子集合以及下一级反馈} .....'30'=>{子集合以及下一级反馈} }
将树导出，需要用的时候加载使用，这样就不用每次都进行筛选，循着树的分支选取下一个数字。