Search in Complex Space & Adversarial Search

Question $1$: Hill$-$Climbing Basics

a$\backslash )$ Define the hill$-$climbing search algorithm and explain its main characteristics. $\backslash$

b$\backslash )$ Describe the difference between the ascent hill$-$climbing and descent hill$-$climbing variants. $\backslash$

c$\backslash )$ Discuss the advantages and disadvantages of the hill$-$climbing algorithm. $\backslash$

Question $2$: Local Optima

Consider the following optimization problem: $\backslash \backslash$

Maximize the function $f$($x$)=-$x$^2+5$x $-6$$ using the hill$-$climbing algorithm.

a$)$ Apply the hill$-$climbing algorithm to find the local maximum starting from different initial states. Show the steps and the corresponding values of x and f$($x$).$

b$)$ Discuss whether the hill$-$climbing algorithm is prone to getting trapped in local optima for this particular problem. If so$,$ propose a modification to the algorithm to overcome this issue.

Question $3$: Minimax

In the following game tree, figure out the values for A$-$E$.$

$```$

$($max$)$A

$/\backslash$

$/\backslash$

$($min$)$B $$ C

$/\backslash /\backslash$

$/\backslash /\backslash$

max$)$D $36$ E

$/\backslash /\backslash$

$2545$

$```$

Question $4$: $$\backslash$alpha$-\backslash$beta$ Pruning

In the following game tree, figure out which branch should be pruned.

$```$

$($max$)$ A

$/\backslash$

$/\backslash$

$($min$)$ B $$ C

$/\backslash /\backslash$

$/\backslash /\backslash$

$($max$)$D $31$E

$/\backslash /\backslash$

$2546$

$```$