Introduction to Artificial Intelligence

Fall 2021 Introduction to Artificial Intelligence Midterm • You have approximately 110 minutes. • The exam is open book, open calculator, and open notes. • In the interest of fairness, we want everyone to have access to the same information. To that end, we will not be answering questions about the content or making clarifications. • For multiple choice questions, – – □ means mark all options that apply # means mark a single choice First name Last name SID Q1. Q2. Q3. Q4. Q5. Q6. For staff use only: Potpourri CSPs: Secret Santa Collaborative Search Morning Commute Games Reinforcement Learning Total 1 /16 /17 /14 /15 /19 /19 /100 SID: Q1. [16 pts] Potpourri (a) [3 pts] Q1.1 Let 𝑇 be the set of all possible game trees with alternating levels of maximizer and expectation nodes. Consider each of the following conditions independently. For each condition, select the condition if and only if there exists a tree in 𝑇 such that knowing that condition and no others allows us to prune. □ When all the leaf node values are bounded by some lower bound ■ When all the leaf node values are bounded by some upper bound ■ When all the leaf node values are negative □ It is possible to prune a tree in 𝑇 , but the necessary condition is not in the above list □ We can never prune any tree in 𝑇 Upper bound: consider a scenario where the maximizer is choosing between two expectimax nodes that each take uniform distributions over children (10, 10, 10) and (0,0,𝑥) respectively. If all values are upper bounded by 10, the last child 𝑥 can be pruned since 1 (0 + 0 + 𝑥) < 1 (10 + 10 + 10) for any value of 𝑥 less than 10. 3 3 Negative: Having all leaf values be a negative number is equivalent to applying an upper bound of 0. Note: You cannot prune on a lower bound because this would not allow you to determine the score of the maximizer node. (b) [3 pts] Q1.2 Jason is on Memorial Glade, and he is searching for Soda Hall. He knows that Soda Hall exists and is reachable in some finite distance. For each action, he can only move one step in the direction North, East, South, or West. Each action incurs a cost of 1. Jason can step off campus so he represents his search problem as a graph with infinite nodes. Which of the following algorithms will allow him to eventually reach Soda? ■ Breadth First Graph Search □ Depth First Graph Search ■ Uniform Cost Search ■ A* tree search with an admissible heuristic □ None of the above This is asking which algorithms are complete on an infinite graph. DFS graph search is not complete because it can go down an infinite path that doesn’t bring us closer to Soda. BFS will reach the goal since it is a finite distance away, and the same is true for Iterative Deepening and A*. (c) Consider the following grid. Here, 𝐷, 𝐸 and 𝐹 are exit states. Pacman starts in state 𝐴. The reward for entering each state is reflected in the grid. Assume that discount factor 𝛾 = 1. (i) [3 pts] Write the optimal values 𝑉 ∗ (𝑠) for 𝑠 = 𝐴 and 𝑠 = 𝐶 and the optimal policy 𝜋 ∗ (𝑠) for 𝑠 = 𝐴. Q1.3 𝑉 ∗ (𝐴) = Q1.5 𝜋 ∗ (𝐴) = 100 # Up # Down # Q1.4 𝑉 ∗ (𝐶) = Left Right 3 100 Since the discount factor is 1 and actions are deterministic, all values will eventually converge to the optimal exit value of 100. The optimal action from 𝐴 is to move right to state 𝐶 since 𝑄(𝐴, Right) = 100 and 𝑄(𝐴, Down) = 99. (ii) [4 pts] Now, instead of Pacman, Pacbaby is travelling in this grid. Pacbaby has a more limited set of actions than Pacman and can never go left. Hence, Pacbaby has to choose between actions: Up, Down and Right. Pacman is rational, but Pacbaby is indecisive. If Pacbaby enters state 𝐶 , Pacbaby finds the two best actions and randomly, with equal probability, chooses between the two. Let 𝜋 ∗ (𝑠) represent the optimal policy for Pacman. Let 𝑉 (𝑠) be the values under the policy where Pacbaby acts according to 𝜋 ∗ (𝑠) for all 𝑠 ≠ 𝐶, and follows the indecisive policy when at state 𝐶. What are the values 𝑉 (𝑠) for 𝑠 = 𝐴 and 𝑠 = 𝐶 ? Q1.6 𝑉 (𝐴) = 25 Q1.7 𝑉 (𝐶) = 25 We first calculated 𝑉 (𝐶). Under the indecisive policy, Pacbaby will choose between actions down and right (exit states 𝐷 and 𝐹 ) with equal probability so 𝑉 (𝐶) = 1 ⋅ 100 + 1 ⋅ (−50) = 25. 2 2 For 𝑉 (𝐴), Pacbaby is following Pacman’s optimal policy which we calculated in the previous part to be the Right action. Since the discount factor is 1 and actions are deterministic, the value of 𝐴 is 𝑉 (𝐴) = 25. (iii) [3 pts] Now Pacman knows that Pacbaby is going to be indecisive when at state 𝐶 and he decides to recompute the optimal policy for Pacbaby at all other states, anticipating his indecisiveness at 𝐶. What is Pacbaby’s new policy 𝜋(𝑠) and new value 𝑉 (𝑠) for 𝑠 = 𝐴? Q1.8 𝑉 (𝐴) = 99 Q1.9 𝜋(𝐴) = # Up Down # Left # Right From the previous part, we know that 𝑄(𝐴, Right) = 25. We also know from part a(i) that 𝑄(𝐴, Down) = 99. Therefore, the value of 𝐴 is the max over all 𝑄-values which would be 99 by taking action Down. 4 SID: Q2. [17 pts] CSPs: Secret Santa The CS 188 staff members are playing Secret Santa! Each person brings a gift to the table, intending for a different person to receive that gift. However, past TA Albert, furious that he was not invited to participate, removes all the name cards on each gift so that none of the staff members know whose gift is whose! The gifts are: AI textbook (A), Backgammon (B), Chess (C), Dinosaur toy (D), Easter egg (E), Flying drone (F). The participants are: Angela, Daniel, Lexy, Ryan, Saagar, Yanlai While the staff members have forgotten which gift is for who, Albert has left them some clues. 1. Each person should receive exactly one gift. 2. Yanlai should not receive the AI textbook (A). 3. Backgammon (B) should be gifted to either Lexy, Ryan, or Yanlai. 4. The Chess set (C) is not gifted to Daniel, Lexy or Saagar. 5. The name of the person who receives Backgammon (B) is alphabetically earlier than the name of the person who receives the AI textbook (A). We frame this problem as a CSP, with the variables being gifts, and the domain being the six TAs who should receive gifts. (a) (i) [1 pt] Q2.1 Which of the following constraints are binary constraints? □ Constraint 1 □ Constraint 2 □ Constraint 3 □ Constraint 4 ■ Constraint 5 (ii) [2 pts] Q2.2 Given just these clues, we use local search to try to find a satisfying assignment. We’ll initialize the assignments alphabetically (i.e. assign the 𝑖th person in alphabetical order to the 𝑖th gift in alphabetical order). Which of the variables are conflicted in this assignment? ■ A ■ B ■ C □ D □ E □ F # None A and B are conflicted because of constraint 5. C is conflicted because of constraint 4. (iii) [2 pts] Q2.3 Say we randomly choose to swap the value of A with the value of some other variable, and use minconflicts to decide which to swap with. Which of the variables could be selected by the min-conflicts heuristic for A to swap with? □ A □ B ■ C □ D □ E □ F # None Switching A with C results in only variable B being conflicted. Otherwise, at least both variable B and variable C will be conflicted. Now Albert gives another clue: 6. The person who should get Backgammon (B) and the person who should get the Dinosaur (D) have names with the same number of letters (Angela/Daniel/Saagar/Yanlai, Lexy/Ryan). We have provided a full list of constraints along with a table at the end of this problem. Please feel free to use it as you work through each of the subparts. Note that constraint 7 which is introduced later applies only to questions 2.7 and after. (b) The TAs restart with all the variables unassigned, then enforce all unary constraints and perform arc consistency. We first enforce unary constraints. Eliminate Yanlai from A. Eliminate Angela, Daniel, and Saagar from B. Eliminate Daniel, Lexy, and Saagar from C. Next we enforce arc consistency. Eliminate Angela, Daniel, and Lexy from A, because the person who receives A must alphabetically come after the person who receives B. Eliminate Yanlai from B because the person who receives B must alphabetically come before the person who receives A. Eliminate Angela, Daniel, Saagar, and Yanlai from D, because the person who gets B must have the same number of letters as the person who receives D, and only 4-letter names are remaining in the domain of B. Remaining values for each variable: A: Ryan, Saagar; B: Lexy, Ryan; C: Angela, Ryan, Yanlai; D: Lexy, Ryan; E: everything; F: everything. 5 (i) [1 pt] Q2.4 How many values are left in the domain of C? # 1 # 2 3 # 4 # 5 # 6 (ii) [2 pts] Q2.5 Using the MRV heuristic, which variable(s) could be assigned next? Select multiple if there’s a tie. ■A ■B □C ■D □E □F (iii) [2 pts] Q2.6 Say we choose to assign a value for E. Which value should we assign to E according to the LCV Heuristic? Break ties alphabetically. Assigning E to Daniel would only remove Daniel from the domain of F. Assigning E to any other person would remove that person from more than one other domain (and potentially remove other values from other domains as well, if we perform arc-consistency). Thus, assigning E to Daniel is the Least Constraining Value. # Angela Daniel # Lexy # Ryan # Saagar 6 # Yanlai SID: Albert now gives one last clue: 7. The Easter egg (E) should be given to Daniel, Ryan, or Yanlai. (c) We want to use this information to solve our CSP. Continue where we left off from the previous part, and remove Angela, Lexy, and Saagar from the domain of E. (i) [1 pt] Q2.7 Given all the constraints we have so far, do we have enough information to fully deduce the value of any of the variables? Yes # No At first glance, it may seem like all the variables have more than one value left in their domain so we can’t fully deduce the value of any variable. However, we can notice that if A is assigned to Ryan, then there’s no possible way to satisfy constraint 6. So, Saagar must receive A, and so A is a variable whose value we can fully deduce. (ii) [3 pts] Complete a full recursive backtracking search and identify a satisfying assignment. Apply the MRV heuristic when needed and break any ties alphabetically. Which gift does each person get? Hint: Try to keep track of assignments by numbering each layer of domain pruning for easier backtracking. It may also help to keep a copy of the variables’ domains after only enforcing unary constraints and arc consistency. Following the MRV heuristic and breaking ties alphabetically, we assign A to Ryan. After enforcing arc consistency, though, we see that there are no more values in the domain of D, so we must backtrack and assign A to Saagar. We then eliminate Saagar from the domains of all the other variables Next, we apply MRV again and assign B to Lexy. Enforcing arc consistency, we also see that D must be assigned to Ryan. We eliminate Lexy and Ryan from the domains of all the other variables. We apply MRV one more time and assign C to Angela. Then eliminate Angela from the domains of all the other variables. Finally, apply MRV one last time and assign E to Daniel, which leaves only Yanlai in the domain of F. Q2.8 Q2.9 Q2.10 Q2.11 Q2.12 Q2.13 A: B: C: D: E: F: # # # # # Angela Angela Angela Angela Angela Angela # # # # # Daniel Daniel Daniel Daniel Daniel Daniel # # # # # Lexy Lexy Lexy Lexy Lexy Lexy # # # # # Ryan Ryan Ryan Ryan Ryan Ryan # # # # # Saagar Saagar Saagar Saagar Saagar Saagar # # # # # Yanlai Yanlai Yanlai Yanlai Yanlai Yanlai (iii) [1 pt] Q2.14 Which variable is assigned last in the backtracking search? # A # B # C # D # E F (iv) [2 pts] Q2.15 How many different solutions does this CSP have? 6 B/D can be Lexy/Ryan. C-E-F can be Angela-Daniel-Yanlai, Angela-Yanlai-Daniel, Yanlai-Daniel-Angela. (d) [0 pts] Q2.16 Optional: Which TA do you think would be most happy with their gift? # Angela # Daniel # Lexy # Ryan # Saagar 7 # Yanlai Q3. [14 pts] Collaborative Search We have a grid of 𝑚 by 𝑛 squares where some edges between adjacent squares are blocked by a wall. An Explorer wants to move from a starting square 𝐸 to a goal square 𝐺. At each time step, the Explorer can move Up (𝑈 ), Down (𝐷), Left (𝐿) or Right (𝑅) to the adjacent square unless there is a wall on the edge that the Explorer wants to cross, and each move incurs a cost of 1. The locations of the walls are fixed. In addition, some squares are occupied by a booster (𝐵). If the Explorer moves to a square with a booster at time step 𝑡, then at time step 𝑡 + 1 the booster disappears from the grid, and the Explorer can choose to teleport in a certain direction (𝑈 , 𝐷, 𝐿, or 𝑅) for 1, 2, 3 or 4 squares (bypassing all the walls along the way), but the move incurs a cost of 𝑘 the 𝑘th time a booster is used. (a) (i) [3 pts] Q3.1 Assume for now that there are 𝑏 boosters in the whole 𝑚 by 𝑛 grid, numbered 1, 2, … , 𝑏, and the locations of these boosters are fixed and known. The Explorer wants to search for a minimum-cost path from 𝐸 to 𝐺. Which of the following quantities should be included in a minimal but sufficient state space for this search problem? ■ The current position of the Explorer □ An array of booleans indicating whether each square contains a booster □ The number of boosters used so far ■ An array of booleans of length 𝑏, indicating whether each of the 𝑏 boosters has been used □ The number of total time steps traveled so far □ An array of booleans indicating whether each edge is occupied by a wall Since we know the number of boosters, we only need to keep track of whether each of them has been used. (ii) [1 pt] Q3.2 What is the maximum branching factor? 16 Once stepped onto a square with a booster, the Explorer can choose one of the four directions (U, D, L, R), and 1, 2, 3, or 4 squares on that direction. So the maximum branching factor is 4 × 4 = 16. Note that "not using the booster" is not an option. (b) Suppose that we introduce a second agent called a Transporter and we have an unknown number of boosters on the grid to start. The Transporter starts at square 𝑇 and its moves follow all the same rules as the Explorer, except that when the Transporter moves to a square with a booster at time step 𝑡, then at time step 𝑡 + 1 it can choose to either move normally to an adjacent square without moving the booster, or carry the booster and move to an adjacent square along with the booster together, and put the booster down at any time. The Explorer and the Transporter can occupy the same square. For each time step, we first control the Explorer to make a move, and then we control the Transporter to make a move. (i) [3 pts] Q3.3 We want to search for a minimum-cost sequence of actions for both agents which enables the Explorer to reach the goal 𝐺. Which of the following quantities should be included in a minimal but sufficient state space for this search problem? ■ The current position of the Transporter ■ An array of booleans indicating whether each square contains a booster ■ The number of boosters used so far Since we do not know the number of boosters in the problem, we need to have one Boolean for each square. We also need to know the number of boosters used so far to calculate the cost of using a booster. (ii) [1 pt] Q3.4 What is the maximum branching factor? Represent your answer in terms of 𝐴, the solution to Q3.2. 8𝐴 The explorer has a branching factor of 𝐴, and the transporter has a branching factor of 8 (it can choose to use the booster or not, and move in any direction). (iii) [3 pts] Q3.5 Under which of the following modifications to the state space or to the rules of moving can DFS Tree Search always find a sequence of moves which enables the Explorer to move from 𝐸 to 𝐺, if one such sequence exists (in the modified problem)? These modifications are applied individually and independently. □ Include in the state space an array of numbers indicating the number of times each square has been visited by Explorer. ■ The Transporter is not allowed to visit a previously visited square. ■ The Explorer is not allowed to visit a previously visited square. ■ The Explorer is not allowed to visit a previously visited square, but after each usage of a booster, the set of previously visited squares is reset to empty. DFS tree search always find a solution when there is no infinite loop and the state space is finite. Option 1 makes the state space infinite so DFS tree search may still not halt. If the transporter/explorer is not allowed to visit a previously visited square, then there is no infinite loop because the problem cannot return to a previous state. 8 SID: (c) [3 pts] Q3.6 Which of the following statements are correct regarding the existence of solutions to the search problems in parts (a) and (b)? □ When there is at least one booster, the search problem in part (a) always has a solution. □ When there is at least one booster, the search problem in part (b) always has a solution. ■ For a given configuration of booster locations, if the search problem in part (a) has a solution, then the search problem in part (b) also has a solution. ■ For a given configuration of booster locations, it is possible that the search problem in part (a) does not have a solution, but the search problem in part (b) has a solution. A simplest counterexample for options 1 and 2 is that the Explorer is trapped in a square with walls on all four sides, and there is no booster at that square. Option 3 is correct since the transporter is only there to help the explorer move the boosters. For option 4, consider the case where there is a vertical wall separating the grid into a left and a right region. The left region has 6 columns, and there is one booster at the left-most column. Then without the transporter, the explorer cannot use the booster to cross the wall, if the goal is in the right region. 9 Q4. [15 pts] Morning Commute Pacman’s apartment is really far from campus, so he decides to model his commute as a search problem for fun. He models Berkeley as an 𝑀 by 𝑁 square grid and starts out in the top left square; his goal is to find his way to campus 𝐶 in the bottom right square in the least number of timesteps. He can move left, right, up, or down, as long as he doesn’t leave the grid. There is a single fixed bus route on the grid where a bus travels in a cycle at a constant rate of three spaces per timestep. You may assume that any square along this route is a valid bus stop. Pacman knows the route of the bus and if he is on the same square as the bus, he can get on the bus and travel at a rate of three spaces per timestep along the bus route. He can travel on the route for any number of timesteps and get off at any square adjacent to the path. Pacman’s Clipper card is only good for one use, so he can only enter and exit the bus route at most once per commute. Below is an example start state on a 6 by 6 grid. The arrows represent the bus’s route. Note that this is just an example route, and the bus route does not necessarily have to be in this pattern. For the following questions, consider the general case, not the specific example below. Also consider each part separately (i.e.: do not carry over assumptions). (a) [3 pts] Q4.1 Which of the following are admissible heuristics? Select all that apply. □ The Manhattan distance between Pacman and campus. ■ The Manhattan distance between Pacman and campus divided by 4. □ The Manhattan distance between Pacman and the bus. □ The Manhattan distance between the closest bus stop to Pacman and campus. □ None of the above. 1. Not admissible: Pacman can reach campus in less timesteps than the actual number of spaces between if he takes the bus. 2. Admissible: At best, Pacman would be able to reach campus by moving 3 spaces per timestep, assuming he rides the bus the whole way. Therefore, this heuristic is an underestimate of the true cost of reaching campus. 3. Not admissible: Consider the case where Pacman is already next to campus; the best path does not necessarily involve Pacman’s distance to the bus. 4. Not admissible: Consider the case where Pacman is already next to campus; the best path does not necessarily involve Pacman’s distance to any bus stop. (b) [3 pts] Q4.2 Suppose Pacman knows that there is at least one bus stop adjacent to campus. Which of the following are admissible heuristics? Select all that apply. □ The Manhattan distance between Pacman and the bus. □ The Manhattan distance between the bus and the stop next to campus divided by 3. □ 13 for all states. □ The minimum of the above heuristics. ■ None of the above. 10 SID: 1. Not admissible: The bus could be far away from Pacman, while Pacman could be right next to campus. 2. Not admissible: The bus travels in a fixed route, and its distance from campus does not represent how close Pacman is to achieving his goal. 3. Not admissible: The heuristic’s value at the goal state must be 0 for admissibility, even though we underestimate everywhere else. 4. Not admissible: The minimum would be admissible if one of the heuristics achieved 0 at the goal state, because the third heuristic underestimates at all states except the goal state; however, since none of them do, the minimum is still not admissible. (c) [3 pts] Q4.3 Suppose that there are 𝐵 different buses with their own routes. Pacman can now ride the bus multiple times, but he must also ride a bus at least once. Which of the following are admissible heuristics? Select all that apply. ■ The minimum of the Manhattan distances between every bus stop and campus, and Pacman and campus. □ The number of times Pacman has ridden the bus so far. □ The Manhattan distance from Pacman to the closest bus stop plus the distance from that bus stop to campus divided by three. □ None of the above. 1. Admissible: Because Pacman must now ride a bus at least once, he must at least travel the Manhattan distance from the closest bus stop to campus at some point. After arriving at said bus stop, the Manhattan distance between Pacman and campus becomes the minimum number of steps necessary to reach the goal. The combination of these two becomes an admissible heuristic. 2. Not admissible: The number of times Pacman has ridden the bus is not representative of how close Pacman is to reaching the goal state. 3. Not admissible: Once Pacman has already ridden the bus to campus, this is an overestimate since it recalculates the distance from Pacman to the closest bus stop even when he could go straight to campus. (d) [3 pts] Suppose Pacman now wants to work out at the RSF (campus gym), located in the bottom left square of the grid. It doesn’t matter if he goes before or after he gets to campus but he must visit both locations. Below is an example start state with the RSF represented by a dumbbell in the bottom left corner: Q4.4 Which of the following are admissible heuristics? Select all that apply. ■ The minimum of the Manhattan distances between Pacman and the RSF, the RSF and campus, and Pacman and campus, divided by 3. □ The sum of the Manhattan distances between Pacman and the RSF, the RSF and campus, and Pacman and campus, divided by 3. □ The maximum of the above heuristics. □ None of the above. 11 1. Admissible: From any space, Pacman is heading to either the RSF or campus, so the minimal Manhattan distance between him and either (divided by 3 assuming he could take the bus the whole way) is less than or equal to the timesteps necessary to reach a goal state. 2. Not admissible: Since Pacman only needs to reach either the RSF or campus before going to the other, summing the distance between Pacman and the RSF with the distance between Pacman and campus overcounts by a factor. 3. Not admissible: Generally the maximum of admissible heuristics would be admissible, but since one of them is not, the maximum isn’t. (e) [3 pts] Suppose that Pacman and his friend Albert want to go to campus together today. Albert lives in an apartment in the top right corner of the grid and wants to meet up with Pacman somewhere before moving together to campus. Assume that Albert moves independently from Pacman, one space per timestep, and that they must meet in another square before either is able to go to campus. Albert cannot take the bus with or without Pacman (although Pacman can still take it alone). In this updated search problem, you can control both Pacman and Albert. Below is an example start state with Albert’s apartment in the top right corner. Albert is currently in his apartment: Q4.5 Which of the following are admissible heuristics? Select all that apply. □ The Manhattan distance between Pacman and Albert divided by 2. ■ The Manhattan distance from Albert to campus. ■ The Manhattan distance from Pacman to campus divided by 3. □ None of the above. 1. Not admissible: Pacman travelling by bus could move toward Albert faster than Albert can move toward Pacman, making this an overestimate, since it assumes they move towards each other at the same rate. 2. Admissible: Because Albert can’t take the bus, he must at minimum move exactly the number of spaces between himself and campus at a rate of 1 space per timestep in order to reach campus. 3. Admissible: Wherever Pacman is in the grid, he must at minimum reach campus to end the search, so this is a relaxation of the problem where he just goes straight to campus via bus and ignores ever meeting Albert. The solution to a relaxed problem is admissible. 12 SID: Q5. [19 pts] Games Alice, Eve, and Bob are playing a multiplayer game. Each game state consists of three numbers where the left value represents Alice’s score, the middle value represents Eve’s score, and the right value represents Bob’s score. Alice makes the first move, followed by Eve, and finally Bob. All scores for a single player are between 1 and 9 inclusive. In all pruning scenarios, remember that we do not prune on equality. Rather than trying to maximize their individual scores, Alice and Bob decide to work together to maximize their combined score, hoping that this will allow them to score higher. At each of Alice’s and Bob’s nodes, they will choose the option that maximizes left value + right value. (a) Eve overhears their plan and decides that instead of maximizing her own score, she will try to minimize Alice and Bob’s combined score. Alice and Bob are aware of Eve’s strategy. Let the value of a node be the sum of the left and right scores of the node. Answer the following questions based on the game tree shown below. Figure 1: Game tree where Alice is the root maximizer, Eve is the minimizer, and Bob is the bottom maximizer. Eve’s score at each node (center cell) is not shown for simplicity. (i) [1 pt] Q5.1 Solve the game tree shown in figure 1. What is the value of the root node? # # # # # # 6 12 13 Depends on the value of X only. Depends on the value of Y only. Depends on the values of both X and Y. None of the above. See diagram below. (ii) [2 pts] Q5.2 Without pruning, which of the following are possible values for the right minimizer? □<6 ■6 ■7 ■8 13 □>8 Consider each child of the right minimizer. The right child has a value of 8 (max(5 + 3, 6 + 1) = 8). For the left child, we must consider the bounds on 𝑌 . Given that 1 ≤ 𝑌 ≤ 9, we know that at minimum, the left child is max(1 + 1, 2 + 4) = 6 and at most it is max(1 + 9, 2 + 4) = 10. So the value of the left child is between 6 and 10. The minimizer is guaranteed to choose the lower of its two children’s values so the bounds on its values are between 6 and 8. (iii) [2 pts] Q5.3 Which of the following nodes are guaranteed to be pruned when running alpha beta pruning on the game tree above? If there are nodes that may or may not be pruned depending on the values of 𝑋 and 𝑌 , do not select them. □A □B □C □D □E □F ■G ■H # None of the above. The root maximizer gets a value of 12 from its left subtree. When visiting the right subtree, we know that the maximum value that the maximizer of 𝐸 and 𝐹 can have is max(1 + 9, 2 + 4) = 10 assuming 𝑌 takes on the highest value possible. Since 10 < 𝛼 = 12, we can prune the entire right child of the right minimizer. Therefore, 𝐺 and 𝐻 are both guaranteed to be pruned regardless of the value of 𝑌 since 𝑌 is upper-bounded by 9. (iv) [3 pts] Q5.4 Which of the following nodes may or may not be pruned depending on the values of 𝑋 and 𝑌 ? Do not select any nodes from the previous part which are guaranteed to be pruned regardless of the values for 𝑋 and 𝑌 . □A □B □C ■D □E □F □G □H # None of the above. From the previous part, we know that the value of 𝑌 does not affect whether nodes are pruned or not, so here we consider only the possible values of 𝑋. In the left subtree, the left child of the minimizer has a value of 12 (from max(2 + 2, 7 + 5) = 12). Therefore, if 𝐶 > 𝛽 = 12, then we can prune 𝐷. This case occurs if 9 + 𝑋 > 12 or when 𝑋 > 3. 14