Assignment 2 Search Problems in AI Solution

Problem 1 (20 points): Trace the operation of A search (the tree version) applied to the problem of getting to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes that the algorithm will con-sider and the f, g, and h score for each node. You don’t need to draw the graph, just right down a sequence of (city; f(city); g(city); h(city)) in the order in which the nodes are expanded.









Oradea






71




Neamt










Zerind




87


151




75






















Iasi
Arad
140






















92




Sibiu
99
Fagaras








118






Vaslui




80













Timisoara








Rimnicu Vilcea


















































211






142
















































111
















Pitesti




























Lugoj








97
































70




146








85




98


Hirsova




Mehadia








101






































































































Urziceni
75
















138
















86






























Bucharest


























































































Drobeta


120


















90




























































Craiova












Giurgiu








Eforie



Figure 1: A simplified road map of part of Romania indicating distances between different cities.








Section 3.5.
Informed (Heuristic) Search Strategies


93
























Arad
366
Mehadia
241








Bucharest
0
Neamt
234








Craiova
160
Oradea
380








Drobeta
242
Pitesti
100








Eforie
161
Rimnicu Vilcea
193








Fagaras
176
Sibiu
253








Giurgiu
77
Timisoara
329








Hirsova
151
Urziceni
80








Iasi
226
Vaslui
199








Lugoj
244
Zerind
374




































Figure 3.22 Values of hSLD —straight-line distances to Bucharest.










Figure 2: Straight-line distances to Bucharest








expanding a node that is not on the solution path; hence, its search cost is minimal. It is
Problem 2 (10 points): Consider a state space where the start state is number
1 and each state k has two successors:






not optimal, however: the path via Sibiu and Fagaras to Bucharest is 32 kilometers longer
numbers 2k and 2k + 1.














than the path through Rimnicu Vilcea and Pitesti. This shows why the algorithm is called
(a)




“greedy”—at each step it tries to get as close to the goal as it can.




Suppose the goal state is 11. List the order in which states will be visited for breadthfirst search, depth-limited search






Greedy best-first tree search is also incomplete even in a finite state space, much like


with limit 3, and iterative deepening search.














depth-first search. Consider the problem of getting from Iasi to Fagaras. The heuristic sug-
(b)




gests that Neamt be expanded first because it is closest to Fagaras, but it is a de d end. The
How well would bidirectional search work on this problem? List the order in which states will be visited. What is the
solution is to go first to Vaslui—a step that is actually farther from the goal according to branching factor in each direction of the bidirectional search?

the heuristic—and then to continue to Urziceni, Bucharest, and Fagaras. The algorithm will

Problem 3 ( never find this solution, however, because expanding Neamt puts Iasi back into the frontier, 5 points): Which of the following statements are correct and which ones are wrong?

Iasi is closer to Fagaras than Vaslui is, and so Iasi will be expanded again, leading to an infi-




Breadth-first searchnite loopisa.special(Thegraphcasesearchofuniformversion-iscostcompletesearchin. finite spaces, but not in infinite ones.) The worst-case time and space complexity for the tree version is O(bm), where m is the maximum
Depth-first searchdepthisaofspecialthesearchcasespaceofbest.With-firsta treegoodsearchheuristic. function, however, the complexity can be
(c)




reduced substantially. The amount of the reduction depends on the particular problem and on
Uniform-cost search is a special case of A search.






the quality of the heuristic.
(d)
Depth-first graph search is guaranteed to return an optimal solution.






3.5.2 A* search: Minimizing the total estimated solution cost
(e)
A SEARCH
T e most widely known form of best-first search is called A∗ search (pronounced “A-star
Breadth∗
-first graph search is guaranteed to return an optimal solution.






search”). It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost
(f)
Uniform-cost graphtogetsearchfromtheis nodeguarantetohedgoal:toreturn an optimal solution.
(g)




f (n) = g(n) + h(n) .
A graph search is guaranteed to return an optimal solution if the heuristic is consistent.
Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have




f (n) = estimated cost of the cheapest solution through n .




Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable: provided that the heuristic function h(n) satisfies certain conditions, A∗ search is

Alpha-Beta Pruning




(h) A graph search is guaranteed to expand no more nodes than depth-first graph search if the heuristic is consistent.







blem (i)#22Agraph search is guaranteed to expand no more nodes than uniform-cost graph search if the heuristic is consistent. Problem 4 (5 points): Iterative deepening is sometimes used as an alternative to breadth first search. Give one advantage of iterative deepening over BFS, and give one disadvantage of iterative deepening as compared with BFS. Be concise and specific.

Problem 5 (10 points): Prove that if a heuristic is consistent, it must be admissible. Construct an example of an admissible




nsider theeuristicfollowingthatisnotcosistentgame.(Hint:youtreecandraw. a small graph of 3 nodes and write arbitrary cost and heuristic values

so that the heuristic is admissible but not consistent).




Find theProblembest6(10points):moveInaConstraintfor SatheisfactionMAXProblem(CSP)playersearch,explainusingwhyitis theagood heuristicminimaxtochoosethe proced variable that is most constrained but the value that is least constraining.

Problem 7 (10 points): Consider the following game tree, where the first move is made by the MAX player and the second




Performove isamadeleftbyhe-toMIN-playerright. alpha-beta pruning on the tree. Indicate w

(a) What is the best move for the MAX player using the minimax procedure?

the cutoffs occur.

(b) Perform a left-to-right (left branch first, then right branch) alpha-beta pruning on the tree. That is, draw only the parts

