猜数游戏

猜数游戏

问题概述

猜一个没有重复数字的四位数,每猜一次会反馈2个数字c和e,c表示你所猜的四位数中有几个数字在答案中出现,e表示出现的这几个数字有几个在四位数中的位置与答案一致(为了使得问题有良好的对称性,第四位是0的情况,即三位数,也是允许的)。要求写一个程序进行猜数,以尽可能少的次数猜到答案。

思路

设所有可能的数的集合为S,则答案是其中随机的一个元素。游戏的本质是根据反馈信息不断缩小S,直到找到答案。程序的任务就是根据已知信息(包括S的状态和反馈信息),作出猜哪个数的决策。因此,要提高猜数效率,有两点可以入手:
1. 尽可能的利用反馈所带来的信息。不要浪费信息量,使得反馈所携带的所有信息都被程序用来减小集合S,即剔除不满足反馈信息的元素。方法是将集合中的每一个元素假设为答案,然后与你猜的数对比,如果计算出的反馈和实际得到的不同,说明该元素不是答案,换句话说,该元素已被反馈所携带的信息排除。每一次得到反馈后,都马上排除所有不符合信息的元素,即最大程度的利用了反馈信息。
2. 每次猜可以最大程度削减S的那个数。当程序要决定应该猜哪个数时,对S中的每一个元素计算:猜该元素时,出现每种可能反馈时能排除的元素个数(程序中实际计算了能剩下的元素的个数)。然后比较所有元素削减S的程度。比较的方法有两个标准,对于每一个元素,取所有反馈对应剩下个数中最大值作为该猜元素后S还剩下多少的估计值(即最坏情况),另一种是取所有反馈情况的平均情况。使得S中元素剩下个数最少的那个数就是要猜的数。
我的程序里两种标准都尝试了,并多次重复实验计算了平均猜数次数。神奇的是两种标准得到的平均次数是一样的,都是5.59左右。我觉得这个现象应该是可以理论证明的,但是我还没有想出来。先把疑问记录在这里,以后有了想法再补充吧。

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
from random import randint as ri


def feedback(num_a, num_b):
str_a = str(num_a)
str_b = str(num_b)
c = 0
e = 0
if len(str_a) == 3:
str_a = "0" + str_a
if len(str_b) == 3:
str_b = "0" + str_b
for i in range(4):
for j in range(4):
if str_a[i] == str_b[j]:
c += 1
if i == j:
e += 1
return (c, e)


def update_set(list_old, last, feed):
list_new = []
num = len(list_old)
for i in range(num):
if feedback(list_old[i], last) == feed:
list_new.append(list_old[i])
return list_new


def decision_1(list_new):
choise = 0
for n in list_new:
min_n = 10000
dict_f = {}
for m in list_new:
feed = feedback(n, m)
if feed not in dict_f:
dict_f[feed] = 1
else:
dict_f[feed] += 1
temp = sum(dict_f.values()) / len(dict_f)
if min_n > temp:
min_n = temp
choise = n
return choise


def decision_2(list_new):
choise = 0
for n in list_new:
min_n = 10000
dict_f = {}
for m in list_new:
feed = feedback(n, m)
if feed not in dict_f:
dict_f[feed] = 1
else:
dict_f[feed] += 1
temp = max(dict_f.values())
if min_n > temp:
min_n = temp
choise = n
return choise


list_ini = [] # 初始数据集
for i1 in range(10):
for i2 in range(10):
if i1 == i2:
continue
for i3 in range(10):
if i3 == i1 or i3 == i2:
continue
for i4 in range(10):
if i4 == i1 or i4 == i2 or i4 == i3:
continue
list_ini.append(i1 * 1000 + i2 * 100 + i3 * 10 + i4)
n = 10 * 9 * 8 * 7

sum_1 = 0
sum_2 = 0
t = 10000
dict_choise = {(0, 0): 9876, (1, 0): 9872, (1, 1): 9873, (2, 0): 9832, (2, 1): 9821, (2, 2): 9823, (3, 0): 9312, (3, 1): 9321, (3, 2): 9123, (3, 3): 9023, (4, 0): 3210, (4, 1): 3120, (4, 2): 3021, (4, 3): 0, (4, 4): 1023}
# dict_choise_2 = {}

# for c in range(5):
# for e in range(c + 1):
# list_temp = update_set(list_ini, 1023, (c, e))
# choise_temp_1 = decision_1(list_temp)
# choise_temp_2 = decision_2(list_temp)
# dict_choise_1[(c, e)] = choise_temp_1
# dict_choise_2[(c, e)] = choise_temp_2
# print(dict_choise_1)
# print(dict_choise_2)
for j in range(t): # 循环测试,调整数字以控制测试次数
ans_index = ri(0, n - 1) # 在初始数据集中随机取一个数字作为答案
ans = list_ini[ans_index]
# print("Case", j, ":", ans)
# choise = 1023
i = 0
feed_ini = feedback(ans, 1023)
list_one = update_set(list_ini, 1023, feed_ini)
list_new = list_one
for i in range(1, 50):
if i == 1:
choise = dict_choise[feed_ini]
feed = feedback(ans, choise)
# print(choise, feed)
# c = int(input())
# e = int(input())
if feed[1] == 4:
# print("win!")
i += 1
break
# feed = (c, e)
list_new = update_set(list_new, choise, feed)
choise = decision_1(list_new)
sum_1 += i
# choise = 1023
list_new = list_one
i = 0
for i in range(1, 50):
if i == 1:
choise = dict_choise[feed_ini]
feed = feedback(ans, choise)
# print(choise, feed)
# c = int(input())
# e = int(input())
if feed[1] == 4:
# print("win!")
i += 1
break
# feed = (c, e)
list_new = update_set(list_new, choise, feed)
choise = decision_2(list_new)
sum_2 += i
print(j)
print(sum_1 / t)
print(sum_2 / t)
# if i == 20:
# print("fail!")
# else:
# print("tried", i, "times\n")