CIS 412: Artificial Intelligence
Midterm Exam
Date: We 03/06/2024
Multiple Choice (2 pts each)
Instructions: BOLDLY circle your answer. If a question specifies "Select all that apply," you must select all correct answers (may be one or more than one). If a question doesn't specify "Select all that apply," assume there is only one correct answer.
1. Which type of agent does not retain an internal representation of the parts of the environment it cannot currently perceive?
a. Single reflex agent
b. Model-based reflex agent
c. Goal-based agent
d. Utility-based agent
2. Which of the following statements is NOT true? Select all that apply.
a. BFS is complete
b. BFS is optimal
c. DFS is complete
d. DFS is optimal
e. UCS is complete
f. UCS is optimal
3. Which of the following search algorithms does NOT take into account any information about the problem other than its definition?
a. Best-First Search
b. Breadth-First Search
c. A* Search
d. Forward Chaining
4. Given the problem of navigating through a 2D grid to reach a goal and assuming no obstacles, which of the following heuristics is admissible? Select all that apply.
a. The number of squares in the entirety of the grid.
b. The number of turns made so far in the path.
c. Half the straight-line distance from the current node to the goal.
d. The number of squares left to reach the goal regardless of direction.
5. What advantage(s) does α - β Pruning provide over Minimax? Select all that apply.
a. Increases the maximum depth the algorithm can search to.
b. Allows the algorithm to consider additional moves at each node.
c. Enhances the accuracy of the heuristic evaluation function.
d. Reduces the number of nodes evaluated without affecting the outcome.
6. Which class of search algorithms generally requires the least amount of memory?
a. Uninformed search
b. Informed search
c. Adversarial search
d. Local search
7. In a smart home system that uses sensor data to automatically adjust temperature and lighting based on environmental conditions and occupancy, which logical inference
algorithm is most appropriate?
a. Forward chaining because it’s data-driven
b. Forward chaining because it’s goal-driven
c. Backward chaining because it’s data-driven
d. Backward chaining because it’s goal-driven
8. Which operation is used to add new information or facts to an agent's knowledge base?
a. QUERY
b. TELL
c. LEARN
d. STORE
e. ASK
9. Let “ = “The Tic-Tac-Toe board has 3 X’s in a row” and β = “X wins the game” . Given the knowledge base "A row of three means a win in Tic-Tac-Toe," which statement correctly applies entailment?
a. “ ⊨ β
b. β ⊨ “
c. KB ⊨ “
d. “ ⊨ KB
10. What three components of a problem make up the state space?
a. Initial State, Actions, and Path Cost
b. Initial State, Goal Test, and Path Cost
c. Initial State, Transition Model, and Path Cost
d. Initial State, Actions, and Transition Model
True or False (2 pts each)
Instructions: Fully write out TRUE or FALSE on the lines provided. No explanations needed.
11. In a game tree for a two-player game, the MIN node represents the move where the 2nd player is trying to minimize the 1st player's score (assuming MAX is the 1st player).
Answer: True
12. A* and UCS both consider the actual costs to reach any state n from the start state. Answer: True
13. If heuristic h2 dominates h1 , then A* using h2 will always expand fewer or the same number of nodes compared to A* using h1 .
Answer: True
14. Greedy Best First Search is optimal if the heuristic is both admissible and consistent. Answer: False (it’s not optimal)
15. Horn clauses, which contain at least one positive literal, are used by inference algorithms like forward and backward chaining.
Answer: False (Horn clauses contain at most one positive literal) Note: Some versions had T/F questions flipped. EX: version Z flipped h2 and h1 for Q12.
Short Answer (10 pts each)
Instructions: CONCISELY answer the following questions. Please write legibly.
16. Describe the task environment of the Wumpus World using the PEAS framework by stating at least two items for each PEAS component.
|
P
|
1. Slide 37 of Midterm Review
2.
|
|
E
|
1.
2.
|
|
A
|
1.
2.
|
|
S
|
1.
2.
|
17. Describe Sudoku using 3 out of the 6 dimensions for describing a task environment that we discussed in class. Provide concise explanations for each.
Sudoku is a logic-based number puzzle game played on a 9x9 grid, where the objective is to fill each row, column, and 3x3 subgrid with the numbers 1 to 9, ensuring that no number repeats in any row, column, or subgrid.
Sample Sudoku Puzzle: Solved Sudoku Puzzle:
Similar to crossword puzzle example discussed in class (Slide 9 of Midterm Review)
|
Dimension
|
Explanation
|
|
Fully observable
|
|
|
Single agent
|
|
|
Deterministic
|
|
Bonus #1 (optional, 3pts): Continue describing Sudoku using the other 3 dimensions.
|
Dimension
|
Explanation
|
|
Sequential
|
|
|
Static
|
|
|
Discrete
|
|
18. Explain the difference between a tree search and a graph search algorithm. Give a concrete example of when it is advantageous to use graph search over tree search?
Slide 16 of Midterm Review
Graph search uses an explored set, which avoids revisiting explored nodes.
Bonus #2 (optional, 3pts):
In your own words (no code or pseudocode), explain how graph search works. Be thorough enough (but concise) that if you gave your explanation to someone, they could implement it in code.
Slide 16 of Midterm Review
TBH if you wrote anything thought-provoking here I gave you full points
Algorithm Walkthrough (20 pts each)
19. Consider the following graph. Every node of the graph is a state, and the only actions allowed are along directed edges. Actual costs are written next to the edges and heuristic costs are written in the table. The start state is S and the goal state is G.
This is the same graph as Slide 25 of Midterm Review except cost(S,G) = 11 not 10.
For each of the following search algorithms, write the order in which nodes are explored. Break any ties alphabetically (e.g., if A and B are tied, node A is explored before B). You may assume that the search algorithms use graph search, not tree search. Don’t forget to include the start and goal nodes.
BFS:
Explored Path: S, A, G
Was the optimal path to the goal found? (circle your answer) YES / NO
(BFS always finds optimal path)
DFS:
Explored Path: S, A, B, D, G
Was the optimal path to the goal found? (circle your answer) YES / NO
(DFS could find the optimal path, but it’s not a guarantee)
A*:
Explored Path: S, A, C, G
Was the optimal path to the goal found? (circle your answer) YES / NO
(A* always finds optimal path)
I did not take points off for the optimal path question … there might have been confusion if I meant if the order of explored nodes was the optimal path.
20. Apply the MINIMAX algorithm with ɑ- β Pruning to the game tree. Mark any branches that
are pruned (if any) with a clear X. What is the best outcome for the root MAX node?
Terminal values differ between versions.
Prune edges C to its 2nd child, and C to its 3rd child
Best outcome for root MAX: 5 (the rightmost child of B)
If the leftmost terminal node (with utility 7) is changed to a 1 (i.e., smaller value than the first child of C), would any branches be pruned? (circle your answer) YES / NO
If the leftmost terminal node (with utility 7) is changed to a 4 (i.e., larger value than the first child of C but smaller value than A), would any branches be pruned? (circle your answer) YES / NO