Essays/AnimalsGame
Game
There is a game called animals that uses expanding tree structures to try to guess what animal you were thinking of. If it guesses wrong it asks you what animal you are thinking of and for a question to identify it. Thus the decision tree grows and the program gets "smarter."<<FootNote(from http://www.amzi.com/articles/prolog_fun.htm)>> (Additionally, you could save the knowledge base permanently and reload it next time)
This game is famous especially to AI people as a simple example of building expert system with decision trees. Hence, there are many examples of this game programmed in Prolog<<FootNote(http://www.amzi.com/articles/prolog_fun.htm)>> and Lisp/Scheme<<FootNote(http://www-inst.eecs.berkeley.edu/~cs61a/su05/readernotes/readernotes5.1.pdf)>>. It's done in other programming languages, too, like Python<<FootNote(http://greenteapress.com/thinkpython/html/chap20.html)>> <<FootNote(http://www.ibiblio.org/obp/py4fun/animal/animal.html)>>, Atari BASIC<<FootNote(http://www.atarimagazines.com/v4n12/Animal.html)>>, Ruby<<FootNote(http://www.rubyquiz.com/quiz15.html)>>, and Eiffel<<FootNote(http://efsa.sourceforge.net/archive/bielak/animal_guess.htm)>>. Moreover, there are some APL implementations<<FootNote(Comparison with Lisp attachment:kaneko.pdf)>> <<FootNote(APLOMB attachment:guazzo.pdf)>>.
Joe Marasco recommends this game as the standard problem for learning a new language in his How to Learn a New Programming Language article.
Sample Session
Following is a sample running session from Raul Miller's program:
go '' Does it have fur? N Is it a lizard? Y go '' Does it have fur? Y Is it a mouse? N What animal were you thinking of? dog What is a yes/no question that distinguishes a dog from a mouse? Does it bark? For a dog: Does it bark? Y go '' Does it have fur? Y Does it bark? Y Is it a dog? Y
Raul Miller's
From JForum:programming/2006-August/002960
The initial functions I defined are a bit more elaborate than I really need, because I did not have the full program architecture developed at the time I wrote them, and I didn't care to go back and reduce the program.
Rather than a loop asking the person if they want to continue, I elected to make the verb go only ask one series of questions. It's simple enough to type go'' again if you want to deal with another set of questions about some animal. (It would also be simple to add another level of looping, but I found this approach more convenient.)
I did not use a "tree", as such. Instead, I used a list of questions, a list of animals, and a corresponding table of known facts: Given a question and an animal, would the answer be yes, no or maybe (where "maybe" really means "I don't know what the answer would be")?
"Animals" doesn't say what should happen if at one point in time an animal is said to have some feature and at another point in time an animal is said to not have that feature. I elected to throw an error for those cases. Conceivably you could invalidate earlier q&a sessions with answers received in those sessions being hints at possible answers but not necessarily true. However, this would be more complicated to implement.
Oleg's
Save as user/animals_oleg.ijs. It uses user/animals_oleg.txt for database. Rename as needed.
Session example::
load 'user\animals.ijs' animals '' Think of some animal. Answer y(es), 1, n(o) or 0. Type "quit" or "restart" at any time". Does it have fur? y Does it bark? n Does it purr? n Does it have hooves? n Is it a mouse? n What animal were you thinking of? bear What is its yes/no question? Does it hibernate For a bear the answer is? y Play again? n
Features::
- Data is represented in a compact tabular binary tree
- Database in saved after each play and between sessions
- Database file is in easy human readable and editable format
Data structure::
- Binary tree is represented as a list of questions each with two animals for yes and no
- Questions should be unique
- Each animal can appear once per question in any number of questions
- Leaf node is determined by absence of the same animal in rows below current
I never come across the representation of a binary tree in such data structure, where reference to the next node is represented by a element of a pair. So I am not sure how to refer to it. I would appreciate if someone would provide any reference.
Play::
- The table is worked from top to bottom
- User is asked a question
- If picked (by yes/no) animal is a "leaf" node
- then user is asked to confirm
- if yes, game restarts
- otherwise user is offered to enter new animal, its question and answer, which is appended to the end of the table, with the unconfirmed animal as the complementary answer
- otherwise game proceeds to next question, in which the picked animal appears
Properties::
- To identify an animal, every row in which that animal is present must have an answer (yes/no) in the corresponding position for that animal
- Thus the order rows of the table are insignificant to determine the animal
- However, semantically, all rows with a given animal need to be ordered from general to special
Database Example::
Does it have fur ? mouse : fish Does it bark ? dog : mouse Does it purr ? cat : mouse Does it weave webs ? spider : fish Does it have hooves ? cow : mouse Does it hibernate ? bear : mouse
Boxed Tree
This does not have the play, just the structure and operations.
The APL2 example uses nested boxes to emulate LISP lists. Here's such structures in J. Each nesting is Question;YesChoice;NoChoice, Choice is either animal of another nesting. Path in such binary tree is 0 for Yes and 1 for No.
Readable representation of nested structures with stacked list, where each line is pushed on the stack and the dot placeholder pops a line to use in its place.
Inserting a new tuple in place of an animal is done with emulated pseudo-unfetch }:: for binary tree path (0-1 sequence of choices).
Example output
parse BASE
+---+----------------------------------------+-----------------+
|fur|+----+----------------+----------------+|+---+------+----+|
| ||bark|+-----+----+---+|+----+---+-----+|||web|spider|fish||
| || ||woods|wolf|dog|||purr|cat|mouse|||+---+------+----+|
| || |+-----+----+---+|+----+---+-----+|| |
| |+----+----------------+----------------+| |
+---+----------------------------------------+-----------------+
gen parse BASE
web ? spider : fish
purr ? cat : mouse
woods ? wolf : dog
bark ? . : .
fur ? . : .
('fish';'fisherman';'spider') 1 1 unfetch parse BASE
+---+----------------------------------------+------------------------------------+
|fur|+----+----------------+----------------+|+---+------+-----------------------+|
| ||bark|+-----+----+---+|+----+---+-----+|||web|spider|+----+---------+------+||
| || ||woods|wolf|dog|||purr|cat|mouse|||| | ||fish|fisherman|spider|||
| || |+-----+----+---+|+----+---+-----+||| | |+----+---------+------+||
| |+----+----------------+----------------+|+---+------+-----------------------+|
+---+----------------------------------------+------------------------------------+
gen ('dam';'beaver';'mouse') 0 1 1 unfetch parse BASE
web ? spider : fish
dam ? beaver : mouse
purr ? cat : .
woods ? wolf : dog
bark ? . : .
fur ? . : .
See Also
Footnotes
<<FootNote>>
Contributed by June Kim, Raul Miller, Oleg Kobchenko