0. An intelligent agent has to answer 3 questions in a quiz on AI, what is the optimal time allocation and pruning on the search space for solutions? (most people have flunked this part of the quiz), solution to this question embedded in the rest of the answers. 1. In the anti tic-tac-toe game, the current position is: | | X ---+---+--- O | O | ---+---+--- X | | X 1.1: The game tree up to the terminal nodes: we will use the notation (who's move: position) to denote the new move in each case. Board position to be read by the path from the state up to the current move. Position is denoted by (x,y), where x is from the right and y from the top. Thus, we have the following tree (omitting the initial position). Tree also includes values for terminal nodes. MAX MIN MAX O:(1,1) X:(2,1) O:(2,3) X:(3,2) Value: 1 (win for O) O:(3,2) Value: -1 (win for X) X:(3,2) Value: 1 (win for O) X:(2,3) Value: 1 (win for O) O:(2,1) X:(1,1) O:(2,3)) Value: -1 (win for X) O:(3,2)) Value: -1 (win for X) X:(3,2) Value: 1 (win for O) * X:(2,3) Value: 1 (win for O) * O:(2,3) X:(1,1) O:(2,1) Value: -1 (win for X) O:(3,2) Value: -1 (win for X) X:(2,1) O:(1,1) X:(3,2) Value: 1 (win for O) * O:(3,2) Value: -1 (win for X) * X:(3,2) Value: 1 (win for O) * O:(3,2) Value: -1 (win for X) 1.2 Optimal ordering for alpha-beta is exactly as above. Now, if the program does NOT know the maximal value of the game, it will compute the whole subtree rooted at O:(1,1) to get an alpha value of 1. Then, all branches marked * can be pruned, as in each case X is guaranteed a win and thus it is sure that O will not make that move. If, in addition, the program knows the bounds of 1 on game score, it need only evaluate the subtree rooted at O:(1,1), but without the sub-branch O(3,2), because it can never get a score higher than 1 elsewhere! 1.3 Clearly, optimal move is O:(1,1). 1.4 If we have a RANDOM player, we need to look at the tree as an EXPECTI-MAX tree rather than MINIMAX. But we can save a lot of work by computing BOUNDS. Since move O:(1,1) forces a win against ANY moves by the oppenent, this move also has an EXPECTED VALUE of 1 (anything higher is impossible). Thus, no need to check anything else, the best move against a random opponent is STILL O:(1,1) ! 1.5 If we cannot see the response by the opponent, we MIGHT wish to model this as a random move - and thus use an "expecti-mini-max" tree. However, that will unfortunately be incorrect. The problem here is that the state is not currently observable, NOT that it is stochastic. And since there is an intelligent agent as an opponent, not a random process, we cannot use the expecti-mini-max to obtain optimum. This is a HARD problem, but then you were NOT required to find the solution here! 2 Resolution theorem proving in CNF propositional logic. 2.1 The given KB as a CNF (listed as separate clauses, with conjunction between clauses written as commas, for convenience): A , ~A v B , ~B v C , ~C v D , ~E , ~A v D v E 2.2 First, resolve the last two clauses to get ~A v D Then, resolve the clause A with the above to get D 2.3 This is optimal because there is no 0-step proof (obvious). We can prove that there is no one-step proof by trying all possible resolution steps from the initial KB: 1st and 2nd clauses: result B 2nd and 3rd clasues: result ~A v C 3rd and 4th clauses: result ~B v D 1st and last clauses: result D v E The above list (including the one in 2.2) are all possible applications of resolution in the original KB, and none of the produce a one-step proof. Thus, the proof in 2.2 is the shortest (though there may be, and in fact there IS, another 2-step proof). The "direct" proof: A -> B -> C -> D requires THREE steps. 2.4 First, we show that h(n) is an admissible heuristic. It is exact for a goal state - since if the KB contains the result, h(n)=0. The resolution operator on CNF can only at most decrease the size of a conjunct by 1, (and even that only if one of the conjuncts is of UNIT size). Since the heuristic measures the size of the SMALLEST disjunction, containing the goal literal minus 1, this heuristic is clearly OPTIMISTIC. Thus, the heuristic is ADMISSIBLE. Therefore, A* is guaranteed to find the optimal solution, i.e. a shortest proof IF it exists using only resolution steps. Admissability of h(n) allows for a shorter proof in 2.3 - for the original KB we have h(n) = 1. The only clause with distance 1 is ~C v D, but no single resolution step on this clause can produce D, and thus the children of the original KB under A* must all have h(n) = 1. Since h is optimistic, the solution length is at least 2! 3. Situation calculus question. This is a VERY simple domain. The axioms required are: If the robot grabs an object, it will be holding it as a result: (forall x, s) holding(x, result(grab(x), s) If the robot is holding an object, it will still hold it after it grabs an object (whether the same object or not is immaterial): (forall x, y, s) holding(x, s) => holding(x, result(grab(y), s)) If the robot executes exit in a situation where it is holding exactly 2 object, it will be in a situation wher wins is true: (forall s) ((exists x, y) holding(x, s) ^ holding(y, s) ^ ~(x=y) ^ (forall z) ~holding(z, s) v z=x v z=y) => wins(result(exit, s)) Since the above contains complicated nesting of quantifiers, there are several equivalent variants...