Quiz 0

Milestones

Rubric

All questions on the quizzes in this course are out of 3 points. When assessing these quizzes, score answers as follows:

• 3 is reserved for excellent responses that that fully explain the answer to the question, show a true understanding of the question being asked, and don’t contain any errors. As a general guideline, we expect no more than 25-30% of answers are likely to receive a 3 on any particular question.
• 2 is awarded for a good response that’s getting at the right idea, but might not explain it fully or might have a few minor errors. 2, indeed, is what the course expects most students are likely to earn. As a general guideline, we expect approximately 50-60% of answers are likely to receive a 2 on any particular question.
• 1 is awarded for an inadequate response that misses the mark, is wholly incorrect, or otherwise fails to answer what the question is asking.
• 0 is given to answers that are exceedingly brief, or blank, and as such are effectively non-responses.

The above rubric should be applied for all questions on the quiz.

If you give a score lower than full credit, please include a brief comment in the “Provide comments specific to this submission” section of the form. You can also re-use comments in the “Apply Previously Used Comments” to save time so that you don’t find yourself typing the same thing over and over!

Grading Responsibilities

Answer Key

Question 1

1. Greedy best-first search can sometimes find solutions to a goal more quickly, by prioritizing paths that are likely to lead to a goal (according to some heuristic).
2. Breadth-first search is guaranteed to find the optimal solution (assuming the cost of each step is 1), since it will exhaust all shorter paths before exploring longer paths. Greedy best-first search runs the risk of choosing a path that may look like the right path, but actually be suboptimal.
3. Yes, depth-first search can always get lucky, where the very first path it chooses to attempt might be the optimal solution. Even A* search with an admissible and consistent heuristic might sometimes explore states that don’t lead to a goal in the process of finding the optimal solution.

Question 2

The only possible algorithm is depth-first search. Breadth-first search would have explored all states that can be reached in fewer than 22 steps before exploring a path that takes 22 steps (the solution), but there are shorter paths that were not explored here. Greedy best-first search and A* search would both have chosen to first explore by moving upwards when they reached the fork in the road where they could choose to either explore up or down, since moving up decreases the Manhattan distance to B.

Question 3

1. Yes, Minimax can produce a more optimal move than depth-limited Minimax. Depth-limited Minimax eventually judges game states based on an evaluation function. That evaluation function is an approximation, so it may prefer a game state that is actually worse than another game state. Minimax, on the other hand, looks through the entire game tree to guarantee the optimal move.
2. No, Minimax and Minimax with alpha-beta pruning produce the same results: alpha-beta pruning is a way of making the process more efficient, not a way of making the result more optimal.

Question 4

1. The value of the root node is 8.
2. Nodes D, G, H, and L can all be pruned.