O título fala por si só. Aqui estão Akinator e 20Q .
O princípio desses jogos é fazer ao usuário uma série de perguntas relacionadas a alguma entidade escolhida pelo usuário. E então descubra o que é essa entidade. O núcleo do algoritmo é encontrar a "pergunta mais útil" a cada rodada, enquanto lida com um usuário que pode não responder a todas as perguntas corretamente.
"pergunta mais útil" sendo definida como a pergunta que fornece mais informações, no caso ideal de dividir o público (ou número?) das entidades candidatas em duas partes iguais.
Encontrei um artigo que descrevia alguns algoritmos (bem, a palavra "algoritmo" não foi usada, mas as provas poderiam ser transformadas em algoritmos). Infelizmente, não consigo encontrar este artigo novamente :(. O artigo descreveu o problema com os conceitos da teoria dos jogos, com alguns níveis de mentira permitidos ao usuário (discutiu três níveis de mentira). Por favor, poste se achar que conhece o artigo.
fonte
Respostas:
Acho que você provavelmente está procurando "Jogando" Vinte perguntas "com um mentiroso", Dhagat, Gacs e Winkler, SODA 1992, http://portal.acm.org/citation.cfm?id=139404.139409
Os muitos outros artigos que citam este provavelmente incluem hits relevantes adicionais.
fonte