Exercise 9: 20 Questions

Objectives

• to use a decision tree ADT
• to implement a data structure using binary trees

Introduction

A decision tree is a tool for determining what action to take based on the results of a sequence of yes/no questions, where what question is asked at any point in the sequence can depend on the questions asked and answers received previously. A decision tree is equivalent to a sequence of nested if-then-elses and can be represented by a binary tree. Each internal (non-leaf) node in the tree contains a test (question); the left child represents the next question to ask or the action to take if the answer is "yes" and the right branch is used when the answer is "no."

Decision trees have many applications. The behavior of non-player characters (NPCs) in a video are often determined by decision trees, where the action the NPC takes is determined by its observations of the world. For example, a farmer NPC could choose between conversation, fleeing, tending fields, or herding sheep based on the following decision tree.

Decision trees are also common in data science to predict the class of an object based on its attributes. The tests in the internal nodes are then yes/no questions about the values of those attributes and the actions in the leaves are "predict that the object belongs to class X". For example, a decision tree that predicts what species of iris a specimen belongs to is given below.

The game 20 questions in which one player thinks of something and the other player tries to guess what it is by asking yes/no questions can also be modelled with a decision tree.

Assignment

Complete the implementation of the decision tree ADT contained in /c/cs223/hw9/Optional/dt.c to conform to the interface defined in the header file /c/cs223/hw9/Required/dt.h and then use that to finish a program in /c/cs223/hw9/Optional/20_questions.c that plays 20 Questions.

The program asks its questions and makes its guesses based on the current decision tree. For the first game, the root of the decision tree will be a leaf, so the program always guesses the object stored in the root. But as it plays more games, it will add nodes to its decision tree so it can correctly guess more and more objects. It will start each game by asking the question in the root, and will follow the left or right branch depending on the player's answer. It continues asking the questions, moving left or right according to the player's answers until it gets to a leaf, at which point it makes its guess. If the guess was wrong, then it asks the player for a question that distinguishes the correct answer (what the player was thinking of) from its incorrect guess, and adds a test node at the location in the tree where it ended up.

Code

Decision Tree ADT

You can use three structs to implement the ADT functions: one for nodes in the tree, one for the tree itself, and one for iterators. The nodes should contain a pointer to a string for the text (either a test (question) or a class (guess)). A tree then contains just a pointer to its root, and an iterator contains just a pointer to its current node.

dt_create should create a node with no children that contains a pointer to a copy of the initial guess. Then it should create a tree with that node as its root.

dt_iterator_create should create an iterator whose current node is the root of the tree.

dt_iterator_at_leaf tests whether one of the children is NULL (because the structure of a decision tree requires that each node has either zero or two children, if one child is NULL then the other is too, so it doesn't matter which one you check).

dt_iterator_move_left and dt_iterator_move_right set the current node in the iterator to the left or right child of the current node respectively.

dt_iterator_get_test and dt_iterator_get_class return the text inside the iterator's current node (we implement these as two separate functions to make it easier to generalize later to decision trees for which the tests and classes are of different types).

dt_iterator_add_branch_left and dt_iterator_add_branch_right should create two new nodes with no children, copy the pointer to the guess in the iterator's current node to one of them, save a pointer to a new copy of the new guess to the other, link the current node to the two new children, and store a pointer to a copy of the new test in the current node.

dt_iterator_destroy should free the iterator.

dt_destroy should call a recursive helper function that performs a postorder traversal of the tree, freeing the text inside the current node and the node itself after recursively freeing the left subtree and the right subtree. Once the helper function returns, dt_destroy should free the tree.

20 Questions

The main module in /c/cs223/hw9/Optional/20_questions.c implements the main structure of the program. You must add the calls to the decision tree ADT in the appropriate places.

The provided code initializes a decision tree that always guesses "orange".

At the beginning of each game, get an iterator positioned at the root of the current tree. As long as that iterator is not positioned at a leaf (a guess), ask the player to answer the question stored in the iterator's current node. Then move the iterator left or right depending on the response.

Once the iterator is positioned at a leaf, announce the computer's guess by getting the class stored in the iterator's current node. If that guess is correct, then there is nothing more to be done. Otherwise, a new test (question) must be added at the current location, with the wrong guess as one child and what the player was actually thinking of as the other. The iterator can then be destroyed.

Once the player decides not to play again, destroy the decision tree.

Example

(base) [jrg94@turtle code]$ ./20Q
Would you like to play a game? (yes/no)
yes
Think of something.  I will ask yes/no questions to deduce what it is.
Is it a(n) orange? (yes/no)
no
What were you thinking of?
apple
What question distinguishes a(n) orange from a(n) apple?
Do you eat its clothes?
What is the answer to that question for apple? (yes/no)
yes
Would you like to play again? (yes/no)
yes
Think of something.  I will ask yes/no questions to deduce what it is.
Do you eat its clothes? (yes/no)
no
Is it a(n) orange? (yes/no)
no
What were you thinking of?
minneola tangelo
What question distinguishes a(n) orange from a(n) minneola tangelo?
Is it just the right tartness, juicy, and easy to peel?
What is the answer to that question for minneola tangelo? (yes/no)
yes
Would you like to play again? (yes/no)
yes
Think of something.  I will ask yes/no questions to deduce what it is.
Do you eat its clothes? (yes/no)
no
Is it just the right tartness, juicy, and easy to peel? (yes/no)
yes
Is it a(n) minneola tangelo? (yes/no)
yes
Score one for me!
Would you like to play again? (yes/no)
no
    

Submissions

Submit your modified 20_questions.c and dt.c files, any other files you created, and your makefile with the 20Q executable as the default target as assignment number 9. You need not submit the other given files, and your makefile should assume they have been copied into the current directory rather than that they are in their original locations.