设计二十个问题算法

Question

我有兴趣编写类似于akinator的20个问题算法,并且在较小程度上,20q.net使用.后者似乎更关注对象,明确告诉你不要想到人或地方.可以说,akinator更通用,允许你从字面上思考任何东西,包括诸如"我的兄弟"之类的抽象.

这个问题是我不知道这些网站使用了什么算法,但从我读到的内容来看,他们似乎正在使用一种概率方法,在这种方法中,问题根据他们导致正确猜测的次数而具有一定的适应性.这个SO问题提出了几种技术,但含糊不清,我会对更多细节感兴趣.

那么,什么是一个准确有效的算法来播放二十个问题呢？

我对以下方面的细节感兴趣:

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

我意识到这可能并不容易,我不是要求代码或2000字的演示文稿.关于每个操作和底层数据结构的几句话应该足以让我开始.

Answer 1

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

这并不难,但我会说,你不会立刻想到这是不直观的那种不难.我的方法包括一些基于健康的琐碎排名,强化学习的想法以及安排要问的新问题的循环方法.所有这些都是在规范化的关系数据库上实现的.

我的基本想法如下.如果有人有兴趣,我也会分享代码,请联系我.我打算最终把它变成开源,但是一旦我做了更多的测试和改造.所以,我的想法:

• 一个实体表,用于保存播放的角色和对象;
• 包含问题的问题表,也由用户提交;
• 一个EntityQuestions表保存实体问题的关系.这保留了每个问题与每个实体相关的每个答案的次数(嗯,无论如何要求提出问题的答案).它还有一个Fitness字段,用于将问题从"更一般"下调到"更具体";
• 一个GameEntities表用于根据迄今对每个正在进行的游戏给出的答案排名的实体.的回答A一个问题Q推了所有的实体当中,多数回答的问题Q是A;
• 提出的第一个问题是从EntityQuestions表中具有最高拟合度的那些问题中挑选出来的;
• 从与表中当前顶部条目相关联的具有最高适应度的那些中挑选每个下一个问题GameEntities.预期答案为"是"的问题甚至在适应性之前受到青睐,因为这些问题有更多机会巩固当前排名靠前的实体;
• 如果系统在提出所有20个问题之前都非常确定答案,那么它将开始提出与其答案无关的问题,以便了解有关该实体的更多信息.现在,这是通过全球问题池以循环方式完成的.讨论:循环法是否很好,还是应该完全随机？
• 在某些条件和概率下也给出了过早的答案;
• 猜测是根据GameEntities中的排名给出的.这也允许系统解释谎言,因为它永远不会消除任何可能性,只是降低了作为答案的可能性;
• 在每次游戏之后,健身和答案统计数据相应地更新:如果游戏丢失则实体 - 问题关联的适合度值减小,否则增加.

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