Come funziona il servizio web dietro l'Akinator?

Non ho costruito Akinator, e non ho idea se quanto segue sia vero, ma ecco un abbozzo di come costruirei qualcosa di simile ad Akinator.

In parole povere, potete pensare ad Akinator, o a qualsiasi altro gioco di 20 domande, come a una forma ad alta dimensione di ricerca binaria. (Nel caso ideale, sareste sempre in grado di escludere la metà delle risposte rimanenti ad ogni domanda, e sareste in grado di restringere il campo ad una tra circa 2^20 = 1.048.576 possibilità in 20 domande. L'algoritmo specifico che Akinator usa per decidere tra le domande potrebbe probabilmente essere una delle tante cose, ma in ogni caso l'obiettivo è sicuramente quello di dividere il set di possibilità il più vicino possibile alla metà con ogni domanda.

Le domande che Akinator pone sono memorizzate in un database, come si può vedere quando si clicca "Aggiungi una domanda" dopo aver finito una partita. Si può effettivamente cercare nella lista di tutte le domande che l'Akinator pone. Di conseguenza, per tutti i personaggi che Akinator conosce, deve tenere traccia di ciò che pensa sia la risposta corretta a tutte le domande nel suo database. Se ci sono N personaggi e M domande, stiamo memorizzando N*M risposte qui.

Dopo che gli utenti finiscono il gioco, le loro risposte sono usate per migliorare il database. Poiché l'utente non sta dando risposte sì/no, l'Akinator probabilmente non sta memorizzando risposte booleane. Invece, dato che gli utenti possono rispondere sì/probabilmente/non lo so/probabilmente no/no, probabilmente memorizza un valore float nell'intervallo [0,1] (una forma di logica fuzzy). Quindi, se sì = 1, probabilmente = 0,75, non so = 0,50, probabilmente no = 0,25, e no = 0, stiamo fondamentalmente memorizzando il valore atteso di una risposta dell'utente.

Questo fornisce diversi vantaggi. In primo luogo, fa in modo che non tutte le risposte debbano essere applicate ad ogni personaggio, così che le domande che non si applicano realmente ad un personaggio possono avere un valore per quel personaggio vicino a 0,50 nel database. In secondo luogo, le persone potrebbero non essere d'accordo su alcune risposte, quindi alcune domande potrebbero essere più o meno affidabili per escludere certi personaggi. In terzo luogo, dà all'Akinator più robustezza contro le risposte errate. Quando ricorda quanto spesso le persone giocano con ogni personaggio e combina questa conoscenza con queste risposte confuse, può avere un'idea di quando è più probabile che qualcuno stia giocando un personaggio popolare e abbia dato una risposta sbagliata o quando è più probabile che qualcuno stia cercando di giocare un personaggio davvero oscuro (o un personaggio che non ha mai visto prima).

Siccome l'Akinator non fa le stesse domande ogni volta, presumo ci sia qualche elemento di casualità nella scelta delle domande. Oltre ad aumentare il valore di rigiocabilità del gioco, questo aiuta l'Akinator a migliorare il suo database più velocemente raccogliendo risposte a una più ampia varietà di domande, anche se potrebbe non fare sempre la domanda migliore in assoluto in ogni situazione. (A meno che il programma non scelga e segua uno dei molteplici alberi decisionali pregenerati ogni volta che si gioca, questo rafforzerebbe la mia convinzione che Akinator sceglie le domande (ovvero costruisce il suo albero decisionale) mentre il giocatore gioca.

(Nota: anche http://pages.cs.wisc.edu/~dyer/cs540/demos.html sembra pensare che Akinator sia un albero decisionale. Il sito in qualche modo simile 20q.net sostiene invece di usare una rete neurale.)

Più su giochi in stile 20 domande:
http://openbookproject.net/py4fun/animal/animal.html
http://stackoverflow.com/questions/887533/how-do-20-questions-ai-algorithms-work

Più sulla logica fuzzy e il suo uso negli alberi decisionali:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4051&rep=rep1&type=pdf