# How does the Pangolins program work?

The example game.

## Round 1

At the start of the game, we assumed that all the computer knows is a single object:
```a pangolin
```
and no questions, so all it can do to begin with is ask
```Is it a pangolin?
```
If the player answers "yes", then that is the end of the round.

## Round 2

If the player answers "no", then the computer asks questions to improve its knowledge base:
```Oh. Well you win then -- What were you thinking of?
> Pete
Please give me a question about Pete, so I can tell the difference between Pete and a pangolin
> Does it have a tail?
What is the answer for Pete?
> No
```
At the end of the 2nd round of the game, the objects the computer now knows about are:
```a pangolin
Pete
```
and the question it now knows is:
```Does it have a tail?
```
and it can put these together into a single data structure, a binary (or 2-way) decision tree:
```                       Start here
|
v
Does it have a tail?
/yes               no\
v                      v
a pangolin                 Pete
```
so in the next round, the first thing it will do is ask "Does it have a tail?". If the answer is "yes" it will guess "a pangolin" and if the answer is "no" it will guess "Pete"

## Round 3

At the end of the 3nd round of the game, the objects the computer now knows about are:
```a pangolin
Pete
a pizza
```
and the questions it has accumulated are:
```Does it have a tail?
Is it flat, round and edible?
```
It has had to make a fairly simple change to its decision tree - its guess "Is it Pete?" turned out to be wrong, so it had to replace the part of the decision tree that means "the answer is Pete" by the new question and attach (what it thinks are) the two possible outcomes "Pete" and "a pizza" to the new question:
```                       Start here
|
v
Does it have a tail?
/yes               no\
v                      v
a pangolin         Is it flat, round and edible?
/yes               no\
v                      v
a pizza                    Pete
```

## Round 4

At the end of the 4th round of the game, the objects the computer now knows about are:
```a pangolin
Pete
a pizza
a biscuit
```
and the questions it has accumulated are:
```Does it have a tail?
Is it flat, round and edible?
Can you dip it in your tea?
```
It has had to make another fairly simple change to its decision tree - its guess "Is it a pizza?" turned out to be wrong, so it had to replace the part of the decision tree that means "the answer is a pizza" by the new question and attach the outcomes "a biscuit" and "a pizza" to the new question:
```                       Start here
|
v
Does it have a tail?
/yes               no\
v                      v
a pangolin         Is it flat, round and edible?
/yes               no\
v                      v
Can you dip it in your tea?            Pete
/yes               no\
v                      v
a biscuit                    a pizza
```

## Round 5

At the end of the 5th round of the game, the objects the computer knows about are:
```a pangolin
Pete
a pizza
a biscuit
A Cat
```
the questions it has accumulated are:
```Does it have a tail?
Is it flat, round and edible?
Can you dip it in your tea?
Does it like to chase mice?
```
and its decision tree looks like this:
```                       Start here
|
v
Does it have a tail?
/yes               no\
v                      v
Does it like to chase mice?          Is it flat, round and edible?
|yes                    no|         /yes                        no\
v                         v        v                               v
A Cat                 a pangolin   Can you dip it in your tea?     Pete
|yes                   no|
v                        v
a biscuit                 a pizza
```
If you now played one more round, while thinking of a pizza (again), the questions and answers would look like this:
```Does it have a tail?
> no
Is it flat, round and edible?
> yes
Can you dip it in your tea?
> no
It it a pizza?
> yes
```

## Definitions

Trees consist of "leaf nodes" that don't point to any other nodes (in this game they are always the names of objects) and "non-leaf nodes" that point to one or more other nodes (in this game they are always questions, and they always point to two other nodes, one for "yes" and one for "no"). The start of the tree (i.e. "Start here" in the diagrams above) is usually called the "root" of the tree.
(Q: What's the difference between a normal person and a computer scientist?
A: A normal person knows which way up a tree grows.)
Hints about how to code all this in C.