Animals and the Tree of Knowledge

What it Does

This little program builds a classification tree by interacting with the user. It starts off knowing only that a Bird is an animal and bit by bit learns more as it interacts with you.

Here is an example run. You may type 'n' for no and 'y' is yes.

$ python animal.py                  # or python3
Are you thinking of an animal? yes
Is it a bird? no
What is the animals name? dog
What question would distinguish a dog from a bird? does it fly
If the animal were dog the answer would be? no

Are you thinking of an animal? yes
does it fly? yes
Is it a bird? no
What is the animals name? bat
What question would distinguish a bat from a bird? does it have feathers
If the animal were bat the answer would be? no

Are you thinking of an animal? no

The Data Structure

This is a diagram of the knowledge tree built from the above dialog.

The Program

The program is quite simple. It starts with the top question and depending on the users yes or no response, continues either to the left or right down a tree that grows as the game is played. At the last element (the "leaf" node), it makes its guess. If the guess is wrong then it has the user input the name of a new animal and a question to distinguish the new animal from the guess. Then the tree is grown by one more node to accomodate the question and the new animal.

Click here for program code . This is a numbered listing to accompany the explanation.

 1 #
 2 #  A n i m a l . p y
 3 #
 4 import sys
 5
 6 if sys.version > '3' : raw_input = input  # Python 3
 7
 8 class Node :
 9     "Node objects have a question, and  left and right pointer to other Nodes"
10     def __init__ (self, question, left=None, right=None) :
11         self.question = question
12         self.left     = left
13         self.right    = right
14
15 def yes (ques) :
16     "The user answers 'yes' or something similar. Otherwise it's a no"
17     while True :
18         ans = raw_input (ques)
19         ans = ans[0:1].lower()
20         if ans == 'y' : return True
21         else          : return False
22
23 knowledge = Node("bird")
24
25 def main () :
26     "Guess the animal. Add a new Node for a wrong guess."
27
28     while True :
29         print("")      # line break, either Python 2 or 3
30         if not yes("Are you thinking of an animal? ") : break
31         p = knowledge
32         while p.left != None :
33             if yes(p.question+"? ") : p = p.right
34             else                    : p = p.left
35
36         if yes("Is it a " + p.question + "? ") : continue
37         animal   = raw_input ("What is the animals name? ")
38         question = raw_input ("What question would distinguish a %s from a %s? "
39                                   % (animal,p.question))
40         p.left     = Node(p.question)
41         p.right    = Node(animal)
42         p.question = question
43
44         if not yes ("If the animal were %s the answer would be? " % animal) :
45             (p.right, p.left) = (p.left, p.right)
46
47 if __name__ == "__main__" : main ()
48

An object class Node (line 8) is used to construct nodes in the tree. Each node contains a question plus pointers to the next node depending on a yes or no from the user.

Leaf nodes simply contain the name of an animal in the question field and the value None in the two pointer fields.

The function "yes" is a convenience. It will recognize "Yes", "YES", "Y", "y", etc. all correctly. Anything else is taken as a "No".

The tree knowledge starts out (line 23) with just a leaf node.

In main (line 25) the while loop repeatably proceeds down the tree to the left or right (line 32) until it reacheѕ a leaf node (line 36). If the guess is wrong then a new node, with a new question and a new animal is built from user input and linked into the tree. The pointers are set one way (lines 40,41) and then possibly swapped in line 44. That's it.

I first saw this program in very old fashioned Basic from the early 1970s. The code was more complex than this requiring separate arrays of strings and pointers.

Later, I was starting a new job in Holland and I took it along. It was something of a hit. After several people played with it for an hour or so, it had developed a nice catagorization, half in English and half in Dutch, of everyone who worked in the office!

Ideas for further Development

Enable the program to save its knowledge tree between runs. You might use the pickle mechanism. Or write a function that saves all the user responses so that they can be played back as a script.

Make a command to display the knowledge tree on the screen using indenting. You might want to consider using recursion for this. Alternatively map the tree with a graphics package like TKinter.

If you have comments or suggestions You can email me at mail me

* * *