1

I'm thinking about writing a program that asks the user to think of an object(a physical one) and then it asks questions about the object and tries to figure out what the user was thinking. (Similar to http://20q.net)

I tried to do it in Python but figured my approach was naive and would be very inefficient. How would you guys do this?

2 Answers2

2

Doing this efficiently requires a somewhat advanced method in probability called Kullback-Liebler Divergence. Applied to decision trees (which is what you want to do) it is often called Information Gain.

But don't let that stop you! Do some searches for implementation samples of decision trees and start from there. I'd write a much simpler program before you go about solving 20 Questions.

Also, take a look at http://www.20q.net/ . Click "Think in English" then "Classic 20Q". It's scary good, sometimes.

Justin Morgan
  • 2,427
  • 2
  • 16
  • 19
1

Sounds like you want to make a computerized 21 questions game. I'd do it with a tree of questions and answers.

Here is a nice stackoverflow article about implementing trees in python How can I implement a tree in Python? Are there any built in data structures in Python like in Java?

Community
  • 1
  • 1
Nick
  • 3,096
  • 3
  • 20
  • 25
  • Of course, this does necessitate `2^21 - 1` questions and `2^21` answers saved in memory, and more importantly written somewhere. – Christian Mann Feb 09 '11 at 03:10
  • Chrisian, yes, I know that it isn't limited to 21 questions, I was just referring to a popular game that illustrated this point. – Nick Feb 09 '11 at 03:21
  • Implementing a tree data structure isn't the challenge. That's trivial. The challenge is implementing the algorithm to *learn* and automatically *construct* the optimal tree structure. – Cerin Feb 10 '11 at 01:31