猜数游戏AI设计

猜数游戏简介

通常由两个人玩,一方出数字,一方猜。出数字的人要想好一个没有重复数字的4个数,不能让猜的人知道。猜的人就可以开始猜。每猜一个数字,出数者就要根据这个数字给出几A几B,其中A前面的数字表示位置正确的数的个数,而B前的数字表示数字正确而位置不对的数的个数。如正确答案为 5234,而猜的人猜 5346,则是 1A2B,其中有一个5的位置对了,记为1A,而3和4这两个数字对了,而位置没对,因此记为 2B,合起来就是 1A2B。接着猜的人再根据出题者的几A几B继续猜,直到猜中(即 4A0B)为止。(摘自百度百科)

这个游戏在班级里兴起,考虑到总共只有10000个数(如果除去不合法的数,结果将更小),因此每一步都可以支持n^2的运算量,因此AI是可行的。

版本划分原则

整数部分的增加只在猜数策略改进时发生,每一代间,AI猜数能力有实质提升。小数部分的增加在bug修复、功能更新、参数优化时增加。

vers1.x

实在没有能力写神经网络orz,因此这只是一个广义的AI。第一代只打算探究一下程序的实现方式。在这个版本中引入了“待选池”这一概念。待选池是所有可能成为答案的数的集合。在游戏开始,待选池是所有合法的数。从0123开始猜,根据每次反馈的结果从待选池中删去不符合的数,然后以第一个比0123大的数作为下一个猜数,以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//vers1.0
#include<bits/stdc++.h>
#define eps (1e-3)
#define abs(a) ((a)>0?(a):(-(a)))
#define sqr(a) ((a)*(a))
#define fsb(a,b,c) for(int a=b;a<=c;a++)
#define fbs(a,b,c) for(int a=b;a>=c;a--)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int tot=0,a[10000]/*编号-->数字*/,b[10000]/*编号*/,comp[5][5],pre,check,start;
int rd[10000],l,tern,lA;
struct result{
int A,B;
}res;
inline void rll(int &x){
x=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
inline void addtot(int i,int j,int k,int l){
a[++tot]=i*1000+j*100+k*10+l;b[tot]=1;
}
inline int getn(int X,int n){
fsb(i,1,4-n)X/=10;
return X%10;
}
inline result cmp(int X/*答案*/,int Y/*猜测*/){
int x[10],y[10],A=0,B=0;
fsb(i,1,4)x[i]=getn(X,i);
fsb(i,1,4)y[i]=getn(Y,i);
fsb(i,1,4)
fsb(j,1,4){
if(x[i]==y[j]){
if(i==j)A++;else B++;
break;
}
}
return (result){A,B};
}
inline void kil(int A,int B,int guess){
int cnt=0;
fsb(i,1,tot){
if(b[i]==1&&(cmp(a[i],guess).A!=A||cmp(a[i],guess).B!=B))b[i]=0;
if(a[i]==guess)b[i]=-1;
if(b[i]==1)cnt++;
}
if(cnt==0)check=-1;
}
inline int make_guess(){
if(start==0)start=rand()%tot+1;
pre=0;fsb(i,1,tot)if(b[i]==1)pre++;
fsb(i,start,tot)if(b[i]==1)return a[i];
fsb(i,1,start-1)if(b[i]==1)return a[i];
}
inline int len(int x){
if(x>=1000)return 4;if(x>=100)return 3;if(x>=10)return 2;return 1;
}
inline void op(int x){
printf("guess: ");fsb(i,1,4)printf("%d ",getn(x,i));printf("(%d)",pre);
fsb(i,1,6-len(pre))printf(" ");
}
int main(){
printf("-猜数游戏辅助vers1.0 zijunhz@126.com\n");
printf("-回复A和B的个数并press回车\n");
printf("-括号内为剩余可能性\n");
srand(time(NULL));
mem(b,0);
fsb(i,0,9)fsb(j,0,9)fsb(k,0,9)fsb(l,0,9){
if(i==j||i==k||i==l)continue;
if(j==k||j==l)continue;
if(k==l)continue;
addtot(i,j,k,l);
}
// /*
while(1){
puts("");system("pause");puts("");
fsb(i,1,tot)b[i]=1;
tern=0;check=1;lA=0;start=0;
while(1){
tern++;int guess=make_guess();
op(guess);
rll(res.A);rll(res.B);lA=res.A;
cin.sync();
if(res.A==4)break;
kil(res.A,res.B,guess);
if(check==-1){
puts("---illegal---");break;
}
}
printf("共%d步猜出\n",tern);
}
// */
/*
int count=0,lun=0,fnl,mo;
printf("输入统计间隔:");scanf("%d",&mo);
while(1){
fsb(i,1,tot)b[i]=1;
lun++;//int singlecount=0;
// puts("Input your num:");rll(fnl);
fnl=a[rand()%tot+1];
tern=0;lA=0;start=0;
while(1){
tern++;count++;//singlecount++;
int guess=make_guess();
res=cmp(fnl,guess);lA=res.A;
// op(guess);//输出猜测
// printf(" %d %d \n",res.A,res.B);//输出回复
if(res.A==4)break;
kil(res.A,res.B,guess);
}
// if(singlecount>=8)return 0;
if(lun%mo==0)printf(" ave: %10.5lf\n",1.0*count/lun);
// system("pause");
}
*/
return 0;
}

平均次数:5.53

vers2.x

vers1.x的缺点显而易见,猜测盲目,最坏情况次数太多。因此vers2.x在猜数策略上有较大调整,拒绝盲猜。猜数策略具体是这样的:

考虑猜一个数a,这个数会把待选池按照回复不同划分成几组,我们希望这几组尽量平均,也就是能以最快的速度缩小待选池的大小。因此遍历每个在待选池中的数,依照其对待选池的划分计算方差,选择方差最小的那个数作为下一个猜的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//vers2.0
#include<bits/stdc++.h>
#define eps (1e-3)
#define abs(a) ((a)>0?(a):(-(a)))
#define sqr(a) ((a)*(a))
#define fsb(a,b,c) for(int a=b;a<=c;a++)
#define fbs(a,b,c) for(int a=b;a>=c;a--)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int tot=0,a[10000]/*编号-->数字*/,b[10000]/*编号*/,comp[5][5],pre,check;
int rd[10000],l,flag;
struct result{
int A,B;
}res;
inline void rll(int &x){
x=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
inline void addtot(int i,int j,int k,int l){
a[++tot]=i*1000+j*100+k*10+l;b[tot]=1;
}
inline int getn(int X,int n){
fsb(i,1,4-n)X/=10;
return X%10;
}
inline result cmp(int X/*答案*/,int Y/*猜测*/){
int x[10],y[10],A=0,B=0;
fsb(i,1,4)x[i]=getn(X,i);
fsb(i,1,4)y[i]=getn(Y,i);
fsb(i,1,4)
fsb(j,1,4){
if(x[i]==y[j]){
if(i==j)A++;else B++;
break;
}
}
return (result){A,B};
}
inline void kil(int A,int B,int guess){
int cnt=0;
fsb(i,1,tot){
if(b[i]==1&&((cmp(a[i],guess).A!=A||cmp(a[i],guess).B!=B)||a[i]==guess))b[i]=0;
if(b[i])cnt++;
}
if(cnt==0)check=-1;
}
inline int make_guess(){
double bestans=1e10,ans,ave,cnt;l=0;
pre=0;
fsb(i,1,tot){
if(b[i]==0)continue;
pre++;
mem(comp,0);
fsb(j,1,tot)
if(b[j]==1){
comp[cmp(a[j],a[i]).A][cmp(a[j],a[i]).B]++;
}
cnt=0;ave=0;
fsb(j,0,4)fsb(k,0,4-j)
if(comp[j][k]!=0){
cnt++;ave+=comp[j][k];
}
ave/=cnt;ans=0;
fsb(j,0,4)fsb(k,0,4-j)
if(comp[j][k]!=0){
ans+=sqr(ave-comp[j][k]);
}
ans/=cnt;
if(abs(ans-bestans)<=eps){
rd[++l]=i;continue;
}
if(ans<bestans){
l=1;rd[1]=i;bestans=ans;
}
}
int k=rand()%l+1;
// printf("? %d\n",b[rd[k]]);
return a[rd[k]];
}
inline void op(int x){
printf("guess: ");fsb(i,1,4)printf("%d ",getn(x,i));printf("(%d)\n",pre);
}
int main(){
printf("-猜数游戏辅助-vers2\n-更新:\n- 全新猜数策略\n-回复A和B的个数并press回车\n\n");
srand(time(NULL));
mem(b,0);
fsb(i,0,9)fsb(j,0,9)fsb(k,0,9)fsb(l,0,9){
if(i==j||i==k||i==l)continue;
if(j==k||j==l)continue;
if(k==l)continue;
addtot(i,j,k,l);
}
// /*
while(1){
system("pause");
fsb(i,1,tot)b[i]=1;
flag=1;check=1;
while(1){
int guess;
if(flag==0){
guess=make_guess();
}else{
guess=a[rand()%tot+1];flag=0;pre=5040;
}
op(guess);
rll(res.A);rll(res.B);
if(res.A==4)break;
kil(res.A,res.B,guess);
if(check==-1){
puts("---illegal---");break;
}
}
}
// */
/*
int count=0,lun=0,fnl;
while(1){
fsb(i,1,tot)b[i]=1;
lun++;
// puts("Input your num:");rll(fnl);
fnl=a[rand()%tot+1];
flag=1;
while(1){
count++;
int guess;
if(flag==0){
guess=make_guess();
}else{
guess= a[rand()%tot+1];
flag=0;pre=5040;
}
res=cmp(fnl,guess);
// op(guess);//输出猜测
// printf(" %d %d \n",res.A,res.B);//输出回复
if(res.A==4)break;
kil(res.A,res.B,guess);
}

if(lun%1000==0)printf(" ave: %10.5lf\n\n",1.0*count/lun);
// system("pause");
}
*/
return 0;
}

平均次数:5.33

vers3.x

在vers2.x的策略中,程序会被第一次3A0B的情况卡,也就是遍历剩下的6个数。这就可以被人为地轻易卡到7。因此在出现3A的时候改变猜数策略,再随机猜一次,从第三次开始遵从vers2.x的原则。

另外,vers3.x加了很多功能更新,比如显示猜对成功率,不合法的输入判断(在vers2.x会导致程序崩溃)

1
//vers3.1

平均次数:5.32

vers4.x

考虑一种情况,待选池中有10个数。第一种猜测导致的分组是2 2 2 2 2,第二种猜测导致的分组是2 2 2 1 1 1 1。在3.x的版本中,因为我们只考虑方差,因此会选择分成5个2的猜测——显然第二种猜测更优。导致这种结果的原因是,程序过度看重平分每一组,而忽略了组数。因此在4.x的版本中,估值函数加入了组数。

1
//vers4.1

平均次数:5.31