algorithm - 设计二十个问题的算法

Question

我有兴趣写一个 twenty questions算法类似于akinator并且，在较小程度上，20q.net使用。后者似乎更关注对象，明确告诉你不要去想人或地方。可以说 akinator 更通用，让您可以从字面上想到任何东西，包括诸如“我的兄弟”之类的抽象概念。

这个问题是我不知道这些网站使用什么算法，但从我读到的内容来看，他们似乎使用了一种概率方法，在这种方法中，问题被赋予了一定的适应性，基于它们导致的次数正确的猜测。这SO question介绍了几种技术，但相当含糊，我对更多细节感兴趣。

那么，什么是玩二十道题的准确有效的算法呢？

我对以下方面的详细信息感兴趣:

1. 接下来要问什么问题。
2. 如何在 20 个问题的最后做出最佳猜测。
3. 如何将新对象和新问题插入数据库。
4. 如何有效地查询 (1, 2) 和更新 (3) 数据库。

我意识到这可能并不容易，我并不是要代码或 2000 字的演示文稿。关于每个操作和底层数据结构的几句话就足以让我入门。

Answer 1

更新，10 多年后

我现在在这里托管一个(WIP，但功能正常)实现:https://twentyq.evobyte.org/使用此处的代码:https://github.com/evobyte-apps/open-20-questions .它基于下面列出的相同粗略想法。

---

好吧，三年多后，我做到了(虽然我没有全职工作)。我在 http://twentyquestions.azurewebsites.net/ 主持了一个粗略的实现如果有人感兴趣(请不要教它太多错误的东西!)。

它并没有那么难，但我会说它是一种你不会立即想到的非直观的不难。我的方法包括一些简单的基于适应度的排名，想法来自 reinforcement learning和一个 round-robin安排要问的新问题的方法。所有这些都在规范化的关系数据库上实现。

我的基本想法如下。如果有人感兴趣，我也会分享代码，请与我联系。我计划最终将其开源，但一旦我做了更多的测试和返工。所以，我的想法:

• Entities 表，其中包含所玩的角色和对象；
• 包含问题的问题表，这些问题也是由用户提交的；
• EntityQuestions 表保存实体-问题关系。这保存了与每个实体相关的每个问题的每个答案的次数(好吧，那些问题无论如何都会被问到)。它还有一个 Fitness 字段，用于对从“更一般”到“更具体”的问题进行排序；
• GameEntities 表用于根据目前为每个正在进行的游戏给出的答案对实体进行排名。 A 对问题 Q 的回答会推高所有对问题 Q 的多数回答是 A 的实体>;
• 第一个问题是从 EntityQuestions 表中适应度总和最高的问题中挑选出来的；
• 每个下一个问题都是从那些与 GameEntities 表中当前排名靠前的条目相关联的适应性最高的问题中挑选出来的。预期答案为"is"的问题甚至在健身之前就受到青睐，因为这些问题更有可能巩固当前排名最高的实体；
• 如果系统在问完所有 20 个问题之前就非常确定答案，它会开始问与其答案无关的问题，以便了解有关该实体的更多信息。这是目前在全局问题池中以循环方式完成的。 讨论:循环法好还是应该完全随机？
• 在某些条件和概率下也会给出过早的答案；
• 根据 GameEntities 中的排名给出猜测。这使得系统也可以解释谎言，因为它永远不会消除任何可能性，只会降低它成为答案的可能性；
• 每场比赛结束后，适应度和答案统计数据都会相应更新:如果比赛输了，实体-问题关联的适应度值会降低，否则会增加。

如果有人感兴趣，我可以提供更多细节。我也愿意合作改进算法和实现。