Adversarial Search

1 Adversarial Search
Consider an adversarial game with two players acting independently and the winner is unique. Suppose we have an
AI agent using the min-max algorithm to play this game and it has produced a search tree shown in the figure above.
In this search tree,
• the first level (node 0) is the maximizing level;
• the second level (node 1 and 2) is the minimizing level;
• the third level (node 3, 4, 5, and 6) is the maximizing level;
• the fourth level (node 7 to 14) is the minimizing level;
• the fifth level (node 15 to 30) is the leaf level and the number beneath each node is the static evaluator score of
the corresponding game state.
Your tasks are the following:
1. Apply the min-max algorithm without pruning. Show the returned value for each non-leaf node (node 0 to 14).
node 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
value
2. Indicate the optimal path as a linked list of nodes (e.g., 0 - 1 - 3 - 7 - 15) the agent will choose.
3. Apply the min-max algorithm with alpha-beta pruning. List all of the nodes in ascending order that will be
pruned.
1
2 Constraint Satisfaction Problem
A degree program has the following nine courses: C1, C2, C3, C4, C5, C6, C7, C8 and C9. These courses fall into the
following area of knowledge: A student is required to complete at least one course from each of the areas to obtain the
Area Courses
1 C1, C2, C3, C4, C6
2 C3, C4, C5
3 C6, C7, C8
4 C3, C9
degree. Further, there are five restriction on choosing the courses:
1. For A1 only, the courses must be taken in pair specified as follows: (C1, C2), (C1, C3), and (C4, C6).
2. A student can only choose one from C3, C4, C9.
3. A student can only choose one between C1 and C7.
4. A student can only choose one between C6 and C8.
5. A course can only be used to count in one area and can only be taken at most once. For example, if a student
takes C3 for A1, then they cannot use it or retake it for A2 or A4.
Please answer the following questions.
1. Model the situation as a CSP. Specifically,
• define variables (hint: use the area of knowledge requirements),
• list their domains, and
• list the constraints (just for convention, use R1, R2, ... to denote them).
2. Use DFS with backtracking to find a solution to complete the degree while obeying all of the restrictions. When
exploring, select variable/value based on the index order (e.g., Ci goes before Ci+1). If backtracking occurs,
specify the constraint that is violated. Please show your work in a figure.
3. Suppose a student has already taken C8 for area 3 and C9 for area 4, what courses should they take for the
remaining areas in order to obtain the degree?
2