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.