20 Questions Guessing Game using Binary Trees

In this article, we will create a program that resembles 20 questions using a custom made binary tree. Any prior knowledge of Binary Trees is not necessary, though having basic knowledge of C# programming and creating classes is assumed. Thank you for your interest in my work.

Project Details

Create a game that asks users to think of an object and test that object against previously known questions and answers. If the object is outside of the computer's knowledge then the computer's knowlege will need to be updated.

(Note: see Sample Output for more information)

Binary Trees

Used to hold computer's knowledge. Each node has an object or question field and a reference to a 'yes' and 'no' node.

Binary Trees

Introduction to Binary Trees: A binary tree is a very efficient data structure consisting of nodes that point to each other. Each node has a data field and two references to other nodes. When progressing through a tree, one starts at the root node and moves to another node, left or right, until reaching a null reference. A node containing two null references is called a leaf node. For more information about binary trees visit: http://en.wikipedia.org/wiki/Binary_tree.

Using Binary Trees in our program: Each node will contain a question and two links to other nodes. If 'yes' is entered for a question, yes Node will be referenced. When the referenced node is a leaf node, the computer will make a guess on the object. Answering 'no' to the root node, in the example to the right, will produce the following output:

Is your object living? No

Are you thinking of a(n) Door? Yes

The computer wins!

If the computer's guess is incorrect, a new object and question has to be inserted into the tree.

Coding Binary Nodes

Programming the Binary Node Class

Create a new project named MCS_Week1 and add a new class named BTNode.cs. Add the following code which creates a constructor for the class. We are using three variables: message, noNode, and yesNode.

Creating the BTNode Class

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MCS_Week_001
{
    class BTNode
    {
        string message; //holds user's question or if a leaf node an object
        BTNode noNode; //reference to node if user enters no
        BTNode yesNode; //reference to node if user enters yes
        public BTNode(string nodeMessage)
        {
            message = nodeMessage;
            noNode = null;
            yesNode = null;
        }
    }
}

Adding Mutator Methods

The constructor's variables need mutator methods. These methods allow variables within a class to be changed by creating a public method that changes them. Add the following code to your BTNode class.

Adding Mutator Methods to BTNode Class

//Mutator Methods
public void setMessage(string nodeMessage)
{
    message = nodeMessage;
}
public string getMessage()
{
    return message;
}
public void setNoNode(BTNode node)
{
    noNode = node;
}
public BTNode getNoNode()
{
    return noNode;
}
public void setYesNode(BTNode node)
{
    yesNode = node;
}
public BTNode getYesNode()
{
    return yesNode;
}

Checking Leaf Nodes

When a node has two null references the computer has no more questions and the computer is ready to make a guess. The following method will check to see if a node is a leaf node and it will be used later when progressing through the binary trees. Add the following code inside your BTNode class.

Creating the BTNode Class

public bool isQuestion()
{
   if (noNode == null && yesNode == null)
       return false;
   else
       return true;
}

Progressing Through the Binary Tree

This game requires a user to answer a question. If the user answers yes, it asks the next question contained in the yesNode. To access the next node we are going to use a method called query(). To access the yes node use yesNode.query() and noNode for the no node. This method will also have to reconstruct the tree when the computer does not know the answer. This is done in the updateTree() method. Add the following code to your BTNode class. A complete BTNode.cs file can be found at the end of this resource.

Query through the Binary Tree

public void query()
{
    if (this.isQuestion())
    {
        Console.WriteLine(this.message);
        Console.Write("Enter 'y' for yes and 'n' for no: ");
        char input = getYesOrNo(); //y or n
        if (input == 'y')
            yesNode.query();
        else
            noNode.query();
    }
    else
        this.onQueryObject();
}

public void onQueryObject()
{
    Console.WriteLine("Are you thinking of a(n) " + this.message + "?");
    Console.Write("Enter 'y' for yes and 'n' for no: ");
    char input = getYesOrNo(); //y or n
    if (input == 'y')
        Console.Write("The Computer Wins\n");
    else
        updateTree();
}

