I wrote an android application that plays a 20-questions style game with you, where the program must guess the animal you are thinking of. Not only are the entries saved in a persistent database, but the game “inflates” data from the database on an as-needed basis, with potential savings in efficiency.
The game knowledge is a binary tree. Each (non-leaf) node contains a question that demands a yes-or-no answer, and 0-2 children. The children correspond to “yes” or “no”. The leaf node ends with straightforward question “Is it a dog?” for example. When the game starts, the controller starts at the root node, and asks the question associated with that node. The user’s response determines which child node the game moves to. The game repeats this process with each successive node it hits a leaf node. At the leaf node, if the guess is correct, the game ends. If not, the game must add a new node and call the learning method.
Explaining learning works best with an example. Say node A, a leaf node, asks “Are you thinking of a whale?” If the user is not, in face, of thinking of a whale, then the following operation occurs:
- The program asks for two pieces of user input. X: “What were you thinking of?” and Y: “What question is true for that, but not a whale?”
- Node A gets two children – node T and node F. The text of node F is set to “whale”. The text of node T is set to the answer of prompt X “Is it a parrot?”.
- Lastly, the text of node A is rewritten to be the answer to prompt Y: “Can it fly?”
Naively, the game would lose all memory every time it is shut down. The real trick is to save a persistent database that will store the tree structure between sessions. I’ve implemented the database in such a way that each node is its own row in a table, and nodes are only “inflated” from row to Node representation when needed. This means that most parts of the database will never be accessed in any given game, making the memory and CPU of this program drastically lighter. You can see the code to do this in the Node and QuestionGame classes.
- Android SQLite database wrangling
- Optimized Data structure -> Database -> Data Structure conversion.
- General Java Proficiency
- Basic Android Proficiency – Intents, Buttons, Controllers