ST449 – ASSIGNMENT 1 (MT2022)
Substitute your candidate ID here
October 21, 2022
AI applications and task environment description
1. Please answer the following questions:
a. Give two examples of applications of AI in daily life: describe their primary goal, elab-
orate on how these systems can be beneficial and how they could be detrimental to
us.
b. For one of the following activities, give a PEAS description of the task environment:
i. playing football;
ii. riding a mechanical bull;
iii. playing a table tennis match.
Search algorithms
2. The performance of heuristic search algorithms depends on the quality of the heuristic func-
tion. One can sometimes construct good heuristics by:
a. relaxing the problem definition;
b. using subproblems;
c. using precomputation (landmarks).
For each heuristic pick one possible application and explain why the heuristic works well in
that context.
3. For this exercise, refer to Week02 seminar’s material for the Romania map problem.
a. Trace the operation of Breadth First Search and Depth First Search applied to the
problem of getting to Giurgiu from Zerind. What are the routes suggested by the
algorithms Compute the total length you must travel across these routes.
b. What differences do you experience How many nodes did the algorithms explore How
long did each algorithm take to return the answer
Games
4. Consider the zero-sum game tree shown in figure 1. Triangles that point up, such as at
the top node (root), represent choices for the maximizing player; triangles that point down
represent choices for the minimizing player. Assuming both players act optimally:
a. detail the computation of the minimax value of each node (A, B, C, D).
b. which actions will be chosen by player MAX and player MIN, and why
5. Which nodes can be pruned from the game tree in figure 1 through alpha-beta pruning and
why (justify your answer in detail) Assume the search goes from left to right; when choosing
which child to visit first, choose the left-most unvisited child.
6. Consider the similar zero-sum game tree illustrated in figure 2. Now, instead of a minimiz-
ing player, we have a chance node that will select one of the three values at random with
probabilities (0, 0, 1),
(
1
4 ,
1
2 ,
1
4
)
and
(
1
3 ,
1
3 ,
1
3
)
. Explain:
a. how you computed the expectimax value of the nodes (A, B, C, D).
b. which action (a1, a2 or a3) will be taken by the player, and why
1
Figure 1: MIN and MAX game
Figure 2: Chance game
2
Solution
Write your solutions here.
3