of the tree that are visited and don’t draw branches that are cut off (no need to show the alpha or beta values).

Perform a right-to-left alpha-beta pruning on the tree. Discuss w

(c) Do the same thing as in the previous question, but with a right-to-left ordering of the actions. Discuss why different

differentpruningpruningoccurs. occurs.






MAX
A






B




C
D
E
F
G
H
3
5




4


I
J
K
L








5
7
8






N



07




Problem 8 (10 points): Which of the following are admissible, given admissible heuristics h1, h2? Which of the following




oran Duric (CS Dept., GMU) Midterm Review 3 5/ 10 October 7, 2008 are consistent, given consistent heuristics h1, h2? Justify your answer.




h(n) = minfh1(n); h2(n)g



h(n) = wh1(n) + (1 w)h2(n); where 0 w 1



h(n) = maxfh1(n); h2(n)g



Which one of these three new heuristics (a, b or c) would you prefer to use for A*? Justify your answer.




Problem 9 (10 points): Simulated annealing is an extension of hill climbing, which uses randomness to avoid getting stuck in local maxima and plateaux.




For what types of problems will hill climbing work better than simulated annealing? In other words, when is the random part of simulated annealing not necessary?
For what types of problems will randomly guessing the state work just as well as simulated annealing? In other words, when is the hill-climbing part of simulated annealing not necessary?



Reasoning from your answers to parts (a) and (b) above, for what types of problems is simulated annealing a useful technique? In other terms, what assumptions about the shape of the value function are implicit in the design of simulated annealing?



As defined in your textbook, simulated annealing returns the current state when the end of the annealing schedule is reached and if the annealing schedule is slow enough. Given that we know the value (measure of goodness) of each state we visit, is there anything smarter we could do?



(e) Simulated annealing requires a very small amount of memory, just enough to store two states: the current state and the proposed next state. Suppose we had enough memory to hold two million states. Propose a modification to simulated annealing that makes productive use of the additional memory. In particular, suggest something that will likely perform better than just running simulated annealing a million times consecutively with random restarts. [Note: There are multiple correct answers here.]




(f) Gradient ascent search is prone to local optima just like hill climbing. Describe how you might adapt randomness in

(b) Explain briefly how A∗ε can use the second heuristic function hN to reduce the time of the

simulated annealingsearchtogradient.Whattradeoffascentis searchbeingmadeavoidinchoosingtrapof εlocal?[5points]maximum.




(15 points for graduates - 20 points for undergraduates)

Problem 10 (10 points) : Consider the two-player game described in Figure 3.

Problem 4: Consider the two-player game described in Figure 1.

Draw the completea. Drawgamethetree,completeusinggamethe tree,followingusingtheconventions:followingconventions: [3/4 points]



Write each state as (sA, sB) where sA and sB denote the token locations.
Write each state as (s•APut;sBeach)whereterminalsAstatendinsaBsquaredenoteboxtheandtokenwriteitslocationsgamevalue. in a circle.



Put loop states (states that already appear on the path to the root) in double square



Put each terminal state boxesina.squareSinceit boxisnotandclearwritehowtoitsassigngamevaluesvalueto inloopa states,circle.annotate each with a “?” in a circle.



Put loop states (statesb.Nowthatmarkalreadyeachnodeappearwith onits backedthepath-up tominimaxtheroot)valuein(alsodoubleincircle)square.Explainboxeshow.Sinceyou it is not clear how to



handled the “?” values and why. [3/4 points]

assign values to loop states, annotate each with a “?” in a circle.



c. Explain why the standard minimax algorithm would fail on this game tree and briefly sketch


how you might fix it, drawing on your answer to (b). Does your modified algorithm give
5. Now mark each node with its backed-up minimax value (also in circle). Explain how you handled the “?” values and
why.
optimal decisions for all games with loops? [3/4 points]
d. This 4-square game can be generalized to n squares for any n 2. Prove that A wins if n is




even and loses if n is odd. [6/8 points]





















Figure 1: The start position of a simple game. Player A moves first. The two players take turns

Figure 3: The start position of a simple game. Player A moves first. The two players take turns moving, and each player moving, and each layer must move his token to an open adjacent space in either direction. If

the opponent occupies an djacent space, than a player may jump ov r the oppon nt to the next


must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, than a player
open space if any. (For example, if A is on 3 and B is on 2, then A may move back to 1.) The game
A may move back
may jump over the opponentendswhentoonetheplayernext openreachesspacetheoppositeifany. end(Forof example,theboard. ifIf playerAisonA reaches3and Bspaceison4 firs2,then,
then the value of the game to A is +1; if player B reaches space 1 first, then the value of the game

to 1.) The game ends when one player reaches the opposite end of the board. If player A reaches space 4 first, then the

to A is -1.

value of the game to A is +1; if player B reaches space 1 first, then the value of the game to A is -1.




(15 points for graduates - 20 points for undergraduates)




Problem 5: Consider the problem of constructing (not solving) crossword puzzles: fitting words into a rectangular grid. The grid, which is given as part of the problem, specifies which squares are blank and which are shaded. Assume that a list of words (i.e., a dictionary) is provided and that the task is to fill in the blank squares using any subset of the list. Formulate the problem in two ways: [Hint: There might be multiple correct answers here.].




As a general search problem. Choose an appropriate algorithm, and specify a heuristic func-tion, if you think is needed. Is it better to fill in blanks one letter or one word at a time?



As a constraint satisfaction problem. Should the variables be words or letters?



Which formulation do you think will be better? Why?




(10 points)