由 20 个问题组成的简单在线游戏，由极其准确的 AI 提供支持。
他们怎么猜得这么好？
问问题
72879 次
5 回答
58
您可以将其视为二分搜索算法。在每次迭代中，我们都会提出一个问题，该问题应该消除大约一半的可能单词选择。如果总共有 N 个单词，那么我们可以期望在 log2(N) 个问题之后得到答案。
有 20 个问题，我们应该能够在 2^20 = 100 万个单词中找到一个单词。
消除异常值（错误答案）的一种简单方法可能是使用类似RANSAC的东西。这意味着，您无需考虑所有已回答的问题，而是随机选择一个较小的子集，这足以给您一个答案。现在你用不同的随机问题子集重复几次，直到你看到大多数时候，你得到了相同的结果。然后你就知道你有正确的答案。
当然，这只是解决这个问题的许多方法中的一种。
于 2009-05-20T13:21:20.043 回答
27
我建议在这里阅读有关游戏的信息：http ://en.wikipedia.org/wiki/Twenty_Questions
特别是计算机部分：
该游戏表明，识别任意对象所需的信息（由香农熵统计量测量）约为 20 位。在向人们教授信息论时，该游戏经常被用作示例。在数学上，如果每个问题的结构都消除了一半的对象，那么 20 个问题将允许提问者区分 2 20或 1,048,576 个主题。因此，对于二十个问题，最有效的策略是提出的问题每次都会将剩余可能性的范围大致分成两半。该过程类似于计算机科学中的二进制搜索算法。
于 2009-05-20T12:13:20.290 回答
26
决策树直接支持这种应用。决策树通常用于人工智能。
决策树是一棵二叉树，它在每个分支处询问“最佳”问题，以区分由其左右子节点表示的集合。最佳问题由 20 个问题应用程序的创建者用来构建树的一些学习算法确定。然后，正如其他海报所指出的，一棵 20 层深的树会给你一百万件事。
在每个点定义“最佳”问题的一种简单方法是寻找一个最均匀地将集合分成两半的属性。这样，当您对该问题的回答是“是/否”时，您在每个步骤中都会删除大约一半的集合。这样你就可以近似二分搜索。
维基百科给出了一个更完整的例子：
http://en.wikipedia.org/wiki/Decision_tree_learning
和一些一般背景：
于 2009-05-20T13:37:17.127 回答
16
它自称是“互联网上的神经网络”，关键就在这里。它可能将问题/答案概率存储在备用矩阵中。使用这些概率，它能够使用决策树算法来推断要问的问题最能缩小下一个问题的范围。一旦它将可能的答案数量缩小到几十个，或者如果它已经达到 20 个问题，那么它最有可能开始阅读。
20q.net 真正有趣的方面是，与我所知道的大多数决策树和神经网络算法不同，20q 支持稀疏矩阵和增量更新。
编辑：原来答案一直在网上。发明者 Robin Burgener 在2005 年的专利申请中详细描述了他的算法。
于 2010-01-18T21:04:55.040 回答
6
于 2009-05-20T12:09:59.610 回答