CSE 473 Sp 00 Homework 1 Solution Due 4/17/00
Name: _______________________________________ Email: _____________________________________

1. In the following search space, the number beside edges denotes the path cost between nodes, and h is the estimated path cost from the node to the goal state G.
1. Give the order by which the nodes are visited in an A* search of the space. Write down the f(n) for each node n.
   f(B)=3, f(C) =14, f(D)=11, f(E)=6, f(H)=14, f(F) = 11, f(I)=22, f(G)= 12
   A, B, E, D, H, C, F, G.
   You can use pathmax here too, and the numbers would be slightly different. You lose points if you didn't visit A, or didn't state f(I).
2. Would greedy search do better? How many more or less nodes does it take greedy search to reach G?
   greedy search sequence: A, B, E, D, H, C, G, so yes, in this particular search space, greedy search works better. It searches 1 less node.
3. Both breadth-first search and A* search takes exponential memory. How would you modify A* to use less space? What is the space complexity of your new algorithm?
   You can implement an iterative-deepening version of A*, with cost as the depth limit. See the IDA* discussion in chapter 4. You'll lose points if you don't mention the f-cost bound, which is quite important because it maintains optimality of A*.
4. If H is also a goal, which algorithms among breadth-first, depth-first and iterative-deepening would find the optimal solution?
   Only depth-first search will find the optimal solution H.
5. (Bonus) The heuristic function h has a problem, it overestimates the cost from C to G. What property of A* search would be lost if h has this problem?
   A* search will no longer be optimal.

 



  

