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 ofthe 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 bepruned.
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 studenttakes C3 for A1, then they cannot use it or retake it for A2 or A4.
