CS472Foundations of Artificial IntelligencePrelim IOctober 4, 2004Name:Netid:Instructions: You have 50 minutes to complete this exam. The exam is a closed-bookexam.# description score max score1 state space search ____ / 252 adversarial search ____ / 203 local search and GAs ____ / 354 constraint satisfaction problems ____ / 20Total score: ______ / 1001State Space Search: (25 points total)1. (20 pts) Consider the graph drawn below; the start and goal states are labeled. Notethat arcs are directed. For each of the search strategies listed below, indicate whichgoal state is reached (if any) and list, in order, the states as they are removedfrom thefringe/open list. When all else is equal, nodes should be expanded in alphabetical order.Finally, do not handle repeated states in any special manner.Arcsare labeled with the cost of traversal. Nodes contain an estimateofthedistanceto the closest goal.A13B11goal10goal20121C141start1514D4511F37362E1433115Greedy Best-First SearchGoal state reached:States expanded:Iterative DeepeningGoal state reached:States expanded:Hill ClimbingGoal state reached:States expanded:Uniform Cost SearchGoal state reached:States expanded:2. (5 pts) Would the h function in this graph lead to an admissible search? Explainyour answer.2Adversarial Search: (20 points total)1. Consider the game of tic-tac-toe (also sometimes called noughts and crosses). Wedefine Xnas the number of rows, columns, or diagonals with exactly nX’s andno O’s. Similarly, Onis the number of rows, columns, or diagonals with exactlynO’s and no X’s. The utility function assigns +1 to any position with X3=1and -1 to any position with O3=1. All other terminal positions have utility 0.For nonterminal positions, we use a linear evaluation function defined as Eval(s)=3X2(s)+X1(s) − (3O2(s)+O1(s)).The figure below shows a partial game tree to depth 2.(a) (10 pts) Given the partial game tree, use the minimax algorithm to choose thebest starting move. Mark on the tree the minimax value associated with everynode in the tree.(b) (10 pts) Circle the nodes that would not be evaluated if alpha-beta pruningwereapplied,assumingthe nodesaregeneratedintheoptimal orderforalpha-beta pruning. (This means that it’s ok to (virtually) reorder the leaves andassociated internal nodes if they are not in the optimal order.)x xxxoxoxoxox oxoxo xoxoxoxoxo3Local Search and Genetic Algorithms: (35 points total)1. Short answer questions• (2 pts) Give the name of the algorithm that results from the following specialcase: Simulated annealing with T =0at all times.• (3 pts) In what sense is a genetic algorithm a local search algorithm?2. (15 pts) In order to describe and solve a problem via a genetic algorithm, one mustnormally specify a number of elements of the GA (e.g., the crossover operator). Listand very briefly describe 5 of the most critical such elements (excluding crossover,of course).(a)(b)(c)(d)(e)43. (15 pts) Genetic programming is another form of evolutionary computing whereprograms are evolved instead of bit strings. Consider the block stacking problemdiscussed in class in which an agent operates in a simulated “blocks world” envi-ronment. Given an arbitrary starting configuration of the blocks, the goal of theagent is to stack the blocks according to some arbitrary goal state (see figure). Yourjob is to design a GA to evolve a program that can perform the above task.ANIRxyzANIRxyzstart goal• (5 pts) Describe two terminals and two primitive functions that you would use.5• (5 pts) Explain how crossover works in the gentic programming context.• (5 pts) In genetic programming, how is the quality of an evolving programtypically determined?6Constraint Satisfaction Problems (20 points total)Consider the crossword puzzle given below:1234Suppose we have the following words in our dictionary: {ant, ape, big, bus, car, has,bard, book, buys, hold, lane, year, rank, browns, ginger, symbol, syntax}. The goal is tofill the puzzle with words from the dictionary.1. (10 pts) Formalize the problem as a constraint satisfaction problem.72. (5 pts) Show the resulting constraint network.3. (5pts) Theresultingconstraint networkis notarc-consistent. Giveonedomain valuethat can be pruned. Explain which constraint arc can be used to prune it, and