2. Pick an agent problem and explain the terms observable, deterministic, episodic, static, discrete and single-agent with respect to that problem. 3. Give algorithms for the following. In addition, for each algorithm indicate whether the search is complete, optimal and give some estimate of the cost of the algorithm. For tree search, assume the branching factor is b, the depth of the optimal solution is d, and the maximum depth of the search space is m. - Breadth-First Search - Depth-First Search - A* Search - Metropolis Algorithm - Simulated Annealing - Genetic Algorithm - Hill Climbing - Minimax Search - Minimax Search with alpha-beta pruning 4. Define a graph with costs and a heuristic cost to the goal for each node and show the order the nodes would be visited in a depth-first search, breadthfirst search and an A search. 5. How does the Metropolis Algorithm and Simulated Annealing differ? 6. Why is it important for a heuristic to be admissible for A search to be optimal. Give an example where a heuristic is not admissible and would result in a non-optimal path. 7. Show minimax search for some game tree. How would alpha-beta pruning apply? 8. Does alpha-beta pruning affect the optimality of minimax search? Explain. 9. Why is minimax search generally not used for real games? How is the search algorithm altered for such games? 10. How is chance incorporated into minimax search? Give an example