An example of the handheld game I used to have.
Each time the program asks the user a question, it is able to narrow down the vast number of options to a smaller subset. For example, a typical starting question is "person, place, or thing." Depending on the answer, the algorithm can then rule out all of the other two subsets. By continually asking questions, this process is compounded so that by the end of the 20 questions, there are only a few reasonable options.
In order for this program to function, the game must be pre-programmed with descriptions of thousands of possible answers. It must also be pre-programmed with hundreds of possible questions for the game to ask, and corresponding categories for an answer. The technical term for this is a binary search algorithm, which is described on Wikipedia as "comparing the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful." For twenty questions, this means that it eliminates the other subsets of answers and continues to search through the correct subset. What seems like a simple game in twenty questions becomes much more complex when programming ideals are applied.
https://en.wikipedia.org/wiki/Twenty_Questions#Computers.2C_scientific_method_and_situation_puzzles
https://en.wikipedia.org/wiki/Binary_search_algorithm
https://www.amazon.com/Radica-20Q-Artificial-Intelligence-Game/dp/B0001NE2AK
Great post!! I was actually thinking about this game as my final project, but picked another game by the end. The fundamental idea for this game was the binary tree, which is made by a series of node, and each node contains left point and right pointer. The more questions you have, the more complicated is the binary tree. This game is perfect for the final project, because it involves file I/O that user can answer yes or no. It contaisn several objects including storage of all the questions, user play the game, and nodes. Check more details from this website: https://courses.cs.washington.edu/courses/cse143/15su/homework/6/spec.pdf
ReplyDeleteWhat blows my mind is how a game that seems simple and fun to us is actually the product of several programmers hard work. The complexity of this game is not known by the average user, but when understanding how the game actually works then maybe a user can figure out how to beat the game. Every code can be cracked if enough searching is done, just like in class we must refine our code to become less prone to being easily broken by a person using it, here we can also try to undo the binary tree and maybe beat it. Great post!
ReplyDeleteGreat article! I have played twenty questions before and I was always so confused about how the game was able to respond to even the most random of answers. I think the same idea can be how the Siri program addresses random questions, as well. I had never thought of the game or program as having to search through a vast array, but that makes total sense! good job!
ReplyDelete