问题描述
又名猜数字。
一方准备从0到9十个数字里抽出4个数，随机排列，另一方同样以这样的方法回应四个数。位置相同数字相同为A，数字出现，位置不同为B，然后计数。
例1234
5678-0A0B
9012-0A2B
4321-0A4B
1243-2A2B
分析
这个问题关键在于估算备选答案带来的收益。比如题中说的4位数，那么每次决策都有10000种。不同的决策带来的信息量是不同的。我们所期望的是信息量快速增加。所以关键在于如何定义一个决策带来的收益（信息量）。
可以使用熵，熵是描述事物混乱程度的度量。但是我觉得用下面这种方式更好：
如果我猜数字x，你给出的答案（几个A几个B）最多有n*n种，将当前的可行解当做小球放入n*n个盒子。我需要考虑你给出答案之后，期望能够排除掉多少个可行解，排除掉的可行解的个数越多越好。记c1,c2,c3,c4..... C_{n*n} 分别表示你的答案对应的可行解的个数，这些数字之和（也就是可行解的个数）记为N。
那么，我猜数字x，你给出答案1的概率为 $frac{c_1}{N} $，这时剩余可行解的个数为$ c_1 $
你给出答案2的概率为$ frac{c_2}{N} $，这时剩余可行解的个数为$ c_2$
......
综上可知，我猜数字x，期望可行解的个数为$ frac{c_1}{N} imes c_1+frac{c_2}{N} imes c_2+...+frac{c_n}{N} imes c_n $
我们想要的是最优决策，最优决策之后，能够最大限度地缩小可行解范围。经过以上定义，就可以枚举全部决策，找到最有答案。
如果是4位数，需要建立一个10000*10000的大表。还是用3位数来说明一下吧。
n = 3
a = [[0] * 10 ** n for _ in range(10 ** n)]
valid = [1] * (10 ** n)
def bit(x, k):
# 获取数字x的第k为数字
return x // (10 ** k) % 10
def dif(x, y):
# 计算x和y的dif结果，也就是p个数字位置数值都相同，q个数字数值相同位置不同
p, q = 0, 0
x_set = set()
y_set = set()
for i in range(n):
if bit(x, i) == bit(y, i):
p += 1
else:
x_set.add(bit(x, i))
y_set.add(bit(y, i))
q = len(x_set.intersection(y_set))
return p * n + q
# 初始化数组
for i in range(10 ** n):
for j in range(i + 1):
a[i][j] = a[j][i] = dif(i, j)
def get_profit(cnt):
"""
c1,c2,c3 N=c1+c2+c3 有c1/N的概率取c1，剩下的不确定度为c1（也就是不确定数字的个数）
所以期望不确定度为：ci*ci/N
这个概念类似基尼系数
:param cnt:
:return:
"""
return -sum(i * i for i in cnt)
def if_guess(x):
# 如果猜测x，会有多大的好处
cnt = [0] * (n * n + 1)
for res in range(n * n + 1):
for i in range(10 ** n):
if valid[i]:
cnt[a[x][i]] += 1
return get_profit(cnt)
def get_strategy():
# 获取当前局面下的策略
best_number = -1
best_profit = 0
for i in range(10 ** n):
if valid[i]:
profit = if_guess(i)
if best_number == -1 or profit > best_profit:
best_profit = profit
best_number = i
return best_number
def update(guess, ans):
# 根据我的猜测和他的回答，更新当前备选答案
for i in range(10 ** n):
if valid[i]:
if a[guess][i] != ans:
valid[i] = False
def over():
# 游戏是否结束
return len([i for i in valid if i]) == 1
def read_eval():
real_ans = 891
while not over():
x = get_strategy()
print("guess", x)
res = dif(real_ans, x)
print("your ans", res // n, res % n)
update(x, res)
input()
read_eval()