本文将给出解答猜数字游戏（guess number）的一种算法，最多6步就可猜出结果。这个的解法需要用到部分信息论的知识。
猜数字问题表述如下：答案是0至9十个数的四位排列（没有重复元素）。每猜一次，游戏比较答案和输入这两组排列，反馈aAbB。aA表示有a个数字数值正确位置正确，bB表示b个数字数值正确位置错误。
考虑问题的互动方式，这道题目属于输入反馈的问题。每次输入，从反馈中获取部分信息，当获得系统的全部信息时，就能猜出答案。所以解这个问题的关键是寻找合适的输入使反馈的信息量最大。
这道题的解法思路比较简单，由于是有穷状态，而且数量不大，可用穷举法解答。比较所有可能的输入，找出最佳输入（某个标准下）。问题变成了如何衡量输入的好坏。输入越好则反馈的信息越大，山农给出的信息量的定义是衡量输入好坏的标准。信息量是不确定性的大小，如果某个事件的概率为P，则它含有的信息量为log(1/P)。具体的理论可以参考一本关于信息论的书。
具体到猜数字这个题目，答案有多种可能。得到反馈前，每一个输入的反馈有不同的可能。得到反馈后，反馈是确定的，不确定性变为0。这样问题的信息量变小了。前后的信息量之差就是这个输入能够得到的信息量。
统计反馈前这个输入可能得到的反馈，求出各种反馈的概率，可由下面公式计算出反馈前的信息量：
H=P1*log(1/P1)+P2*log(1/P2)+...。P1，P2等分别为不同反馈的概率。
反馈后，这个输入的反馈是确定的，信息量为0。比较所有输入能够得到信息量，就能找出最佳的输入。
统计反馈前这个输入可能得到的反馈：
// 把输入和所有可能的答案比较，得到所以不同反馈可能出现的次数
// 输入参数：input输入
// 输出参数：feedbacks反馈可能出现的次数
void GetPsbFeedbacksNum(VectorInt& feedbacks, const VectorInt& input)
{
// 和所有可能的答案比较
for (int j=0; j<ALL_ANS_NUM; j++)
{
// 答案是否已经被排除
if (g_AnsState[j] != 0)
continue;
feedbacks[GetFeedback(input, g_AllAns[j])]++;
}
}计算这个输入能够获得的信息量
// 计算信息量
// 输入参数：不同反馈出现的次数
// 返回值：信息量
double CalcEntropy(const VectorInt &feedbacks)
{
int sum = 0;
double entropy = 0.;
for (int j=0; j<feedbacks.size(); j++)
sum += feedbacks[j];
for (int j=0; j<feedbacks.size(); j++)
{
if (feedbacks[j] == 0)
continue;
float tmp = (float)feedbacks[j]/sum;
entropy += -1*tmp*log(tmp);
}
return entropy;
}
这样就得到每个输入的信息量。下面讨论如何枚举所有可能的输入。
输入的种类有10*9*8*7种，把每一种输入和所有可能答案比较。这方法比较直观，但运算次数太多。
// 得到最佳的输入，不分类直接比较的方法
// 最佳输入存放在g_AnsGuess中
void GetBestInputNoSort()
{
double max_entropy = 0.; // 存放最大的信息量
VectorInt feedbacks((ANS_SIZE+1)*(ANS_SIZE+1), 0); // 反馈的结果分类
// 比较所有输入的信息量
for (int i=0; i<ALL_ANS_NUM; i++)
{
// 这个输入的信息量是否是0
if (g_InputState[i] == 1)
continue;
// 是否只在可能的答案中搜索最佳输入
// if (g_AnsState[i] != 0)
// continue;
// 得到所有可能的反馈
feedbacks.assign((ANS_SIZE+1)*(ANS_SIZE+1), 0);
GetPsbFeedbacksNum(feedbacks, g_AllAns[i]);
// 计算信息量
double entropy = CalcEntropy(feedbacks);
// 排除信息量为0的输入
if (entropy < 0.00001)
{
g_InputState[i] = 1;
continue;
}
// 求最大的信息量
if (max_entropy < entropy)
{
max_entropy = entropy;
g_AnsGuess = g_AllAns[i];
}
}
}
由于第一次输入，各种输入能够得到的信息量是一样的，因此第一次可以不比较，任给一组输出。改进后的代码如下：
// 得到最佳的输入，不分类直接比较的方法，但优化过第一次输入。
// 最佳输入存放在g_AnsGuess中
void GetBestInputIpvFst()
{
// 如果是第一次，所有输入的信息量是一样的，任选一个
if (g_isFirstTime)
{
g_isFirstTime = 0;
g_AnsGuess = g_AllAns[0];
}
else
GetBestInputNoSort();
}
第一次输入时10个元素之间是没有分别的。沿着这个思路考虑，第二次输入时，6个没有参与输入的元素，也没有分别。举例来说，第一次输入{0，1，2，3}，则4，5，6，7，8，9六个元素属同一类元素，在第二次输入时可以相互替换。如{0，1，2，4}和{0，1，2，5}两组输入能够得到的信息量应该相同。把元素分类枚举则可以优化算法。
分类方法如下，参入输出的元素单独成一类，没有参与的元素是一类。第一次输入时，只有一类元素，这类元素个数为10。第二次输入时，有五类元素，有四类元素个数为1，一类元素个数为6。依次类推。关于如何枚举见
《从集合中枚举子集》。
// 得到最佳的输入,元素分类的方法
// 最佳输入存放在g_AnsGuess中
void GetBestInputSort()
{
double max_entropy = 0.; // 存放最大的信息量
VectorInt feedbacks((ANS_SIZE+1)*(ANS_SIZE+1), 0);// 反馈的结果分类
// 初始化枚举
CSetIterAgent<int> iter(g_AnsEle);
iter.Init(ANS_SIZE, CSetIter::MULT_ORDERED_IN);
// 比较所有输入的信息量
VectorInt setsub(ANS_SIZE, 0);
while (iter.GetNextSubset(setsub, g_AnsEle))
{
// 把-1元素具体化，-1表示该元素没有输入过
AssembleInput(setsub);
// // 这个输入的信息量是否是0
// if (g_InputState[GetSetPosition(setsub)] == 1)
// continue;
// 是否只在可能的答案中搜索最佳输入
// if (g_AnsState[GetSetPosition(setsub)] != 0)
// continue;
// 得到所有可能反馈的数目
feedbacks.assign((ANS_SIZE+1)*(ANS_SIZE+1), 0);
GetPsbFeedbacksNum(feedbacks, setsub);
// 计算信息量
double entropy = CalcEntropy(feedbacks);
// // 排除信息量为0的输入
// if (entropy < 0.00001)
// {
// g_InputState[GetSetPosition(setsub)] = 1;
// continue;
// }
// 求最大的信息量
if (max_entropy < entropy)
{
max_entropy = entropy;
g_AnsGuess = setsub;
}
}
// 元素分类
SortEle();
}
分类的方法可以大大提升运算速度，下面的测试会证明这一点。但当参与输入元素慢慢增加时，分类就不那么重要，而且调用CSetIterAgent也是一笔不小的开销。将第一种算法和分类法结合：
// 不分类法和分类法的混合法
// 输入参数：num表示当输入元素个数等于或超过num时用直接法
void GetBestInputBlend(int num)
{
// 计算没有输入过的元素个数
int sum = 0;
for (int i=0; i<g_AnsEle.size(); i++)
{
if (g_AnsEle[i] == -1)
sum++;
}
sum = g_AnsEle.size() - sum;
if (sum >= num)
GetBestInputNoSort();
else
GetBestInputSort();
}
下面给出这些算法的测试结果。测试方法是将10*9*8*7种答案依次用这些算法求解，统计猜出每个答案需要多少次数。一共花费了多少时间。
1次 1
2次 12
3次 261
4次 2082
5次 2500
6次 184
平均次数：4.51190
N次是指N次输入反馈后，就可以确定答案，并不指第N次输入的反馈是4A0B。
花费的时间：
GetBestInputNoSort： 8h也没有算完
GetBestInputIpvFst： 9385s
GetBestInputSort： 1596s
GetBestInputBlend7： 2151s
GetBestInputBlend10： 1515s
这些方法在本质上是一样的，即在所有的输入中寻找反馈信息量最大的输入。下面考虑其他方法，比较这些方法的差别。
如果缩小寻找范围，不考虑不是答案的输入。代码如下：
取消GetBestInputNoSort函数中
// 是否只在可能的答案中搜索最佳输入
if (g_AnsState[i] != 0)
continue;
和GetBestInputSort函数中
// 是否只在可能的答案中搜索最佳输入
if (g_AnsState[GetSetPosition(setsub)] != 0)
continue;
这两行注释。
测试结果如下：
1次 1
2次 16
3次 228
4次 1555
5次 2688
6次 542
7次 10
平均次数：4.70218
运行时间：
GetBestInputIpvFst：1375s
GetBestInputSort： 97s
缩小范围后，速度有很多提升，但平均次数增加了。
再考虑另外一种方法，不从信息量的角度考虑。用第一个可能为答案的排列作为输入。
// 得到第一个可能的答案
void GetFstPsbInput()
{
for (int i=0; i<ALL_ANS_NUM; i++)
{
if (g_AnsState[i] == 0)
{
g_AnsGuess = g_AllAns[i];
break;
}
}
}
测试结果：
1次 1
2次 15
3次 211
4次 1240
5次 2108
6次 1203
7次 252
8次 10
平均次数：5.00515
花费的时间：7s
这个方法令人吃惊的是它的速度，如此简单却又不错的效果。平均次数要比上面两个方法差些。
上面的测试结果是在vc2005的release下编译测试。
本文用信息量大小作为判断最佳输入的标准，相比其他算法平均步数较少，但花费的时间较多。如何缩短计算时间将在以后的文章中继续探讨。此外从测试中看出，方法2，3在两次内猜中答案的次数比方法1多。在这个意义下方法2，3比方法1要优。以后还会在不同的意义下比较各类算法。大家有什么好的想法可以联系我，大家一起讨论。我的邮箱
lemene@sina.com.cn 代码下载