Part $2.$ Search

Each of the following problems is something you may consider solving using some form of graph search,

local search or optimization approach:

$1.$ An agent to control the ghosts in Pac Man when Pac Man himself is controlled by unknown

agents$/$algorithms$.$

$2.$ An agent playing Chess with humans for their entertainment.

$3.$ An agent to help unit coordinators with assigning students into project groups. The input will be

a list of students and information on their academic performance $($such as Course Weighted

Average$).$ You are also given a list of students that are unable to be in a group with one another

$($perhaps due to past conflicts, conflicts of interest, or that they have simply been in groups with

one another before$).$ Your agent should fairly assign groups of students for use in units like

COMP$2009$ or capstone units.

For each of the above problems, consider the application of each of the following search methods. Which

of the methods below are more appropriate and which are possibly not appropriate $($or impossible$)?$ Why?

You don$$t need to apply all of them, but you should consider their appropriateness.

Hint: The reason should relate to the problem, not your $($dis$)$like of an approach.

$$ BFS

$$ A$*$

$$ Hill Climbing with Random Restart

$$ Minimax with alpha$-$beta pruning

$$ AC$-3$

For each problem, choose one appropriate method from the list above and apply that, either by coding it

or on paper. If no methods are applicable at all, be prepared to justify this in detail. If you do not have

enough information to apply the chosen method, consider $($in detail$)$ how you would apply it for some

different scenarios. As with the tutorials, you do not need to do all of it$,$ just enough to get an idea of

what$$s happening.