private void updateTree()
{
    Console.Write("You win! What were you thinking of?");
    string userObject = Console.ReadLine();
    Console.Write("Please enter a question to distinguish a(n) "
        + this.message + " from " + userObject + ": ");
    string userQuestion = Console.ReadLine();
    Console.Write("If you were thinking of a(n) " + userObject
        + ", what would the answer to that question be?");
    char input = getYesOrNo(); //y or n
    if (input == 'y')
    {
        this.noNode = new BTNode(this.message);
        this.yesNode = new BTNode(userObject);
    }
    else
    {
        this.yesNode = new BTNode(this.message);
        this.noNode = new BTNode(userObject);
    }
    Console.Write("Thank you my knowledge has been increased");
    this.setMessage(userQuestion);
}

Coding Binary Tree

Creating the BTTree Class

When a new game is created, a reference to a root node is needed which holds the first question of the game. The BTTree Class will store the root reference and two object nodes. These object nodes are the two choices for the first question. Create a new class and name it BTTree.cs. Add the following code to the class.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MCS_Week_001
{
    class BTTree
    {
        BTNode rootNode;
        public BTTree(string question, string yesGuess, string noGuess)
        {
            rootNode = new BTNode(question);
            rootNode.setYesNode(new BTNode(yesGuess));
            rootNode.setNoNode(new BTNode(noGuess));
        }
        public void query()
        {
            rootNode.query();
        }
    }
}

Finishing the game

The binary tree is now programmed and it is time to put the finishing details on the project. When the game starts we need to create a new binary tree to hold the computer's knowledge. A new game needs one question and two objects and is executed in the startNewGame() method. Add the following code to the file which contains your main method.

Starting a New Game

static void startNewGame()
{
    Console.WriteLine("No previous knowledge found!");
    Console.WriteLine("Initializing a new game.\n");
    Console.WriteLine("Enter a question about an object: ");
    string question = Console.ReadLine();
    Console.Write("Enter a guess if the response is Yes: ");
    string yesGuess = Console.ReadLine();
    Console.Write("Enter a guess if the response is No: ");
    string noGuess = Console.ReadLine();
    tree = new BTTree(question, yesGuess, noGuess);
}

The startNewGame method needs to be called by the Main() method. Change the current Main() method to the following. After you add the following code you will be able to run one game.

Adding the ability to play one game

static void Main(string[] args)
{
    startNewGame();
    Console.WriteLine("\nStarting the Game");
    tree.query(); //play one game
}

Making a Play Again Option

This is not a useful game if we can only play one round. We need to add a play again option. Add the following method to the file that contains the Main() method. This method returns true if the user wants to play again, else false.

Adding the ability to play one game

static bool playAgain()
{
    Console.Write("\nPlay Another Game? ");
    char inputCharacter = Console.ReadLine().ElementAt(0);
    inputCharacter = Char.ToLower(inputCharacter);
    while (inputCharacter != 'y' && inputCharacter != 'n')
    {
        Console.WriteLine("Incorrect input please enter again: ");
        inputCharacter = Console.ReadLine().ElementAt(0);
        inputCharacter = Char.ToLower(inputCharacter);
    }
    if (inputCharacter == 'y')
        return true;
    else
        return false;
}

Change your main function to the following and enjoy playing your game. Please feel free to contact me if you have any questions. My email is located at the top of this lesson.

Adding the ability to play one game

static void Main(string[] args)
{
    startNewGame();
    Console.WriteLine("\nStarting the Game");
    tree.query(); //play one game
    while(playAgain())
    {
        Console.WriteLine();
        tree.query(); //play one game
    }
}

Complete Code Files

BTNode.cs

