Como funciona o serviço web por trás do Akinator?

Eu fiz'não construí o Akinator, e não tenho idéia se alguma das seguintes é verdade, mas aqui'é um esboço rudimentar, de alto nível, de como eu construiria algo como o Akinator.

Em termos gerais, você pode pensar no Akinator, ou qualquer outro jogo de 20 perguntas, como uma forma de busca binária de alta dimensão. (Ou como construir uma árvore de decisão.) No caso ideal, você'seria sempre capaz de descartar metade das respostas restantes com cada pergunta, e você'seria capaz de reduzir a uma de cerca de 2^20 = 1.048.576 possibilidades em 20 perguntas. O algoritmo específico que o Akinator usa para decidir entre questões pode provavelmente ser uma de várias coisas, mas em qualquer caso o objetivo é definitivamente dividir o conjunto de possibilidades o mais próximo possível da metade com cada questão.

As questões que o Akinator faz são armazenadas em uma base de dados, como você pode ver quando você clica em "Adicionar uma questão" depois de terminar um jogo. Você pode realmente procurar na lista de todas as perguntas que o Akinator faz. Assim, para todos os personagens que o Akinator conhece, ele deve manter um registro do que pensa ser a resposta correta para todas as perguntas em seu banco de dados. Se houver N caracteres e M perguntas, nós'estamos armazenando respostas de N*M aqui.

Após o usuário terminar o jogo, suas respostas são usadas para melhorar o banco de dados. Como o usuário está't dando respostas sim/não, o Akinator provavelmente está't armazenando respostas booleanas. Ao invés disso, como os usuários podem responder sim/probavelmente/don't know/probably not/no answers, ele provavelmente armazena alguma flutuação no intervalo [0,1] (uma forma de lógica fuzzy). Então se sim = 1, provavelmente = 0,75, don't sabe = 0,50, provavelmente não = 0,25, e não = 0, we're basicamente armazena o valor esperado de um usuário's answer.

Isto fornece várias vantagens. Primeiro, ele faz com que nem toda resposta tenha que se aplicar a todos os caracteres para que questões que don't realmente se aplicam a um caractere possam ter um valor para aquele caractere próximo a 0.50 na base de dados. Segundo, as pessoas podem discordar em algumas das respostas, então algumas perguntas podem ser mais ou menos confiáveis ao descartar certos caracteres. Terceiro, ele dá ao Akinator mais robustez contra respostas incorretas. Quando ele se lembra de quantas vezes as pessoas jogam cada personagem e combina esse conhecimento com essas respostas confusas, ele pode ter alguma idéia de quando ele'é mais provável que alguém estava jogando um personagem popular e deu uma resposta incorreta ou quando ele'é mais provável que alguém esteja tentando jogar um personagem realmente obscuro (ou um personagem que ele's nunca viu antes).

Desde que o Akinator faz't fazer as mesmas perguntas toda vez, eu assumo que há algum elemento de aleatoriedade na escolha das perguntas. Além de aumentar o valor de replay do jogo, isso ajuda o Akinator a melhorar sua base de dados mais rapidamente, reunindo respostas para uma variedade maior de perguntas, embora nem sempre ele possa estar fazendo a melhor pergunta em qualquer situação. (Uma troca exploração vs. exploração.) A menos que o programa escolha e siga uma das múltiplas árvores de decisão pré-geradas cada vez que você joga, isto reforçaria minha crença de que o Akinator escolhe perguntas (também conhecido como a construção de sua árvore de decisão) enquanto o jogador joga.

(Nota: http://pages.cs.wisc.edu/~dyer/cs540/demos.html também parece pensar que o Akinator é uma árvore de decisão. O site 20q.net um pouco semelhante afirma usar uma rede neural em seu lugar.)

Mais sobre 20 questões estilo jogos:
http://openbookproject.net/py4fun/animal/animal.html
http://stackoverflow.com/questions/887533/how-do-20-questions-ai-algorithms-work

Mais sobre lógica difusa e seu uso em árvores de decisão:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4051&rep=rep1&type=pdf