AI Assignment 4

CS591 Adv Artificial Intelligence Homework 4 (for Ch. 3, 5, & 6) Rupa Kodali S02057353 1. (16 points) Term Definition (4 points for each question). (a) Game tree A tree structure representing all possible sequences of moves in a game. Each node represents a state, and the branches represent possible moves from that state. (b) Most Constrained Variable In constraint satisfaction problems, the variable with the fewest legal values left that constraints have not ruled out. This is often chosen next during the search. (c) Backtracking search A general algorithm for systematically searching through a space of potential solutions, keeping track of a path through the search space. When a dead end is reached, it backtracks and tries a different path. (d) Admissible heuristics A heuristic function that never overestimates the actual cost to reach the goal. Admissible heuristics are often used in an informed search to guide the search toward promising areas.

2. (39 points) Short Answer Questions. 2.1 [12 points] Say we define an evaluation function for a heuristic search problem as f ( n ) = ( w ∗ g ( n )) + ((1 – w ) ∗ h ( n )) where g ( n ) is the cost of the best path found from the start state to state n , h ( n ) is an admissible heuristic function that estimates the cost of a path from n to a goal state, and 0.0 ≤ w ≤ 1.0. What search algorithm do you get when: (a) w = 0.0 When w = 0.0, the evaluation function ignores path cost and depends only on the heuristic value h(n). This is equivalent to pure heuristic search, also known as greedy best-first search. (b) w = 0.5 When w = 0.5, the evaluation function balances path cost and heuristic estimate. This is equivalent to A* search , a more informed search algorithm guaranteed to find the optimal path if the heuristic is admissible. (c) w = 1.0 When w = 1.0, the evaluation function depends only on path cost g(n) and ignores the heuristic value. This is equivalent to uniform-cost search, a search algorithm that is guaranteed to find the optimal path, but it may not be as efficient as A* search if the heuristic is not very accurate.

2.3 (15 points) Heuristics Consider the 8-puzzle in which there is a 3 x 3 board with eight tiles numbered 1 through 8. The goal is to move the tiles from a start configuration to a goal configuration, where a move consists of a horizontal or vertical move of a tile into an adjacent position where there is no tile. Each move has cost 1. (a) Is the heuristic function defined by admissible, where is the number of ℎ = 𝑖=1 8 ∑ α 𝑖 𝑑 𝑖 𝑑 𝑖 vertical plus the number of horizontal moves of tile i from its current position to its goal position assuming there are no other tiles on the board, and 0 ≤ ≤ 1 is a α 𝑖 constant weight associated with tile i ? Explain briefly why or why not. The heuristic h(n) is admissible if 0 ≤ w_i ≤ 1 for all tiles i. This is because h(n) estimates the cost to reach the goal by summing the weighted estimated number of moves for each tile i to reach its goal position. Since the estimated number of moves for each tile is a lower bound on the actual number of moves required, multiplying it by a weight 0 ≤ w_i ≤ 1 maintains admissibility by preventing overestimates of the true total cost to the goal. If any w_i > 1, h(n) could potentially overestimate. (b) Is the heuristic defined by h ( n ) = 8 – cost ( n ) admissible, where cost ( n ) is the cost from start to node n ? Explain briefly why or why not. No, the heuristic h(n) = 8 - cost(n) is not admissible . The optimal solution cost for the 8-puzzle is, at most, eight moves. However, it is possible for the path cost from the start to node n, cost(n), to exceed 8 (for example, if the cost(n) is nine after taking some suboptimal moves). In that case, h(n) = 8 - 9 = -1 would underestimate the true cost to reach the goal from n, violating the condition for admissibility. (c) Given two arbitrary admissible heuristics, h1 and h2 , which composite heuristic is better to use, max ( h1 , h2 ), ( h1 + h2 )/2, or min ( h1 , h2 )? Explain briefly why. A composite heuristic is admissible if every component heuristic is admissible. Since max(h1, h2) always returns the larger of h1 and h2, it follows that max(h1, h2) is admissible whenever h1 and h2 are admissible. Therefore, the composite heuristic max(h1, h2) is the best choice, as it is guaranteed to be admissible whenever h1 and h2 are admissible.

3. (45 points) Algorithms. 3.1 [12 points] 3-Player Games. Consider the 3-player game shown below. The player going first (at the top of the tree) is the Left player, the player going second (in the second layer of the tree) is the Middle player, and the player going last (in the third layer of the tree) is the Right player, optimizing the left, middle and right components respectively of the utility vectors shown. (a) [14 points] Fill in the values at all nodes. Note that all players maximize their own respective utilities.

Variables: S, B, M, D, P, G (representing PacStudent, PacBaby, PacMom, PacDad, GrandPac, and Ghost, respectively) Domains: {1, 2, 3, 4, 5, 6} for each variable (the possible positions) Constraints: Unary constraint: S ∈ {1, 2} (PacStudent must be in position 1 or 2) (S=1 or S=2) Binary constraint: ● B beside M (PacBaby beside PacMom) (B=M+1 or B=M − 1) ● B beside D (PacBaby beside PacDad) (B=D+1 or B=D − 1) ● P beside G (GrandPac beside Ghost) (P=G+1 or P=G − 1) AllDiff constraint: Each position can only contain one character, ensuring that all characters occupy distinct positions in the lineup. 3.3 [9 pts] Arc-Consistency Consider a CSP with variables X , Y with domains {1, 2, 3, 4, 5, 6} for X and {2, 4, 6} for Y , and constraints X < Y and X + Y > 8. List the values that will remain in the domain of X after enforcing arc consistency for the arc X Y (recall arc consistency for a specific arc only prunes → the domain of the tail variable, in this case X ). Domains: X = {1, 2, 3, 4, 5, 6} Y = {2, 4, 6} Constraints: 1) X < Y 2) X + Y > 8 To enforce arc consistency, we consider each value in X's domain and prune any value that does not satisfy the constraints when paired with a value in Y's domain.

We check each value for X: 1) X = 1: - Satisfies X < Y (1 < 2, 1 < 4, 1 < 6) - Does NOT satisfy X + Y > 8 for any value of Y. So 1 is pruned. 2) X = 2: - Satisfies X < Y (2 < 4, 2 < 6) - Does NOT satisfy X + Y > 8 (2 + 2 ≤ 8, 2 + 4 ≤ 8) So 2 is pruned. 3) X = 3: - Satisfies X < Y (3 < 4, 3 < 6) - Satisfies X + Y > 8 (3 + 6 > 8) So 3 remains in X's domain. 4) X = 4: - Satisfies X < Y (4 < 6) - Satisfies X + Y > 8 (4 + 6 > 8) So 4 remains in X's domain. 5) X = 5: - Satisfies X < Y (5 < 6) - Satisfies X + Y > 8 (5 + 6 > 8) So 5 remains in X's domain. 6) X = 6: - Does NOT satisfy X < Y So 6 is pruned. After enforcing arc consistency on XY, the domain of X is: {3, 4, 5}