The Complete BTNode.cs Class File

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MCS_Week_001
{
    [Serializable] class BTNode
    {
        string message;
        BTNode noNode;
        BTNode yesNode;
        /**
         * Constructor for the nodes: This class holds an String representing
         * an object if the noNode and yesNode are null and a question if the
         * yesNode and noNode point to a BTNode.
         */
        public BTNode(string nodeMessage)
        {
            message = nodeMessage;
            noNode = null;
            yesNode = null;
        }
        public void query()
        {
            if (this.isQuestion())
            {
                Console.WriteLine(this.message);
                Console.Write("Enter 'y' for yes and 'n' for no: ");
                char input = getYesOrNo(); //y or n
                if (input == 'y')
                    yesNode.query();
                else
                    noNode.query();
            }
            else
                this.onQueryObject();
        }
        public void onQueryObject()
        {
            Console.WriteLine("Are you thinking of a(n) " + this.message + "?");
            Console.Write("Enter 'y' for yes and 'n' for no: ");
            char input = getYesOrNo(); //y or n
            if (input == 'y')
                Console.Write("The Computer Wins\n");
            else
                updateTree();
        }
        private void updateTree()
        {
            Console.Write("You win! What were you thinking of?");
            string userObject = Console.ReadLine();
            Console.Write("Please enter a question to distinguish a(n) "
                + this.message + " from " + userObject + ": ");
            string userQuestion = Console.ReadLine();
            Console.Write("If you were thinking of a(n) " + userObject
                + ", what would the answer to that question be?");
            char input = getYesOrNo(); //y or n
            if (input == 'y')
            {
                this.noNode = new BTNode(this.message);
                this.yesNode = new BTNode(userObject);
            }
            else
            {
                this.yesNode = new BTNode(this.message);
                this.noNode = new BTNode(userObject);
            }
            Console.Write("Thank you my knowledge has been increased");
            this.setMessage(userQuestion);
        }
        public bool isQuestion()
        {
            if (noNode == null && yesNode == null)
                return false;
            else
                return true;
        }
        /**
         * Asks a user for yes or no and keeps prompting them until the key
         * Y,y,N,or n is entered
         */
        private char getYesOrNo()
        {
            char inputCharacter = ' ';
            while (inputCharacter != 'y' && inputCharacter != 'n')
            {
                inputCharacter = Console.ReadLine().ElementAt(0);
                inputCharacter = Char.ToLower(inputCharacter);
            }
            return inputCharacter;
        }
        //Mutator Methods
        public void setMessage(string nodeMessage)
        {
            message = nodeMessage;
        }
        public string getMessage()
        {
            return message;
        }
        public void setNoNode(BTNode node)
        {
            noNode = node;
        }
        public BTNode getNoNode()
        {
            return noNode;
        }
        public void setYesNode(BTNode node)
        {
            yesNode = node;
        }
        public BTNode getYesNode()
        {
            return yesNode;
        }
    }
}

BTTree.cs

The Complete BTTree.cs Class File

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MCS_Week_001
{
    class BTTree
    {
        BTNode rootNode;
        public BTTree(string question, string yesGuess, string noGuess)
        {
            rootNode = new BTNode(question);
            rootNode.setYesNode(new BTNode(yesGuess));
            rootNode.setNoNode(new BTNode(noGuess));
        }
        public void query()
        {
            rootNode.query();
        }
    }
}

Program.cs (Main() Method file)

The Complete Main() Method file

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;

namespace MCS_Week_001
{
    class Program
    {
        static BTTree tree;
        static void Main(string[] args)
        {
            startNewGame();
            Console.WriteLine("\nStarting the Game");
            tree.query(); //play one game
            while(playAgain())
            {
                Console.WriteLine();
                tree.query(); //play one game
            }
        }
        static bool playAgain()
        {
            Console.Write("\nPlay Another Game? ");
            char inputCharacter = Console.ReadLine().ElementAt(0);
            inputCharacter = Char.ToLower(inputCharacter);
            while (inputCharacter != 'y' && inputCharacter != 'n')
            {
                Console.WriteLine("Incorrect input please enter again: ");
                inputCharacter = Console.ReadLine().ElementAt(0);
                inputCharacter = Char.ToLower(inputCharacter);
            }
            if (inputCharacter == 'y')
                return true;
            else
                return false;
        }
        static void startNewGame()
        {
            Console.WriteLine("No previous knowledge found!");
            Console.WriteLine("Initializing a new game.\n");
            Console.WriteLine("Enter a question about an object: ");
            string question = Console.ReadLine();
            Console.Write("Enter a guess if the response is Yes: ");
            string yesGuess = Console.ReadLine();
            Console.Write("Enter a guess if the response is No: ");
            string noGuess = Console.ReadLine();
            tree = new BTTree(question, yesGuess, noGuess);
        }
    }
}