Wednesday 11 March 2026: Quiz 5: Genetic Algorithms Also: Practice Midterm Machine Learning Nowadays, when people think of AI, Machine Learning is what they think of. Decision Trees AI is used to create and modify decision trees. A decision tree is exactly what it sounds like. The root node is a question and the tree's children are roots of subtrees that you will visit depending on the answer to the question. Example: Should I go to class today? The root question might be something like: Is today a class today? NO: No, do not go to class today. YES: Is today a Snow Day? YES: Do not go to class today. NO: Am I sick? YES: Am I contagious? YES: Do not go to class today. NO: Am I physically able to go to class? YES: Go to class. NO: Do not go to class. NO: Go to class. Your next program will be to make an (easy) decision tree to play the game Twenty Questions. The game: You think of anything you want to think of. The computer will guess what it is. The first time you play the game: Computer: I give up. What is it? Suppose you say a dog. The second time you play the game: Computer: Is it a dog? If it is a dog, you say yes. The computer announces that it has guessed your item in one guess. If it is not a dog, you say no. Computer: I give up. What is it? Suppose you say a deck of cards. Computer: What question would you ask to give a yes answer for a dog and a no answer for a deck of cards? Suppose you say Is it a living being? The third time you play the game: Computer: Is it a living being? Suppose you say yes. Computer: Is i a dog? t If you had said no to the living being question, then Computer: Is it a deck of cards? In general, the program keeps track of a binary search tree. The leaves of the tree represent specific guesses of an item. ("A dog", "A deck of cards.") When the program processes a leaf it asks the question ("Is it...?") if the answer is yes, then the computer announces how many questions it needed. If the answer is no, then the computer has to give up and will then ask the user a question that will distinguish the item guessed from the correct answer. The computer then adjust the tree by making a new node just above the leaf, with both the last guess and the correct answer as children of that new node (keeping them as leaves). As the computer plays the game, it starts at the root, every time it processes a node that is not a leaf, it will ask a yes or no question, and then process the node corresponding to the answer to that question (the YES child or the NO child). You will have to store the tree in a file. When the program has finished playing the game. The tree is stored in the file. When the program is run again, the tree is loaded from the file. You will see, as you develop this program, that the AI here (and the game itself) actually sucks a fair bit. And the reason it sucks is that new questions are only added just above the leaf level. This program does have not have the capability to add new questions at the top or middle of the tree, only at the bottom. So when you play the game, and add new questions, you want the questions to be as broad as possible. In our sample above, the first question we asked, to distinguish between a dog and a deck of cards was "Is it a living being?" This is good question because that question is going to be the first question this program ever asks in this iteration of the game. If the question was more specific, say, "Is it a canine of the species canis familiaris?" This would also yield a yes answer for a dog and a no answer for a deck of cards? But you're going to be able to build too much on the yes side because a dog is just about the only thing that would give a yes answer to that question. In real life, when you build decision trees, you make the most important question the first question. And you use AI to adjust over time what that first question ought to be. (Our above uses binary yes/no questions. However, there is no law that says our questions need to have binary answers. The node will have a number of children equal to the number of possible answers to that question. The book for decision trees uses the example of: Should we wait for a table at a restaurant? How many patrons are at the restaurant? NONE: NO (don't wait for a table) SOME: YES (probably there isn't much of a wait) FULL: Other questions The book's example: Should I wait for a table? There are 10 categories to measure: Alternate (YES/NO): is there a suitable restaurat nearby? Bar (YES/NO): Does this restaurant have a bar to wait at? Fri/Sat (YES/NO): Is this Friday or Saturday (YES) or another day of the week (NO) Hungry (YES/NO): Am I hungry right now? Patrons (NONE/SOME/FULL): How many people are at the restaurant? Price ($/$$/$$$): How expensive is the restaurant? Raining (YES/NO): Is it raining? Reservation (YES/NO): Do we have a reservation? Type (FRENCH/ITALIAN/THAI/BURGER): Type of food served Wait Estimate (0-10/10-30/30-60/>60): How long is the wait? Notice that these are all discrete questions? Six questions with binary choices, 2 questions with ternary choices, 2 questions with four choices. 2^6 x 3^2 x 4^2 = 64 x 144 = 9216 possibilities. If we already knew the correct answer for all 9216 possibilties/combinations, we wouldn't need a decision tree, we wouldn't need AI. We would just have a lookup table give us the answer. The idea of building a decision tree is that with limited data, we should be able to extrapolate what the answer ought to be given a list of choices beyond the possibilities we were already given. If we have the correct answer for, say, 12 possibilities rather than for all 9216, those 12 possibilities are called the "training data." Alt: YES Bar: NO Fri/Sat: NO Hungry: YES Patrons: SOME Price: $$$ Raining: NO Reservations: YES Type: French Wait: 0-10 Answer: Yes, wait for a table. Patrons: None: Don't wait Some: Wait Full: Hungry: NO: Don't wait YES: Type French: Wait Italian: Don't wait Thai: Fri/Sat: NO: Don't wait YES: Wait Burger: Wait