artificial intelligence - Designing a twenty questions algorithm -

i interested in writing twenty questions algorithm similar akinator and, lesser extent, 20q.net uses. latter seems focus more on objects, explicitly telling not think of persons or places. 1 akinator more general, allowing think of literally anything, including abstractions such "my brother".

the problem don't know algorithm these sites use, read seem using probabilistic approach in questions given fitness based on how many times have lead correct guesses. so question presents several techniques, rather vaguely, , interested in more details.

so, accurate , efficient algorithm playing twenty questions?

i interested in details regarding:

1. what question ask next.
2. how make best guess @ end of 20 questions.
3. how insert new object , new question database.
4. how query (1, 2) , update (3) database efficiently.

i realize may not easy , i'm not asking code or 2000 words presentation. few sentences each operation , underlying data structures should enough me started.

well, on 3 years later, did (although didn't work full time on it). hosted crude implementation @ http://twentyquestions.azurewebsites.net/ if interested (please don't teach wrong stuff yet!).

it wasn't hard, it's non-intuitive kind of not hard don't think of. methods include trivial fitness-based ranking, ideas reinforcement learning , round-robin method of scheduling new questions asked. of implemented on normalized relational database.

my basic ideas follow. if interested, share code well, contact me. plan on making open source eventually, once have done bit more testing , reworking. so, ideas:

• an entities table holds characters , objects played;
• a questions table holds questions, submitted users;
• an entityquestions table holds entity-question relations. holds number of times each answer given each question in relation each entity (well, question asked anyway). has fitness field, used ranking questions "more general" down "more specific";
• a gameentities table used ranking entities according answers given far each on-going game. answer of a question q pushes entities majority answer question q a;
• the first question asked picked highest sum of fitnesses across entityquestions table;
• each next question picked highest fitness associated top entries in gameentities table. questions expected answer yes favored before fitness, because these have more chances of consolidating current top ranked entity;
• if system quite sure of answer before 20 questions have been asked, start asking questions not associated answer, learn more entity. done in round-robin fashion global questions pool right now. discussion: round-robin fine, or should random?
• premature answers given under conditions , probabilities;
• guesses given based on rankings in gameentities. allows system account lies well, because never eliminates possibility, decreases likeliness of being answer;
• after each game, fitness , answers statistics updated accordingly: fitness values entity-question associations decrease if game lost, , increase otherwise.

i can provide more details if interested. open collaborating on improving algorithms , implementation.