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 would type everything that follows a '?'. 'n' is no and 'y' is yes.

$ python
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 the tree. 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.

01 #
02 #  A n i m a l . p y
03 #
04 import string
06 class Node :
07     "Node objects have a question, and  left and right pointer to other Nodes"
08     def __init__ (self, question, left=None, right=None) :
09         self.question = question
10         self.left     = left
11         self.right    = right
13 def yes (ques) :
14     "The user answers 'yes' or something similar. Otherwise it's a no"
15     while 1 :
16         ans = raw_input (ques)
17         ans = string.lower(ans[0:1])
18         if ans == 'y' : return True
19         else          : return False
21 knowledge = Node("bird")
23 def main () :
24     "Guess the animal. Add a new Node for a wrong guess."
26     while 1 :
27         print
28         if not yes("Are you thinking of an animal? ") : break
29         p = knowledge
30         while p.left != None :
31             if yes(p.question+"? ") : p = p.right
32             else                    : p = p.left
34         if yes("Is it a " + p.question + "? ") : continue
35         animal   = raw_input ("What is the animals name? ")
36         question = raw_input ("What question would distinguish a %s from a %s? "
37                                   % (animal,p.question))
38         p.left     = Node(p.question)
39         p.right    = Node(animal)
40         p.question = question
42         if not yes ("If the animal were %s the answer would be? " % animal) :
43             (p.right, p.left) = (p.left, p.right)
45 if __name__ == "__main__" : main ()

An object class Node (line 6) 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 21) with just a leaf node.

In main (line 23) the while loop repeatably proceeds down the tree to the left or right (line 30) until it reacheѕ a leaf node (line 34). 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 38,39) and then possibly swapped in line 42. 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 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

Copyright © 2002-2018 Chris Meyers