2. Consider the 8-puzzle problem, explain why the number of misplaced tiles and the Manhattan distance heuristics do not always make the best move. For each heuristic, give an example to support your explanation by drawing the original state of the 8-puzzle, and describe what move the heuristic chooses and what the optimal move is.
   Both heuristics prefer tiles to be in their final resting place, but in some cases, you need to scarify and move some of these correctly placed tiles in order to solve the puzzle (You lose points if you don't explain this and only provided the examples.) An example would be
   1 2 3
   8 O 7
   4 6 5
   In this case 4 is trapped and we should move away 8 or 6 in order to proceed. However, moving either 2, 6 or 8 would result in worse values for both heuristics, so 7 is moved instead (this move has a shorter Manhattan distance) However this move is not going to help anything and is superfluous. The better moves would 8 or 6.
   You lose points if your example consists of tied moves (no one move is preferred over the others.)
3. How would you implement best-first search if you can only tell if one node is better than the other, but not the exact cost (h(n))? Explain the differences, if any, of this algorithm.
   You have to modify the procedure for finding the "minimum cost" node. First, the comparison function is not guaranteed to be transitive, and it is possible to not have an absolute minimum among the nodes involved. In this case, you can simply pick one from the lot (I'll accept any reasonable behavior here). Second, you can no longer use a log n procedure to insert new nodes into the priority queue. Even if you queue is sorted in the previous iteration, you still have to traverse the whole queue in order to decide where the new nodes can be inserted. Notice that best-first search is not guaranteed to be optimal nor complete, so this modification doesn't destroy these properties, so you'll lose points if you say you've lost those properties. However some people say in case of A* search, it'll lose optimality, that's ok. You lose points if you don't mention non-transitivity cases, how to resolve cyclic relationships, and the fact that you need to compare with all the nodes before you insert the new nodes into the queue, and it's slower.
4. In the classroom scheduling problem, we have c classrooms and k classes, each class starts at s_k ends at e_k, both of which are integers. No two classes shares the same classroom. Classrooms are only available from 1:00 to 4:00.
1. Formulate this problem into a CSP.
   The answer to this classroom assignment problem is a mapping from classes to classrooms, therefore:
   Variables: C1, ... ,Ck
   Domain: {1, ... ,c}
   nnn Constraints: Forall i,j, if (ei >= ej > si| ei<sj<=si) then (Ci != Cj)
   Actually, since i and j range over all c's, I think you just need ei >=ej > si.
   You can optionally add the constraints si < ei, si > 1 (1 stands for 1:00), ei < 4, but they're not really necessary. In instances of the classroom assignment problem, s and e are both given values. The CSP is unsolvable if any class happen before 1 or after 4.
   There are a lot of very similar-looking constraints but in fact they don't cover all cases, and you got points off for that.
   Another formulation involves setting variables for each hour of the classroom. That works but it's a less efficient formulation, and you don't get points off. However you need to have some extra constraints to make sure the classes are in one piece.
2. Suggest a heuristic for solving this CSP and explain why you think your heuristic would work.
   Just mention a CSP heuristic mentioned in class applied to this problem.
5. Suppose you want to implement a program to play tic-tac-toe. The human player always use O and computer always use X. Each square on the board is labeled as a_ij where i is the row number and j is the column
1. Define the states, goal test, and operators for this problem in terms of a_ij. How many possible states are there?
   State: board configuration = <a11, a12... a33>
   Goal test: X's in straight line, or algebraic formulation of it.
   Operator: put an X or O on the board
   # of possible states:
   I apologize for this difficult combinatorics problem. You'll get full points if you do something half way decent (e.g. no points off if you include the illegal moves in your calculation but the exact numbers are wrong) You'll get extra credits if you went the mile and worked out the exact numbers. You don't have to understand what happens below for this class, unless of course you want to.
   The approach I use here is count the number of board configurations for each additional move in the game, subtract off the illegal positions. Since each of the O's and X's are indistinguishable, you need to adjust the factorials so that they account for this. In the following, the notation {n m} denotes the combination function n! / (m! x (n - m)!) (the number of ways to choose m identical black balls out of a mixture of n white and black balls). The idea is that you first place the x O's on the board, resulting in {9 x} states. Then you choose to place the y X's for each of these states, thus multiplying by {9-x y}.
   The numbers may look surprising, how can more O's and X's result in less states beyond 3 O's? The reason is the # of possible states is different from the number of nodes in the search space. There are a lot of identical states in the search space, especially near the end.
   When the board has no O, 1 state
   1 O => {9 1} = 9 states
   1 O, 1 X => {9 1} x {8 1} = 72
   2 O, 1 X => {9 2} x {7 1} = 252
   2 O, 2 X => {9 2} x {7 2} = 756
   3 O, 2 X => {9 3} x {6 2} = 1260
   So far, it is not yet possible to generate an illegal configuration, but from here on, it is possible to put 3 O's and 3 X's in two rows or columns, and we need to account for that.
   3 O, 3 X => {9 3} x {6 3} = 1680, # of states in which human already won = 8 x {6 3} = 160
   4 O, 3 X => {9 4} x {5 3} = 1260, # of states in which X wins = 8 x {6 4} = 120
   4 O, 4 X => {9 4} x {5 4} = 630, + # of states where O's win and X's didn't = 2 x 8 x {6 4} = 240
   5 O, 4 X => {9 5} x {4 4} = 126, illegal states = # of states X wins = 8 x {6 1} = 48
   same numbers as 4 O, 3X because the blank can be counted as O.
   # of possible states = 6046 - 160 - 120 -240 - 48= 5478
   
   
2. What search algorithm would you use to implement the search? Why?
   Minimax search. Chapter 5 explain the use of minimax search for 2 player games, which tic-tac-toe is an instance of.
   It is not wrong to say depth-first or others, but you have to state how to pick the next move from the search tree, and you'll get points off if you didn't. Also note that alpha-beta pruning is not an algorithm by itself, it's a pruning method for minimax.
3. Briefly describe a function that evaluates the performance of the computer player given one of the states you defined in part A.
   This function is called evaluation function (there's a full section of it in Chapter 5) A reason for implementing this function is for choosing the most promising candidate move, so that we can perform a lot of alpha-beta pruning.
   Any reasonable function would be accepted here; the idea is to penalize possibly losing moves and award winning moves. E.g. the number of X's in the same straight line minus the number of O's in the same straight line is a possible function.
   You'll lose points if you describe something that's exponential, or something that resembles minimax search.