我正在尝试编写一个类似于 “二十问”的算法，类似于 akinator，以及在较小程度上类似于 20q.net 的算法。后者似乎更专注于物体，明确告诉你不要想人或地方。可以说 akinator 更通用，允许你思考任何事物，包括像“我的兄弟”这样的抽象概念。
问题在于我不知道这些网站使用什么算法，但从我读到的内容来看，它们似乎使用了一种概率方法，其中问题会根据它们导致正确猜测的次数来赋予一定的“适应度”。这个 SO 问题提出了一些技术，但相当模糊，我对更多细节感兴趣。
那么，什么才是玩“二十问”游戏准确而高效的算法呢？
我对以下方面的细节感兴趣：
- 接下来该问什么问题。
- 如何在 20 个问题结束时做出最佳猜测。
- 如何将新对象和新问题插入数据库。
- 如何高效地查询 (1, 2) 和更新 (3) 数据库。
我知道这可能不容易，我不是要求提供代码或 2000 字的演示。只需几句话介绍每个操作和底层数据结构就足以让我入门了。
回答：
更新，10 多年后
我现在托管了一个（WIP，但功能齐全的）实现：https://twentyq.evobyte.org/，代码在这里：https://github.com/evobyte-apps/open-20-questions。它基于下面列出的相同粗略想法。
好吧，三年多以后，我做到了（虽然我没有全职工作）。如果有人感兴趣，我将一个粗略的实现托管在 http://twentyquestions.azurewebsites.net/ 上（请不要教它太多错误的东西！）。
这并不难，但我想说这是那种非直觉的不难，你不会立刻想到。我的方法包括一些基于适应度的简单排序，来自 强化学习 的思想和一种 循环赛 的方法来安排要问的新问题。所有这些都是在规范化的关系数据库上实现的。
我的基本想法如下。如果有人感兴趣，我也会分享代码，请与我联系。我计划最终将其开源，但在我进行更多测试和修改之后。所以，我的想法：
- 一个 Entities 表，用于保存角色和对象；
- 一个 Questions 表，用于保存问题，这些问题也是由用户提交的；
- 一个 EntityQuestions 表，用于保存实体-问题关系。它保存了每个问题相对于每个实体的答案被给出的次数（好吧，至少是那些被问到过的问题）。它还有一个 Fitness 字段，用于将问题从“更通用”到“更具体”进行排序；
- 一个 GameEntities 表，用于根据每个正在进行的游戏的答案对实体进行排序。对问题
Q的回答A会推高所有对问题Q的多数答案为A的实体； - 第一个被问到的问题是从 EntityQuestions 表中适应度总和最高的问题中选择的；
- 每个接下来的问题都是从与
GameEntities表中当前排名靠前的条目关联的适应度最高的问题中选择的。对于预期答案为“是”的问题，甚至在适应度之前都会受到青睐，因为这些问题更有可能巩固当前排名最高的实体； - 如果在所有 20 个问题都被问到之前，系统对答案非常确定，它将开始询问与答案无关的问题，以便更多地了解该实体。这是现在以循环方式从全局问题池中完成的。 讨论： 循环赛好吗，还是应该完全随机？
- 在某些条件和概率下，也会给出过早的答案；
- 根据 GameEntities 中的排名给出猜测。这允许系统解释谎言，因为它从不消除任何可能性，只是降低了其成为答案的可能性；
- 每次游戏结束后，适应度和答案统计数据会相应更新：如果游戏失败，实体-问题关联的适应度值会降低，否则会增加。
如果有人感兴趣，我可以提供更多细节。我也乐于合作改进算法和实现。
